# Efficient First Order Method for Saddle Point Problems with Higher Order Smoothness

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2023.

## Built on by (most cited first, 4 of 4)

- [Near-Optimal Nonconvex-Strongly-Convex Bilevel Optimization with Fully First-Order Oracles](https://mlsanity.com/paper/2306.14853/) (2023)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [Stochastic Bilevel Optimization with Heavy-Tailed Noise](https://mlsanity.com/paper/2509.14952/) (2025)
- [On the Condition Number Dependency in Bilevel Optimization](https://mlsanity.com/paper/2511.22331/) (2025)

## Abstract (arXiv)

This paper studies the complexity of finding approximate stationary points for the smooth nonconvex-strongly-concave (NC-SC) saddle point problem: minxmaxyf(x,y). Under the standard first-order smoothness conditions where f is ℓ-smooth in both arguments and μy-strongly concave in y, existing literature shows that the optimal complexity for first-order methods to obtain an ε-stationary point is tildeObig(√kappayℓε-2big), where kappay=ℓ/μy is the condition number. However, when Phi(x):=maxy f(x,y) has L2-Lipschitz continuous Hessian in addition, we derive a first-order algorithm with an tildeObig(√kappayℓ1/2L21/4ε-7/4big) complexity by designing an accelerated proximal point algorithm enhanced with the "Convex Until Proven Guilty" technique. Moreover, an improved Omegabig(√kappayℓ3/7L22/7ε-12/7big) lower bound for first-order method is also derived for sufficiently small ε. As a result, given the second-order smoothness of the problem, the complexity of our method improves the state-of-the-art result by a factor of tildeObig(big(fracℓ2L2εbig)1/4big), while almost matching the lower bound except for a small tildeObig(big(fracℓ2L2εbig)1/28big) factor.