Smooth boosting for low VC dimensional classes and a fable about out-of-distribution learning
Russell Impagliazzo (UCSD)
Monday, April 21th 2025, 2-3pm
Abstract:
One mystery of machine learning is that training for one domain is often also useful as a preprocessing step for other domains. In this work, we will give a simple case when this out-of-distribution learning is provable, in boosting and multi-calibration using concepts from a small VC-dimension class. Building on work by Alon, Gonen, Hazan, and Moran, we first show an analysis of smooth (in the sense of Servedio) boosting algorithms for weak learners returning concepts from a small VC dimension class. In particular, for some choices of parameters, the round complexity of these algorithms will beat known lower bounds for general boosting algorithms.
Then we'll show that this round complexity applies in the continual learning setting, where we are solving a sequence of classification problems. If the data distribution is identical, the round complexity of an arbitrary sequence is the same as for a single classification problem. If the data distributions are overlapping but not identical, there is a quantitative tradeoff between overlap and joint round complexity. We give a reduction from multi-calibration to boosting that yields similar results for multi-calibration and output indistinguishability.
Work in progress which is joint with Maya Josyula, Yasaman Mahdaviyeh and Toni Pitassi.