論文の概要: Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's
Momentum, and Polyak's Momentum
- arxiv url: http://arxiv.org/abs/2106.12923v1
- Date: Wed, 23 Jun 2021 17:53:39 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-25 14:53:21.871908
- Title: Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's
Momentum, and Polyak's Momentum
- Title（参考訳）: 最適化における現代的な技術を理解する:Frank-Wolfe、NesterovのMomentum、PolyakのMomentum
- Authors: Jun-Kun Wang
- Abstract要約: コンベックス最適化のための反復アルゴリズムの構築と解析のレシピとして機能するモジュラーフレームワークを開発した。
我々は,いくつかの制約セットに対して,FrankWolf Nesterovアルゴリズムを新たに3つ導入した。
第2部では、ある問題に対するPolyak運動量のモジュラー解析を開発する。
- 参考スコア（独自算出の注目度）: 8.515692980023948
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the first part of this dissertation research, we develop a modular
framework that can serve as a recipe for constructing and analyzing iterative
algorithms for convex optimization. Specifically, our work casts optimization
as iteratively playing a two-player zero-sum game. Many existing optimization
algorithms including Frank-Wolfe and Nesterov's acceleration methods can be
recovered from the game by pitting two online learners with appropriate
strategies against each other. Furthermore, the sum of the weighted average
regrets of the players in the game implies the convergence rate. As a result,
our approach provides simple alternative proofs to these algorithms. Moreover,
we demonstrate that our approach of optimization as iteratively playing a game
leads to three new fast Frank-Wolfe-like algorithms for some constraint sets,
which further shows that our framework is indeed generic, modular, and
easy-to-use.
In the second part, we develop a modular analysis of provable acceleration
via Polyak's momentum for certain problems, which include solving the classical
strongly quadratic convex problems, training a wide ReLU network under the
neural tangent kernel regime, and training a deep linear network with an
orthogonal initialization. We develop a meta theorem and show that when
applying Polyak's momentum for these problems, the induced dynamics exhibit a
form where we can directly apply our meta theorem.
In the last part of the dissertation, we show another advantage of the use of
Polyak's momentum -- it facilitates fast saddle point escape in smooth
non-convex optimization. This result, together with those of the second part,
sheds new light on Polyak's momentum in modern non-convex optimization and deep
learning.
- Abstract（参考訳）: この論文研究の第1部では,凸最適化のための反復アルゴリズムの構築と解析のためのレシピとして機能するモジュラーフレームワークを開発した。
具体的には,2プレイヤーゼロサムゲームを反復的に行うことで最適化を行う。
フランク・ウルフやネステロフの加速法を含む既存の多くの最適化アルゴリズムは、2人のオンライン学習者を互いに適切な戦略でピットすることでゲームから復元することができる。
さらに、ゲーム中のプレイヤーの重み付けされた平均的後悔の和は収束率を示している。
その結果,本手法はこれらのアルゴリズムに簡単な代替的証明を与える。
さらに,ゲームプレイを反復的に行うことによる最適化のアプローチが,いくつかの制約セットに対してフランク・ウルフ風のアルゴリズムを新たに3つ導入すること,さらに,我々のフレームワークが本当に汎用的でモジュール的で使いやすくなっていることを示す。
第2部では,古典的強二次凸問題の解法,神経接核系下での広いreluネットワークの訓練,直交初期化を用いた深い線形ネットワークの訓練など,ある問題に対するpolyakの運動量による証明可能な加速度のモジュラー解析を開発した。
我々はメタ定理を開発し、これらの問題にポリアックの運動量を適用するとき、誘導力学はメタ定理を直接適用できる形式を示すことを示した。
論文の最後の部分では、ポリアックの運動量の使用の別の利点を示し、滑らかな非凸最適化において、サドルポイントの高速脱出を容易にする。
この結果、第2部と共に、現代の非凸最適化とディープラーニングにおけるPolyakの勢いに新たな光を当てた。
関連論文リスト
- Analyzing and Enhancing the Backward-Pass Convergence of Unrolled
Optimization [50.38518771642365]
ディープネットワークにおけるコンポーネントとしての制約付き最適化モデルの統合は、多くの専門的な学習タスクに有望な進歩をもたらした。
この設定における中心的な課題は最適化問題の解によるバックプロパゲーションであり、しばしば閉形式を欠いている。
本稿では, 非線形最適化の後方通過に関する理論的知見を提供し, 特定の反復法による線形システムの解と等価であることを示す。
Folded Optimizationと呼ばれるシステムが提案され、非ローリングなソルバ実装からより効率的なバックプロパゲーションルールを構築する。
論文 参考訳（メタデータ） (2023-12-28T23:15:18Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - The Curse of Unrolling: Rate of Differentiating Through Optimization [35.327233435055305]
未分化は反復解法を用いて解を近似し、計算経路を通して解を微分する。
我々は,(1)高速収束につながる大きな学習率を選択することができるが,アルゴリズムが任意に長いバーンインフェーズを持つことを受け入れるか,あるいは(2)即時収束につながるより少ない学習率を選択するかのどちらかを示す。
論文 参考訳（メタデータ） (2022-09-27T09:27:29Z) - Fast Convex Optimization for Two-Layer ReLU Networks: Equivalent Model
Classes and Cone Decompositions [41.337814204665364]
ReLUアクティベーション機能を持つ2層ニューラルネットワークの凸最適化アルゴリズムを開発した。
凸ゲート型ReLUモデルでは,ReLUトレーニング問題に対するデータ依存の近似バウンダリが得られることを示す。
論文 参考訳（メタデータ） (2022-02-02T23:50:53Z) - No-Regret Dynamics in the Fenchel Game: A Unified Framework for
Algorithmic Convex Optimization [20.718016474717196]
我々は,非regretゲームダイナミクスを用いた凸最適化問題を解くためのアルゴリズムフレームワークを開発した。
これらの戦略の一般的な選択は、いわゆるno-regret学習アルゴリズムである。
コンベックス最適化のための古典的な一階法の多くは、我々のフレームワークの特別なケースとして解釈できることを示す。
論文 参考訳（メタデータ） (2021-11-22T16:10:18Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - SHINE: SHaring the INverse Estimate from the forward pass for bi-level
optimization and implicit models [15.541264326378366]
近年,深層ニューラルネットワークの深度を高める手法として暗黙の深度学習が登場している。
トレーニングは双レベル問題として実行され、その計算複雑性は巨大なヤコビ行列の反復反転によって部分的に駆動される。
本稿では,この計算ボトルネックに対処する新たな手法を提案する。
論文 参考訳（メタデータ） (2021-06-01T15:07:34Z) - Acceleration Methods [87.07695512525717]
まず,二次最適化問題を用いて,モメンタムとネスト正則性最適化スキームという2つの主要な手法を導入する。
我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。
次に、emphCatalystとemphAccelerated Hybrid Proximal Extragradientフレームワークの中心にある加速度技術をカバーする。
論文 参考訳（メタデータ） (2021-01-23T17:58:25Z) - Accelerating Smooth Games by Manipulating Spectral Shapes [51.366219027745174]
滑らかなゲームにおけるアクセラレーションを特徴付けるために行列反復理論を用いる。
スペクトル形状の変換として, 勾配法, 指数勾配法について述べる。
バイリニアゲームに最適なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-01-02T19:21:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。