Complexity of Multiblock Convex-Concave Saddle-Point Problems with General Smooth Coupling
Abstract
We study multiblock convex--concave saddle-point problems of the form minxmaxy{f(x)+H(x,y)−g(y)}, with separately charged partial-gradient oracles for all three objective components. We impose joint smoothness and strong convexity bounds on the functions f and g, together with blockwise Lipschitz conditions on the partial gradients of H, so that the resulting oracle complexities reflect the smoothness and dependency parameters specific to each oracle. Under strong convexity, we develop a randomized lifted extragradient method that achieves linear convergence while providing simultaneous complexity guarantees for all oracles. The partial-gradient complexities for f and g exhibit the expected square-root dependence on the corresponding block condition numbers, whereas the coupling-gradient complexities depend on the associated curvature-normalized smoothness parameters. Finite-dimensional bilinear subclasses provide lower-complexity benchmarks within a randomized blockwise linear-span model. When strong convexity of f and g is not assumed, a regularization argument yields expected restricted-gap guarantees with accuracy dependence ε−1/2 for the objective-gradient oracles and ε−1 for the coupling-gradient oracles, up to logarithmic factors. Experiments show observed oracle savings and runtime improvements in regimes of poor objective conditioning.
Related
- A New Primal-Dual Algorithm with Two Convex Combinations and Linesearch for General Convex-Concave Saddle-Point Problems
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- ALDER: A Single-Loop Augmented-Lagrangian Damped Extragradient Method for Nonconvex--Concave Minimax Problems with Nonlinear Coupled Constraints
- Sharp Fresh-Gradient Complexity of Nonconvex-Strongly-Concave Minimax Optimization
BibTeX
@misc{nguyen2026complexity,
title = {{Complexity of Multiblock Convex-Concave Saddle-Point Problems with General Smooth Coupling}},
author = {Nhat Trung Nguyen and Ivan Dorofeev and Irina Podlipnova and Yuriy Dorn and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12656},
eprint = {2610.12656},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12656},
}
RIS
TY - UNPB
TI - Complexity of Multiblock Convex-Concave Saddle-Point Problems with General Smooth Coupling
AU - Nhat Trung Nguyen
AU - Ivan Dorofeev
AU - Irina Podlipnova
AU - Yuriy Dorn
AU - Alexander Gasnikov
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12656
UR - https://arxiv.org/abs/2610.12656
AB - We study multiblock convex--concave saddle-point problems of the form min_xmax_y{f(x)+H(x,y)−g(y)}, with separately charged partial-gradient oracles for all three objective components. We impose joint smoothness and strong convexity bounds on the functions f and g, together with blockwise Lipschitz conditions on the partial gradients of H, so that the resulting oracle complexities reflect the smoothness and dependency parameters specific to each oracle. Under strong convexity, we develop a randomized lifted extragradient method that achieves linear convergence while providing simultaneous complexity guarantees for all oracles. The partial-gradient complexities for f and g exhibit the expected square-root dependence on the corresponding block condition numbers, whereas the coupling-gradient complexities depend on the associated curvature-normalized smoothness parameters. Finite-dimensional bilinear subclasses provide lower-complexity benchmarks within a randomized blockwise linear-span model. When strong convexity of f and g is not assumed, a regularization argument yields expected restricted-gap guarantees with accuracy dependence ε^−1/2 for the objective-gradient oracles and ε^−1 for the coupling-gradient oracles, up to logarithmic factors. Experiments show observed oracle savings and runtime improvements in regimes of poor objective conditioning.
ER -