Search Mailing List Archives
[theory-seminar] Theory Lunch 08/12: Mingda Qiao
wajc at stanford.edu
Mon Aug 9 10:08:41 PDT 2021
This week's theory lunch will take place Thursday at noon (PDT), at this
usual, we'll start with some socializing, followed by a talk starting at
12:30pm. Pras will be MCing. Thanks Pras!
Mingda will tell us about: *Exponential Weights Algorithms for Selective
*Abstract:* We study the selective learning problem, in which a learner
observes $n$ labeled data points one at a time. At a time of its choosing,
the learner picks a window length $w$ and a hypothesis $h$ from a given
hypothesis class $H$, and then labels the next $w$ data points using $h$.
The excess risk incurred by the learner is defined as the difference
between the average loss of $h$ over the $w$ data points and the smallest
possible average loss among all hypotheses in $H$ over those data points.
We give an improved algorithm, termed the hybrid exponential weights
algorithm, that achieves an expected excess risk of $O((\log\log|H| +
\log\log n)/\log n)$. This gives a doubly exponential improvement in the
dependence on $|H|$ over the best known upper bound. We also prove an
almost matching lower bound, showing that the $\log\log|H|$ dependence is
Based on joint work with Greg Valiant.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the theory-seminar