Thinking Inside the Ball: Near-Optimal Minimization of the Maximal Loss
This work addresses optimization efficiency for machine learning and operations research problems involving max-loss objectives, representing a strong specific gain rather than a broad paradigm shift.
The paper tackles the problem of minimizing the maximal loss for convex, Lipschitz functions, achieving improved complexity bounds of ϕ(Nε^{-2/3} + ε^{-8/3}) for non-smooth cases and ϕ(Nε^{-2/3} + √Nε^{-1}) for smooth cases, with a lower bound showing optimal dependence on N up to polylog factors.
We characterize the complexity of minimizing $\max_{i\in[N]} f_i(x)$ for convex, Lipschitz functions $f_1,\ldots, f_N$. For non-smooth functions, existing methods require $O(Nε^{-2})$ queries to a first-order oracle to compute an $ε$-suboptimal point and $\tilde{O}(Nε^{-1})$ queries if the $f_i$ are $O(1/ε)$-smooth. We develop methods with improved complexity bounds of $\tilde{O}(Nε^{-2/3} + ε^{-8/3})$ in the non-smooth case and $\tilde{O}(Nε^{-2/3} + \sqrt{N}ε^{-1})$ in the $O(1/ε)$-smooth case. Our methods consist of a recently proposed ball optimization oracle acceleration algorithm (which we refine) and a careful implementation of said oracle for the softmax function. We also prove an oracle complexity lower bound scaling as $Ω(Nε^{-2/3})$, showing that our dependence on $N$ is optimal up to polylogarithmic factors.