Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss

We characterize the complexity of minimizing the maximum of 𝑁 convex, Lipschitz functions. For non-smooth functions, existing methods require O(𝑁𝜖⁻²) queries to a first-order oracle to compute an 𝜖-suboptimal point and O(𝑁𝜖⁻¹) queries if the functions are O(𝜖⁻¹)-smooth. We develop methods with improved complexity bounds O(𝑁𝜖⁻²/³ + 𝜖⁻⁸/³) in the non-smooth case and O(𝑁𝜖⁻²/³ + √𝑁𝜖⁻¹) in the O(𝜖⁻¹)-smooth case. Our methods consist of a recently proposed ball optimization oracle acceleration algorithm (which we refine), combined with careful implementation of said oracle for the softmax function. We also prove an oracle complexity lower bound scaling as 𝛺(𝑁𝜖⁻²/³), showing that our dependence on 𝑁 is optimal up to polylogarithmic factors.