論文の概要: Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes
- arxiv url: http://arxiv.org/abs/2604.07796v1
- Date: Thu, 09 Apr 2026 04:49:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-10 18:34:05.697404
- Title: Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes
- Title（参考訳）: 一般的なタイルレジームにおける順序最適1ビット平均推定
- Authors: Ivan Lau, Jonathan Scarlett,
- Abstract要約: ランダム化しきい値クエリのみに基づく適応型平均推定器を提案する。
我々の推定器のサンプル複雑性は、余分な乗法的な$O(log(/))$ペナルティを持つ。
しきい値クエリとより一般的な間隔クエリの両方において、任意の非適応推定器のサンプル複雑性は線形にスケールしなければならない。
- 参考スコア（独自算出の注目度）: 32.65125292684608
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study the problem of mean estimation under strict 1-bit communication constraints. We propose a novel adaptive mean estimator based solely on randomized threshold queries, where each 1-bit outcome indicates whether a given sample exceeds a sequentially chosen threshold. Our estimator is $(ε, δ)$-PAC for any distribution with a bounded mean $μ\in [-λ, λ]$ and a bounded $k$-th central moment $\mathbb{E}[|X-μ|^k] \le σ^k$ for any fixed $k > 1$. Crucially, our sample complexity is order-optimal in all such tail regimes, i.e., for every such $k$ value. For $k \neq 2$, our estimator's sample complexity matches the unquantized minimax lower bounds plus an unavoidable $O(\log(λ/σ))$ localization cost. For the finite-variance case ($k=2$), our estimator's sample complexity has an extra multiplicative $O(\log(σ/ε))$ penalty, and we establish a novel information-theoretic lower bound showing that this penalty is a fundamental limit of 1-bit quantization. We also establish a significant adaptivity gap: for both threshold queries and more general interval queries, the sample complexity of any non-adaptive estimator must scale linearly with the search space parameter $λ/σ$, rendering it vastly less sample efficient than our adaptive approach. Finally, we present algorithmic variants that (i) handle an unknown sampling budget, (ii) adapt to an unknown scale parameter~$σ$ given (possibly loose) bounds, and (iii) require only two stages of adaptivity at the expense of more complicated general 1-bit queries.
- Abstract（参考訳）: 本稿では,厳密な1ビット通信制約下での平均推定問題について検討する。
ランダム化しきい値クエリのみに基づく適応型平均推定器を提案し、各1ビットの結果が、与えられたサンプルが順次選択されたしきい値を超えるか否かを示す。
我々の推定子は、有界平均$μ\in [-λ, λ]$と有界な$k$-th Central moment $\mathbb{E}[|X-μ|^k] \le σ^k$ を持つ任意の分布に対して$(ε, δ)$-PACである。
重要なことに、我々のサンプルの複雑さは、全ての尾のレギュレーション、すなわちそのような$k$の値に対して順序最適である。
k \neq 2$ の場合、我々の推定器のサンプルの複雑さは、不定値のミニマックス下限と、避けられない$O(\log(λ/σ))$ローカライゼーションコストに一致する。
有限分散の場合(k=2$)、我々の推定器のサンプル複雑性は余剰乗法$O(\log(σ/ε))$ペナルティを持ち、このペナルティが1ビット量子化の基本的な極限であることを示す新しい情報理論の下限を確立する。
しきい値クエリとより一般的な区間クエリの両方に対して、任意の非適応的推定器のサンプル複雑性は、探索空間パラメータ$λ/σ$と線形にスケールしなければなりません。
最後に,アルゴリズムの変種について述べる。
(i)未知のサンプリング予算を処理する。
(ii)未知のスケールパラメータ~$σ$ given(おそらくゆるい)境界に適応し、
(iii) より複雑な1ビットのクエリを犠牲にして、適応性の2段階しか必要としない。
関連論文リスト
- Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
基本的で長期にわたる課題は、その効率的な近似である。
一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。
本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
論文 参考訳（メタデータ） (2026-04-09T16:38:14Z) - Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity [32.65125292684608]
1ビット通信制約を用いた分散平均推定問題について検討する。
私たちの推定器は、有界平均$-lambda le mathbbE(X) le lambda $)と変数$mathrmVar(X) le sigma2$)を持つすべてのディストリビューションに対して$(epsilon, delta)$-PACです。
論文 参考訳（メタデータ） (2025-09-26T06:22:57Z) - Sample Complexity Bounds for Scalar Parameter Estimation Under Quantum Differential Privacy [9.244521717083696]
本稿では, 所定の精度を達成するために必要な試料の最小値について, 上下境界について述べる。
ベストケース(最適)シナリオは、すべての微分プライベートチャネルにおけるサンプルの複雑さを最小化することで考慮される。
論文 参考訳（メタデータ） (2025-01-24T02:23:51Z) - Optimal Sample Complexity for Average Reward Markov Decision Processes [1.0445957451908694]
平均報酬 MDP の最適ポリシを$widetilde O(|S||A|t_textmix2 epsilon-2)$で推定する。
これは文学の下位境界に到達した最初のアルゴリズムと分析である。
論文 参考訳（メタデータ） (2023-10-13T03:08:59Z) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。
我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。
我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
論文 参考訳（メタデータ） (2020-10-16T08:10:02Z) - Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。
$n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。