論文の概要: Optimistic and Adaptive Lagrangian Hedging

• arxiv url: http://arxiv.org/abs/2101.09603v2
• Date: Wed, 3 Feb 2021 02:59:24 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-19 13:31:06.282464
• Title: Optimistic and Adaptive Lagrangian Hedging
• Title（参考訳）: 最適および適応的なラグランジアンヘッジ
• Authors: Ryan D'Orazio and Ruitong Huang
• Abstract要約: オンライン学習では、アルゴリズムは各ラウンドの敵によって選択される可能性のある損失のある環境と対戦する。 私たちは、後悔マッチングとヘッジを含むオンラインアルゴリズムのクラスであるLagrangian hedgingに楽観と適応的なステップを導入します。
• 参考スコア（独自算出の注目度）: 11.698607733213226
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In online learning an algorithm plays against an environment with losses possibly picked by an adversary at each round. The generality of this framework includes problems that are not adversarial, for example offline optimization, or saddle point problems (i.e. min max optimization). However, online algorithms are typically not designed to leverage additional structure present in non-adversarial problems. Recently, slight modifications to well-known online algorithms such as optimism and adaptive step sizes have been used in several domains to accelerate online learning -- recovering optimal rates in offline smooth optimization, and accelerating convergence to saddle points or social welfare in smooth games. In this work we introduce optimism and adaptive stepsizes to Lagrangian hedging, a class of online algorithms that includes regret-matching, and hedge (i.e. multiplicative weights). Our results include: a general general regret bound; a path length regret bound for a fixed smooth loss, applicable to an optimistic variant of regret-matching and regret-matching+; optimistic regret bounds for $\Phi$ regret, a framework that includes external, internal, and swap regret; and optimistic bounds for a family of algorithms that includes regret-matching+ as a special case.
• Abstract（参考訳）: オンライン学習では、アルゴリズムは各ラウンドの敵によって選択される可能性のある損失のある環境と対戦する。 このフレームワークの一般性には、例えばオフライン最適化やサドル点問題(つまり)など、逆でない問題が含まれる。 min max optimization)。 しかし、オンラインアルゴリズムは通常、非敵問題に存在する追加構造を利用するように設計されていない。 近年、オンライン学習を加速するために、楽観主義や適応的ステップサイズといった有名なオンラインアルゴリズムのわずかな変更が、オンライン学習を加速するために、いくつかのドメインで使用されています。 本研究では,後悔マッチングを含むオンラインアルゴリズムのクラスである lagrangian hedging に対して,楽観主義と適応的ステップズを導入する。 multiplicative weights (複数形 multiplicative weights) 以上の結果から, 一般的な後悔境界, 一定の円滑な損失に対するパス長さの後悔境界, 後悔マッチングと後悔マッチング+の楽観的な変種に適用可能, 遺書$\Phi$の楽観的な後悔境界, 外部, 内部, スワップ後悔を含むフレームワーク, 特別ケースとして後悔マッチング+を含むアルゴリズム群に対する楽観的な後悔境界が得られた。

関連論文リスト

• Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously [8.850922234275636]
  スイッチング後悔は、トライアルシーケンスの任意のセグメンテーションに対して定義され、各セグメンテーションの静的後悔の和に等しい。 我々のアルゴリズムは非常に効率的で、時間軸の対数的な空間と時間単位の複雑さを持つ。
  論文  参考訳（メタデータ） (2024-05-31T14:16:52Z)
• A Unified Framework for Analyzing Meta-algorithms in Online Convex Optimization [33.38582292895673]
  完全適応逆数を用いたオンライン線形最適化のアルゴリズムは,オンライン凸最適化のアルゴリズムであることを示す。 これを用いて、一般メタアルゴリズムを記述し、決定論的アルゴリズムを同様の後悔境界を持つゼロ次アルゴリズムに変換する。
  論文  参考訳（メタデータ） (2024-02-13T17:42:27Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Distributed Online Non-convex Optimization with Composite Regret [31.53784277195043]
  本稿では,分散オンライン一般損失に対する新たなネットワーク後悔を伴う,新たな複合後悔を提案する。 我々の知る限り、オンラインの非線形学習における最初の後悔である。
  論文  参考訳（メタデータ） (2022-09-21T04:16:33Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability [59.81339109121384]
  我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。 提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
  論文  参考訳（メタデータ） (2021-11-24T07:14:57Z)
• Online estimation and control with optimal pathlength regret [52.28457815067461]
  オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。 OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
  論文  参考訳（メタデータ） (2021-10-24T22:43:15Z)
• Online Learning with Imperfect Hints [72.4277628722419]
  オンライン学習において,不完全な方向ヒントを用いたアルゴリズムを開発し,ほぼ一致している。 我々のアルゴリズムはヒントの品質を損なうものであり、後悔の限界は常に相関するヒントの場合と隠れない場合とを補間する。
  論文  参考訳（メタデータ） (2020-02-11T23:06:09Z)
• Minimizing Dynamic Regret and Adaptive Regret Simultaneously [60.17824125301273]
  動的後悔と適応的後悔を同時に最小化できる新しいオンラインアルゴリズムを提案する。 我々の理論的保証は、あるアルゴリズムが任意の間隔で動的後悔を最小化できるという意味でさらに強い。
  論文  参考訳（メタデータ） (2020-02-06T03:32:37Z)

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

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