Title: Bagging provides assumption-free stability
Abstract: Distribution-free uncertainty quantification yields principled statistical tools which input black-box machine learning models and produce predictions with statistical guarantees, such as distribution-free prediction or calibration. In this work, we add algorithmic stabilization to the list of possible distribution-free guarantees. We derive a finite-sample guarantee on the stability of bagging for any model with bounded outputs. Our result places no assumptions on the distribution of the data, on the regularity of the base algorithm, or on the dimensionality of the covariates. Our guarantee applies to many variants of bagging and is optimal up to a constant. This is joint work with Rina Foygel Barber and Rebecca Willett.