Boosting: weak learners made strong

Michael Kearns and Leslie Valiant had asked, in the framework of computational learning theory, whether a rule that is only slightly better than guessing could be turned into one that is very good. Robert Schapire's 1990 paper answered yes, constructively: train a weak learner, train another on the examples the first gets wrong, train a third on the disagreements, and combine them. Repeating the trick drives the error down as far as you like. Yoav Freund and Schapire's AdaBoost of 1995 made the procedure practical, reweighting the data rather than resampling it, and the two shared the Gödel Prize for it in 2003.

Boosting was the most successful learning method of the 1990s that was not a neural network. It made weak, cheap models, usually shallow decision trees, into strong ones, and it came with a theory that explained why it rarely overfit. Viola and Jones's boosted face detector of 2001 put it in every digital camera.

Gradient boosting, its extension by Jerome Friedman in 2001, became XGBoost and LightGBM, which won most structured-data competitions of the 2010s and still run a large part of the world's fraud detection, credit scoring and advertising.