論文の概要: Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games

• arxiv url: http://arxiv.org/abs/2006.07541v1
• Date: Sat, 13 Jun 2020 02:55:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-21 20:32:42.581336
• Title: Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games
• Title（参考訳）: the perturbed leader: 滑らかなミニマックスゲームのための最適化と高速並列アルゴリズム
• Authors: Arun Sai Suggala, Praneeth Netrapalli
• Abstract要約: オンライン学習の問題点とそのミニマックスゲームへの応用について考察する。 オンライン学習の問題に対して、Follow Perturbed Leaderは、最も優れたレスポンスを計算する、広く摂動されたオラクル設定である。
• 参考スコア（独自算出の注目度）: 33.9383996530254
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of online learning and its application to solving minimax games. For the online learning problem, Follow the Perturbed Leader (FTPL) is a widely studied algorithm which enjoys the optimal $O(T^{1/2})$ worst-case regret guarantee for both convex and nonconvex losses. In this work, we show that when the sequence of loss functions is predictable, a simple modification of FTPL which incorporates optimism can achieve better regret guarantees, while retaining the optimal worst-case regret guarantee for unpredictable sequences. A key challenge in obtaining these tighter regret bounds is the stochasticity and optimism in the algorithm, which requires different analysis techniques than those commonly used in the analysis of FTPL. The key ingredient we utilize in our analysis is the dual view of perturbation as regularization. While our algorithm has several applications, we consider the specific application of minimax games. For solving smooth convex-concave games, our algorithm only requires access to a linear optimization oracle. For Lipschitz and smooth nonconvex-nonconcave games, our algorithm requires access to an optimization oracle which computes the perturbed best response. In both these settings, our algorithm solves the game up to an accuracy of $O(T^{-1/2})$ using $T$ calls to the optimization oracle. An important feature of our algorithm is that it is highly parallelizable and requires only $O(T^{1/2})$ iterations, with each iteration making $O(T^{1/2})$ parallel calls to the optimization oracle.
• Abstract（参考訳）: オンライン学習の問題とミニマックスゲームへの応用について考察する。 オンライン学習問題において、FTPL (Follow the Perturbed Leader) は、凸損失と非凸損失の両方に対して最適な$O(T^{1/2})$最悪の後悔を保証するアルゴリズムである。 本研究では,損失関数の列が予測可能である場合,最適化を組み込んだFTPLの簡単な修正により,予測不可能な列に対する最悪の後悔保証を保ちながら,より良好な後悔保証が得られることを示す。 これらの厳密な後悔境界を得る上で重要な課題はアルゴリズムの確率性と楽観性であり、FTPLの分析でよく使われるものとは異なる分析技術を必要とする。 私たちが分析で用いている重要な要素は、摂動を正規化する双対的視点である。 アルゴリズムにはいくつかの応用があるが、ミニマックスゲームの特定の応用を考える。 滑らかな凸凸ゲームを解くために、このアルゴリズムは線形最適化オラクルへのアクセスのみを必要とする。 lipschitz と smooth nonconvex-nonconcave games では、アルゴリズムは乱れたベストレスポンスを計算する最適化 oracle へのアクセスを必要とします。 これら2つの設定で,最適化オラクルへの$T$コールを用いて,O(T^{-1/2})$の精度でゲームを解決する。 アルゴリズムの重要な特徴は、高度に並列化可能であり、O(T^{1/2})$反復しか必要とせず、各反復は最適化オラクルへの$O(T^{1/2})$並列呼び出しを行う。

関連論文リスト

• An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
  リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。 私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。 非滑らかな非最適化
  論文  参考訳（メタデータ） (2023-07-10T11:56:04Z)
• Doubly Optimal No-Regret Learning in Monotone Games [10.760195409078591]
  本研究では,スムーズなモノトーンゲームのための2倍最適非線形学習アルゴリズムを提案する。 このアルゴリズムは, 滑らかかつ凸な損失関数の下での対角的条件下での最適$O(sqrtT)$後悔と, (ii) 最適$O(frac1T)$最後の収束率をナッシュ平衡に達成する。
  論文  参考訳（メタデータ） (2023-01-30T17:55:53Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)
• Quantum Algorithm for Online Convex Optimization [4.702729080310267]
  ゼロ階オンライン凸最適化問題に対して量子的優位性を求める。 本稿では,この問題に対する量子アルゴリズムを提案し,量子的優位性の可能性を示す。
  論文  参考訳（メタデータ） (2020-07-29T18:34:05Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

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

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