論文の概要: Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation

• arxiv url: http://arxiv.org/abs/2608.02538v1
• Date: Mon, 03 Aug 2026 17:28:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-04 15:07:25.730141
• Title: Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation
• Title（参考訳）: 順序最適1ビット平均推定にはインタラクションは必要ない
• Abstract要約: 我々は$[-,]$の平均の$mathbbR$上の分布と、$k>1$が固定される最大$k$における絶対$k$-th中心モーメントを考える。 この相互作用は、ランダム化された完全非適応プロトコルを構築することで回避できることを示す。
• 参考スコア（独自算出の注目度）: 14.106326180143666
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper is concerned with one-bit mean estimation, where each independent sample is represented by a single binary message. We consider distributions on $\mathbb{R}$ with mean in $[-λ,λ]$ and absolute $k$-th central moment at most $σ^k$, where $k>1$ is fixed. For this class, previous work attained the optimal sample complexity for general queries using a two-stage protocol. The first stage localizes the mean. The second-stage queries are chosen after localization and refine the estimate around the decoded center. We show that this interaction can be avoided by constructing a randomized fully non-adaptive protocol that fixes all queries before observing the data and matches the optimal adaptive sample complexity. For target accuracy $ε$ and confidence $1-δ$, its sample complexity scales as \[ \log\fracλσ + \begin{cases} (σ/ε)^2\log(1/δ), & k>2,\\ (σ/ε)^2\log(σ/ε)\log(1/δ), & k=2,\\ (σ/ε)^{k/(k-1)}\log(1/δ), & 1<k<2, \end{cases} \] up to constants depending only on $k$. In the range covered by the known lower bound, this rate is minimax optimal even among fully adaptive protocols. This gives a negative answer to the COLT 2026 open problem asking whether interaction is necessary for order-optimal one-bit mean estimation with general queries \citep[Open Problem~1]{lau2026open}.
• Abstract（参考訳）: 本稿では,各独立したサンプルを1つのバイナリメッセージで表現する1ビット平均推定について述べる。 我々は、$[-λ,λ]$の平均を持つ$\mathbb{R}$上の分布と、$k>1$が固定される最大$σ^k$における絶対$k$-番目の中心モーメントを考える。 このクラスのために、以前の研究は2段階のプロトコルを用いて、一般的なクエリの最適なサンプル複雑性を達成した。 第1ステージは平均をローカライズする。 第2段階のクエリは、ローカライズ後に選択され、デコードされた中心周辺の見積もりを洗練する。 この相互作用は、データを観測する前に全てのクエリを修正し、最適な適応サンプルの複雑さに適合するランダム化された完全非適応プロトコルを構築することで回避できることを示す。 目標精度$ε$と信頼1-δ$に対して、そのサンプル複雑性は \[ \log\fracλσ + \begin{cases} (σ/ε)^2\log(1/δ), & k>2,\\ (σ/ε)^2\log(σ/ε)\log(1/δ), & k=2,\ (σ/ε)^{k/(k-1)}\log(1/δ), & 1<k<2, \end{cases} \] として、$k$のみに依存する定数までスケールする。 既知の下界でカバーされる範囲では、このレートは完全な適応プロトコルの中でも最小限の最適値である。 これにより COLT 2026 の開問題に対する負の回答が得られ、一般の問合せである citep[Open Problem~1]{lau2026open} との順序最適1ビット平均推定に相互作用が必要とされるかどうかを問う。

関連論文リスト

• Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff [32.65125292684608]
  1ビット通信制約下での1次元平均推定について検討する。 我々は、$k>1$毎に、適応性のないプロトコルが適応性1ビットのミニマックスレートに達することを発見した。
  論文  参考訳（メタデータ） (2026-09-08T10:52:52Z)
• Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes [32.65125292684608]
  ランダム化しきい値クエリのみに基づく適応型平均推定器を提案する。 我々の推定器のサンプル複雑性は、余分な乗法的な$O(log(/))$ペナルティを持つ。 しきい値クエリとより一般的な間隔クエリの両方において、任意の非適応推定器のサンプル複雑性は線形にスケールしなければならない。
  論文  参考訳（メタデータ） (2026-04-09T04:49:21Z)
• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。 我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
  論文  参考訳（メタデータ） (2026-02-01T17:05:31Z)
• 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)
• Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
  幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。 これは密度推定のための新しい統計計算トレードオフである。
  論文  参考訳（メタデータ） (2024-10-30T15:03:33Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  本稿では,プライバシのシャッフルモデルにおけるプライベートベクトル平均推定の問題について検討する。 我々は,$tildemathcalOleft(min(nvarepsilon2,d)right)$ message per users を用いて,最適なエラーを実現する新しいマルチメッセージプロトコルを提案する。
  論文  参考訳（メタデータ） (2024-04-16T00:56:36Z)
• 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)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• 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)
• 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)
• Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
  差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。 $n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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