Variance Reduction for Matrix Games
This work addresses computational efficiency for matrix games and related problems like linear programming and SVM, offering incremental improvements in runtime for sparse or accurate settings.
The paper tackles the problem of solving matrix games to additive error ε with a randomized primal-dual algorithm, achieving a time complexity of nnz(A) + √(nnz(A)n)/ε, which improves exact gradient methods by a factor of √(nnz(A)/n) and outperforms stochastic methods in certain regimes.
We present a randomized primal-dual algorithm that solves the problem $\min_{x} \max_{y} y^\top A x$ to additive error $ε$ in time $\mathrm{nnz}(A) + \sqrt{\mathrm{nnz}(A)n}/ε$, 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 $ε\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.