論文の概要: Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity

• arxiv url: http://arxiv.org/abs/2509.21940v1
• Date: Fri, 26 Sep 2025 06:22:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-29 20:57:54.232876
• Title: Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity
• Title（参考訳）: ほぼ最適サンプル複素数を用いた連続1ビット平均推定
• Authors: Ivan Lau, Jonathan Scarlett,
• Abstract要約: 1ビット通信制約を用いた分散平均推定問題について検討する。 私たちの推定器は、有界平均$-lambda le mathbbE(X) le lambda $)と変数$mathrmVar(X) le sigma2$)を持つすべてのディストリビューションに対して$(epsilon, delta)$-PACです。
• 参考スコア（独自算出の注目度）: 32.65125292684608
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the problem of distributed mean estimation with 1-bit communication constraints. We propose a mean estimator that is based on (randomized and sequentially-chosen) interval queries, whose 1-bit outcome indicates whether the given sample lies in the specified interval. Our estimator is $(\epsilon, \delta)$-PAC for all distributions with bounded mean ($-\lambda \le \mathbb{E}(X) \le \lambda $) and variance ($\mathrm{Var}(X) \le \sigma^2$) for some known parameters $\lambda$ and $\sigma$. We derive a sample complexity bound $\widetilde{O}\big( \frac{\sigma^2}{\epsilon^2}\log\frac{1}{\delta} + \log\frac{\lambda}{\sigma}\big)$, which matches the minimax lower bound for the unquantized setting up to logarithmic factors and the additional $\log\frac{\lambda}{\sigma}$ term that we show to be unavoidable. We also establish an adaptivity gap for interval-query based estimators: the best non-adaptive mean estimator is considerably worse than our adaptive mean estimator for large $\frac{\lambda}{\sigma}$. Finally, we give tightened sample complexity bounds for distributions with stronger tail decay, and present additional variants that (i) handle an unknown sampling budget (ii) adapt to the unknown true variance given (possibly loose) upper and lower bounds on the variance, and (iii) use only two stages of adaptivity at the expense of more complicated (non-interval) queries.
• Abstract（参考訳）: 本稿では,1ビット通信制約を用いた分散平均推定問題について検討する。 本稿では,与えられたサンプルが指定された区間内にあるか否かを示す1ビット結果の区間クエリ(ランダム化および逐次チョーゼン)に基づく平均推定器を提案する。 我々の推定子は、有界平均$-\lambda \le \mathbb{E}(X) \le \lambda $) と分散$-mathrm{Var}(X) \le \sigma^2$) を持つすべての分布に対して $(\epsilon, \delta)$-PAC であり、既知のパラメータに対して $\lambda$ と $\sigma$ である。 例えば、$\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)未知のサンプリング予算を扱う (二 分散に与えられた未知の真の分散(おそらくゆるい)の上と下の境界に適応し、 三 より複雑な(非内部的な)クエリを犠牲にして、適応性の二段階のみを使用すること。

関連論文リスト

• Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation [13.535770763481906]
  LeCamの2点試験法は、分布の平均を推定する最も単純な下界を与える。 本研究では,2点検定の下限を達成できる条件について検討する。 2点検定率は対称な単調分布であってもほぼ達成不可能であることを示す。
  論文  参考訳（メタデータ） (2025-02-09T00:17:49Z)
• 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)
• Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions [8.40077201352607]
  我々は,高次元共分散認識平均推定のための高速,微分プライベートなアルゴリズムを提案する。 我々のアルゴリズムは$tildemu$を生成し、$|mu|_Sigma leq alpha$が$n gtrsim tfrac d alpha2 + tfracd sqrtlog 1/deltaalpha varepsilon+fracdlog 1/deltavarepsilon$である。
  論文  参考訳（メタデータ） (2023-01-28T16:57:46Z)
• A Fast Algorithm for Adaptive Private Mean Estimation [5.090363690988394]
  我々は、$Sigma$に適応する$(varepsilon, delta)$-differentially privateアルゴリズムを設計する。 推定子は、誘導されたマハラノビスノルム $|cdot||_Sigma$ に対して最適な収束率を達成する。
  論文  参考訳（メタデータ） (2023-01-17T18:44:41Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$ [5.457150493905064]
  ガウス下収束を考慮した新しい推定器を提案する。 我々の推定器はその分散に関する事前の知識を必要としない。 我々の推定器の構成と分析は、他の問題に一般化可能なフレームワークを提供する。
  論文  参考訳（メタデータ） (2020-11-17T02:47:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。