Beyond Worst-Case Analysis in Online Learning

One of the primary goals of the mathematical analysis of algorithms is to provide guidance about which algorithm is the “best” for solving a given computational problem. Worst-case analysis summarizes the performance profile of an algorithm by its worst performance on any input of a given size, implicitly advocating for the algorithm with the best-possible worst-case performance. Strong worst-case guarantees are the holy grail of algorithm design, providing an application-agnostic certification of an algorithm’s robustly good performance.

However, for many fundamental problems and performance measures, such guarantees are impossible and a more nuanced analysis approach is called for. Research in "beyond worst-case analysis" develops alternatives to worst-case analysis, with applications ranging from clustering to linear programming to neural network training. The first part of this talk will provide a general introduction to the area. The second part of this talk will describe an application to a fundamental problem in learning theory: regret-minimization in online learning. Worst-case online learnability has long been known to be characterized by the Littlestone dimension of the class of allowable hypotheses (which, for example, is infinite already for the class of one-dimensional threshold functions). Our main result here shows that this characterization is brittle in the sense that, with a "smoothed" adversary (with adversarially chosen inputs subjected to small random perturbations), online learnability is instead characterized by the VC dimension of the hypothesis class (which, for the same example, is 1). Time permitting, we will also discuss applications of our proof techniques to an online version of the Komlos problem in discrepancy theory.

Includes joint work with Nika Haghtalab (UC Berkeley) and Abhishek Shetty (MIT), published in Journal of the ACM (2024).