一般的な裾（テール）レジームにおける順序最適な逐次1ビット平均推定

arXiv stat.ML / 2026/4/10

💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、1ビットメッセージに厳密に通信を制限し、過去の1ビットの結果に基づいて逐次的に閾値を選ぶランダム化閾値クエリのみを用いる状況で、平均推定を研究する。
統計分布の平均が μ∈[-λ,λ] に収まり、かつ中心モーメントのk次までが有界である任意の分布に対して、提案する適応的推定器が（ε, δ）-PACとなることを示す。さらに、任意の固定された k>1 に対して、これら「一般的な裾レジーム」全体で順序最適な標本計算量（サンプル複雑性）を達成する。
k≠2 の裾レジームでは、標本計算量は非量子化（無量子化）のミニマックス下界と、避けられない対数的な局所化コスト O(log(λ/σ)) のみを除いて一致する。一方、有限分散（k=2）では、1ビット量子化により本質的な追加の乗法的ペナルティ O(log(σ/ε)) が生じる。
著者らは、k=2 の場合の追加ログペナルティが、提案アルゴリズムの偶然的な振る舞いではなく、1ビット量子化そのものに固有なものであることを情報理論的下界として証明する。
さらに、巨大な適応性ギャップも示す。非適応（非逐次）の1ビット推定器（区間クエリを用いる場合であっても）は、探索空間パラメータ λ/σ に対して線形にスケールせざるを得ない。これに対し、適応的な逐次クエリは標本効率がはるかに高い。また、予算が不明な場合やスケールパラメータが不明な場合に対するアルゴリズム拡張も提示している。

要旨: 本論文では、厳密な1ビット通信制約の下での平均推定問題を研究する。逐次的に選択される閾値に対して、与えられたサンプルがその閾値を超えるかどうかを示す1ビットの結果だけに基づく、ランダム化された閾値クエリに基づく新しい適応型平均推定器を提案する。本推定器は、平均 $\mu \in [-\lambda, \lambda]$ が有界であり、任意の固定された $k>1$ に対して $k$ 次の中心モーメントが有界で $\mathbb{E}[|X-\mu|^k] \le \sigma^k$ を満たす任意の分布に対して、 $(\epsilon, \delta)$ -PAC である。重要なのは、サンプル複雑性が、そのようなすべての裾（tail）レジームにおいて、順序（order）の点で最適である、つまり任意のそのような $k$ 値について成り立つことである。 $k eq 2$ の場合、推定器のサンプル複雑性は、非量子化のミニマックス下界に一致し、さらに回避不能な $O(\log(\lambda/\sigma))$ のローカリゼーション（localization）コストが上乗せされる。有限分散の場合（ $k=2$ ）では、推定器のサンプル複雑性には追加の乗法的な $O(\log(\sigma/\epsilon))$ のペナルティがあり、このペナルティが1ビット量子化の基本的な限界であることを示す新しい情報理論的下界を確立する。また、重要な適応性ギャップも確立する。閾値クエリにおいても、より一般的な区間クエリにおいても、非適応（non-adaptive）な任意の推定器のサンプル複雑性は探索空間パラメータ $\lambda/\sigma$ に対して線形にスケールせねばならず、これは我々の適応型アプローチよりもはるかにサンプル効率が低いことを意味する。最後に、アルゴリズムの変種を提示する。(i) 未知のサンプリング予算を扱う、(ii)（おそらく緩い）上界が与えられる下で未知のスケールパラメータ~ $\sigma$ に適応する、(iii) より複雑な一般の1ビット・クエリを必要とする代わりに、適応（adaptivity）の段階を2段階のみとする、というものである。