## 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
Thu Mar 11 12:28:13 PST 2021

Reminder: talk starts in a few minutes.

Cheers,
David

On Thu, 11 Mar 2021 at 10:00, David Wajc <wajc at stanford.edu> wrote:

> Reminder: this is happening in two hours. Come hang out with PhD admits
> and then hear a talk by Mingda.
>
> See you there,
> David
>
> On Wed, 10 Mar 2021 at 15:16, Moses Charikar <moses at cs.stanford.edu>
> 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 stanford.edu> wrote:
>>
>>> Hi all,
>>>
>>> This week's theory lunch will take place Thursday at noon (PDT), at our
>>> gather space:
>>>  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 lists.stanford.edu
>>> https://mailman.stanford.edu/mailman/listinfo/theory-seminar
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20210311/53493e09/attachment-0003.html>