Convex-Concave Interpolation and Application of PEP to the Bilinear-Coupled Saddle Point Problem

V. O. Krivchenko, Alexander Gasnikov, Dmitry KovalevNelineinaya 2024 · DOI

Abstract

In this paper we present interpolation conditions for several important convex-concave function classes: nonsmooth convex-concave functions, conditions for difference of strongly-convex functions in a form that contains oracle information exclusively and smooth convex-concave functions with a bilinear coupling term. Then we demonstrate how the performance estimation problem approach can be adapted to analyze the exact worst-case convergence behavior of first-order methods applied to composite bilinear-coupled min-max problems. Using the performance estimation problem approach, we estimate iteration complexities for several first-order fixed-step methods, Sim-GDA and Alt-GDA, which are applied to smooth convex-concave functions with a bilinear coupling term.

Introduction

Min-max optimization—finding $\min_x \max_y f(x, y)$—is the backbone of modern AI techniques like Generative Adversarial Networks (GANs) and robust machine learning. However, analyzing how fast these algorithms converge is notoriously difficult. In standard minimization, researchers use a tool called Performance Estimation Problems (PEP). PEP turns the search for an algorithm's worst-case performance into a solvable optimization problem, specifically a Semidefinite Program (SDP).

To make this work, one requires "interpolation conditions": a set of rules guaranteeing that a collection of data points (gradients and values) actually belongs to a specific class of functions. Until now, these conditions were largely missing for convex-concave functions, leaving researchers to rely on loose theoretical bounds or asymptotic estimates. This paper fills that gap, providing a computer-aided way to calculate exact worst-case convergence rates.

Methodology

The authors derive interpolation conditions for three specific function classes:

  1. Nonsmooth $M$-Lipschitz convex-concave functions: General functions where the slopes are bounded.
  2. Differences of strongly-convex functions: A structure where the function is separated into independent $x$ and $y$ components.
  3. Smooth convex-concave functions with bilinear coupling: Functions of the form $f(x) + y^T Ax - g(y)$, common in empirical risk minimization.

Once established, these conditions allow the formulation of a PEP for first-order fixed-step methods. By employing a "high-dimensional assumption," the authors simplify the mathematical constraints, allowing the problem to be solved as a standard convex SDP. This enables a computer to numerically identify the absolute worst-case function and the resulting convergence rate for a given algorithm.

Key Insights

  • The Role of Interpolation: Interpolation conditions are the essential link between infinite-dimensional function spaces and finite-dimensional computer programs. They prevent PEP solvers from "cheating" by inventing gradient values that could not exist on a real function.
  • Bilinear Coupling: By focusing on bilinear interaction (where $x$ and $y$ interact through a matrix $A$), the authors tackle a class of problems that is both practically useful and mathematically tractable enough to yield exact bounds.
  • Automated Proofs: The results demonstrate that finding convergence proofs does not always require manual derivation of Lyapunov functions. If the function class is correctly defined, SDP solvers can find these proofs automatically.

Results: Sim-GDA vs. Alt-GDA

The authors compared Simultaneous Gradient Descent-Ascent (Sim-GDA) and Alternating Gradient Descent-Ascent (Alt-GDA). Their numerical PEP results confirmed that for bilinear composite problems, Alt-GDA is significantly more efficient. It achieves an iteration complexity of $O(k)$, whereas Sim-GDA lags behind at $O(k^2)$, where $k$ is the condition number. These results match previous findings obtained through Integral Quadratic Constraints (IQC), validating the accuracy of the new PEP approach.

Limitations and Future Work

The authors have not yet derived interpolation conditions for the most general class of "smooth strongly-convex-strongly-concave" (SCSC) functions, describing their current work as "setting the stage" for this broader goal. Additionally, the current PEP formulation assumes the problem dimension is high enough ($d \ge 3N+3$). While typically true in machine learning, the bounds might not be perfectly exact for very low-dimensional problems. Future research will involve extending these conditions to general SCSC classes and leveraging the PEP framework for further algorithmic verification.

Summary updated

Abstract

In this paper we present interpolation conditions for several important convex-concave function classes: nonsmooth convex-concave functions, conditions for difference of strongly-convex functions in a form that contains oracle information exclusively and smooth convex-concave functions with a bilinear coupling term. Then we demonstrate how the performance estimation problem approach can be adapted to analyze the exact worst-case convergence behavior of first-order methods applied to composite bilinear-coupled min-max problems. Using the performance estimation problem approach, we estimate iteration complexities for several first-order fixed-step methods, Sim-GDA and Alt-GDA, which are applied to smooth convex-concave functions with a bilinear coupling term.
BibTeX
@inproceedings{krivchenko2024convex,
  author = {V. O. Krivchenko and Alexander Gasnikov and Dmitry Kovalev},
  title = {{Convex-Concave Interpolation and Application of PEP to the Bilinear-Coupled Saddle Point Problem}},
  booktitle = {Nelineinaya},
  year = {2024},
  doi = {10.20537/nd241215},
}
Figure