論文の概要: Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries
- arxiv url: http://arxiv.org/abs/2202.08549v1
- Date: Thu, 17 Feb 2022 09:49:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-18 20:35:21.268080
- Title: Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries
- Title（参考訳）: oracleによる最悪の敵に対するオンライン学習の効率化
- Authors: Nika Haghtalab, Yanjun Han, Abhishek Shetty, Kunhe Yang
- Abstract要約: オンライン学習の最悪のケース分析を超越した,オラクル効率のアルゴリズムについて検討する。
このスムーズな分析設定のために,本研究は,スムーズな相手を持つオンライン学習のための最初のオラクル効率のアルゴリズムを提供する。
- 参考スコア（独自算出の注目度）: 29.598518028635716
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, we study oracle-efficient algorithms for beyond worst-case
analysis of online learning. We focus on two settings. First, the smoothed
analysis setting of [RST11, HRS12] where an adversary is constrained to
generating samples from distributions whose density is upper bounded by
$1/\sigma$ times the uniform density. Second, the setting of $K$-hint
transductive learning, where the learner is given access to $K$ hints per time
step that are guaranteed to include the true instance. We give the first known
oracle-efficient algorithms for both settings that depend only on the VC
dimension of the class and parameters $\sigma$ and $K$ that capture the power
of the adversary. In particular, we achieve oracle-efficient regret bounds of $
O ( \sqrt{T (d / \sigma )^{1/2} } ) $ and $ O ( \sqrt{T d K } )$ respectively
for these setting. For the smoothed analysis setting, our results give the
first oracle-efficient algorithm for online learning with smoothed adversaries
[HRS21]. This contrasts the computational separation between online learning
with worst-case adversaries and offline learning established by [HK16]. Our
algorithms also imply improved bounds for worst-case setting with small
domains. In particular, we give an oracle-efficient algorithm with regret of $O
( \sqrt{T(d \vert{\mathcal{X}}\vert ) ^{1/2} })$, which is a refinement of the
earlier $O ( \sqrt{T\vert{\mathcal{X} } \vert })$ bound by [DS16].
- Abstract（参考訳）: 本稿では,オンライン学習の最悪のケース分析を超越した,オラクル効率のアルゴリズムについて検討する。
私たちは2つの設定に集中します。
まず,[rst11,hrs12]の平滑化解析設定は,一様密度の1/\sigma$倍の上限値を持つ分布からサンプルを生成することに制約される。
第二に、$K$-hintトランスダクティブ学習の設定では、学習者が真のインスタンスを含むことが保証される時間毎に$K$ヒントにアクセスできるようになる。
私たちは、クラスのvc次元のみに依存する設定と、敵の力をキャプチャする$\sigma$と$k$の両方に対して、最初のoracle効率の高いアルゴリズムを提供します。
特に、これらの設定に対してそれぞれ$ O ( \sqrt{T (d / \sigma )^{1/2} } ) $ と $ O ( \sqrt{T d K } )$ のオラクル効率の後悔境界を達成する。
このスムーズな分析設定のために,本研究は,スムーズな相手を用いたオンライン学習のための最初のオラクル効率アルゴリズムを提供する[HRS21]。
これは[HK16]が確立したオフライン学習と, オンライン学習と最悪の相手との計算的分離とは対照的である。
私たちのアルゴリズムは、小さなドメインで最悪の場合のバウンダリも改善しています。
特に、$O ( \sqrt{T(d \vert{\mathcal{X}}\vert ) ^{1/2} })$を後悔したオラクル効率のアルゴリズムを与え、これは [DS16] で束縛された以前の$O ( \sqrt{T\vert{\mathcal{X} } \vert })$の洗練である。
関連論文リスト
- Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning [6.236688509180343]
政策訓練と展開環境が異なるオフダイナミックス強化学習(RL)について検討する。
We-DRIVE-Uは,平均的最適値$widetildemathcalObig(d H cdot min 1/rho, H/sqrtK big)$を満足するアルゴリズムを提案する。
また、新しいハードインスタンスを構築し、この設定で最初の情報理論の下界を導出する。
論文 参考訳（メタデータ） (2024-09-30T17:21:15Z) - Oracle-Efficient Hybrid Online Learning with Unknown Distribution [16.73555330791045]
有限VCクラスに対して$tildeO(Tfrac34)$,$tildeO(Tfracp+1p+2)$に対して$alpha$fat-shattering dimensionを持つクラスに対して$tildeO(Tfracp+1p+2)$という,計算効率のよいオンライン予測器が存在することを示す。
すると、結果が$K$変更で分布をシフトするシナリオにまで拡張され、$tildeO(Tfrac45Kfrac15)が返り咲く。
論文 参考訳（メタデータ） (2024-01-27T22:45:02Z) - Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。
我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
論文 参考訳（メタデータ） (2023-12-24T08:27:30Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文 参考訳（メタデータ） (2023-02-09T18:58:05Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Contextual Recommendations and Low-Regret Cutting-Plane Algorithms [49.91214213074933]
本稿では、ナビゲーションエンジンやレコメンデーションシステムにおけるルーティングアプリケーションによって動機付けられた、コンテキスト線形帯域の次の変種について考察する。
我々は、真の点$w*$と分離オラクルが返す超平面の間の全距離を、低い「回帰」を持つ新しい切断平面アルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-06-09T05:39:05Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z) - Online Learning with Vector Costs and Bandits with Knapsacks [8.340947016086739]
オンライン学習にベクターコスト(OLVCp)を導入し、各時間に1,ldots,T$の$tのステップで、未知のベクターコストを発生させるアクションを実行する必要がある。
オンラインアルゴリズムの目標は、コストベクトルの和の$ell_p$ノルムを最小化することである。
論文 参考訳（メタデータ） (2020-10-14T18:28:41Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。