Research map / Optimization / Nonconvex and smooth optimization
On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives the first lower complexity bounds for smooth convex-concave bilinearly-coupled saddle-point problems under a quadratic-growth condition, and proposes a matching optimal linearly converging algorithm with complexity separation for gradient and matrix-vector oracles.
Problem
Smooth convex-concave bilinearly-coupled saddle-point optimization min_x max_y f(x) + <y,Bx> - g(y): finding optimal first-order methods with linear convergence and separate optimal gradient and matrix-vector complexities.
Approach
Introduces condition numbers kappa_x, kappa_y, kappa_xy for general (possibly non-strongly convex) f, g under the condition min{delta_x, delta_y} > 0; proves matching lower bounds for execution time with separate costs for gradients and matrix-vector products; and builds an optimal sliding-based VI algorithm (recursive accelerated scheme with extra quadratic regularizer p_3) that attains them via
Key results
- Lower bound on execution time: Omega(tau_f sqrt(kappa_x) log(cR^2/eps) + tau_g sqrt(kappa_y) log(cR^2/eps) + tau_B sqrt(kappa_xy) log(cR^2/eps)) for any first-order saddle-point method.
- Proposed algorithm with restarts achieves O(sqrt(kappa_x) log), O(sqrt(kappa_y) log), O(sqrt(kappa_xy) log) gradient and matvec complexities, matching the lower bound up to constants.
- Specializing to strongly-convex-strongly-concave, bilinear, and affinely constrained cases recovers existing optimal lower bounds and matches existing optimal algorithms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the optimal algorithm with complexity separation | Smooth convex-concave bilinearly-coupled saddle-point optimization · Problem class satisfying δ_x > 0 and δ_y > 0 | oracle complexity: O(√κ_x log(cR²/ε)); O(√κ_y log(cR²/ε)); O(√κ_xy log(cR²/ε)) | Helped |
| Use the optimal sliding algorithm instead of the cited algorithm | Monotone variational inequalities with n=2, p₂(z)=0 and Q₁(z)=0 · Monotone variational inequality | evaluations of Q₂(z): O(M₂R²/ε) vs. O(√(L₁R²/ε) + M₂R²/ε) | Helped |
Surprising findings
- Linear convergence is impossible in general when delta_x = 0 or delta_y = 0, even though the problem is convex-concave with smoothness.
Limitations
- Theoretical focus; no experiments reported in the provided text.
- Assumes a parameter set with extra constraints (e.g., L_x > 4 mu_x) that are stated not to be fundamental but are needed for the analysis.
- Algorithm requires a sliding-type recursion with n+ nested inner loops, with complexity exponential in n = O(1) requirement.
Experimental setup
Metrics: gradient evaluation complexity matrix-vector multiplication complexity execution time lower bound
Baselines: Gradient descent ascent Extragradient Optimistic gradient Algorithm of Lin et al. (2020) / Zhang et al. (affine constraints) Algorithm of Yang et al. / Alkousa et al. (complexity separation) Chambolle-Pock-type primal-dual methods
Builds on: Sliding algorithm (Lan and Ouyang) Nesterov accelerated gradient Lan and Zhou bilinear/affinely constrained lower bounds
Closest papers by meaning
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization (NeurIPS 2024 · similarity 0.87)
- Second-Order Min-Max Optimization with Lazy Hessians (ICLR 2025 · similarity 0.87)
- Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry (NeurIPS 2024 · similarity 0.87)
- Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints (NeurIPS 2024 · similarity 0.87)
- Efficiently Escaping Saddle Points under Generalized Smoothness via Self-Bounding Regularity (NeurIPS 2025 · similarity 0.87)
- Escaping saddle points without Lipschitz smoothness: the power of nonlinear preconditioning (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.