Variance Reduction for Matrix Games

           Yair Carmon, Yujia Jin, Aaron Sidford and Kevin Tian
                   Stanford University
           {yairc,yujiajin,sidford,kjtian}@stanford.edu

                       Abstract
     We present a randomized primal-dual algorithm thatpsolves the problem
     minx maxy y > Ax to additive error  in time nnz(A) + nnz(A)n/, for ma-
     trix A with larger dimension n and nnz(A) nonzero
                            p entries. This improves the best
  ...