CSE Colloquium: Sequential Prediction—Calibration and Selectivity


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:





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


Share this event

facebook linked in twitter email

Media Contact: Erin Ammerman



The School of Electrical Engineering and Computer Science was created in the spring of 2015 to allow greater access to courses offered by both departments for undergraduate and graduate students in exciting collaborative research fields.

We offer B.S. degrees in electrical engineering, computer science, computer engineering and data science and graduate degrees (master's degrees and Ph.D.'s) in electrical engineering and computer science and engineering. EECS focuses on the convergence of technologies and disciplines to meet today’s industrial demands.

School of Electrical Engineering and Computer Science

The Pennsylvania State University

207 Electrical Engineering West

University Park, PA 16802


Department of Computer Science and Engineering


Department of Electrical Engineering