概要: 本論文では、1ビット通信制約の下での分散平均推定の問題を研究します。我々は、(ランダム化され、かつ逐次的に選択された) 区間クエリに基づく平均推定器を提案します。このとき1ビットの出力は、与えられたサンプルが指定された区間内にあるかどうかを示します。我々の推定器は、既知のパラメータ
\lambda
\sigma-\lambda \le \mathbb{E}(X) \le \lambda）かつ分散が有界な分布（\mathrm{Var}(X) \le \sigma^2）のすべてに対して (\epsilon, \delta)-PAC です。サンプル複雑度の上界
\widetilde{O}\big( \frac{\sigma^2}{\epsilon^2}\log\frac{1}{\delta} + \log\frac{\lambda}{\sigma}\big)\log\frac{\lambda}{\sigma} を除けば、量子化なし設定におけるミニマックス下界と一致します。また、区間クエリベースの推定器に対する適応性ギャップを確立します。すなわち、最良の非適応型平均推定器は、大きな \frac{\lambda}{\sigma} に対しては、我々の適応型平均推定器よりも著しく劣ります。最後に、裾の減衰がより強い分布に対して、サンプル複雑度のより厳密な境界を与え、さらに (i) 未知のサンプリング予算を扱う (ii) 分散についての（たとえ緩いとしても）上限と下限が与えられていることから、未知の真の分散に適応する、そして (iii) より複雑な（区間ではない）クエリを用いる代わりに、適応の段階を2段階に限定する、という追加の変種も提示します。
近最適サンプル複雑度を達成する逐次1ビット平均推定
arXiv stat.ML / 2026/4/7
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、厳格な1ビット通信制約のもとでの分散平均推定を扱っており、確率化した逐次的な区間クエリを用いる。単一ビットの応答は、サンプルが照会した範囲内に入るかどうかを示す。
- 平均と分散が有界な分布に対してPAC保証を証明し、近ミニマックスのサンプル複雑度に対する境界を約\(\tilde{O}( (\sigma^2/\varepsilon^2)\cdot\log(1/\delta) + \log(\lambda/\sigma))\) と導出する。
- 得られた率は、対数因子を除けば、量子化なし（実数値）のミニマックス基準と本質的に一致することを示し、さらに追加される \(\log(\lambda/\sigma)\) 項は不可避であると主張する。
- \(\lambda/\sigma\) が大きい場合には、適応的な区間クエリ推定器が最良の非適応推定器を大きく上回り得ることを、適応性ギャップとして示す。
- さらに、本論文は裾の軽い分布に対する境界を精密化し、予算が未知な場合、分散が範囲内で未知な場合、そしてより複雑なクエリを用いた低減された（二段階）適応設定に対する複数のアルゴリズム変種も提示する。
