論文の概要: Almost Optimal Variance-Constrained Best Arm Identification
- arxiv url: http://arxiv.org/abs/2201.10142v1
- Date: Tue, 25 Jan 2022 07:36:00 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-27 03:46:04.693250
- Title: Almost Optimal Variance-Constrained Best Arm Identification
- Title(参考訳): ほぼ最適変数制約によるベストアーム同定
- Authors: Yunlong Hou, Vincent Y. F. Tan, Zixin Zhong
- Abstract要約: パラメータフリーなアルゴリズムであるVA-LUCBを用いて、固定信頼設定の下で最適なアームを識別する。
VA-LUCBは、リスクに制約された最高の腕識別問題に対して、最も低いサンプル複雑性を有する。
- 参考スコア(独自算出の注目度): 81.60136088841948
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We design and analyze VA-LUCB, a parameter-free algorithm, for identifying
the best arm under the fixed-confidence setup and under a stringent constraint
that the variance of the chosen arm is strictly smaller than a given threshold.
An upper bound on VA-LUCB's sample complexity is shown to be characterized by a
fundamental variance-aware hardness quantity $H_{VA}$. By proving a lower
bound, we show that sample complexity of VA-LUCB is optimal up to a factor
logarithmic in $H_{VA}$. Extensive experiments corroborate the dependence of
the sample complexity on the various terms in $H_{VA}$. By comparing VA-LUCB's
empirical performance to a close competitor RiskAverse-UCB-BAI by David et al.
(2018), our experiments suggest that VA-LUCB has the lowest sample complexity
for this class of risk-constrained best arm identification problems, especially
for the riskiest instances.
- Abstract(参考訳): パラメータフリーなアルゴリズムであるva-lucbを設計・解析し,固定信頼設定下で最良アームを同定し,選択したアームのばらつきが与えられたしきい値よりも厳密に小さいという厳密な制約の下で解析する。
VA-LUCBのサンプルの複雑さの上限は、基本分散を考慮したハードネス量$H_{VA}$によって特徴づけられる。
低境界を証明することにより、VA-LUCBのサンプル複雑性が$H_{VA}$の係数対数に最適であることを示す。
大規模な実験は、サンプル複雑性の様々な項への依存を$H_{VA}$で相関させる。
David et al. (2018) によるVA-LUCBの実証的な性能と近い競合である RiskAverse-UCB-BAI (2018) を比較することで、VA-LUCBはリスクに制約された最高の腕の識別問題、特に最もリスクの高い症例において、最も低いサンプルの複雑さを持つことが示唆された。
関連論文リスト
- Cost Aware Best Arm Identification [15.038210624870656]
emphCost Aware Best Arm Identification (CABAI)と呼ぶ。
そこで我々は,2本腕の単純化モデルにおいて最適であることが証明され,数値実験で驚くほどよく一般化されるCOという低複素性アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-02-26T16:27:08Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Optimal Multi-Distribution Learning [94.73322179348332]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では,$(d+k)/varepsilon2$の順に,サンプルの複雑さを伴って,$varepsilon$-optimal randomized hypothesisを生成するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T16:06:29Z) - Fixed-Budget Best-Arm Identification with Heterogeneous Reward Variances [12.00630538470713]
不均一な報酬分散を伴う固定予算設定におけるベストアーム識別(BAI)の問題について検討する。
本稿では, 既知報酬分散に対するSHVarと未知報酬分散に対するSHAdaVarの2つの分散適応型BAIアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-06-13T05:41:38Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳(メタデータ) (2022-10-08T08:26:22Z) - Towards Minimax Optimal Best Arm Identification in Linear Bandits [95.22854522340938]
固定予算設定における線形包帯における最適な腕識別の問題について検討する。
G-最適設計の特性を活用し、アーム割り当て規則に組み込むことにより、パラメータフリーなアルゴリズムを設計する。
OD-LinBAIの故障確率に関する理論的解析を行った。
論文 参考訳(メタデータ) (2021-05-27T09:19:10Z) - Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。
$n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z) - The Simulator: Understanding Adaptive Sampling in the
Moderate-Confidence Regime [52.38455827779212]
エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。
適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。
我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
論文 参考訳(メタデータ) (2017-02-16T23:42:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。