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

Yair Carmon , Arun Jambulapati , Yujia Jin , Aaron Sidford

[Proceedings link] [PDF]

Session: Optimization(A)

Session Chair: Simon Du

Poster: Poster Session 1

Abstract: 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 ร•(๐‘๐œ–โปยน) queries if the functions are O(๐œ–โปยน)-smooth. We develop methods with improved complexity bounds ร•(๐‘๐œ–โปยฒ/ยณ + ๐œ–โปโธ/ยณ) in the non-smooth case and ร•(๐‘๐œ–โปยฒ/ยณ + โˆš๐‘๐œ–โปยน) 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.

Summary presentation

Full presentation