Abstract
本論文では、d 次元におけるブール積分布（Boolean product distribution）のパラメータ推定問題を扱う。サンプルは、メンバーシップオラクルを通じてアクセス可能な集合 S \subset \{0, 1\}^d によって打ち切られる。本研究は、離散的な設定において、打ち切りサンプルからの学習の計算量的複雑性と統計的複雑性が考察された初めての試みである。
我々は、打ち切り集合 S の「自然な太さ（fatness）」という概念を導入し、この条件の下では、打ち切られたサンプルが真の分布に関する十分な情報を明らかにすることを示す。打ち切り集合が十分に太いなら、真の分布からのサンプルを、打ち切られたサンプルから生成できることを示す。驚くべき帰結として、ブール積分布に対して効率的に実行可能なほとんどあらゆる統計タスク（例えば、全変動距離における学習、パラメータ推定、一様性（uniformity）や同一性（identity）テスト）も、サンプル複雑性がわずかに増えるだけで、打ち切りサンプルから実行できることがわかる。我々はこのアプローチを、d 個の選択肢上の分布のランキングに一般化し、太さが、打ち切りサンプルから Mallows モデルの効率的なパラメータ推定を導く方法を示す。
打ち切りサンプルから離散モデルを学習することの限界を探る中で、効率的な識別可能性（efficient identifiability）に必要な3つの自然な条件を特定する： (i) 打ち切り集合 S は十分に豊かであるべきである； (ii) S はメンバーシップ問い合わせ（membership queries）によってアクセス可能であるべきである； (iii) S による打ち切りが、あらゆる方向において十分なランダム性を残すべきである。 (Daskalakis et al., FOCS 2018) の Stochastic Gradient Descent（確率的勾配降下法）アプローチを慎重に適応させることで、これらの条件が、打ち切られたブール積分布の効率的な学習に対しても十分であることを示す。
