論文の概要: Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
- arxiv url: http://arxiv.org/abs/2609.08564v1
- Date: Tue, 08 Sep 2026 10:52:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-10 19:44:08.631715
- Title: Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
- Title（参考訳）: 非適応1ビット平均推定:ミニマックスレートとサンプルインターバルトレードオフ
- Abstract要約: 1ビット通信制約下での1次元平均推定について検討する。
我々は、$k>1$毎に、適応性のないプロトコルが適応性1ビットのミニマックスレートに達することを発見した。
- 参考スコア（独自算出の注目度）: 32.65125292684608
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study distributed one-dimensional mean estimation under a 1-bit communication constraint. Each agent observes one sample, drawn independently from an unknown distribution, and returns a single bit in response to a query $Q: \mathbb{R}\to\{0,1\}$ chosen by a central learner. The distribution has mean in $[-λ,λ]$ and $k$-th central moment at most $σ^k$, for a fixed $k>1$. The order-optimal two-stage protocol of Lau and Scarlett uses responses from the first batch to choose the second-batch queries, motivating the question of whether this single round of interaction is necessary. We answer this negatively: for every $k>1$, a non-adaptive protocol attains the adaptive 1-bit minimax rate (and concurrent works reached the same conclusion via different strategies). We further determine the minimax sample complexity among non-adaptive 1-bit estimators when every one-set $Q^{-1}(1)$ is restricted to a union of at most $s$ intervals. Relative to unrestricted non-adaptive 1-bit querying, this constraint adds a term of order $(λσ/(s\varepsilon^2))\log(1/δ)$, giving the full tradeoff between sample complexity and interval complexity to within $k$-dependent constant factors. As a corollary, we identify, order-wise, the minimum interval budget needed to retain the unrestricted 1-bit minimax sample rate.
- Abstract（参考訳）: 1ビット通信制約下での分散1次元平均推定について検討する。
各エージェントは、未知の分布から独立して引き出された1つのサンプルを観察し、クエリー$Q: \mathbb{R}\to\{0,1\}$に応答して1ビットを返す。
この分布は、$[-λ,λ]$と$k$-第中心モーメントにおいて、固定された$k>1$に対して最大$σ^k$となる。
LauとScarlettのオーダー最適2段階プロトコルは、第1バッチからの応答を使用して第2バッチクエリを選択し、この単一ラウンドのインタラクションが必要かどうかという疑問を提起する。
すべての$k>1$に対して、適応的でないプロトコルは適応的な1ビットのミニマックスレートを達成する(そして並行処理は異なる戦略で同じ結論に達した)。
さらに、任意の 1-集合 $Q^{-1}(1)$ が少なくとも$s$間隔の和に制限されるとき、非適応的な 1-ビット推定器のミニマックス標本複雑性を決定付ける。
制限のない非適応的な1ビットクエリとは対照的に、この制約は位数 $(λσ/(s\varepsilon^2))\log(1/δ)$ の項を追加し、サンプルの複雑性と区間の複雑さの完全なトレードオフを$k$依存の定数因子に与える。
結論として、制約のない1ビットのミニマックスサンプル率を維持するのに必要な最小間隔の予算を、順序的に特定する。
関連論文リスト
- Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
分布的に堅牢なマルコフ決定プロセスは、モデルの不確実性の下でのシーケンシャルな意思決定のための原則化されたフレームワークを提供する。
我々は,平均回帰基準の下で,$varepsilon$-Optimal robust policyを学習するのに必要なサンプル数と十分なサンプル数について検討した。
論文 参考訳（メタデータ） (2026-08-06T19:49:48Z) - Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation [14.106326180143666]
我々は$[-,]$の平均の$mathbbR$上の分布と、$k>1$が固定される最大$k$における絶対$k$-th中心モーメントを考える。
この相互作用は、ランダム化された完全非適応プロトコルを構築することで回避できることを示す。
論文 参考訳（メタデータ） (2026-08-03T17:28:12Z) - Minimax PAC Bounds for Learning in Exogenous Contextual MDPs [26.599514971653615]
PAC学習は、割引係数$$、有限状態空間$mathcal X$、アクション空間$mathcal A$、コンテキスト空間$mathcal Z$を含む割引決定プロセスにおける。
論文 参考訳（メタデータ） (2026-06-23T21:02:18Z) - Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes [32.65125292684608]
ランダム化しきい値クエリのみに基づく適応型平均推定器を提案する。
我々の推定器のサンプル複雑性は、余分な乗法的な$O(log(/))$ペナルティを持つ。
しきい値クエリとより一般的な間隔クエリの両方において、任意の非適応推定器のサンプル複雑性は線形にスケールしなければならない。
論文 参考訳（メタデータ） (2026-04-09T04:49:21Z) - 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) - 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) - Sharper Convergence Guarantees for Asynchronous SGD for Distributed and
Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。
本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。
また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文 参考訳（メタデータ） (2022-06-16T17:10:57Z) - 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) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。
$n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。