Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 08/26: Yujia Jin

David Wajc wajc at
Mon Aug 23 13:12:20 PDT 2021

Hi all,

The last theory lunch of the summer quarter will take place Thursday at
noon (PDT), at this zoom room
usual, we'll start with some socializing, followed by a talk starting at
Yujia will tell us about: *Thinking Inside the Ball: Near-Optimal
Minimization of the Maximal Loss*

*Abstract:* In this work, we characterize the complexity of minimizing the
maximal of N functions for convex, Lipschitz functions f_1,… , f_N.  For
non-smooth functions, existing methods require O(N*\epsilon^{-2}) queries
to a first-order oracle  to compute an \epsilon-suboptimal point and
\Otil{N*\epsilon^{-1}} queries if the functions f_i are

We develop methods with improved complexity bounds of
\Otil{N*\epsilon^{-2/3} + \epsilon^{-8/3}} in the non-smooth case and
\Otil{N*\epsilon^{-2/3} + \sqrt{N}*\epsilon^{-1}} in the
O(1/\epsilon)-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 \Omega(N*\epsilon^{-2/3}), showing
that our dependence on N is optimal up to polylogarithmic factors.

This talk is based on joint work with Yair Carmon, Arun Jambulapati, and
Aaron Sidford.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list