# The Role of Randomness in Stability

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2025.

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

- [Replicable Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2509.08660/) (2025)
- [The Sample Complexity of Replicable Realizable PAC Learning](https://mlsanity.com/paper/2602.19552/) (2026)
- [Tight list replicability bounds via a novel sphere covering theorem](https://mlsanity.com/paper/2606.06148/) (2026)
- [Surprises in Proper Positive-Only Learning](https://mlsanity.com/paper/2606.28309/) (2026)

## Abstract (arXiv)

Stability is a central property in learning and statistics promising the output of an algorithm A does not change substantially when applied to similar datasets S and S'. It is an elementary fact that any sufficiently stable algorithm (e.g. one returning the same result with high probability, satisfying privacy guarantees, etc.) must be randomized. This raises a natural question: can we quantify how much randomness is needed for algorithmic stability? We study the randomness complexity of two influential notions of stability in learning: replicability, which promises A usually outputs the same result when run over samples from the same distribution (and shared random coins), and differential privacy, which promises the output distribution of A remains similar under neighboring datasets. The randomness complexity of these notions was studied recently in (Dixon et al. ICML 2024) and (Cannone et al. ITCS 2024) for basic d-dimensional tasks (e.g. estimating the bias of d coins), but little is known about the measures more generally or in complex settings like classification. Toward this end, we prove a `weak-to-strong' boosting theorem for stability: the randomness complexity of a task M (either under replicability or DP) is tightly controlled by the best replication probability of any deterministic algorithm solving the task, a weak measure called `global stability' that is universally capped at frac12 (Chase et al. FOCS 2023). Using this, we characterize the randomness complexity of PAC Learning: a class has bounded randomness complexity iff it has finite Littlestone dimension, and moreover scales at worst logarithmically in the excess error of the learner. This resolves a question of (Chase et al. STOC 2024) who asked for such a characterization in the equivalent language of (error-dependent) `list-replicability'.