Solving Convex-Concave Problems with π’ͺ ~ ( Ο΅ βˆ’ 4 / ( 3 p + 1 ) ) \tilde{\mathcal{O}}(\epsilon^{-4/(3p+1)}) p p th-Order Oracle Complexity *

Lesi Chen, Xinliang Zhang, Chengchang Liu, Junru Li, Luo Luo, Jingzhao Zhang Β· 2026

Read Solving Convex-Concave Problems with π’ͺ ~ ( Ο΅ βˆ’ 4 / ( 3 p + 1 ) ) \tilde{\mathcal{O}}(\epsilon^{-4/(3p+1)}) p p th-Order Oracle Complexity * by Lesi Chen, Xinliang Zhang, Chengchang Liu, Junru Li, Luo Luo, Jingzhao Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-19462.txt.

Introduction

Chen and colleagues improve the upper bound on pth-order oracle complexity for convex-concave minimax problems with Lipschitz continuous pth-order derivatives. The previous bound was speculated to be optimal, since the best first-order method generalizes naturally to attain it. The authors obtain their improved upper bound by applying Monteiro-Svaiter acceleration. They also establish a lower complexity bound, suggesting a gap still exists for order 2 and above.

Catalog record

CREATORLesi Chen, Xinliang Zhang, Chengchang Liu, Junru Li, Luo Luo, Jingzhao Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE111575
LICENSEhttp://creativecommons.org/publicdomain/zero/1.0/
RIGHTSCC0
SOURCEarXiv

Source: https://arxiv.org/abs/2604.19462

Browse the full library Β· About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Solving Convex-Concave Problems with π’ͺ ~ ( Ο΅ βˆ’ 4 / ( 3 p + 1 ) ) \tilde{\mathcal{O}}(\epsilon^{-4/(3p+1)}) p p th-Order Oracle Complexity * Lesi Chen, Xinliang Zhang, Chengchang Liu, Junru Li, Luo Luo, Jingzhao Zhang Abstract When the objective has Lipschitz continuous p p th-order derivatives, it is known that convex-concave minimax problems can be solved with π’ͺ ( Ο΅ βˆ’ 2 / ( p + 1 ) ) \mathcal{O}(\epsilon^{-2/(p+1)}) p p th-order oracle calls. This complexity upper bound was speculated to be optimal as it is achieved by a natural generalization of the optimal first-order method. In this work, we show an improved upper bound of π’ͺ ~ ( Ο΅ βˆ’ 4 / ( 3 p + 1 ) ) \tilde{\mathcal{O}}(\epsilon^{-4/(3p+1)}) by applying the Monteiro-Svaiter acceleration. We also establish a lower complexity bound of Ξ© ( Ο΅ βˆ’ 2 / ( 3 p βˆ’ 1 ) ) \Omega(\epsilon^{-2/(3p-1)}) , suggesting a gap still exists for p β‰₯ 2 p\geq 2 . * * footnotetext: The first two authors contribute equally. The conference version of this manuscript is published in COLT 2025 [ 14 ] , which contains the upper bound when p=2 . This work shows our upper bound can be readily extended to p th-order methods, and provides a new lower bound for the problem. 1 Introduction We study smooth convex-concave minimax optimization problems over convex compact sets {\mathcal{X}}\subset{\mathbb{R}}^{d_{x}} and {\mathcal{Y}}\subset{\mathbb{R}}^{d_{y}} : \min_{{\bm{x}}\in{\mathcal{X}}}\max_{{\bm{y}}\in{\mathcal{Y}}}f({\bm{x}},{\bm{y}}), (1) where the objective f has L_{p} -Lipschitz continuous p th-order derivatives. This problem naturally arises from many applications, including finding a Nash equilibrium of a two-player zero-sum game [ 53 , 33 , 24 ] , solving the Lagrangian function in constrained optimization [ 45 , 50 ] , and many machine learning problems such as adversarial training [ 56 ] , AUC maximization [ 55 ] , and distributionally robust optimization [ 9 ] . A fundamental result for Problem ( 1 ) is the minimax theorem, which was first proved for bilinear problems by 53 , and extended to general convex-concave functions by 51 . The minimax theorem guarantees the existence of a saddle point ({\bm{x}}^{*},{\bm{y}}^{*}) such that f({\bm{x}}^{*},{\bm{y}}^{*})=\min_{{\bm{x}}\in{\mathcal{X}}}\max_{{\bm{y}}\in{\mathcal{Y}}}f({\bm{x}},{\bm{y}})=\max_{{\bm{y}}\in{\mathcal{Y}}}\min_{{\bm{x}}\in{\mathcal{X}}}f({\bm{x}},{\bm{y}}). Given the existence of the saddle point, a natural question is: β€œWhat is the complexity of finding such a point?” We study this question under the oracle model [ 35 ] . This model restricts algorithms to access oracles that contain local information about the objectives, where the p th-order oracle returns the tuple (f({\bm{x}},{\bm{y}}),\nabla f({\bm{x}},{\bm{y}}),\cdots,\nabla^{p}f({\bm{x}},{\bm{y}})) that gives the function value and derivatives up to order p at the query point ({\bm{x}},{\bm{y}}) . The order p naturally gives a division of different algorithm classes. For example, first-order methods purely use gradient information; second-order methods (also known as Newton-type methods) jointly use gradient and Hessian information; and tensor methods (p\geq 2) leverage higher-order derivatives information. A central problem in optimization theory research is to accurately characterize the gains provided by higher-order oracles [ 16 , 41 , 42 ] . The complexity of first-order methods for solving minimax optimization is well understood. In his seminal work, 25 proposed the celebrated extragradient (EG) method and proved it can find an \epsilon -solution to Problem ( 1 ) in {\mathcal{O}}\left(\nicefrac{{L_{1}}}{{\epsilon}}\right) iterations, where each iteration calls two first-order oracles. 46 proposed the optimistic gradient (OG) method which has the same convergence guarantee but only requires a single first-order call every iteration. 34 , 37 further proposed methods for more general spaces known as mirrox-prox (MP) and dual extrapolation (DE), respectively. 34 also proved a lower bound to show that the \Omega(\nicefrac{{L_{1}}}{{\epsilon}}) complexity is the limit of all first-order algorithms, and recent works [ 57 , 45 ] further refined the diameter dependency in the lower bound. Compared with the theory of first-order methods, we have less knowledge of higher-order minimax optimization. In their seminal work, 31 proposed the second-order generalization of EG, which can provably find an \epsilon -solution with {\mathcal{O}}((\nicefrac{{L_{2}}}{{\epsilon}})^{2/3}) second-order calls. Recently, 6 generalized this method to non-Euclidean setup and to p th order, achieving the {\mathcal{O}}((\nicefrac{{L_{p}}}{{\epsilon}})^{2/(p+1)}) upper complexity bound of p th-order oracle calls. 18 , 1 simplified the proof of the p th-order EG by viewing the p th-order tensor step as an oracle. 30 provided alternative analyses from the control-theoretic perspective. Besides the high-order EG algorithm, numerous other algorithms have also been proposed, including high-order OG [ 23 , 22 ] , high-order DE [ 29 ] , and high-order reduced-gradient methods [ 43 ] . All of these methods have the same {\mathcal{O}}((\nicefrac{{L_{p}}}{{\epsilon}})^{2/(p+1)}) upper complexity bound of p th-order oracle calls, which is speculated to be optimal in [ 1 , 29 ] . The main contribution of this paper is to break the commonly conjectured \Omega((\nicefrac{{L_{p}}}{{\epsilon}})^{2/(p+1)}) barrier by proving a better upper complexity bound of \tilde{\mathcal{O}}((\nicefrac{{L_{p}}}{{\epsilon}})^{4/(3p+1)}) for objectives with L_{p} -Lipschitz continuous p th-order derivatives. Our new result is achieved by applying the high-order momentum acceleration technique [ 32 ] to both variables {\bm{x}} and {\bm{y}} , and reducing solving the original Problem ( 1 ) to solving \tilde{\mathcal{O}}\left((\nicefrac{{\gamma}}{{\epsilon}})^{4/(3p+1)}\right) proximal minimax subproblems \min_{{\bm{x}}\in{\mathcal{X}}}\max_{{\bm{y}}\in{\mathcal{Y}}}f({\bm{x}},{\bm{y}})+\frac{\gamma}{p+1}\|{\bm{x}}-\bar{\bm{x}}\|^{p+1}-\frac{\gamma}{p+1}\|{\bm{y}}-\bar{\bm{y}}\|^{p+1}, where (\bar{\bm{x}},\bar{\bm{y}}) is the proximal center. If we take \gamma=L_{p} , the above subproblem has a constant condition number for p th-order methods. Then an \tilde{\mathcal{O}}\left((\nicefrac{{L_{p}}}{{\epsilon}})^{4/(3p+1)}\right) upper complexity bound can easily be achieved by applying any existing convergent p th-order method to solve the above subproblems. Finally, we complement our upper bound by proving a lower complexity bound showing that any p th-order algorithm can not find an \epsilon -solution in less than \Omega((\nicefrac{{L_{p}}}{{\epsilon}})^{2/(3p-1)}) oracle calls. Our lower bound is the first non-trivial lower bound for high-order minimax optimization under general conditions: Existing lower bounds either require the diameter to scale with \nicefrac{{1}}{{\epsilon}} [ 1 , 29 ] , or is subsumed by the \Omega((\nicefrac{{1}}{{\epsilon}})^{2/(3p+1)}) bound for standard minimization problems [ 3 ] (see the discussion in Section 5.1 ). Our lower bound matches the upper bound when p=1 , but a gap still exists when p\geq 2 . We hope our results can be an initial step for future works to further fill the gap. Additional Related Works Apart from the aforementioned related works in minimax optimization, we also review closely relevant studies on high-order convex optimization. In a seminal work, 36 proposed the Cubic Regularized Newton (CRN) method with the {\mathcal{O}}((\nicefrac{{L_{2}}}{{\epsilon}})^{1/2}) second-order oracle complexity, which initiated a series of subsequent works analyzing the complexity of second- and higher-order algorithms. 38 proposed the accelerated CRN (ACRN) method that achieves the improved {\mathcal{O}}((\nicefrac{{L_{2}}}{{\epsilon}})^{1/3}) complexity. 32 introduced a novel and intricate acceleration framework, under which they proposed a method with {\mathcal{O}}((\nicefrac{{L_{2}}}{{\epsilon}})^{2/7}\log(\nicefrac{{1}}{{\epsilon}})) second-order oracle complexity. 40 gave a second-order implementation of third-order tensor step and generalized the ACRN method to p th order, achieving the {\mathcal{O}}((\nicefrac{{L_{p}}}{{\epsilon}})^{1/(p+1)}) upper bound. Later, three independent groups [ 19 , 4 , 17 ] generalized the Monteiro-Svaiter accelerated method to p th order and achieved the {\mathcal{O}}((\nicefrac{{L_{p}}}{{\epsilon}})^{2/(3p+1)}\log(\nicefrac{{1}}{{\epsilon}})) upper bound, which matches the \Omega((\nicefrac{{L_{p}}}{{\epsilon}})^{2/(3p+1)}) lower bound established by 3 up to only logarithmic factors. Recently, 8 , 26 independently proposed different novel enhancements to remove the \log(\nicefrac{{1}}{{\epsilon}}) factor caused by the line search subroutine in the Monteiro-Svaiter acceleration, achieving the optimal {\mathcal{O}}((\nicefrac{{L_{p}}}{{\epsilon}})^{2/(3p+1)}) oracle complexity. 10 analyzed both the upper and lower bounds for

Read the complete text