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 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