論文の概要: A positive resolution of the gap-entropy conjecture

• arxiv url: http://arxiv.org/abs/2609.10529v1
• Date: Wed, 09 Sep 2026 17:57:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:09.14038
• Title: A positive resolution of the gap-entropy conjecture
• Title（参考訳）: ギャップエントロピー予想の正の分解
• Abstract要約: 固定信頼度ベストアーム識別のためのギャップエントロピー予想を証明した。 各部分最適アーム $i$ に対して、$_i=_*-_i$ を最適平均とのギャップとする。 インスタンスに依存しないアルゴリズムがあり、期待されるサンプル数は、この量の定数倍数で制限される。
• 参考スコア（独自算出の注目度）: 33.232618834192564
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove the gap-entropy conjecture for fixed-confidence best-arm identification with independent unit-variance Gaussian arms, means in $[0,1]$, and a unique optimal arm. For each suboptimal arm $i$, let $Δ_i=μ_*-μ_i$ be its gap from the optimal mean, and write $H=\sum_{i\ne *}Δ_i^{-2}$. Let $p_r$ be the fraction of $H$ contributed by arms with $2^{-(r+1)}<Δ_i\le2^{-r}$, and let $\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)$. Among all algorithms that identify the optimal arm with probability at least $1-δ$ on every Gaussian instance, the optimal expected number of samples on a given instance, averaged over all permutations of the arm labels, is within absolute constant factors of $H(\log(1/δ)+\mathrm{Ent}(I))$. Moreover, there is an algorithm, independent of the instance, whose expected number of samples is bounded by a constant multiple of this quantity plus $g^{-2}\log\log(e^e/g)$, where $g=\min_{i\ne *}Δ_i$ is the gap to the closest competitor.
• Abstract（参考訳）: 我々は、独立な単位分散ガウス腕を持つ固定信頼ベストアーム識別に対するギャップエントロピー予想を証明し、すなわち$[0,1]$であり、一意の最適腕である。 各最適アーム $i$ に対して、$Δ_i=μ_*-μ_i$ を最適平均とのギャップとし、$H=\sum_{i\ne *}Δ_i^{-2}$ と書く。 p_r$ を 2^{-(r+1)}<Δ_i\le2^{-r}$ の腕で寄付された$H$ の分数とし、$\mathrm{Ent}(I)=\sum_{r:p_r>0} p_r\log(1/p_r)$ とする。 任意のガウスのインスタンスで確率が1-δ$以上の最適アームを識別する全てのアルゴリズムの中で、与えられたサンプルの最適な期待数は、アームラベルのすべての置換平均で、$H(\log(1/δ)+\mathrm{Ent}(I))$の絶対定数要素の範囲内である。 さらに、インスタンスとは独立なアルゴリズムがあり、期待されるサンプル数は、この量の定数倍で有界であり、$g^{-2}\log\log(e^e/g)$、$g=\min_{i\ne *}Δ_i$ は最も近い競合とのギャップである。

関連論文リスト

• Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification [10.999442451351385]
  順序公約のインスタンス右下界が$ (H(I)[log(1/)+Ent(I)])であることが示される。 また、期待されるサンプル複雑性を持つ単一の$$-correctアルゴリズムを、O(H(I)[log(e+log(e+D))),D=_[2]-2,$に対して、そのギャップを事前に知ることなく与える。 我々の下限は、以前の作業のdyadic-gapとmonotonicity制限を取り除き、上限は追加の多対数性を取り除きます。
  論文  参考訳（メタデータ） (2026-09-12T04:31:38Z)
• Multi-thresholding Good Arm Identification with Bandit Feedback [1.079960007119637]
  我々は,多目的のバンドイット設定において,良好な腕識別問題を考える。 サンプル複雑性境界を持つマルチスレッド UCB (MultiTUCB) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-03-13T14:04:04Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• 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)
• Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions [8.40077201352607]
  我々は,高次元共分散認識平均推定のための高速,微分プライベートなアルゴリズムを提案する。 我々のアルゴリズムは$tildemu$を生成し、$|mu|_Sigma leq alpha$が$n gtrsim tfrac d alpha2 + tfracd sqrtlog 1/deltaalpha varepsilon+fracdlog 1/deltavarepsilon$である。
  論文  参考訳（メタデータ） (2023-01-28T16:57:46Z)
• 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)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• 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)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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