論文の概要: Solving Convex-Concave Problems with $\tilde{\mathcal{O}}(ε^{-4/7})$ Second-Order Oracle Complexity
- arxiv url: http://arxiv.org/abs/2506.08362v1
- Date: Tue, 10 Jun 2025 02:20:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-11 15:11:41.162904
- Title: Solving Convex-Concave Problems with $\tilde{\mathcal{O}}(ε^{-4/7})$ Second-Order Oracle Complexity
- Title（参考訳）: $\tilde{\mathcal{O}}(ε^{-4/7})$ 2次Oracle複雑度による凸・凹問題の解法
- Authors: Lesi Chen, Chengchang Liu, Luo Luo, Jingzhao Zhang,
- Abstract要約: 凸最適化のための最適二階法を一般化することにより,$tildemathcalO(epsilon-4/7)$の改善された上限を示す。
さらに,遅延ヘシアンアルゴリズムに類似した手法を適用し,提案アルゴリズムが二階触媒の枠組みであることを示す。
- 参考スコア（独自算出の注目度）: 27.760400553380823
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Previous algorithms can solve convex-concave minimax problems $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x,y)$ with $\mathcal{O}(\epsilon^{-2/3})$ second-order oracle calls using Newton-type methods. This result has been speculated to be optimal because the upper bound is achieved by a natural generalization of the optimal first-order method. In this work, we show an improved upper bound of $\tilde{\mathcal{O}}(\epsilon^{-4/7})$ by generalizing the optimal second-order method for convex optimization to solve the convex-concave minimax problem. We further apply a similar technique to lazy Hessian algorithms and show that our proposed algorithm can also be seen as a second-order ``Catalyst'' framework (Lin et al., JMLR 2018) that could accelerate any globally convergent algorithms for solving minimax problems.
- Abstract（参考訳）: 以前のアルゴリズムでは、convex-concave minimax problem $\min_{x \in \mathcal{X}} \max_{y \in \mathcal{Y}} f(x,y)$ with $\mathcal{O}(\epsilon^{-2/3})$ 2次オラクル呼び出しをニュートン方式で解くことができる。
この結果は、上限が最適一階法の自然な一般化によって達成されるため、最適であると推測されている。
本研究では、凸最適化の最適二階法を一般化して、凸-凹極小問題を解くことにより、$\tilde{\mathcal{O}}(\epsilon^{-4/7})$の改善された上限を示す。
さらに,遅延ヘシアンアルゴリズムに類似した手法を適用し,提案アルゴリズムは,ミニマックス問題の解法として,大域的に収束したアルゴリズムを高速化する2次の 'Catalyst'' フレームワーク(Lin et al , JMLR 2018)として見ることもできることを示した。
関連論文リスト
- A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems with Optimal Iteration Complexity [2.815239177328595]
凸凹極小最適化問題の解法として,Lipschitz-free Cubal regularization (LF-CR)アルゴリズムを提案する。
また,この問題のパラメータを必要としない完全パラメータフリー立方正則化(FF-CR)アルゴリズムを提案する。
我々の知る限り、FF-CRアルゴリズムは凸凹極小最適化問題の解法として初めて完全にパラメータフリーな2次アルゴリズムである。
論文 参考訳（メタデータ） (2024-07-04T01:46:07Z) - Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles [13.077441411315759]
両レベル最適化は、低レベル問題が強い凸である場合に考慮する。
我々は,2段階の更新を組み込んで,最適に近い$tilde MathcalO(epsilon-2)$ 1次オラクル複雑性を実現する。
論文 参考訳（メタデータ） (2023-06-26T17:07:54Z) - 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) - The First Optimal Acceleration of High-Order Methods in Smooth Convex
Optimization [88.91190483500932]
本研究では,滑らかな凸最小化問題の解法として最適高次アルゴリズムを求めるための基本的オープンな問題について検討する。
この理由は、これらのアルゴリズムが複雑なバイナリプロシージャを実行する必要があるため、最適でも実用でもないからである。
我々は、最初のアルゴリズムに$mathcalOleft(epsilon-2/(p+1)right)$pthのオーダーオーラクル複雑性を与えることで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-19T16:04:40Z) - Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax
Optimization [47.27237492375659]
双線型結合されたミニマックス問題:$min_x max_y f(x) + ytop A x - h(y)$, ここでは$f$と$h$はどちらも強凸滑らかな関数である。
Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps) の低い複雑性境界を達成した1次アルゴリズムは知られていない。
論文 参考訳（メタデータ） (2022-01-19T05:56:19Z) - Second-order Conditional Gradient Sliding [70.88478428882871]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。