The Role of Randomness in Stability

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 1 . 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, Pavan, Vander Woude, and Vinodchandran ICML 2024) and (Cannone, Su, and Vadhan 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 M, a weak measure called M's 'global stability' that is universally capped at 1 2 (Chase, Moran, Yehudayoff FOCS 2023). Using this connection, 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, Chornomaz, Moran, and Yehudayoff STOC 2024) who asked for such a characterization in the equivalent language of (error-dependent) 'list-replicability'.