A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and
  Minimizing the Maximum of Smooth Functions
Yair Carmon Arun Jambulapati Yujia Jin Aaron Sidford
We design algorithms for minimizing $\max_{i\in[n]} f_i(x)$ over a
$d$-dimensional Euclidean or simplex domain. When each $f_i$ is $1$-Lipschitz
and $1$-smooth, our method computes an $\epsilon$-approximate solution using
$\widetilde{O}(n \epsilon^{-1/3} + \epsilon^{-2})$ gradient and function
evaluations, and $\widetilde{O}(n \epsilon^{-4/3})$ additional runtime. For
large $n$, our evaluation complexity is optimal up to polylogarithmic factors.
In the special case where each $f_i$ is linear -- which corresponds to finding
a near-optimal primal strategy in a matrix game -- our method finds an
$\epsilon$-approximate solution in runtime $\widetilde{O}(n (d/\epsilon)^{2/3}
+ nd + d\epsilon^{-2})$. For $n>d$ and $\epsilon=1/\sqrt{n}$ this improves over
all existing first-order methods. When additionally $d = \omega(n^{8/11})$ our
runtime also improves over all known interior point methods.
  Our algorithm combines three novel primitives: (1) A dynamic data structure
which enables efficient stochastic gradient estimation in small $\ell_2$ or
$\ell_1$ balls. (2) A mirror descent algorithm tailored to our data structure
implementing an oracle which minimizes the objective over these balls. (3) A
simple ball oracle acceleration framework suitable for non-Euclidean geometry.