The paper gives an algorithm for solving minimax matrix games faster, that improve on existing methods in high accuracy/sparse regimes. The new approach is based on an extension of Nemirovsky's mirror-prox algorithm with a novel variance-reduced approximate gradient estimator, which the reviewers found to be significant and of independent interest. The paper contains strong contributions and techniques, and given the high praise of the reviewers, it is a clear accept.