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
Thu Mar 11 10:00:06 PST 2021

Reminder: this is happening in two hours. Come hang out with PhD admits and
then hear a talk by Mingda.

See you there,

On Wed, 10 Mar 2021 at 15:16, Moses Charikar <moses at> wrote:

> 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.
> Best,
> Moses
> 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