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 03/11: Mingda Qiao

David Wajc wajc at stanford.edu
Mon Mar 8 12:24:32 PST 2021


Hi all,

This week's theory lunch will take place Thursday at noon (PDT), at our
gather space:
https://gather.town/app/lR6jRBPK44nZ7V68/StanfordTheory (*password:*
 SongComplexity).
Mingda will tell us about*:* *Stronger Calibration Lower Bounds via
Sidestepping*

*Abstract: *We consider an online binary prediction setting where a
forecaster observes a sequence of T bits one by one. Before each bit is
revealed, the forecaster predicts the probability that the bit is 1. The
forecaster is called well-calibrated if for each p in [0, 1], among the n_p
bits for which the forecaster predicts probability p, the actual number of
ones, m_p, is indeed equal to p * n_p. The calibration error, defined as
\sum_p |m_p - p n_p|, quantifies the extent to which the forecaster
deviates from being well-calibrated. It has long been known that an
O(T^{2/3}) calibration error is achievable even when the bits are chosen
adversarially, and possibly based on the previous predictions. However,
little is known on the lower bound side, except an Omega(T^{1/2}) bound
that follows from the trivial example of independent coin flips.

In this work, we prove an Omega(T^{0.528}) bound on the calibration error,
which is the first super-T^{1/2} lower bound for this setting to the best
of our knowledge. Our technical contributions include a new lower bound
technique, termed "sidestepping", which circumvents the obstacles that have
previously hindered strong calibration lower bounds. We also propose an
abstraction of the prediction setting, termed the Sign-Preservation game,
which may be of independent interest. This game has a much smaller state
space than the full prediction setting and allows simpler analyses. The
Omega(T^{0.528}) lower bound follows from a general reduction theorem that
translates lower bounds on the game value of Sign-Preservation into lower
bounds on the calibration error.

This is a joint work with Greg Valiant.



*Cheers,DavidPSPro tip: To join the talk (at 12:30):(1) go to the lecture
hall, (2) grab a seat, and (3) press X to join the zoom lecture*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20210308/24fe8831/attachment-0001.html>


More information about the theory-seminar mailing list