mlsanityData to 14 Oct 2026

Solving Convex-Concave Problems with tildeO(ε-4/7) Second-Order Oracle Complexity

arXiv 2506.08362 ↗First posted 10 Jun 2025math.OC cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Previous algorithms can solve convex-concave minimax problems minx ∈ X maxy ∈ Y f(x,y) with O(ε-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 tildeO(ε-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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 48 of its 69 references that are in the map. First posted on arXiv 10 Jun 2025.

Builds on

48 of 69 references.

References · 48

  1. 2018Mitigating Unwanted Biases with Adversarial Learningcited by 663
  2. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 143
  3. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  4. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 83
  5. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 76
  6. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 73
  7. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 62
  8. 2018How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGDcited by 57
  9. 2017Stochastic Cubic Regularization for Fast Nonconvex Optimizationcited by 55
  10. 2020Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimizationcited by 43
  11. 2017Catalyst Acceleration for First-order Convex Optimization: from Theory to Practicecited by 39
  12. 2019Adaptive Sampling for Stochastic Risk-Averse Learningcited by 39
36 more
  1. 2019Variance Reduction for Matrix Gamescited by 38
  2. 2021Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimizationcited by 36
  3. 2019The Complexity of Making the Gradient Small in Stochastic Convex Optimizationcited by 34
  4. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34
  5. 2020Acceleration with a Ball Optimization Oraclecited by 31
  6. 2019On Lower Iteration Complexity Bounds for the Saddle Point Problemscited by 28
  7. 2017Oracle Complexity of Second-Order Methods for Smooth Convex Optimizationcited by 24
  8. 2022Optimal and Adaptive Monteiro-Svaiter Accelerationcited by 24
  9. 2019Complexity of Highly Parallel Non-Smooth Convex Optimizationcited by 22
  10. 2022The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimizationcited by 20
  11. 2022The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimizationcited by 20
  12. 2022Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimizationcited by 20
  13. 2021Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Losscited by 17
  14. 2023ReSQueing Parallel and Private Stochastic Convex Optimizationcited by 17
  15. 2018Near-optimal method for highly smooth convex optimizationcited by 16
  16. 2020Higher-order methods for convex-concave min-max optimization and monotone variational inequalitiescited by 16
  17. 2020Coordinate Methods for Matrix Gamescited by 15
  18. 2022Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methodscited by 15
  19. 2022Second-order optimization with lazy Hessianscited by 15
  20. 2022Distributionally Robust Optimization via Ball Oracle Accelerationcited by 14
  21. 2018Stochastic Variance-Reduced Cubic Regularization for Nonconvex Optimizationcited by 12
  22. 2018An Optimal High-Order Tensor Method for Convex Optimizationcited by 12
  23. 2023Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methodscited by 12
  24. 2023Online Learning Guided Curvature Approximation: A Quasi-Newton Method with Global Non-Asymptotic Superlinear Convergencecited by 11
  25. 2021Coordinate Linear Variance Reduction for Generalized Linear Programmingcited by 10
  26. 2022Optimal Methods for Higher-Order Smooth Monotone Variational Inequalitiescited by 10
  27. 2022RECAPP: Crafting a More Efficient Catalyst for Convex Optimizationcited by 8
  28. 2024Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimizationcited by 8
  29. 2022An Approximation-Based Regularized Extra-Gradient Method for Monotone Variational Inequalitiescited by 6
  30. 2022Universal Tensor Methods for Monotone Variational Inequalitiescited by 6
  31. 2024Second-Order Min-Max Optimization with Lazy Hessianscited by 5
  32. 2023Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimizationcited by 4
  33. 2023High-Order Reduced-Gradient Methods for Composite Variational Inequalitiescited by 4
  34. 2024The Oracle Complexity of Simplex-based Matrix Gamescited by 4
  35. 2023A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functionscited by 3
  36. 2025Faster Newton Methods for Convex and Nonconvex Optimization in Gradient Complexitycited by 2

Built on by

Not cited yet.