classification
Learn from the stream, one at a time
It is the era before data sits still in a file: examples arrive one at a time, forever, and you must predict each label before its truth is revealed, then update. There is no training set and no test set — only the endless stream, and an adversary may order it to hurt you. Design an online classifier and bound not its accuracy on some fixed distribution but its total number of mistakes, relative to the best fixed predictor in hindsight. The guarantee must hold against worst-case orderings. Get it wrong and a system that looked fine in batch testing bleeds errors in deployment as the world drifts — the point of online learning is a promise that survives an adversary choosing your data's order.
Who this problem belongs to
The two figures whose methods fit it best, out of 71 in contention.
Bottou's career is built directly on this problem: his work on stochastic gradient descent at scale, from the 1990s through the 2010s, formalized exactly how to update a model one example at a time without ever seeing a fixed training set, and his analysis of large-scale learning explicitly frames online, streaming updates as the practical regime real systems operate in. His research explicitly engages with the tradeoff between statistical efficiency and computational efficiency in the online setting, and his later work on the tradeoffs of large-scale learning under streaming data addresses precisely how a system should behave when examples arrive endlessly and the world may drift. Few careers map onto this problem's exact framing as directly as his does.
Rosenblatt's 1958 perceptron is the direct historical ancestor of this problem's entire framing: it is an inherently online algorithm, updating its weights by a single error-correcting rule immediately after each example, with no notion of a fixed training set at all, predicting a label then updating on the truth exactly as this problem describes. The perceptron convergence theorem, later refined, is among the first mistake-bound guarantees in the field's history, bounding the total number of errors before convergence when data is linearly separable. He predates the adversarial, worst-case-ordering framing this problem specifically demands, and had no notion of bounding regret against the best fixed predictor in hindsight, keeping him below the researchers who later formalized these guarantees rigorously.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
71 figures are scored on this problem. Draw it in a battle to see where you land.