Variance Reduction for Matrix Games.

Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian

Abstract

We present a randomized primal-dual algorithm that solves the problem $\min_x \max_y y^T A x$ to additive error $\epsilon$ in time $\text{nnz}(A) + \frac{\sqrt{\text{nnz}(A) n}}{\epsilon}$, for a matrix $A$ with larger dimension $n$ and $\text{nnz}(A)$ nonzero entries. This improves the best known exact gradient methods by a factor of $\sqrt{\text{nnz}(A) / n}$ and is faster than fully stochastic gradient methods in the accurate and/or sparse regime $\epsilon < \sqrt{n / \text{nnz}(A)}$. Our results hold for $x, y$ in the simplex (matrix games, linear programming) and for $x$ in an $\ell_2$ ball and $y$ in the simplex (perceptron / SVM, minimum enclosing ball). Our algorithm combines Nemirovski's "conceptual prox-method" and a novel reduced-variance gradient estimator based on "sampling from the difference" between the current iterate and a reference point.

Introduction

Bilinear minimax games, formulated as $\min_x \max_y y^\top Ax$, are fundamental to game theory, economics, and machine learning. Finding Nash equilibria in matrix games or training Support Vector Machines (SVMs) often boils down to solving these saddle-point problems. Historically, optimization strategies for these games have been divided into two regimes:

  1. Exact Gradient Methods: These methods, such as Mirror-Prox, are highly accurate but computationally expensive per iteration because they must process the entire matrix $A$.
  2. Stochastic Gradient Methods: These are computationally cheap per step but suffer from high variance, requiring a large number of iterations to reach high-precision solutions.

This paper introduces a randomized algorithm that bridges this gap, providing a "best of both worlds" approach that is both efficient per iteration and stable enough for fast convergence.

The Algorithmic Framework

The proposed solution utilizes a two-level nested algorithmic structure designed to minimize variance while maintaining low computational overhead.

Outer Loop: Conceptual Prox-Method

The algorithm is built upon Nemirovski’s "conceptual prox-method." This framework decomposes the primary minimax problem into a sequence of more manageable subproblems. By solving these subproblems iteratively, the algorithm maintains the stability of a proximal method while allowing for stochastic approximations within the subproblems themselves.

Inner Loop: Variance-Reduced Mirror Descent

To solve the subproblems generated by the outer loop, the authors employ Stochastic Mirror Descent. The core innovation lies in the gradient estimator used: "sampling from the difference."

Traditional variance reduction techniques (like SVRG) typically use fixed probability distributions to sample coordinates. In this work, the authors sample coordinates of the matrix $A$ based on the difference between the current iterate and a fixed reference point. This ensures that the estimator satisfies a "centered" criterion: as the iterates approach the reference point, the variance of the estimate decreases. This property allows the algorithm to use larger step sizes than standard stochastic methods, leading to significantly faster convergence.

For $\ell_2-\ell_1$ games, the authors further refine this approach by incorporating gradient clipping, which manages the trade-off between bias and variance in the stochastic estimates.

Theoretical Results

The paper establishes new state-of-the-art theoretical runtimes for two major classes of minimax problems:

  • $\ell_1-\ell_1$ Games (Matrix Games): The algorithm finds an $\epsilon$-approximate solution in $O\left(\text{nnz}(A) + \frac{\sqrt{\text{nnz}(A)n} \|A\|_{\max}}{\epsilon}\right)$ time. For a dense $n \times n$ matrix, this represents a $\sqrt{n}$ speedup over traditional exact gradient methods.
  • $\ell_2-\ell_1$ Games (SVMs/Minimum Enclosing Ball): The algorithm achieves a similar accelerated rate, substituting the maximum entry norm with a row-wise $\ell_2$ norm.

These results demonstrate that the algorithm is particularly effective in the high-precision regime (small $\epsilon$) and when dealing with sparse matrices, where it outperforms fully stochastic methods.

Discussion and Limitations

While this work provides a significant theoretical advancement, it focuses primarily on bilinear objectives. Although the authors provide an extension for general convex-concave functions, it introduces a logarithmic overhead. Furthermore, as a theoretical contribution, the paper does not evaluate practical constants or performance on hardware accelerators like GPUs, where the overhead of adaptive sampling might impact real-world speedups.

Future research may explore extending these variance reduction principles to the non-linear minimax problems common in deep learning, such as those found in Generative Adversarial Networks (GANs).

Summary updated

Abstract

We present a randomized primal-dual algorithm that solves the problem min<em>x max</em>y y^T A x to additive error epsilon in time nnz(A) + sqrt{nnz(A) n} / epsilon, for matrix A with larger dimension n and nnz(A) nonzero entries. This improves the best known exact gradient methods by a factor of sqrt{nnz(A) / n} and is faster than fully stochastic gradient methods in the accurate and/or sparse regime epsilon &lt; sqrt{n / nnz(A)$. Our results hold for x,y in the simplex (matrix games, linear programming) and for x in an \ell_2 ball and y in the simplex (perceptron / SVM, minimum enclosing ball). Our algorithm combines the Nemirovski's "conceptual prox-method" and a novel reduced-variance gradient estimator based on "sampling from the difference" between the current iterate and a reference point.
BibTeX
@inproceedings{carmon2019variance,
  author = {Yair Carmon and Yujia Jin and Aaron Sidford and Kevin Tian},
  title = {{Variance Reduction for Matrix Games.}},
  booktitle = {NeurIPS},
  year = {2019},
  url = {https://openreview.net/forum?id=mlRJx0-vL6D1},
}
Figure