論文の概要: 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ビット平均推定
• 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段階しか必要としない。

関連論文リスト

• 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)
• 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)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• 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)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning [52.76230802067506]
  漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。 提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。 初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2021-10-09T21:13:48Z)
• 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)

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

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