論文の概要: The SMART approach to instance-optimal online learning

• arxiv url: http://arxiv.org/abs/2402.17720v1
• Date: Tue, 27 Feb 2024 17:55:33 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-28 15:17:28.778714
• Title: The SMART approach to instance-optimal online learning
• Title（参考訳）: インスタンス最適化オンライン学習へのスマートアプローチ
• Authors: Siddhartha Banerjee and Alankrita Bhatt and Christina Lee Yu
• Abstract要約: 我々は、データに適応し、例えば最適な後悔を実現するオンライン学習アルゴリズムを考案する。 入力シーケンスに対するSMARTポリシーの後悔は,(1)FTLがシーケンス上で得た後悔,2)与えられた最悪のケースポリシーによって保証される後悔の上限という,乗算係数$e/(e-1)近似の1.58$の範囲内にあることを示す。
• 参考スコア（独自算出の注目度）: 8.908747084128397
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We devise an online learning algorithm -- titled Switching via Monotone Adapted Regret Traces (SMART) -- that adapts to the data and achieves regret that is instance optimal, i.e., simultaneously competitive on every input sequence compared to the performance of the follow-the-leader (FTL) policy and the worst case guarantee of any other input policy. We show that the regret of the SMART policy on any input sequence is within a multiplicative factor $e/(e-1) \approx 1.58$ of the smaller of: 1) the regret obtained by FTL on the sequence, and 2) the upper bound on regret guaranteed by the given worst-case policy. This implies a strictly stronger guarantee than typical `best-of-both-worlds' bounds as the guarantee holds for every input sequence regardless of how it is generated. SMART is simple to implement as it begins by playing FTL and switches at most once during the time horizon to the worst-case algorithm. Our approach and results follow from an operational reduction of instance optimal online learning to competitive analysis for the ski-rental problem. We complement our competitive ratio upper bounds with a fundamental lower bound showing that over all input sequences, no algorithm can get better than a $1.43$-fraction of the minimum regret achieved by FTL and the minimax-optimal policy. We also present a modification of SMART that combines FTL with a ``small-loss" algorithm to achieve instance optimality between the regret of FTL and the small loss regret bound.
• Abstract（参考訳）: 我々は、モノトン適応レグレトトレース(SMART)と題するオンライン学習アルゴリズムを考案し、データに適応し、例えば、フォロー・ザ・リーダー(FTL)ポリシーのパフォーマンスと、他の入力ポリシーの最悪のケース保証と比較して、すべての入力シーケンスで同時に競合する後悔を実現する。 入力シーケンスに対するSMARTポリシーの後悔は、以下のより小さい乗算係数$e/(e-1) \approx 1.58$の範囲内であることを示す。 1) 配列上のftlにより得られた後悔,及び 2) 与えられた最悪の政策によって保証される後悔の上限 これは、それがどのように生成されるかに関わらず、全ての入力シーケンスに対して保証が保持されるため、典型的な「両世界最高の」境界よりも厳密な保証を意味する。 SMARTは実装が簡単で、FTLの再生から始まり、最悪の場合のアルゴリズムに最大1回切り替える。 本研究のアプローチと結果は,実例最適オンライン学習の運用的削減から,スキーレンタル問題に対する競合分析へと導かれる。 我々は、FTLとミニマックス最適ポリシーによって達成された最小後悔の1.43$-fraction以上のアルゴリズムが得られないことを、全ての入力シーケンスにおいて示す基礎的な下位境界で競合比の上界を補完する。 また、FTLと「小損失」アルゴリズムを組み合わせたSMARTの修正を行い、FTLの後悔と小損失の後悔境界とのインスタンス最適性を実現する。

関連論文リスト

• Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimization [37.24692425018]
  Emphconstrained MDPs(CMDPs)におけるオンライン学習の研究 提案アルゴリズムは, 対向型MDPに対して, 最先端のポリシー最適化アプローチを採用するプリミティブ・デュアル・スキームを実装している。
  論文  参考訳（メタデータ） (2024-10-03T07:54:04Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Stochastic Optimal Control Matching [53.156277491861985]
  最適制御のための新しい反復拡散最適化(IDO)技術である最適制御マッチング(SOCM)を導入する。 この制御は、一致するベクトル場に適合しようとすることで、最小二乗問題を通じて学習される。 実験により,本アルゴリズムは最適制御のための既存のすべての IDO 手法よりも低い誤差を実現する。
  論文  参考訳（メタデータ） (2023-12-04T16:49:43Z)
• Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback [30.23951525723659]
  本研究は,全情報フィードバック設定において,逆向きに損失が変化する低ランクMDPについて検討する。 政策最適化に基づくアルゴリズムPOLOを提案し、$widetildeO(Kfrac56Afrac12dln (1+M)/ (1-gamma)2)$ regret guarantee。
  論文  参考訳（メタデータ） (2023-11-14T03:12:43Z)
• Online Learning in Contextual Second-Price Pay-Per-Click Auctions [47.06746975822902]
  オンライン学習は、クリック単価のオークションで学習し、そこでは、各ラウンドのT$で、学習者がいくつかのコンテキストと広告を受信する。 学習者のゴールは、彼女の後悔を最小限に抑えることであり、それは彼女の総収入と託宣戦略のギャップとして定義される。
  論文  参考訳（メタデータ） (2023-10-08T07:04:22Z)
• 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)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Best-Case Lower Bounds in Online Learning [9.01310450044549]
  オンライン学習における研究の多くは、後悔に対する下線上界の研究に焦点を当てている。 本研究では,オンライン凸最適化における最良ケース下界の研究を開始する。 我々はFTRLの線形化バージョンが負の線形後悔を達成できることを示した。
  論文  参考訳（メタデータ） (2021-06-23T23:24:38Z)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)

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

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