論文の概要: Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed
Distributions
- arxiv url: http://arxiv.org/abs/1908.09094v3
- Date: Fri, 24 Nov 2023 13:40:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-30 18:21:59.557009
- Title: Optimal $\delta$-Correct Best-Arm Selection for Heavy-Tailed
Distributions
- Title（参考訳）: 重層分布に対する最適$\delta$-Correct Best-Arm選択
- Authors: Shubhada Agrawal, Sandeep Juneja and Peter Glynn
- Abstract要約: 我々は、$delta$-correctアルゴリズムを用いて、最大平均値を持つものを識別する問題を考察する。
$delta$-correctアルゴリズムの下位境界はよく知られている。
我々は,下界の$delta$-correctアルゴリズムを提案し,$delta$を0に還元する。
- 参考スコア（独自算出の注目度）: 2.2940141855172036
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a finite set of unknown distributions or arms that can be sampled, we
consider the problem of identifying the one with the maximum mean using a
$\delta$-correct algorithm (an adaptive, sequential algorithm that restricts
the probability of error to a specified $\delta$) that has minimum sample
complexity. Lower bounds for $\delta$-correct algorithms are well known.
$\delta$-correct algorithms that match the lower bound asymptotically as
$\delta$ reduces to zero have been previously developed when arm distributions
are restricted to a single parameter exponential family. In this paper, we
first observe a negative result that some restrictions are essential, as
otherwise, under a $\delta$-correct algorithm, distributions with unbounded
support would require an infinite number of samples in expectation. We then
propose a $\delta$-correct algorithm that matches the lower bound as $\delta$
reduces to zero under the mild restriction that a known bound on the
expectation of $(1+\epsilon)^{th}$ moment of the underlying random variables
exists, for $\epsilon > 0$. We also propose batch processing and identify
near-optimal batch sizes to speed up the proposed algorithm substantially. The
best-arm problem has many learning applications, including recommendation
systems and product selection. It is also a well-studied classic problem in the
simulation community.
- Abstract（参考訳）: 標本化できる未知の分布やアームの有限集合が与えられると、最小のサンプル複雑性を持つ特定の$\delta$にエラーの確率を制限する適応的逐次アルゴリズムである$\delta$-correctアルゴリズムを用いて、最大平均を持つものを特定する問題を考える。
$\delta$-correctアルゴリズムの下限はよく知られている。
$\delta$-correctアルゴリズムは下限に漸近的に$\delta$reducesから 0 に一致するが、以前はarm分布が単一のパラメータ指数関数族に制限されたときに開発された。
本稿では,いくつかの制約が必須であるという負の結果を最初に観察する。そうでなければ$\delta$-correctアルゴリズムでは,非有界なサポートを持つ分布は期待値の無限個のサンプルを必要とする。
次に、下限値の$\delta$に一致する$\delta$-correctアルゴリズムを提案する。$\epsilon > 0$ に対して、基礎となる確率変数の$(1+\epsilon)^{th}$ momentの期待値に既知のバウンドが存在するという穏やかな制約の下で、0に還元する。
また,提案アルゴリズムの高速化のために,バッチ処理を提案し,最適に近いバッチサイズを同定する。
ベストアーム問題には、レコメンデーションシステムや製品選択など、多くの学習アプリケーションがある。
また、シミュレーションコミュニティでよく研究されている古典的な問題でもある。
関連論文リスト
- Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed
Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。
我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。
我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文 参考訳（メタデータ） (2023-10-28T13:01:10Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳（メタデータ） (2023-06-03T04:00:47Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - On the complexity of All $\varepsilon$-Best Arms Identification [2.1485350418225244]
ガウスの報酬を持つ有限の多腕バンディットにおいて、$varepsilon$-optimal armsを全て識別する問題を考える。
我々は,$varepsilon$-good arms w.h.p の集合を同定し,期待されるサンプルの複雑さの観点から最適性($delta$が 0 になるとき)を享受するトラック・アンド・ストップアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-13T10:54:52Z) - Bandits with many optimal arms [68.17472536610859]
最適アームの割合は$p*$、最適アームとサブ最適化アームの間の最小平均ギャップは$Delta$と書きます。
我々は,累積的後悔設定と最良腕識別設定の両方において最適な学習率を特徴付ける。
論文 参考訳（メタデータ） (2021-03-23T11:02:31Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。