論文の概要: Accelerating Smooth Games by Manipulating Spectral Shapes
- arxiv url: http://arxiv.org/abs/2001.00602v2
- Date: Mon, 9 Mar 2020 14:51:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-16 04:02:01.353027
- Title: Accelerating Smooth Games by Manipulating Spectral Shapes
- Title(参考訳): スペクトル形状の操作によるスムースゲームの高速化
- Authors: Wa\"iss Azizian, Damien Scieur, Ioannis Mitliagkas, Simon
Lacoste-Julien, Gauthier Gidel
- Abstract要約: 滑らかなゲームにおけるアクセラレーションを特徴付けるために行列反復理論を用いる。
スペクトル形状の変換として, 勾配法, 指数勾配法について述べる。
バイリニアゲームに最適なアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 51.366219027745174
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We use matrix iteration theory to characterize acceleration in smooth games.
We define the spectral shape of a family of games as the set containing all
eigenvalues of the Jacobians of standard gradient dynamics in the family.
Shapes restricted to the real line represent well-understood classes of
problems, like minimization. Shapes spanning the complex plane capture the
added numerical challenges in solving smooth games. In this framework, we
describe gradient-based methods, such as extragradient, as transformations on
the spectral shape. Using this perspective, we propose an optimal algorithm for
bilinear games. For smooth and strongly monotone operators, we identify a
continuum between convex minimization, where acceleration is possible using
Polyak's momentum, and the worst case where gradient descent is optimal.
Finally, going beyond first-order methods, we propose an accelerated version of
consensus optimization.
- Abstract(参考訳): スムースゲームにおけるアクセラレーションを特徴付けるために行列反復理論を用いる。
ゲーム群のスペクトル形状を、家族内の標準勾配力学のジャコビアンのすべての固有値を含む集合として定義する。
実数直線に制限された形状は、最小化のようなよく理解された問題のクラスを表す。
複雑な平面にまたがる形状は、滑らかなゲームを解くための追加の数値的課題を捉えている。
この枠組みでは、スペクトル形状の変換として、超勾配などの勾配に基づく手法を記述する。
この観点から,双線型ゲームに対する最適アルゴリズムを提案する。
滑らかで強い単調作用素に対しては、ポリアックの運動量を用いて加速が可能となる凸最小化と勾配降下が最適となる最悪の場合の間の連続体を特定する。
最後に、一階法を超えて、コンセンサス最適化の高速化版を提案する。
関連論文リスト
- Euler's Elastica Based Cartoon-Smooth-Texture Image Decomposition [4.829677240798159]
グレースケール画像を3つの異なる成分に分解する新しいモデルを提案する。
構造部は強い境界と強い光-暗黒遷移のある領域、滑らかな部分、柔らかい影と影、振動、テクスチャとノイズを表す。
論文 参考訳(メタデータ) (2024-07-03T03:42:33Z) - ELRA: Exponential learning rate adaption gradient descent optimization
method [83.88591755871734]
我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。
本手法の主な考え方は,状況認識による$alphaの適応である。
これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
論文 参考訳(メタデータ) (2023-09-12T14:36:13Z) - Convex and Non-convex Optimization Under Generalized Smoothness [69.69521650503431]
凸法と非最適化法の分析は、しばしばリプシッツ勾配を必要とし、この軌道による解析を制限する。
最近の研究は、非一様滑らか性条件を通した勾配設定を一般化している。
論文 参考訳(メタデータ) (2023-06-02T04:21:59Z) - Adaptive Approximate Implicitization of Planar Parametric Curves via
Weak Gradient Constraints [11.559302398966468]
ポリノミカル曲線と非ポリノミカル曲線に新たな正規化制約を導入する。
次に、多項式曲線と非多項式曲線の近似的暗黙化の2つの適応アルゴリズムを提案する。
より正確には、このアイデアは、出力の弱い勾配損失に明らかな改善がないまで、徐々に暗黙の度合いを増している。
論文 参考訳(メタデータ) (2023-02-23T04:08:53Z) - Hessian Based Smoothing Splines for Manifold Learning [0.228438857884398]
多様体学習における多次元平滑化スプラインアルゴリズムを提案する。
平らな多様体のソボレフ空間上の二次形式に、薄板スプラインの曲げエネルギーペナルティを一般化する。
解の存在と一意性は、ヒルベルト空間を再現する理論を適用することによって示される。
論文 参考訳(メタデータ) (2023-02-10T02:49:05Z) - No-Regret Dynamics in the Fenchel Game: A Unified Framework for
Algorithmic Convex Optimization [20.718016474717196]
我々は,非regretゲームダイナミクスを用いた凸最適化問題を解くためのアルゴリズムフレームワークを開発した。
これらの戦略の一般的な選択は、いわゆるno-regret学習アルゴリズムである。
コンベックス最適化のための古典的な一階法の多くは、我々のフレームワークの特別なケースとして解釈できることを示す。
論文 参考訳(メタデータ) (2021-11-22T16:10:18Z) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳(メタデータ) (2021-05-13T04:23:07Z) - Average-case Acceleration for Bilinear Games and Normal Matrices [35.14328074551363]
ゼロサム双線型ゲームでは、平均ケース最適法がハミルトニアンの最小化に最適な方法であることを示す。
ディスク内の固有値を持つ行列に特化し、最悪の最適アルゴリズムと比較して証明可能なスピードアップを示す。
論文 参考訳(メタデータ) (2020-10-05T15:13:37Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳(メタデータ) (2020-06-16T13:41:54Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳(メタデータ) (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。