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
Thu Aug 26 11:56:16 PDT 2021

Gentle reminder: last theory lunch of the quarter starting in a few minutes!

On Mon, 23 Aug 2021 at 13:12, David Wajc <wajc at> wrote:

> Hi all,
> The last theory lunch of the summer quarter will take place Thursday at
> noon (PDT), at this zoom room
> <>. As
> usual, we'll start with some socializing, followed by a talk starting at
> 12:30pm.
> 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
> O(1/\epsilon)-smooth.
> 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.
> Cheers,
> David
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list