Greg Valiant: Sequential Prediction: Calibration and Selective Prediction

ABSTRACT: I'll discuss two problems in online prediction.  In the first part of the talk, I'll discuss 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 "well-calibrated" if, for each predicted value p, among the timesteps when probability p was predicted, a p-fraction of those bits were 1.  The calibration error 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.  I'll present the first improvement over the trivial O(sqrt(T)) lower bound.    In the second part of the talk,  I'll discuss the "selective learning" problem in which the forecaster observes a sequence of labeled data points one at a time. At a time of its choosing, the forecaster selects a window length w and a model l from the model class L, and then labels the next w data points using l.  Surprisingly, we will show that the forecaster can compete with the model in L that performs best on the selected data window.   

This talk is based on joint work with Mingda Qiao.