
Beyond Worst-Case Analysis in Online Learning
Tim Roughgarden, speaking at the Institute for Advanced Study's Members' Colloquium, argues that worst-case analysis, long treated as the gold standard for evaluating algorithms, often fails to give useful guidance for problems like clustering, linear programming, and neural network training. He surveys the beyond-worst-case-analysis research program before turning to a specific result in online learning: while worst-case online learnability is governed by the Littlestone dimension (infinite even for simple one-dimensional threshold functions), introducing a smoothed adversary that perturbs inputs randomly shifts the relevant measure to VC dimension, which is just 1 for that same example. Roughgarden also touches on how these proof techniques extend to an online version of the Komlos discrepancy problem. The talk moves from broad framing to technical detail, aimed at an audience familiar with learning theory and algorithm analysis.