Algorithmic stability via ensembling
Abstract
Algorithmic stability refers to the property of an algorithm being insensitive to perturbations of the input data, where the type of perturbation may vary depending on the setting. In this work, we develop a general framework to quantify the extent to which any ensembling strategy defined via averaging can yield stability guarantees for any type of data perturbation. Our main theoretical result is a guarantee on the stability of this ensembled algorithm, given in terms of the norm of a certain covariance operator that describes the ensembling process. We show how our general framework yields interpretable and intuitive insights in several examples of perturbations of practical interest, and provides much sharper guarantees than those obtained from privacy considerations.
Related
- The cost of ensembling: Is it always worth combining global retail forecasting models?
- Two Sample Sizes in Test-Time LLM Ensembling: Buffered ERM and Minimax Theory
- Statistical-Algorithmic Phase Transitions in Stochastic L2-Boosting
- Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
- Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
BibTeX
@misc{barber2026algorithmic,
title = {{Algorithmic stability via ensembling}},
author = {Rina Foygel Barber and Richard J. Samworth},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.10428},
eprint = {2609.10428},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.10428},
}
RIS
TY - UNPB
TI - Algorithmic stability via ensembling
AU - Rina Foygel Barber
AU - Richard J. Samworth
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2609.10428
UR - https://arxiv.org/abs/2609.10428
AB - Algorithmic stability refers to the property of an algorithm being insensitive to perturbations of the input data, where the type of perturbation may vary depending on the setting. In this work, we develop a general framework to quantify the extent to which any ensembling strategy defined via averaging can yield stability guarantees for any type of data perturbation. Our main theoretical result is a guarantee on the stability of this ensembled algorithm, given in terms of the norm of a certain covariance operator that describes the ensembling process. We show how our general framework yields interpretable and intuitive insights in several examples of perturbations of practical interest, and provides much sharper guarantees than those obtained from privacy considerations.
ER -