Variance Reduction for Matrix Games

This improves the best known exact gradient methods by a factor of p nnz(A)/n and is faster than fully stochastic gradient methods in the accurate and/or sparse regime apple p n/nnz(A).