LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Beyond Worst-Case Analysis in Online Learning
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Beyond Worst-Case Analysis in Online Learning

69 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

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.

At a glance

Lecture facts

Runtime compared with the other 507 Mathematics lectures
Runtime1 h 9 m
Compared with MathematicsShorter than 58%
Source channelInstitute for Advanced Study (YouTube)