Abstract
We present a randomized primal-dual algorithm that solves the bilinear minimax problem $\min_{x} \max_{y} y^\top A x$ to additive error $\epsilon$ in time $\mathrm{nnz}(A) + \sqrt{\mathrm{nnz}(A)n}/\epsilon$, where $n$ is the larger dimension and $\mathrm{nnz}(A)$ is the number of nonzero entries in matrix $A$. This complexity improves upon the best known exact gradient methods by a factor of $\sqrt{\mathrm{nnz}(A)/n}$ and outperforms fully stochastic gradient methods in high-accuracy or sparse-matrix regimes (where $\epsilon \le \sqrt{n/\mathrm{nnz}(A)}$). Our algorithm, which applies to matrix games, linear programming, and SVMs, combines Nemirovski's "conceptual prox-method" with a novel gradient estimator based on "sampling from the difference" between the current iterate and a reference point.
Introduction
Minimax problems—often framed as games where one player seeks to minimize a value while another seeks to maximize it—are foundational to economics, game theory, and modern machine learning applications such as Generative Adversarial Networks (GANs) and robust optimization. The most fundamental version of this is the matrix game: $\min_x \max_y y^\top Ax$.
Historically, optimization researchers have relied on two distinct approaches to solve these problems:
- Deterministic "Linear-time" Methods: Algorithms like Mirror-Prox examine the entire matrix $A$ in every iteration. While they converge quickly in terms of accuracy ($1/\epsilon$), they are computationally expensive per iteration because they must touch every non-zero entry in the matrix.
- Stochastic "Sublinear-time" Methods: These methods sample small portions of the matrix. They are computationally cheap per iteration but converge slowly ($1/\epsilon^2$), making them impractical for high-precision solutions.
This research bridges the gap by introducing a variance-reduced algorithm for minimax problems that combines the low per-iteration cost of stochastic methods with the fast $1/\epsilon$ convergence of deterministic ones.
Methodology
The proposed algorithm achieves this speedup through two primary components:
Nemirovski’s Conceptual Prox-Method
This serves as the outer loop of the algorithm. It decomposes the primary minimax problem into a sequence of regularized subproblems. By solving these subproblems to sufficient accuracy, the algorithm maintains the fast $1/\epsilon$ convergence rate characteristic of proximal methods.
"Sampling from the Difference"
The core innovation lies in the gradient estimator used to solve the proximal subproblems. In standard variance reduction (like SVRG), sampling distributions are typically fixed. In this work, the authors design a gradient estimator where sampling probabilities evolve dynamically. By sampling coordinates based on the difference between the current iterate and a reference point, the algorithm ensures that the "noise" (variance) of the stochastic samples decreases as the algorithm approaches the solution.
This approach is specifically tailored for different geometries, including $\ell_1-\ell_1$ (matrix games and linear programming), $\ell_2-\ell_1$ (Perceptron and SVMs), and $\ell_2-\ell_2$ (linear regression-related games).
Key Insights
- Dynamic Sampling: Unlike standard minimization, where fixed-distribution sampling is often sufficient, minimax problems require the sampling distribution to evolve with the iterates to keep variance under control.
- The Centered Criterion: The authors define a "centered" gradient estimator where the variance is bounded by the distance to a reference point. They prove that any estimator meeting this criterion can be integrated into their framework to solve proximal subproblems efficiently.
- Computational Balance: The algorithm balances expensive "full" gradient computations (used to reset the reference point) with many "cheap" stochastic steps. This balance allows the total runtime to be sublinear in the number of non-zeros while maintaining a $1/\epsilon$ dependence.
Results and Complexity
The headline result is a new runtime complexity for an $n \times n$ matrix game: $$\tilde{O}\left(\text{nnz}(A) + \frac{\sqrt{\text{nnz}(A) \cdot n}}{\epsilon}\right)$$
This complexity offers several advantages:
- The $\sqrt{n}$ Speedup: For dense matrices where $\text{nnz}(A) \approx n^2$, the runtime becomes $\tilde{O}(n^{1.5}/\epsilon)$, a $\sqrt{n}$ improvement over the classical $O(n^2/\epsilon)$ rate.
- Sparse Matrix Efficiency: The method is strictly faster than previous exact gradient methods whenever the matrix $A$ is not extremely sparse (specifically, when $\text{nnz}(A) = \omega(n)$).
- High-Precision Performance: Because the complexity scales with $1/\epsilon$ rather than $1/\epsilon^2$, this method is significantly faster than fully stochastic methods when high precision is required.
Limitations and Future Work
While this represents a theoretical breakthrough, certain limitations remain. The most dramatic gains are currently restricted to bilinear (matrix) games; extending these speedups to general smooth convex-concave functions is an ongoing challenge. Additionally, for $\ell_2-\ell_2$ cases, the improvement over Mirror-Prox is only significant if the matrix has a high "spectral rank." Finally, the practical overhead of recomputing sampling distributions in every inner iteration may impact performance on smaller-scale problems, suggesting a need for more hardware-friendly implementations in the future.
Summary updated