論文の概要: No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization

• arxiv url: http://arxiv.org/abs/2111.11309v1
• Date: Mon, 22 Nov 2021 16:10:18 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-23 17:41:17.794897
• Title: No-Regret Dynamics in the Fenchel Game: A Unified Framework for Algorithmic Convex Optimization
• Title（参考訳）: フェンシェルゲームにおけるno-regretダイナミクス:アルゴリズム凸最適化のための統一フレームワーク
• Authors: Jun-Kun Wang and Jacob Abernethy and Kfir Y. Levy
• Abstract要約: 我々は,非regretゲームダイナミクスを用いた凸最適化問題を解くためのアルゴリズムフレームワークを開発した。 これらの戦略の一般的な選択は、いわゆるno-regret学習アルゴリズムである。 コンベックス最適化のための古典的な一階法の多くは、我々のフレームワークの特別なケースとして解釈できることを示す。
• 参考スコア（独自算出の注目度）: 20.718016474717196
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We develop an algorithmic framework for solving convex optimization problems using no-regret game dynamics. By converting the problem of minimizing a convex function into an auxiliary problem of solving a min-max game in a sequential fashion, we can consider a range of strategies for each of the two-players who must select their actions one after the other. A common choice for these strategies are so-called no-regret learning algorithms, and we describe a number of such and prove bounds on their regret. We then show that many classical first-order methods for convex optimization -- including average-iterate gradient descent, the Frank-Wolfe algorithm, the Heavy Ball algorithm, and Nesterov's acceleration methods -- can be interpreted as special cases of our framework as long as each player makes the correct choice of no-regret strategy. Proving convergence rates in this framework becomes very straightforward, as they follow from plugging in the appropriate known regret bounds. Our framework also gives rise to a number of new first-order methods for special cases of convex optimization that were not previously known.
• Abstract（参考訳）: 我々は,ノンレグレットゲームダイナミクスを用いた凸最適化問題を解くためのアルゴリズムフレームワークを開発した。 ミニマックスゲームを逐次的に解くための補助問題に凸関数を最小化する問題を変換することにより、各2人のプレイヤーが次々に選択しなければならない戦略の幅を考えることができる。 これらの戦略に共通する選択は、いわゆる非回帰学習アルゴリズムであり、このような多くのことを記述し、その後悔の限界を証明する。 次に,古典的な凸最適化の一階法 – 平均等階勾配降下,フランク・ウルフアルゴリズム,ヘビーボールアルゴリズム,ネステロフの加速度法など – は,各プレイヤーが非回帰戦略を正しく選択する限り,我々のフレームワークの特別なケースとして解釈できることを示す。 このフレームワークでの収束率の証明は非常に単純で、それらは適切な既知の後悔の境界をプラグインすることに従う。 また,従来は知られていなかった凸最適化の特別な事例に対して,新しい一階法がいくつか提案されている。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Invex Programs: First Order Algorithms and Their Convergence [66.40124280146863]
  Invexプログラムは、固定点ごとに世界最小値が得られる特別な非制約問題である。 そこで我々は,超凸問題における一般収束率を解くために,新しい一階法アルゴリズムを提案する。 提案アルゴリズムは,制約付き凸プログラムを解く最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-10T10:11:01Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  最適解における空間性を促進するために,テキスト規則化を用いた非テキスト・非滑らかな問題のクラスを提案する。 我々のアルゴリズムは、滑らかな凸問題に対する一階法に対するネステロフの最適収束と全く同じ$Ofrac(t2)$の特異収束を達成することができることを示す。
  論文  参考訳（メタデータ） (2023-07-04T16:55:41Z)
• Faster Margin Maximization Rates for Generic and Adversarially Robust Optimization Methods [20.118513136686452]
  一階最適化法は、未決定の訓練目標を最小化する際に、本質的に他よりも特定の解を優先する傾向がある。 本稿では,ミラー降下法と最急降下法について,最先端の暗黙バイアス率を示す。 私たちの加速速度は、このゲームフレームワークにおけるオンライン学習アルゴリズムの残念な部分を活用することによって導き出されます。
  論文  参考訳（メタデータ） (2023-05-27T18:16:56Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。 微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
  論文  参考訳（メタデータ） (2023-02-24T18:41:48Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
  未分化は反復解法を用いて解を近似し、計算経路を通して解を微分する。 我々は,(1)高速収束につながる大きな学習率を選択することができるが,アルゴリズムが任意に長いバーンインフェーズを持つことを受け入れるか,あるいは(2)即時収束につながるより少ない学習率を選択するかのどちらかを示す。
  論文  参考訳（メタデータ） (2022-09-27T09:27:29Z)
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum [8.515692980023948]
  コンベックス最適化のための反復アルゴリズムの構築と解析のレシピとして機能するモジュラーフレームワークを開発した。 我々は,いくつかの制約セットに対して,FrankWolf Nesterovアルゴリズムを新たに3つ導入した。 第2部では、ある問題に対するPolyak運動量のモジュラー解析を開発する。
  論文  参考訳（メタデータ） (2021-06-23T17:53:39Z)
• 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)
• Stochastic Regret Minimization in Extensive-Form Games [109.43344748069933]
  Monte-Carlo counterfactual regret minimization (MCCFR) は、完全な木には大きすぎるシーケンシャルゲームを解くための最先端のアルゴリズムである。 後悔の最小化手法を開発するための新しい枠組みを開発する。 MCCFRよりも優れた方法がいくつかある3つのゲームについて広範な実験を行った。
  論文  参考訳（メタデータ） (2020-02-19T23:05:41Z)

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

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