A Whole New Ball Game: A Primal Accelerated Method for Matrix Games and Minimizing the Maximum of Smooth Functions

We design algorithms for minimizing maxi∈[n] fi(x) over a d-dimensional Euclidean or simplex domain. When each fi is 1-Lipschitz and 1-smooth, our method computes an ε-approximate solution using widetildeO(n ε-1/3 + ε-2) gradient and function evaluations, and widetildeO(n ε-4/3) additional runtime. For large n, our evaluation complexity is optimal up to polylogarithmic factors. In the special case where each fi is linear -- which corresponds to finding a near-optimal primal strategy in a matrix game -- our method finds an ε-approximate solution in runtime widetildeO(n (d/ε)2/3 + nd + dε-2). For n>d and ε=1/√n this improves over all existing first-order methods. When additionally d = ω(n8/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 ℓ2 or ℓ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.