論文の概要: Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee
- arxiv url: http://arxiv.org/abs/2210.12860v1
- Date: Sun, 23 Oct 2022 21:24:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-25 22:10:57.428920
- Title: Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee
- Title(参考訳): 最適収束保証付き二階min-max最適化法
- Authors: Tianyi Lin, Panayotis Mertikopoulos and Michael I. Jordan
- Abstract要約: そこで本稿では,制約のないmin-max問題の大域的サドル点を求めるために,正確にかつ不正確なニュートン型手法を提案し,解析する。
1次法と比較して、min-maxの2次法の研究は比較的限られている。
- 参考スコア(独自算出の注目度): 115.64182929032334
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose and analyze exact and inexact regularized Newton-type methods for
finding a global saddle point of a \textit{convex-concave} unconstrained
min-max optimization problem. Compared to their first-order counterparts,
investigations of second-order methods for min-max optimization are relatively
limited, as obtaining global rates of convergence with second-order information
is much more involved. In this paper, we highlight how second-order information
can be used to speed up the dynamics of dual extrapolation methods {despite
inexactness}. Specifically, we show that the proposed algorithms generate
iterates that remain within a bounded set and the averaged iterates converge to
an $\epsilon$-saddle point within $O(\epsilon^{-2/3})$ iterations in terms of a
gap function. Our algorithms match the theoretically established lower bound in
this context and our analysis provides a simple and intuitive convergence
analysis for second-order methods without requiring any compactness
assumptions. Finally, we present a series of numerical experiments on synthetic
and real data that demonstrate the efficiency of the proposed algorithms.
- Abstract(参考訳): 我々は,制約のないmin-max最適化問題の大域的サドル点を求めるために,正確なニュートン型正規化手法を提案し,解析する。
第1次に比べて、第2次情報との収束率のグローバル化はより深く関与するため、min-max最適化のための第2次手法の調査は比較的限られている。
本稿では,二階情報を用いて双対外挿法 {despite inexactness} のダイナミクスを高速化する方法について述べる。
具体的には、提案アルゴリズムが有界集合内に留まる反復を生成し、平均的な反復はギャップ関数の項で$O(\epsilon^{-2/3})$イテレーション内に$\epsilon$-saddle点に収束することを示す。
我々のアルゴリズムはこの文脈で理論的に確立された下限に一致し、解析はコンパクト性仮定を必要とせず、二階法に対して単純で直感的な収束解析を提供する。
最後に,提案アルゴリズムの効率性を実証する,合成および実データに関する一連の数値実験を示す。
関連論文リスト
- Stochastic Optimization for Non-convex Problem with Inexact Hessian
Matrix, Gradient, and Function [99.31457740916815]
信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。
TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
論文 参考訳(メタデータ) (2023-10-18T10:29:58Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳(メタデータ) (2023-01-10T12:18:47Z) - DRSOM: A Dimension Reduced Second-Order Method [13.778619250890406]
信頼的な枠組みの下では,2次法の収束を保ちながら,数方向の情報のみを用いる。
理論的には,この手法は局所収束率と大域収束率が$O(epsilon-3/2)$であり,第1次条件と第2次条件を満たすことを示す。
論文 参考訳(メタデータ) (2022-07-30T13:05:01Z) - On the Oracle Complexity of Higher-Order Smooth Non-Convex Finite-Sum
Optimization [1.6973426830397942]
平滑な非有限和最適化における高階法の下限を証明する。
pth-order regularized method は有限和の目的から利益を得ることができないことを示す。
新たな二階平滑性仮定は一階平均二乗平滑性に類似していると考えられる。
論文 参考訳(メタデータ) (2021-03-08T23:33:58Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳(メタデータ) (2020-12-11T08:28:51Z) - Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。
この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。
滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
論文 参考訳(メタデータ) (2020-10-22T22:54:54Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。