論文の概要: Newton-type Methods for Minimax Optimization
- arxiv url: http://arxiv.org/abs/2006.14592v2
- Date: Thu, 11 Feb 2021 01:54:34 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-17 03:38:34.596491
- Title: Newton-type Methods for Minimax Optimization
- Title(参考訳): ミニマックス最適化のためのニュートン型手法
- Authors: Guojun Zhang, Kaiwen Wu, Pascal Poupart and Yaoliang Yu
- Abstract要約: ノンコンケーブなミニマックス学習のための2つの新しいニュートン型アルゴリズムを提案する。
それらの収束を厳密なミニマックス点(シーケンシャル解)で証明する。
- 参考スコア(独自算出の注目度): 37.58722381375258
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Differential games, in particular two-player sequential zero-sum games
(a.k.a. minimax optimization), have been an important modeling tool in applied
science and received renewed interest in machine learning due to many recent
applications, such as adversarial training, generative models and reinforcement
learning. However, existing theory mostly focuses on convex-concave functions
with few exceptions. In this work, we propose two novel Newton-type algorithms
for nonconvex-nonconcave minimax optimization. We prove their local convergence
at strict local minimax points, which are surrogates of global solutions. We
argue that our Newton-type algorithms nicely complement existing ones in that
(a) they converge faster to strict local minimax points; (b) they are much more
effective when the problem is ill-conditioned; (c) their computational
complexity remains similar. We verify the effectiveness of our Newton-type
algorithms through experiments on training GANs which are intrinsically
nonconvex and ill-conditioned.
- Abstract(参考訳): 微分ゲーム、特に2プレイヤー連続ゼロサムゲーム(ミニマックス最適化)は応用科学において重要なモデリングツールであり、敵の訓練、生成モデル、強化学習など多くの最近の応用により機械学習に新たな関心が寄せられている。
しかし、既存の理論は、ほとんど例外なく凸凸函数に焦点を当てている。
本研究では,非凸非凸ミニマックス最適化のための2つのニュートン型アルゴリズムを提案する。
我々は、その局所収束を、大域解の代理である厳密な局所極小点で証明する。
私たちはニュートン型アルゴリズムが既存のアルゴリズムをうまく補完すると主張している。
(a) 厳密な局所極小点へより早く収束する。
(b)問題が不調な場合には、より効果的である。
(c)計算複雑性は相変わらず類似している。
我々はニュートン型アルゴリズムの有効性を、本質的に非凸かつ不条件であるGANの訓練実験を通じて検証する。
関連論文リスト
- Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization [20.093236438944718]
我々は非線形ミニマックス問題に対処する新しい勾配法を開発した。
提案手法は,他の手法と同等の結果が得られることを示す。
論文 参考訳(メタデータ) (2024-10-29T17:47:22Z) - Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods [37.1630298053787]
我々はヘルパーフレームワークと呼ばれる新しいフレームワークを提案する。
グローバルな複雑性保証を備えた分散アルゴリズムと二階アルゴリズムの統一的なビューを提供する。
論文 参考訳(メタデータ) (2023-02-23T12:18:28Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳(メタデータ) (2022-11-14T12:32:18Z) - Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。
連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。
提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
論文 参考訳(メタデータ) (2021-11-01T21:06:35Z) - Newton-LESS: Sparsification without Trade-offs for the Sketched Newton
Update [88.73437209862891]
2階最適化において、潜在的なボトルネックは繰り返しごとに最適化関数のヘシアン行列を計算することである。
本稿では,ガウススケッチ行列を劇的に分散させることにより,スケッチの計算コストを大幅に削減できることを示す。
ニュートン=ルネッサはガウス埋め込みとほぼ同じ問題に依存しない局所収束率を享受していることを証明した。
論文 参考訳(メタデータ) (2021-07-15T17:33:05Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳(メタデータ) (2021-06-02T22:03:36Z) - Why Do Local Methods Solve Nonconvex Problems? [54.284687261929115]
非使用最適化は、現代の機械学習においてユビキタスである。
機械学習問題の場合、厳格に定式化します。
我々はこの現象の統一的な説明を仮定する。
論文 参考訳(メタデータ) (2021-03-24T19:34:11Z) - Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax
Problems [26.24895953952318]
我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。
また、単一または2つのミニバッチ誘導体でも機能する。
論文 参考訳(メタデータ) (2020-06-27T03:05:18Z) - On Newton Screening [14.040371216692645]
我々はNewton Screening (NS) と呼ばれる新しいスクリーニング手法を開発した。
NSは、一段階局所収束を達成するという意味で、最適収束特性を有することを示す。
論文 参考訳(メタデータ) (2020-01-27T11:25:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。