論文の概要: Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers

• arxiv url: http://arxiv.org/abs/2110.14804v1
• Date: Wed, 27 Oct 2021 22:38:52 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-29 14:17:17.296544
• Title: Minimax Optimal Quantile and Semi-Adversarial Regret via Root-Logarithmic Regularizers
• Title（参考訳）: ルート対数正規化器による最小量子と半対数レグレット
• Authors: Jeffrey Negrea, Blair Bilodeau, Nicol\`o Campolongo, Francesco Orabona, Daniel M. Roy
• Abstract要約: 量子的(そしてより一般的には、KL)後悔は、最高の個人専門家と競争する目標を緩和し、敵対的なデータに関して、ほとんどの専門家と競争するだけである。 最近では、半対人パラダイム(Bilodeau、Negrea、Roy 2020)は、完全に対人的でも対人的でもないデータを考えることによって、対人的オンライン学習の代替緩和を提供する。 我々は、FTRLと別個のルート対数正規化器を併用したFTRLを用いて、両方のパラダイムにおいて最小限の後悔を達成し、どちらも正規Hedgeの変種と解釈できる。
• 参考スコア（独自算出の注目度）: 31.102181563065844
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantile (and, more generally, KL) regret bounds, such as those achieved by NormalHedge (Chaudhuri, Freund, and Hsu 2009) and its variants, relax the goal of competing against the best individual expert to only competing against a majority of experts on adversarial data. More recently, the semi-adversarial paradigm (Bilodeau, Negrea, and Roy 2020) provides an alternative relaxation of adversarial online learning by considering data that may be neither fully adversarial nor stochastic (i.i.d.). We achieve the minimax optimal regret in both paradigms using FTRL with separate, novel, root-logarithmic regularizers, both of which can be interpreted as yielding variants of NormalHedge. We extend existing KL regret upper bounds, which hold uniformly over target distributions, to possibly uncountable expert classes with arbitrary priors; provide the first full-information lower bounds for quantile regret on finite expert classes (which are tight); and provide an adaptively minimax optimal algorithm for the semi-adversarial paradigm that adapts to the true, unknown constraint faster, leading to uniformly improved regret bounds over existing methods.
• Abstract（参考訳）: 通常のHedge(Chaudhuri、Freund、Hsu 2009)やその変種(Hsu 2009)によって達成されたような(そしてより一般的にはKL)後悔の限界は、最も優れた個人専門家と競合する目標を緩和し、敵対的なデータに関して多くの専門家と競合するのみである。 最近では、半対人パラダイム(Bilodeau、Negrea、Roy 2020)は、完全な対人的でも確率的でもないデータ(すなわちd)を考慮して、対人的オンライン学習の代替緩和を提供する。 分離された新規な根対数正規化器を持つftrlを用いて,両方のパラダイムにおいて最小の最適後悔を達成し,どちらも正規化の変種と解釈できる。 既存のkl 後悔上限を目標分布に対して均一に保持し、任意の事前を持つ非可算なエキスパートクラスに拡張し、有限のエキスパートクラス(厳密なクラス)に対する量的後悔に対する最初の全情報下限を提供し、真の未知の制約に適応し、既存のメソッドに対して一様に改善される半敵パラダイムに対して適応的に最小化された最適アルゴリズムを提供する。

関連論文リスト

• Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints [29.514323697659613]
  我々は,学習者が任意の長期制約を満たすことなく報酬を最大化することを目的とした,knapsacks問題によるバンディットの一般化に対処する。 私たちのゴールは、双方の制約の下で機能するベスト・オブ・ザ・ワールドのアルゴリズムを設計することです。
  論文  参考訳（メタデータ） (2024-05-25T08:09:36Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。 本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
  論文  参考訳（メタデータ） (2023-10-27T09:16:58Z)
• Accelerated Rates between Stochastic and Adversarial Online Convex Optimization [2.628557920905129]
  我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。 完全i.d.の場合、我々の後悔の限界は加速の結果から期待される速度と一致し、オンラインからバッチへの変換によって最適に加速された速度を回復する。
  論文  参考訳（メタデータ） (2023-03-06T16:41:57Z)
• A Non-Asymptotic Moreau Envelope Theory for High-Dimensional Generalized Linear Models [33.36787620121057]
  ガウス空間の任意のクラスの線型予測器を示す新しい一般化境界を証明した。 私たちは、Zhou et al. (2021) の「最適化率」を直接回復するために、有限サンプルバウンドを使用します。 ローカライズされたガウス幅を用いた有界一般化の適用は、一般に経験的リスク最小化に対してシャープであることを示す。
  論文  参考訳（メタデータ） (2022-10-21T16:16:55Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。 エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。 提案手法は(線形速度で)大域的最適値に収束することが示されている。
  論文  参考訳（メタデータ） (2022-06-03T16:26:38Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularization [16.536558038560695]
  我々は、未知の制約セット内でデータを任意に生成する場合、専門家のアドバイスで予測する。 Hedgeアルゴリズムは、最近、i.d.データに対して同時にミニマックス最適であることが示されている。 我々は,すべてのレベルにおいてミニマックス後悔の上限と下限を一致させ,決定論的学習率を持つヘッジが極端外において最適以下であることを示し,すべてのレベルにおいてミニマックス後悔を適応的に得ることを証明した。
  論文  参考訳（メタデータ） (2020-07-13T17:54:34Z)
• Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs [48.44657553192801]
  我々は,適応的相手に対する盗聴フィードバックを用いたオンライン学習において,高い確率的後悔境界を得るための新しいアプローチを開発した。 我々のアプローチは、対数的に均質な自己協和障壁と強化されたフリードマンの不平等の助けを借りて、単純な学習率のスケジュールの増大に依存している。
  論文  参考訳（メタデータ） (2020-06-14T22:09:27Z)

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

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