Variance Reduction for Matrix Games

By Yair Carmon, Yujia Jin, Aaron Sidford, Kevin Tian. 2019

81 citations recorded by the source corpus.

We present a randomized primal-dual algorithm that solves the problem $\min_{x} \max_{y} y^\top A x$ to additive error $\epsilon$ in time $\mathrm{nnz}(A) + \sqrt{\mathrm{nnz}(A)n}/\epsilon$, for matrix $A$ with larger dimension $n$ and $\mathrm{nnz}(A)$ nonzero entries. This improves the best known exact gradient methods by a factor of $\sqrt{\mathrm{nnz}(A)/n}$ and is faster than fully stochastic gradient methods in the accurate and/or sparse regime $\epsilon \le \sqrt{n/\mathrm{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.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

In Game & Decision Theory

Citations in the corpus

Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, methodology): “In another line of work, Carmon et al. (2019) analyze variance reduction methods for constrained ﬁnite-sum problems and Ryu et al. (2019) provide an ODE-based analysis and guarantees in the monotone but potentially non-smooth case.”
Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss (2019, methodology): “Distributionally robust optimization (DRO) is another technique for domain adaptation (see [11, 16, 8] and the reference therein.”