# Black-box tests for algorithmic stability

arXiv: https://arxiv.org/abs/2111.15546 · HTML: https://mlsanity.com/paper/2111.15546/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 22 references that are in the map.
- First posted on arXiv 30 Nov 2021.

## Builds on (most cited first, 3 of 3)

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Predictive inference with the jackknife+](https://mlsanity.com/paper/1905.02928/) (2019)
- [Toward Better Generalization Bounds with Locally Elastic Stability](https://mlsanity.com/paper/2010.13988/) (2020)

## Built on by (most cited first, 15 of 15)

- [Bagging Provides Assumption-free Stability](https://mlsanity.com/paper/2301.12600/) (2023)
- [Conformal Risk Control for Non-Monotonic Losses](https://mlsanity.com/paper/2602.20151/) (2026)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [Distribution-Free Matrix Prediction Under Arbitrary Missing Pattern](https://mlsanity.com/paper/2305.11640/) (2023)
- [On the Relationship Between Interpretability and Explainability in Machine Learning](https://mlsanity.com/paper/2311.11491/) (2023)
- [The Limits of Assumption-free Tests for Algorithm Performance](https://mlsanity.com/paper/2402.07388/) (2024)
- [iLOCO: Distribution-Free Inference for Feature Interactions](https://mlsanity.com/paper/2502.06661/) (2025)
- [Gaussian and Non-Gaussian Universality of Data Augmentation](https://mlsanity.com/paper/2202.09134/) (2022)
- [Are all models wrong? Fundamental limits in distribution-free empirical model falsification](https://mlsanity.com/paper/2502.06765/) (2025)
- [Observational Multiplicity](https://mlsanity.com/paper/2507.23136/) (2025)
- [Stability of a Generalized Debiased Lasso with Applications to Resampling-Based Variable Selection](https://mlsanity.com/paper/2405.03063/) (2024)
- [Is Algorithmic Stability Testable? A Unified Framework under Computational Constraints](https://mlsanity.com/paper/2405.15107/) (2024)
- [Resampling Sensitivity of High-Dimensional PCA](https://mlsanity.com/paper/2212.14531/) (2022)
- [A fast algorithm for solving the lasso problem exactly without homotopy using differential inclusions](https://mlsanity.com/paper/2507.05562/) (2025)
- [Algorithmic stability via ensembling](https://mlsanity.com/paper/2609.10428/) (2026)

## Abstract (arXiv)

Algorithmic stability is a concept from learning theory that expresses the degree to which changes to the input data (e.g., removal of a single data point) may affect the outputs of a regression algorithm. Knowing an algorithm's stability properties is often useful for many downstream applications -- for example, stability is known to lead to desirable generalization properties and predictive inference guarantees. However, many modern algorithms currently used in practice are too complex for a theoretical analysis of their stability properties, and thus we can only attempt to establish these properties through an empirical exploration of the algorithm's behavior on various data sets. In this work, we lay out a formal statistical framework for this kind of "black-box testing" without any assumptions on the algorithm or the data distribution and establish fundamental bounds on the ability of any black-box test to identify algorithmic stability.