CSE Colloquium: Sequential Prediction—Calibration and Selectivity

Abstract

This talk will discuss new perspectives and results on sequential prediction/learning under minimal assumptions on the data. In the first part, I will discuss a model of online binary prediction in which a forecaster observes a sequence of T bits one by one and, before each bit is revealed, predicts the "probability" that the bit is 1. The forecaster is "well-calibrated" if, for each 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, whereas there is a trivial lower bound of Omega(T^{1/2}). I will present the first improvement over this T^{1/2} rate in the lower bound.

The second part of the talk will cover new models of "selective prediction/learning": The forecaster observes a data sequence one at a time. At any time of its choosing, the forecaster may select a window length w and make a prediction about the next w unseen data points. Surprisingly, we will show that the forecaster can obtain non-trivial prediction and learning guarantees even if the data are arbitrary.

This talk is based on joint work with Gregory Valiant.

Paper links:

arxiv.org/abs/2012.03454

arxiv.org/abs/1902.04256

arxiv.org/abs/2106.15662

Biography

Mingda Qiao a fifth-year Ph.D. student in Computer Science at Stanford University, advised by Gregory Valiant. He works on the theoretical foundations of machine learning and artificial intelligence. His doctoral research focuses on the theoretical aspects of prediction, learning, and decision-making in sequential settings, as well as decision tree learning. With his collaborators, his contributions include the first non-trivial lower bound for sequential calibration, and a faster algorithm for properly learning decision trees. Prior to Stanford, Mingda received his BEng in Computer Science from Yao Class at Tsinghua University in 2018.

Faculty Host: Antonio Blanca
Research Area: Theory