Sliding Methods for Hölder-Smooth Convex--Concave Minimax Optimization with Bilinear Coupling
Abstract
We study convex-concave minimax optimization problems with bilinear coupling of the form minx∈ 𝒳maxy∈ 𝒴 f(x)+⟨ y,Bx⟩−g(y), where the functions f and g have Hölder continuous (sub)gradients. This setting covers a broad range of regimes, from nonsmooth problems with bounded subgradient variation to smooth problems with Lipschitz continuous gradients; for a smooth component used in the coupling-induced regularizer, its Lipschitz-gradient constant is assumed to hold in the ambient space. We propose a sliding method that exploits the composite structure of the problem by querying the oracles associated with f, g, and the bilinear coupling operator at prescribed frequencies determined by their individual properties. The method is based on a recursive sliding scheme for monotone variational inequalities. We establish convergence guarantees under Hölder continuity and show how the resulting complexity bounds depend explicitly on the Hölder exponents, Hölder constants, strong convexity parameters, and spectral properties of the coupling matrix. Our analysis covers nonstrongly convex and partially strongly convex regimes. For stochastic function oracles, we prove componentwise Hölder guarantees with separate variance costs: a uniform expected-gap bound on bounded domains and, when both functions are strongly convex on their feasible sets, a restarted Lyapunov guarantee without an anchor noise floor. Numerical experiments reproduce the predicted Hölder exponents and confirm that the number of gradient evaluations required for each function separates according to its own smoothness level rather than the worse of the two. A tomographic benchmark shows runtime gains when gradient evaluations are more expensive than the additional matrix-vector products.
Related
- Single-Loop Stochastic Projected Damped Extragradient Methods for Nonconvex--(Strongly) Concave Minimax Optimization
- Accelerated primal-dual dynamics and algorithms for strongly convex-concave bilinear saddle point problems
- Stein Kernels and Normal Approximation for Log-Concave Bilinear Forms
- Complexity of Multiblock Convex-Concave Saddle-Point Problems with General Smooth Coupling
- The Generalized Excursion Coupling as the Limit of Concave Optimal Transport
BibTeX
@misc{nguyen2026sliding,
title = {{Sliding Methods for Hölder-Smooth Convex--Concave Minimax Optimization with Bilinear Coupling}},
author = {Nhat Trung Nguyen and Alexander Gasnikov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.03846},
eprint = {2608.03846},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.03846},
}
RIS
TY - UNPB
TI - Sliding Methods for Hölder-Smooth Convex--Concave Minimax Optimization with Bilinear Coupling
AU - Nhat Trung Nguyen
AU - Alexander Gasnikov
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2608.03846
UR - https://arxiv.org/abs/2608.03846
AB - We study convex-concave minimax optimization problems with bilinear coupling of the form min_x∈ 𝒳max_y∈ 𝒴 f(x)+⟨ y,Bx⟩−g(y), where the functions f and g have Hölder continuous (sub)gradients. This setting covers a broad range of regimes, from nonsmooth problems with bounded subgradient variation to smooth problems with Lipschitz continuous gradients; for a smooth component used in the coupling-induced regularizer, its Lipschitz-gradient constant is assumed to hold in the ambient space. We propose a sliding method that exploits the composite structure of the problem by querying the oracles associated with f, g, and the bilinear coupling operator at prescribed frequencies determined by their individual properties. The method is based on a recursive sliding scheme for monotone variational inequalities. We establish convergence guarantees under Hölder continuity and show how the resulting complexity bounds depend explicitly on the Hölder exponents, Hölder constants, strong convexity parameters, and spectral properties of the coupling matrix. Our analysis covers nonstrongly convex and partially strongly convex regimes. For stochastic function oracles, we prove componentwise Hölder guarantees with separate variance costs: a uniform expected-gap bound on bounded domains and, when both functions are strongly convex on their feasible sets, a restarted Lyapunov guarantee without an anchor noise floor. Numerical experiments reproduce the predicted Hölder exponents and confirm that the number of gradient evaluations required for each function separates according to its own smoothness level rather than the worse of the two. A tomographic benchmark shows runtime gains when gradient evaluations are more expensive than the additional matrix-vector products.
ER -