Fugu-MT 論文翻訳(概要): Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?

論文の概要: Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?

arxiv url: http://arxiv.org/abs/2607.02896v1
Date: Fri, 03 Jul 2026 02:47:11 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-07 22:26:29.44911
Title: Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?
Title（参考訳）: オープン問題: 対話は順序最適1ビット平均推定に必要か?
Abstract要約: 非パラメトリック有限モーメントクラスに対する順序-最適1ビット平均推定には相互作用が必要であるかどうかを問う。非適応的な設定では、しきい値とインターバルクエリが極めて最適であることが知られている。任意の非適応量子化器は適応率と一致し、最適なワンショットプロトコルが得られるか?
参考スコア（独自算出の注目度）: 32.65125292684608
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optimal 1-bit minimax rate, and the same rate is attainable with general 1-bit queries using only one adaptive transition (i.e., two stages of querying). In the non-adaptive setting, threshold and interval queries are known to be highly suboptimal, but the case of arbitrary non-adaptive quantizers remains unresolved. Can such quantizers match the adaptive rate, yielding an optimal one-shot protocol? Or is the known two-stage estimator stage-optimal, with a single adaptive transition being necessary and sufficient?
Abstract（参考訳）: 非パラメトリック有限モーメントクラスに対する順序-最適1ビット平均推定には相互作用が必要であるかどうかを問う。アダプティブしきい値クエリプロトコルは、オーダー最適1ビットのミニマックスレートを実現し、1つの適応遷移(すなわち、クエリの2段階)のみを使用して、一般的な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)
Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation [14.106326180143666]
我々は$[-,]$の平均の$mathbbR$上の分布と、$k>1$が固定される最大$k$における絶対$k$-th中心モーメントを考える。この相互作用は、ランダム化された完全非適応プロトコルを構築することで回避できることを示す。
論文参考訳（メタデータ） (2026-08-03T17:28:12Z)
Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes [32.65125292684608]
ランダム化しきい値クエリのみに基づく適応型平均推定器を提案する。我々の推定器のサンプル複雑性は、余分な乗法的な$O(log(/))$ペナルティを持つ。しきい値クエリとより一般的な間隔クエリの両方において、任意の非適応推定器のサンプル複雑性は線形にスケールしなければならない。
論文参考訳（メタデータ） (2026-04-09T04:49:21Z)
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)
Adaptive quantum phase estimation can be better than non-adaptive [0.6588840794922407]
推定すべき位相が任意の場合や一様ランダムの場合、適応アルゴリズムには利点がないことが知られている。ここでは、未知の位相が取ることのできる値について約束しながら、位相推定の特別な場合の例を示す。我々は、位相推定のための適応アルゴリズムが非適応的なアルゴリズムよりも優れているという最大の利点について、いくつかの上限を証明した。
論文参考訳（メタデータ） (2025-11-07T15:58:08Z)
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)
The Curse of Conditions: Analyzing and Improving Optimal Transport for Conditional Flow-Based Generation [56.33404393159126]
本稿では,最適輸送代入を計算する際に,コスト行列に条件付き重み付け項を追加する条件付き最適輸送C2OTを提案する。実験では、この単純な修正は8gaussian-to-moons、CIFAR-10、ImageNet-32x32、ImageNet-256x256の離散的条件と連続的条件の両方で動作することを示した。
論文参考訳（メタデータ） (2025-03-13T17:59:56Z)
Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes [22.022674600775993]
分散ミニマックス問題に直接適応的手法を適用することで,非収束性が得られることを示す。追跡追跡プロトコルを用いた分散分散分散ミニマックス法であるD-AdaSTを提案する。
論文参考訳（メタデータ） (2024-06-05T04:54:36Z)
Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
論文参考訳（メタデータ） (2022-06-16T17:10:57Z)
Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimization [24.784754071913255]
AdaGradやAMSのような適応アルゴリズムは、非特異なパラメータの堅牢性に成功している。我々はNeAdaが最適に近いレベルの知識を実現できることを示す。
論文参考訳（メタデータ） (2022-06-01T20:11:05Z)
BiAdam: Fast Adaptive Bilevel Optimization Methods [104.96004056928474]
バイレベル最適化は多くの応用のために機械学習への関心が高まっている。制約付き最適化と制約なし最適化の両方に有用な分析フレームワークを提供する。
論文参考訳（メタデータ） (2021-06-21T20:16:40Z)
Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文参考訳（メタデータ） (2020-07-02T16:02:02Z)

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