Search Mailing List Archives
[theory-seminar] Theory Lunch 08/26: Yujia Jin
David Wajc
wajc at stanford.edu
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
<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/20210823/1424b774/attachment-0001.html>
More information about the theory-seminar
mailing list