論文の概要: Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification

• arxiv url: http://arxiv.org/abs/2609.13703v1
• Date: Sat, 12 Sep 2026 04:31:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:05.479308
• Title: Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification
• Title（参考訳）: ギャップエントロピーとほぼインスタンスワイズ最適ベストアーム同定
• Abstract要約: 順序公約のインスタンス右下界が$ (H(I)[log(1/)+Ent(I)])であることが示される。 また、期待されるサンプル複雑性を持つ単一の$$-correctアルゴリズムを、O(H(I)[log(e+log(e+D))),D=_[2]-2,$に対して、そのギャップを事前に知ることなく与える。 我々の下限は、以前の作業のdyadic-gapとmonotonicity制限を取り除き、上限は追加の多対数性を取り除きます。
• 参考スコア（独自算出の注目度）: 10.999442451351385
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the best-arm identification problem, we are given $n$ stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least $1-δ$, using as few samples as possible. We consider independent Gaussian rewards with unit variance and means in $[0,1]$. Chen and Li [2016] conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy, up to an additive term arising from the two-arm problem. In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures. For an instance $I$, let $Δ_{[i]}$ be the gap between the largest and the $i$-th largest mean, let $H(I)=\sum_{i=2}^{n}Δ_{[i]}^{-2}$, and let Ent$(I)$ denote the entropy of the normalized complexities of its dyadic gap groups. For every $0<δ<0.1$, we show that the order-oblivious instance-wise lower bound is $ Θ (H(I)[\log(1/δ)+Ent(I)]). $ We also give a single $δ$-correct algorithm with expected sample complexity $ O ( H(I)[\log(1/δ)+Ent(I)] +D\log(e+\log(e+D))),D=Δ_{[2]}^{-2}, $ without prior knowledge of the gaps. Our lower bound removes the dyadic-gap and monotonicity restrictions of previous work, and our upper bound removes the additional polylogarithmic factor multiplying the two-arm term. Thus, a single algorithm attains the instance-wise lower bound up to an additive two-arm term. The main theorems have been formalized and proved in Lean 4.
• Abstract（参考訳）: ベストアーム識別問題では、未知の手段を持つ$n$確率的アームが与えられ、できるだけ少数のサンプルを用いて、最大平均で1-δ$の確率で腕を識別したい。 単位分散を持つ独立ガウスの報酬は、$[0,1]$である。 Chen と Li [2016] は、この問題のインスタンスワイドサンプルの複雑さはギャップエントロピーによって特徴づけられ、二腕問題から生じる加法項までである、と推測した。 本稿では、それらのギャップエントロピーとほぼインスタンスワイズ最適性予想を解く。 例えば、$I$ に対して、$Δ_{[i]}$ を最大値と$i$-最大の平均の間のギャップとし、$H(I)=\sum_{i=2}^{n}Δ_{[i]}^{-2}$ とし、Ent$(I)$ をその二進ギャップ群の正規化複素量のエントロピーを表す。 任意の$0<δ<0.1$に対して、順序公約のインスタンス右下界が$ (H(I)[\log(1/δ)+Ent(I)])であることが示される。 さらに、期待されるサンプル複雑性を持つ単一の$δ$-正しいアルゴリズムも与えます。 O ( H(I)[\log(1/δ)+Ent(I)] +D\log(e+\log(e+D))),D=Δ_{[2]}^{-2}, $。 我々の下限は、以前の研究のdyadic-gapとmonotonicity制限を取り除き、上限は、二腕項を乗算する追加の多対数係数を除去する。 したがって、1つのアルゴリズムは、加法的な2つのアーム項までのインスタンス単位の低いバウンドを達成する。 主要な定理は形式化され、Lean 4で証明された。

関連論文リスト

• A positive resolution of the gap-entropy conjecture [33.232618834192564]
  固定信頼度ベストアーム識別のためのギャップエントロピー予想を証明した。 各部分最適アーム $i$ に対して、$_i=_*-_i$ を最適平均とのギャップとする。 インスタンスに依存しないアルゴリズムがあり、期待されるサンプル数は、この量の定数倍数で制限される。
  論文  参考訳（メタデータ） (2026-09-09T17:57:11Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
  非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。 本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
  論文  参考訳（メタデータ） (2024-10-28T18:19:13Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。 本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
  論文  参考訳（メタデータ） (2024-08-10T04:26:19Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。 本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。 訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。 軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-14T16:51:14Z)
• Approximate Top-$m$ Arm Identification with Heterogeneous Reward Variances [11.555138461092177]
  この問題の最悪のサンプルの複雑さは$Thetaleft(sum_i = 1n fracsigma_i2epsilon2 lnfrac1delta + sum_i in Gm fracsigma_j2epsilon2 textEnt(sigma2_Gr) right)$$$$$Gm, Gl, Grである。
  論文  参考訳（メタデータ） (2022-04-11T16:41:33Z)
• Variance-Dependent Best Arm Identification [12.058652922228918]
  マルチアームバンディットゲームにおける最適な腕を特定する問題について検討する。 武器の報酬のギャップと分散を探索する適応アルゴリズムを提案する。 このアルゴリズムは2つの対数項に最適であることを示す。
  論文  参考訳（メタデータ） (2021-06-19T04:13:54Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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