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

We design algorithms for minimizing max i∈[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 ϵ-approximate solution using O(nϵ -1/3 + ϵ -2 ) gradient and function evaluations, and O(nϵ -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 ϵ-approximate solution in runtime O(n(d/ϵ) 2/3 + nd + dϵ -2 ). For n > d and ϵ = 1/ √ n this improves over all existing first-order methods. When additionally d = ω(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 ℓ 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.