論文の概要: A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $Θ(T^{2/3})$ and its Application to Best-of-Both-Worlds

• arxiv url: http://arxiv.org/abs/2405.20028v1
• Date: Thu, 30 May 2024 13:13:12 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-31 14:28:22.574353
• Title: A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $Θ(T^{2/3})$ and its Application to Best-of-Both-Worlds
• Title（参考訳）: 99ドル(T^{2/3})を最小限に設定したオンライン学習におけるFTRLの簡易かつ適応的な学習率とそのBest-of-Both-Worldsへの応用
• Authors: Taira Tsuchiya, Shinji Ito,
• Abstract要約: FTRL(Follow-the-Regularized-Leader)は、さまざまなオンライン学習問題の強力なフレームワークである。 Theta(T2/3)$のミニマックスを後悔する問題に対する適応学習率フレームワークを導入する。 学習率とTsallisエントロピー正規化器によるFTRLは,既存のBest-of-BothWorlds(BOBW)の上界を悪化させることを示す。
• 参考スコア（独自算出の注目度）: 35.8717656676532
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Follow-the-Regularized-Leader (FTRL) is a powerful framework for various online learning problems. By designing its regularizer and learning rate to be adaptive to past observations, FTRL is known to work adaptively to various properties of an underlying environment. However, most existing adaptive learning rates are for online learning problems with a minimax regret of $\Theta(\sqrt{T})$ for the number of rounds $T$, and there are only a few studies on adaptive learning rates for problems with a minimax regret of $\Theta(T^{2/3})$, which include several important problems dealing with indirect feedback. To address this limitation, we establish a new adaptive learning rate framework for problems with a minimax regret of $\Theta(T^{2/3})$. Our learning rate is designed by matching the stability, penalty, and bias terms that naturally appear in regret upper bounds for problems with a minimax regret of $\Theta(T^{2/3})$. As applications of this framework, we consider two major problems dealing with indirect feedback: partial monitoring and graph bandits. We show that FTRL with our learning rate and the Tsallis entropy regularizer improves existing Best-of-Both-Worlds (BOBW) regret upper bounds, which achieve simultaneous optimality in the stochastic and adversarial regimes. The resulting learning rate is surprisingly simple compared to the existing learning rates for BOBW algorithms for problems with a minimax regret of $\Theta(T^{2/3})$.
• Abstract（参考訳）: FTRL(Follow-the-Regularized-Leader)は、さまざまなオンライン学習問題の強力なフレームワークである。 過去の観測に適応するように正規化器と学習率を設計することで、FTRLは基礎となる環境の様々な特性に適応して機能することが知られている。 しかし、既存の適応学習率のほとんどは、ラウンド数$T$に対して$\Theta(\sqrt{T})$のミニマックス後悔を伴うオンライン学習問題に対するものであり、間接的なフィードバックを扱ういくつかの重要な問題を含む$\Theta(T^{2/3})$のミニマックス後悔を伴う問題の適応学習率に関する研究はわずかである。 この制限に対処するため、我々は、$\Theta(T^{2/3})$のミニマックス後悔問題に対する新しい適応学習率フレームワークを構築した。 学習速度は安定性、ペナルティ、バイアスの項を一致させて設計されており、この項は最小限の最小限の残差が$\Theta(T^{2/3})$である問題に対して自然に上界に現れる。 このフレームワークの応用として、間接的なフィードバックを扱う2つの大きな問題として、部分的なモニタリングとグラフの帯域幅について考察する。 学習速度とTsallisエントロピー正規化器を用いたFTRLは,既存のBest-of-Both-Worlds (BOBW) の上界を後悔し,確率的・対角的体制において同時最適性を達成できることを示す。 結果として得られた学習率は、BOBWアルゴリズムの既存の学習率と比較して、$\Theta(T^{2/3})$のミニマックス後悔問題に対して驚くほど単純である。

関連論文リスト

• Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
  ミニマックス問題は、機械学習のトレーニングから大規模学習まで、機械学習アプリケーション全体にわたって発生する。 本稿では,非ミニマックス問題 (emphi) に対するアルゴリズムのクラスを提案し,複雑性を$varepsilon-6)$に減らした。 我々は、FedSGDA-Mが$O(kappa2-3)$と$O(kappa2-3)$の最もよく知られた通信量を持つことを示す。
  論文  参考訳（メタデータ） (2023-10-05T15:48:41Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Near-Optimal Adversarial Reinforcement Learning with Switching Costs [43.895798638743784]
  本稿では, スイッチングコストを伴い, 効率の良いRLアルゴリズムの開発方法について述べる。 我々の下限は、敵RLのコストを切り替えるという根本的な課題のため、最も達成された後悔はもはや達成不可能であることを示している。 本稿では,遷移関数が知られているときの下位境界に一致することを後悔する2つの新しいスイッチング・リデュースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-08T23:41:29Z)
• Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
  本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。 運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
  論文  参考訳（メタデータ） (2022-11-14T12:32:18Z)
• Generalized Bandit Regret Minimizer Framework in Imperfect Information Extensive-Form Game [9.933208900617174]
  我々は,IIEGのダイナミクスを知らない対話型バンディットフィードバック設定の問題点を考察する。 NEを学習するには、後悔最小化器は、全フィードバック損失勾配$ellt$ by $v(zt)$を推定し、後悔を最小化する。 モデルフリーであり、$O(sqrtX B/T+sqrtY C/T)$から$O()$までの最良の収束率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-03-11T13:45:42Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Fast Rates for Nonparametric Online Learning: From Realizability to Learning in Games [36.969021834291745]
  本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。 この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。 実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
  論文  参考訳（メタデータ） (2021-11-17T05:24:21Z)
• Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints [94.76881135901753]
  一般的な限定的適応モデルとして,バッチ学習モデルとレアポリシースイッチモデルがある。 提案したLSVI-UCB-Batchアルゴリズムは,$tilde O(sqrtd3H3T + dHT/B)$ regretを実現する。 まれなポリシスイッチモデルでは,提案されたLSVI-UCB-RareSwitchアルゴリズムは,$tilde O(sqrtd3H3T[1+T/(dH)]dH/B)$の後悔を享受する。
  論文  参考訳（メタデータ） (2021-01-06T18:56:07Z)
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition [37.6975819766632]
  我々は、敵対コストと既知の移行で最短経路問題を研究します。 ミニマックスの後悔は,全情報設定と盗聴フィードバック設定に対して$widetildeO(sqrtDTstar K)$および$widetildeO(sqrtDTstar SA K)$であることを示す。
  論文  参考訳（メタデータ） (2020-12-07T20:55:28Z)

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

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