Solving Convex-Concave Problems with $\tilde{\mathcal{O}}(ε^{-4/7})$ Second-Order Oracle Complexity

• URL: http://arxiv.org/abs/2506.08362v1
• Date: Tue, 10 Jun 2025 02:20:48 GMT
• Title: Solving Convex-Concave Problems with $\tilde{\mathcal{O}}(ε^{-4/7})$ Second-Order Oracle Complexity
• Authors: Lesi Chen, Chengchang Liu, Luo Luo, Jingzhao Zhang,
• Abstract summary: We show an improved upper bound of $tildemathcalO(epsilon-4/7)$ by generalizing the optimal second-order method for convex optimization.<n>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.
• Score: 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.

Related papers

• A Fully Parameter-Free Second-Order Algorithm for Convex-Concave Minimax Problems with Optimal Iteration Complexity [2.815239177328595]
  We propose a Lipschitz-free cubic regularization (LF-CR) algorithm for solving the convex-concave minimax optimization problem. We also propose a fully parameter-free cubic regularization (FF-CR) algorithm that does not require any parameters of the problem. To the best of our knowledge, the proposed FF-CR algorithm is the first completely parameter-free second-order algorithm for solving convex-concave minimax optimization problems.
  arXiv  Detail & Related papers  (2024-07-04T01:46:07Z)
• Dueling Optimization with a Monotone Adversary [35.850072415395395]
  We study the problem of dueling optimization with a monotone adversary, which is a generalization of (noiseless) dueling convex optimization. The goal is to design an online algorithm to find a minimizer $mathbfx*$ for a function $fcolon X to mathbbRd.
  arXiv  Detail & Related papers  (2023-11-18T23:55:59Z)
• Projection-Free Methods for Stochastic Simple Bilevel Optimization with Convex Lower-level Problem [16.9187409976238]
  We study a class of convex bilevel optimization problems, also known as simple bilevel optimization. We introduce novel bilevel optimization methods that approximate the solution set of the lower-level problem.
  arXiv  Detail & Related papers  (2023-08-15T02:37:11Z)
• Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles [13.077441411315759]
  We consider bilevel optimization when the lower-level problem is strongly convex.<n>We incorporate a two-time-scale update to improve their method to achieve the near-optimal $tilde mathcalO(epsilon-2)$ first-order oracle complexity.
  arXiv  Detail & Related papers  (2023-06-26T17:07:54Z)
• A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
  In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization. In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
  arXiv  Detail & Related papers  (2023-01-10T20:43:29Z)
• The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization [88.91190483500932]
  We study the fundamental open question of finding the optimal high-order algorithm for solving smooth convex minimization problems. The reason for this is that these algorithms require performing a complex binary procedure, which makes them neither optimal nor practical. We fix this fundamental issue by providing the first algorithm with $mathcalOleft(epsilon-2/(p+1)right) $pth order oracle complexity.
  arXiv  Detail & Related papers  (2022-05-19T16:04:40Z)
• The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
  In this paper, we revisit the smooth and strongly-strongly-concave minimax optimization problem. Existing state-of-the-art methods do not match lower bound $Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$. We fix this fundamental issue by providing the first algorithm with $mathcalOleft( sqrtkappa_xkappa_ylog
  arXiv  Detail & Related papers  (2022-05-11T17:33:07Z)
• Lifted Primal-Dual Method for Bilinearly Coupled Smooth Minimax Optimization [47.27237492375659]
  We study the bilinearly coupled minimax problem: $min_x max_y f(x) + ytop A x - h(y)$, where $f$ and $h$ are both strongly convex smooth functions. No known first-order algorithms have hitherto achieved the lower complexity bound of $Omega(sqrtfracL_xmu_x + frac|A|sqrtmu_x,mu_y) log(frac1vareps
  arXiv  Detail & Related papers  (2022-01-19T05:56:19Z)
• Second-order Conditional Gradient Sliding [70.88478428882871]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.<n>The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.<n>It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)
• Near-Optimal Algorithms for Minimax Optimization [115.21519161773287]
  The paper presents the first with $tildeO(sqrtkappa_mathbf xkappa_mathbf)$, matching the design on logarithmic factors. The paper also presents algorithms that match or outperform all existing methods in these settings in terms of complexity.
  arXiv  Detail & Related papers  (2020-02-05T16:49:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.