論文の概要: Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Ratio Analysis and Best-of-Both-Worlds

• arxiv url: http://arxiv.org/abs/2403.00715v1
• Date: Fri, 1 Mar 2024 18:03:49 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-05 16:34:52.692413
• Title: Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Ratio Analysis and Best-of-Both-Worlds
• Title（参考訳）: 追従型リーダの適応学習速度:競争率分析とベスト・オブ・ボス・ワールド
• Authors: Shinji Ito, Taira Tsuchiya, Junya Honda
• Abstract要約: FTRL(Follow-The-Regularized-Leader)は、オンライン学習における効果的で汎用的なアプローチとして知られている。 逐次意思決定問題としてFTRLの学習率を調整する問題を定式化する。 我々は,この下限の定数係数内で上限を達成できる学習率の更新ルールを提案する。
• 参考スコア（独自算出の注目度）: 46.30750729936261
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Follow-The-Regularized-Leader (FTRL) is known as an effective and versatile approach in online learning, where appropriate choice of the learning rate is crucial for smaller regret. To this end, we formulate the problem of adjusting FTRL's learning rate as a sequential decision-making problem and introduce the framework of competitive analysis. We establish a lower bound for the competitive ratio and propose update rules for learning rate that achieves an upper bound within a constant factor of this lower bound. Specifically, we illustrate that the optimal competitive ratio is characterized by the (approximate) monotonicity of components of the penalty term, showing that a constant competitive ratio is achievable if the components of the penalty term form a monotonically non-increasing sequence, and derive a tight competitive ratio when penalty terms are $\xi$-approximately monotone non-increasing. Our proposed update rule, referred to as \textit{stability-penalty matching}, also facilitates constructing the Best-Of-Both-Worlds (BOBW) algorithms for stochastic and adversarial environments. In these environments our result contributes to achieve tighter regret bound and broaden the applicability of algorithms for various settings such as multi-armed bandits, graph bandits, linear bandits, and contextual bandits.
• Abstract（参考訳）: FTRL(Follow-The-Regularized-Leader)は、オンライン学習において効果的で汎用的なアプローチとして知られている。 そこで我々は、FTRLの学習率を逐次決定問題として調整する問題を定式化し、競合分析の枠組みを導入する。 我々は,競争比率の下限を設定し,この下限の定数係数内で上限を達成する学習率の更新ルールを提案する。 具体的には、ペナルティ項の成分の(近似的な)単調性により最適競争比が特徴づけられ、ペナルティ項の成分が単調に非増加列を形成し、ペナルティ項が$\xi$-aqua monotone non-increasing であるときに厳密な競争比が導出される場合、一定の競争比が達成可能であることを示す。 提案した更新ルールは,確率的および対向的環境のためのBest-Of-Both-Worlds (BOBW)アルゴリズムの構築を容易にする。 これらの環境下では, より厳密な後悔と, マルチアームバンド, グラフバンド, 線形バンディット, コンテキストバンドディットなどの様々な設定に対するアルゴリズムの適用性の向上に寄与する。

関連論文リスト

• Batched Nonparametric Contextual Bandits [21.031965676746776]
  バッチ制約下での非パラメトリック文脈帯域について検討する。 最適な後悔を実現する新しいバッチ学習アルゴリズムを提案する。 我々の理論的結果は、非パラメトリックな文脈的帯域幅では、ほぼ一定数のポリシー更新が最適な後悔をもたらすことを示唆している。
  論文  参考訳（メタデータ） (2024-02-27T18:06:20Z)
• The equivalence of dynamic and strategic stability under regularized learning in games [33.74394172275373]
  有限ゲームにおける正規化学習の長時間動作について検討する。 戦略的安定性と動的安定性の等価性を得る。 エントロピー正則化に基づく手法は幾何速度で収束することを示す。
  論文  参考訳（メタデータ） (2023-11-04T14:07:33Z)
• Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds [46.30750729936261]
  FTRL(Follow-the-regularized-leader)は近年,バンドイット問題における適応性獲得の最も有望なアプローチの1つである。 我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
  論文  参考訳（メタデータ） (2023-05-26T23:20:48Z)
• Accelerated Rates between Stochastic and Adversarial Online Convex Optimization [2.628557920905129]
  我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。 完全i.d.の場合、我々の後悔の限界は加速の結果から期待される速度と一致し、オンラインからバッチへの変換によって最適に加速された速度を回復する。
  論文  参考訳（メタデータ） (2023-03-06T16:41:57Z)
• On the Complexity of Adversarial Decision Making [101.14158787665252]
  決定推定係数は, 相手の意思決定に対する後悔度を低く抑えるのに必要であり, 十分であることを示す。 我々は、決定推定係数を他のよく知られた複雑性尺度の変種に結びつける新しい構造結果を提供する。
  論文  参考訳（メタデータ） (2022-06-27T06:20:37Z)
• Improved Multi-label Classification under Temporal Concept Drift: Rethinking Group-Robust Algorithms in a Label-Wise Setting [10.655403615541141]
  ドキュメント分類では、非常に稀なクラスを含む数百のクラスを扱うことが多い。 クラス不均衡とドリフトは、トレーニングデータを再サンプリングすることで軽減されることがあるが、もし対象の分布が未知の将来の事象によって決定されたらどうだろうか? グループレベルの格差を軽減するために提案した,複数のグループロバスト最適化アルゴリズムを評価した。 Invariant Risk Minimization and Spectral Decoupling outperform sample-based approach to class im Balance and concept drift。
  論文  参考訳（メタデータ） (2022-03-15T13:08:03Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Adaptive Correlated Monte Carlo for Contextual Categorical Sequence Generation [77.7420231319632]
  我々は,モンテカルロ (MC) ロールアウトの集合を分散制御のために評価する政策勾配推定器に,カテゴリー列の文脈的生成を適用する。 また,二分木ソフトマックスモデルに相関したMCロールアウトを用いることで,大語彙シナリオにおける高生成コストを低減できることを示す。
  論文  参考訳（メタデータ） (2019-12-31T03:01:55Z)

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

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