論文の概要: Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee

• arxiv url: http://arxiv.org/abs/2210.12860v4
• Date: Tue, 23 Apr 2024 15:40:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-24 20:24:35.356608
• Title: Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee
• Title（参考訳）: 最適収束保証を用いた2次最小最適化法
• Authors: Tianyi Lin, Panayotis Mertikopoulos, Michael I. Jordan,
• Abstract要約: 我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
• 参考スコア（独自算出の注目度）: 86.05440220344755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose and analyze several inexact regularized Newton-type methods for finding a global saddle point of \emph{convex-concave} unconstrained min-max optimization problems. Compared to first-order methods, our understanding of second-order methods for min-max optimization is relatively limited, as obtaining global rates of convergence with second-order information is much more involved. In this paper, we examine how second-order information can be used to speed up extra-gradient methods, even under inexactness. Specifically, we show that the proposed methods generate iterates that remain within a bounded set and that the averaged iterates converge to an $\epsilon$-saddle point within $O(\epsilon^{-2/3})$ iterations in terms of a restricted gap function. This matched the theoretically established lower bound in this context. We also provide a simple routine for solving the subproblem at each iteration, requiring a single Schur decomposition and $O(\log\log(1/\epsilon))$ calls to a linear system solver in a quasi-upper-triangular system. Thus, our method improves the existing line-search-based second-order min-max optimization methods by shaving off an $O(\log\log(1/\epsilon))$ factor in the required number of Schur decompositions. Finally, we present numerical experiments on synthetic and real data that demonstrate the efficiency of the proposed methods.
• Abstract（参考訳）: 本研究では,非制約のmin-max最適化問題の大域的サドル点を求めるために,いくつかの不正確な正規化ニュートン型手法を提案し,解析する。 1次法と比較して,2次情報による収束率のグローバル化はより深く関与するため,min-max最適化のための2次法の理解は比較的限られている。 本稿では,不正確な場合であっても,2次情報を用いて段階外手法を高速化する方法について検討する。 具体的には,提案手法が有界集合内に留まるイテレートを生成し,その平均イテレートが制限ギャップ関数の項で$O(\epsilon^{-2/3})$イテレーション内に$\epsilon$-saddle点に収束することを示す。 この文脈において理論的に確立された下界と一致する。 また、各イテレーションにおいてサブプロブレムを解くための簡単なルーチンも提供し、Sur分解を1つと$O(\log\log(1/\epsilon))$を準アップパー三角形系の線形システムソルバに呼び出します。 そこで,本手法は,必要数のシュル分解において,$O(\log\log(1/\epsilon))$因子をシェービングすることで,既存のライン探索に基づく2階分極最適化法を改善する。 最後に,提案手法の有効性を示す合成および実データに関する数値実験を行った。

関連論文リスト

• A Fully First-Order Method for Stochastic Bilevel Optimization [8.663726907303303]
  一階勾配オラクルのみが利用できる場合、制約のない二段階最適化問題を考える。 完全一階近似法(F2SA)を提案し,その非漸近収束特性について検討する。 MNISTデータハイパクリーニング実験において,既存の2次手法よりも提案手法の実用性能が優れていることを示す。
  論文  参考訳（メタデータ） (2023-01-26T05:34:21Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。 特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
  論文  参考訳（メタデータ） (2023-01-10T20:43:29Z)
• DRSOM: A Dimension Reduced Second-Order Method [13.778619250890406]
  信頼的な枠組みの下では,2次法の収束を保ちながら,数方向の情報のみを用いる。 理論的には,この手法は局所収束率と大域収束率が$O(epsilon-3/2)$であり,第1次条件と第2次条件を満たすことを示す。
  論文  参考訳（メタデータ） (2022-07-30T13:05:01Z)
• A Newton-CG based barrier method for finding a second-order stationary point of nonconvex conic optimization with complexity guarantees [0.5922488908114022]
  2つの微分可能な関数の交叉を最小限に抑える2階定常点(SOSP)の発見を検討する。 我々の方法は反復であるだけでなく、最もよく知られた複雑性にマッチする$mincal O(epsilon/2)を達成する。
  論文  参考訳（メタデータ） (2022-07-12T17:21:45Z)
• Generalized Optimistic Methods for Convex-Concave Saddle Point Problems [24.5327016306566]
  この楽観的な手法は凸凹点問題の解法として人気が高まっている。 我々は,係数を知らずにステップサイズを選択するバックトラックライン探索手法を開発した。
  論文  参考訳（メタデータ） (2022-02-19T20:31:05Z)
• Adaptive extra-gradient methods for min-max optimization and games [35.02879452114223]
  本稿では,初期の反復で観測された勾配データの幾何を自動的に活用する,minmax最適化アルゴリズムの新たなファミリーを提案する。 この適応機構により,提案手法は問題がスムーズかどうかを自動的に検出する。 滑らかな問題における$mathcalO (1/varepsilon)$反復と、非滑らかな問題における$mathcalO (1/varepsilon)$反復に収束する。
  論文  参考訳（メタデータ） (2020-10-22T22:54:54Z)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)
• Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query Complexity [109.54166127479093]
  ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。 本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。 我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。 同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
  論文  参考訳（メタデータ） (2019-07-30T02:21:43Z)

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

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