Stochastic No-regret Learning for General Games with Variance Reduction

We present a randomized primal-dual algorithm that solves the problem min x max y y Ax to additive error in time nnz(A) + nnz(A)n/ , for matrix A with larger dimension n and nnz(A) nonzero entries. This improves the best known exact gradient methods by a factor of nnz(A)/n and is faster than fully stochastic gradient methods in the accurate and/or sparse regime ≤ n/nnz(A). Our results hold for x, y in the simplex (matrix games, linear programming) and for x in an 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.