Search Mailing List Archives
[theory-seminar] Theory Lunch 08/26: Yujia Jin
David Wajc
wajc at stanford.edu
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 stanford.edu> wrote:
> Hi all,
>
> The last theory lunch of the summer quarter will take place Thursday at
> noon (PDT), at this zoom room
> <https://stanford.zoom.us/j/98932206471?pwd=YXdubytLVGNTbXhGeXFxNmJaVnhrUT09>. 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: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20210826/74f23ddf/attachment-0001.html>
More information about the theory-seminar
mailing list