Strengthening the finite characterizations of smooth min-max games
Valery Krivchenko, Alexander Gasnikov, Dmitry Kovalev · 2026
Read Strengthening the finite characterizations of smooth min-max games by Valery Krivchenko, Alexander Gasnikov, Dmitry Kovalev (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-2603-17053.txt.
Introduction
Krivchenko, Gasnikov, and Kovalev derive stronger constraints for smooth min-max games. These saddle point problems model many machine learning tasks with a convex concave objective. First order methods are the standard way to solve them. Their worst case guarantees depend on inequalities that constrain iterates, gradients, and function values along the way. The authors present stronger such constraints for smooth convex concave functions. They show these constraints can yield tighter upper bounds for first order methods.
Catalog record
| CREATOR | Valery Krivchenko, Alexander Gasnikov, Dmitry Kovalev |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73918 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.17053
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Strengthening the finite characterizations of smooth min-max games Valery Krivchenko, Alexander Gasnikov, Dmitry Kovalev Abstract In this paper, we address the problem of interpolation of smooth convex–concave functions. Interpolation is a key step for computer-assisted estimation of algorithms’ worst case performance via PEP-like techniques. And smooth convex–concave functions are frequently used to model min-max problems arising in machine learning. We address the challenges associated with deriving conditions that are necessary and sufficient for the interpolation of smooth min–max games and show how existing approaches can be adapted to this setting. As part of this effort, we study the smoothing properties of Moreau–Yosida-like approximations of convex–concave functions. Next, we derive interpolation conditions for several key special cases of smooth min–max games. Finally, we obtain improved (i.e., tighter) characterizations for smooth strongly monotone convex–concave functions. We analyzed linear convergence of Alt-GDA using a PEP-like technique with the novel constraints and (numerically) obtained a new estimate of the algorithm’s complexity. We are confident that the results of this paper provide meaningful progress toward establishing optimal worst-case guarantees for algorithms in the setting of smooth min-max games. keywords saddle point, smooth games, convex–concave, interpolation conditions, constraints, performance estimation problem 1 Introduction In this paper we consider the following saddle point problem \displaystyle\underset{x\in{\mathbb{R}^{d_{x}}}}{\min}\underset{y\in{\mathbb{R}^{d_{y}}}}{\max}f(x,y) (1) where {\mathbb{R}^{d_{x}}} and {\mathbb{R}^{d_{y}}} are Euclidean spaces and f(x,y)\colon{\mathbb{R}^{d_{x}}}\times{\mathbb{R}^{d_{y}}}\to\mathbb{R} is a real-valued function. More specifically, we consider min–max optimization of smooth (and possibly, strongly monotone) convex–concave functions. In literature 27 , this setting is known as smooth min–max games and is closely related to variational inequalities. Smooth min–max games have been a subject of active research largely due to the fact that they can be used to model machine learning problems. Notable examples include generative adversarial networks 7 and reinforcement learning 15 . First-order gradient-based methods are undoubtedly the go-to methodology for solving large-scale optimization problems arising in machine learning, and deep learning in particular. The main reason for this is the low cost per iteration coupled with satisfactory effectiveness. Consequently, there is a need to understand how such methods perform in the worst possible scenarios within the defined setting and to compare their worst-case performance. When it comes to min–max problems, much remains unknown about the worst-case behavior of even basic first-order methods 27 ; 28 ; 13 . One possible solution is to employ SDP-based techniques like performance estimation problems (PEP) 5 ; 26 , which makes it possible to obtain theoretical guarantees through computer-assisted calculations 8 . The idea behind PEP is to express the exact worst-case performance of an optimization algorithm as the solution of a convex SDP problem. Such a tractable formulation requires tight characterizations of function classes—interpolation conditions. Unfortunately, there is currently no approach that allows one to derive interpolation conditions for a function class directly from its definition. Nevertheless, in the absence of proper interpolation conditions, it is still meaningful to derive constraints that are as strong as possible 18 . Although the resulting formulation of PEP is no longer worst-case exact, using such constraints will yield a valid lower bound on an algorithm’s performance, which may still represent a substantial improvement over known bounds. In this paper, we build upon prior work on smooth strongly convex interpolation 20 and convex–concave interpolation 12 to obtain tighter constraints for the smooth min–max game setting. The results of this paper offer theoretical, practical, and methodological value. From a theoretical standpoint, we present the tightest characterizations of smooth strongly monotone convex–concave functions known to date. Methodologically, we demonstrate how careful analysis of special cases and related function classes can yield tighter constraints and narrow the search for proper interpolation conditions. From a practical perspective, the new algebraic characterizations of smooth strongly monotone games are compatible with the PEP framework, providing an alternative to the more cumbersome integral quadratic constraints (IQC) framework 14 ; 27 . Finally, we demonstrate that our novel constraints provide a significantly better (i.e., tighter) characterization of smooth, strongly monotone convex–concave functions than a discretized definition of the class. For this purpose, we performed a series of numerical experiments with Gradient Descent-Ascent with simultaneous updates (Sim-GDA) and Gradient Descent-Ascent with alternating updates (Alt-GDA), comprising automatic search for the best Lyapunov functions. In particular, for Alt-GDA we observe that the proposed constraints yield substantially stronger convergence guarantees, indicating that they capture structural properties that are especially relevant for algorithms with alternating updates. Our contribution can be summarized as follows: • We study smoothing properties of Moreau–Yosida-like approximation of convex–concave functions and prove that it possesses a stronger co-coercive property. To our knowledge, existing studies in the literature establish only Lipschitz smoothness of the envelope. We also adapt a conjugation-based approach (that was previously used for studying smooth convex interpolation) to smooth convex–concave interpolation. • We obtain tighter constraints for the general case of smooth strongly monotone convex–concave functions and perform an experiment to compare them with definition-based constraints. We also derive necessary and sufficient interpolation conditions for key special cases within this setting. • Using the novel constraints we are able to numerically verify a better complexity estimate of \mathcal{O}\left(\kappa^{1.26}\right) for Alt-GDA in smooth min-max games. Currently the best estimate in literature is \mathcal{O}\left(\kappa^{1.385}\right) . 1.1 Motivation and prior work on interpolation Almost all proofs of worst-case bounds (and all proofs obtained via PEP) involve constraints that describe algebraic relations between quantities appearing in the algorithm, most notably the iterates x_{i} , the gradients \nabla f(x_{i}) and the functional values f(x_{i}) . These constraints implicitly impose restrictions on the admissible gradients and functional values, ensuring that they are consistent with some function from a prescribed function class. Crucially, the set of admissible iterates, gradients, and functional values must be restricted to those that can be interpolated by a real function belonging to the considered class. Otherwise, the feasible set may contain artificial configurations that do not correspond to any actual function, leading to overly pessimistic bounds 17 . Unfortunately, a simple discretization of an arbitrary equivalent definition of a function class does not necessarily yield constraints that impose sufficiently strong restrictions. We illustrate this point with a classical example 17 . Consider the class \mathcal{F}_{L} of smooth convex functions and one of its equivalent definitions involving discretizable constraints: \displaystyle\begin{cases}f(y)\geqslant f(x)+\langle\nabla f(x),y-x\rangle,\\ \|\nabla f(y)-\nabla f(x)\|_{2}\leqslant L\|y-x\|_{2}.\end{cases}\quad\forall x,y\in\mathbb{R}^{d} (2) Also consider the alternative definition \displaystyle f(y)\geqslant f(x)+\langle\nabla f(x),y-x\rangle+\frac{\|\nabla f(y)-\nabla f(x)\|_{2}^{2}}{2L},\quad\forall x,y\in\mathbb{R}^{d} (3) Constraints ( 2 ) and ( 3 ) are completely equivalent when imposed on every pair (x,y)\in\mathbb{R}^{d} . However, most proofs involve only a finite number of constraints imposed on a finite number of points. In this case, ( 2 ) and ( 3 ) are no longer equivalent 17 . In fact, ( 3 ) constitutes the strongest discrete characterization of \mathcal{F}_{L} 20 , in the sense that these conditions are necessary and sufficient for interpolation within \mathcal{F}_{L} 19 . In contrast, the weaker constraints ( 2 ) do not guarantee the existence of an interpolating function and can therefore be a source of conservatism in worst-case bounds. Although the degree of conservatism also depends on the analyzed method and on the optimality of the analysis, the availability of stronger constraints clearly opens the path to tighter worst-case guarantees. Interpolation of function classes has