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

Moses Charikar moses at
Wed Mar 10 15:15:55 PST 2021

Hi folks,

Just wanted to add that we will have some of our PhD admits joining us at
theory lunch tomorrow, so do make an extra effort to show up on time and
talk to them.


On Mon, Mar 8, 2021 at 12:25 PM David Wajc <wajc at> wrote:

> Hi all,
> This week's theory lunch will take place Thursday at noon (PDT), at our
> gather space:
> (*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*
> _______________________________________________
> theory-seminar mailing list
> theory-seminar at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list