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

arXiv: https://arxiv.org/abs/2506.08362 · HTML: https://mlsanity.com/paper/2506.08362/

## 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 (most cited first, 30 of 48)

- [Mitigating Unwanted Biases with Adversarial Learning](https://mlsanity.com/paper/1801.07593/) (2018)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2106.02326/) (2021)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Stochastic Cubic Regularization for Fast Nonconvex Optimization](https://mlsanity.com/paper/1711.02838/) (2017)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [Catalyst Acceleration for First-order Convex Optimization: from Theory to Practice](https://mlsanity.com/paper/1712.05654/) (2017)
- [Adaptive Sampling for Stochastic Risk-Averse Learning](https://mlsanity.com/paper/1910.12511/) (2019)
- [Variance Reduction for Matrix Games](https://mlsanity.com/paper/1907.02056/) (2019)
- [Complexity Lower Bounds for Nonconvex-Strongly-Concave Min-Max Optimization](https://mlsanity.com/paper/2104.08708/) (2021)
- [The Complexity of Making the Gradient Small in Stochastic Convex Optimization](https://mlsanity.com/paper/1902.04686/) (2019)
- [Improved Algorithms for Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2006.06359/) (2020)
- [Acceleration with a Ball Optimization Oracle](https://mlsanity.com/paper/2003.08078/) (2020)
- [On Lower Iteration Complexity Bounds for the Saddle Point Problems](https://mlsanity.com/paper/1912.07481/) (2019)
- [Oracle Complexity of Second-Order Methods for Smooth Convex Optimization](https://mlsanity.com/paper/1705.07260/) (2017)
- [Optimal and Adaptive Monteiro-Svaiter Acceleration](https://mlsanity.com/paper/2205.15371/) (2022)
- [Complexity of Highly Parallel Non-Smooth Convex Optimization](https://mlsanity.com/paper/1906.10655/) (2019)
- [The First Optimal Algorithm for Smooth and Strongly-Convex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2205.05653/) (2022)
- [The First Optimal Acceleration of High-Order Methods in Smooth Convex Optimization](https://mlsanity.com/paper/2205.09647/) (2022)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss](https://mlsanity.com/paper/2105.01778/) (2021)
- [ReSQueing Parallel and Private Stochastic Convex Optimization](https://mlsanity.com/paper/2301.00457/) (2023)
- [Near-optimal method for highly smooth convex optimization](https://mlsanity.com/paper/1812.08026/) (2018)
- [Higher-order methods for convex-concave min-max optimization and monotone variational inequalities](https://mlsanity.com/paper/2007.04528/) (2020)
- [Coordinate Methods for Matrix Games](https://mlsanity.com/paper/2009.08447/) (2020)
- [Sharper Rates for Separable Minimax and Finite Sum Optimization via Primal-Dual Extragradient Methods](https://mlsanity.com/paper/2202.04640/) (2022)

## 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.