The Role of Randomness in Stability
Authors: Max Hopkins
Shay Moran
Venue: ICML 2025 spotlightposter (2025)
Keywords: Replicability
Differential Privacy
PAC Learning
Randomness
Stability
Primary area: theory->learning_theory
TL;DR: We study the number of random bits needed to achieve replicability and differential privacy for general statistical tasks and PAC Learning.

Abstract: Stability is a central property in learning and statistics promising the output of an algorithm $\mathcal{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 \textit{how much} randomness is needed for algorithmic stability? We study the randomness complexity of two influential notions of stability in learning: \textit{replicability} (which promises $\mathcal{A}$ usually outputs the same result when run over samples from the same distribution), and \textit{differential privacy} (which promises the output distribution of $\mathcal{A}$ remains similar under neighboring datasets). In particular, building on the ideas of (Dixon, Pavan, Vander Woude, and Vinodchandran ICML 2024) and (Cannone, Su, and Vadhan ITCS 2024), we prove a "weak-to-strong" boosting theorem for stability in these settings: the randomness complexity of a task $\mathcal{M}$ is tightly controlled by the best replication probability of any \textit{deterministic} algorithm solving $\mathcal{M}$, a parameter known as $\mathcal{M}$'s "global stability" (Chase, Moran, Yehudayoff FOCS 2023). Finally, we use this connection to 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. As a corollary, we resolve a question of (Chase, Chornomaz, Moran, and Yehudayoff STOC 2024) about the error-dependent list-replicability of agnostic learning.

The Role of Randomness in Stability
Max Hopkins
Shay Moran
223
Abstract
1. Introduction
Stability a central property in learning and statistics promising the output of an algorithm remains similar when applied to similar datasets S and S' It is ele- mentary fact that any sufficiently stable algorithm (e.g. one returning the same result with high probability, or one satis- fying differential privacy) is either randomized, or constant." This raises a natural question: how much randomness is needed for algorithmic stability?
Stability is central property in learning and statis- ties promising the output of an algorithm A does not change substantially when applied to similar datasets S and S" is an clementary 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 usually outputs the same result when run over samples from the same distribution), and differential privacy (which promises the output distribution of A remains similar under neighboring datasets). In particu- lar, building on the ideas of (Dixon, Pavan, Van- der Woude, and Vinodchandran ICML 2024) and (Cannone, Su, and Vadhan ITCS 2024), we prove "weak-to-sie treak-to-strong" boosting theorem for stability in these settings: the randomness complexity of task M is tightly controlled by the best replication probability of any deterministic algorithm solv- ing M. parameter known as MM's "global sta- bility" (Chase, Moran, Yehudayoff FOCS 2023). Finally, we use this connection to characterize the randomness complexity of PAC Learning: a class has bounded randomness complexity iff it has finite Littlestone dimension, and moreover scales worst logarithmically in the excess error of the learner. As a corollary, we resolve ques- tion of (Chase, Chornomaz, Moran, and Yehu- dayoff STOC 2024) about the error-dependent list-replicability of agnostic learning.
In this work, we study the role of randomness in two fun- damental notions of stability: replicability, and differential privacy. Replicability is the core scientific and algorithmic tener that an experiment, run twice on data from the same underlying distribution, should produce the same output with high probability. Given a statistical task M and an algorithm for the task A (e.g. hypothesis selection, classifi- cation), one might reasonably define the replicability of A to be its (worst-case) collision probability over independent samples, that is:
min { Pr (P(S)((S) = A(S"1} SS-Da
where D ranges over the possible data distributions of M. To achieve true replicability, we'd hope to construct an al- gorithm with collision probability near 1. Unfortunately, it turns out this is unachievable. The best such parameter, called the global stability of M (Bun et al., 2020), is univer- sally capped at 3 for any non-trivial statistical task (Chase et al., 2023). Motivated by this fact, (Impagliazzo et al., 2022) recently proposed an elegant relaxation of global stability allowing shared internal randomness, calling an algorithm A p p-replicable if over independent samples S, S' and a shared random string r:
YD Pr [A(S:r) = A(S':r)) > 1-p. S.
Global stability is then exactly the best replicability parame- ter achieved by any deterministic algorithm solving M.
'Equal contribution 'Department of Computer Science, Prince- ton University. Princeton. USA FFauulty of Mathematics, Tech- nion, Haifa, Israel Google Research, Tel-Aviv, Israel. Correspon- dence to: Max Hopkins <mh4067 @ princcton.edu>. Shay Moran <smoran ttchnion.ac.il..
'Why? This depends on the model of stability. A deterministic DP algorithm, for instance, must have exactly the same output over all neighboring samples. Since one can always construct a path neighbors between any inputs S and S' A is inherently constant. In replicability similar argument is possible hut one interpolates between underlying distributions rather than samples.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
"Traditionally globally stable algorithm isn' assumed to be

---

The Role of Randomness in Stability
In (Dixon et al., 2023), the authors introduce certificate complexity, the smallest number of random bits needed to achieve p-replicability. They prove tight bounds on the cer- tificate complexity of several basic d-dimensional tasks, as well as showing near-matching bounds on the global sta- bility," Intuitively, it is reasonable to think there should be a general connection between the certificate complexity of a task and its global stability - the better the global stability, the better replication can achieve using no ran- dom bits, so the easier it should be to achieve any particular replication threshold Our first main result confirms this intuition, proving a sort of "weak-to-strong' boosting theo- rem for replicability: the number of random bits needed to beat 3-replication probability (up to single bit) exactly inverse log of the global stability. Furthermore, as one might suspect, this can be amplified any p-replicability using an additional log(1/p)
of the class. Recently, (Chase et al., 2024) proved this result does not extend to the general 'agnostic' setting and ask whether it is instead possible to prove bound that decays with the excess enror a. We resolve this problem: a class H has bounded error-dependent global stability (and therefore also certificate complexity) if and only if it has finite Lit- tlestone dimension. Moreover, the randomness complexity suffers only mild dependence on the error, scaling at worst as Ollo )
2. Main Results
We briefly overview our main setting of study, A statistical task .M consists of a data domain X, an output domain y and, for every distribution D over X, family GD C of "accepted solutions' for the task. An algorithm A X + y 'solves' the task M if for any 8 > 0, given sufficiently many samples n (3) from any D over X, A outputs E GD with probability at least 1 - B. At parametrized level, for fixed 3 and r3)), we say the algorithm solves M with confidence 3 and sample complexity n(3).
(1/p) p) random bits.
While replicability and global stability are important notions in their own right, they have perhaps been most impactful in their close relation to the widely influential notion of differential privacy (Dwork et al., 2006b). An algorithm for a statistical task is called differentially private if its out- put distribution remains similar under any two neighboring datasets. Like replicability, differentially private algorithms are inherently randomized, leading to the analogous notion of DP complexity (Canonne et al., 2024) measuring the smallest number of internal random bits required to achieve privacy. Our second main result is an analogous 'weak-to- strong' boosting theorem for differential privacy, closely tying DP Complexity to task's underlying global stability. However, due to privacy's 's multiple parameters and nuanced dependence sample complexity, our results in this context cannot be said to give an exact equivalence as above, and it remains an interesting open problem to fully characterize the relation between them.
A randomized algorithm A X' x f0. + + is called p-replicable if, for all large enough n, l 2 0, over two inde- pendent samples S, S' ~ D and the same shared random string r {0, 13 A returns the same output with high probability:
(A(S:r) = 11 P. p. DD: r- (0.1)"
Pr
21
The (parameter-free) certificate complexity of task M, denoted CRep: is the smallest é such that there exists bet- ter than 1 }-replicable algorithm solving M using at most l random bits, or, more explicitly, the smallest é such that for every / > 0 there exists n(3) E NN and a better than 2 -replicable algorithm on ((m)-esmll and & random bits solving M with confidence / (c.f. Definition A.4).
Boosting in hand, we turn look the randomness com- plexity of one of the best studied tasks in learning: binary classification. We focus on the classical PAC model (Vap- nik& & Chervonenkis, 1974; Valiant, 1984), where learner, given sample access to distribution of labeled examples D, must produce a labeling from some fixed class H that is close to the best possible option with high probability. The global stability of PAC learning is quite well studied (Bun et al., 2020; Ghazi et al., 2021a; Bun et al., 2023; Chase et al., 2023). In the 'realizable setting', where the data is assumed to be consistent with some h E H, it is known how to construct a 2 2-20(1) -globally stable algorithm indepen- dent of the learner's 's error, for the Littlestone dimension
The global stability of task M is the best replicability that can be achieved using no internal randomness. In par- ticular, an algorithm A is called 17globally stable if over independent samples S, S':
VD: Pr (A(S) = A(S")) 2 n. S
The globally-stable complexity (g-stable complexity), de- noted Calob. is log _. where 7M > is the supremum across 17 for which there is a deterministic n-globally sta- ble algorithm solving M (c.f. Definition A.2). Note that any 7-globally stable algorithm automatically has an output which is an h--hevy-hitter, that is some y/ E ) for which Pr(A(S)= = y] 2 17. The traditional notion of global stabil- ity (Bun et al., 2020) only requires this latter condition. In Appendix we show our variant is equivalent up to minor differences in sample complexity (meaning in particular the
deterministic, but one can always de-randomize such an algorithm and achieve the same collision probability. See Appendix B. FFormally. (Dixon et al., 2023) study slightly different pa- rameter called restcceplica,,lity, which essentially equivalent to global stability (Chase et al., 2023).
2

---

The Role of Randomness in Stability
g-stable complexity does not depend on which definition you take).
2. (DP to Stability): Co (n, 3) S , + O(1),
With this in mind, our first main result is a weak-to-strong boosting lemma for replicability: the number of random bits needed to achieve high probability replicability is exactly controlled by the best replication probability of any deter- ministic algorithm, i.e. g-stable and certificate complexity are (essentially) equivalent.
for any ,,,6) satisfying S Vn log(n')
and 8 S ". n N n' exp(Cainssta 3)), and 3 2 3 expp (n. B))
Qualitatively, Theorem 2.2 (Item 1) simply states that given an 17-globally stable (deterministic) algorithm, we can 'boost' it into an (c, 6)-DP algorithm using only log(1 + log(1/e) + log (1/5))rroo bits, where the new algorithm may have somewhat higher failure probability (8 vs 8') and sample complexity (n vs n') than the original. This should be compared to the analogous statement in replica- bility (Theorem 2.1) which roughly stated an 7-globally stable algorithm can be boosted to p-replicable one using log(1/n) + log(1/p) random bits. Theorem 2.2 (Item 2) states the (weak) converse also holds: given a good enough DP algorithm on log(1 //)) random bits, we can 'reverse- engineer' a deterministic 7-globally stable algorithm from it, again paying in the sample size and confidence.
Theorem 2.1 (Stability vs Replicability (Theorem C.1)). Let M be any statistical task. Then:
Catob S Reep S CGiab + 1.
Moreover, the number of random bits required to achieve p-replicability is at most [Couob + log(1/p)].
Replicability and global stability have played an important role in recent work constructing efficient differentially pri- vate algorithms in learning and statistics (Bun et al., 2020; Ghazi et al., 2021b; Bun et al., 2023; Kalavasis et al., 2023). An algorithm A is said to be (e, 8) -differrentially private if for any two datasets S, S' E X differing in only one coordi- nate the output distribution of A is nearly indistinguishable in the following sense. For any measurable event O C V:
We remark the blowup in sample complexity and confidence in Theorem 2.2 is typically mild - while the exponential dependence on CGioh looks large, Criiah is log-scale, so the blowup is only polynomial in stability similar to prior works in the area (Bun et al., 2020; 2023). Furthermore, almost all learning algorithms have logarithmic sample dependence the failure probability 33 (indeed in most cases one can amplify constant success algorithm to confidence 3 simply by repeating it 11g(1/3) times-in in this sense the loss in confidence only results in paying a log log factor in the global stability. Nevertheless, we emphasize the core focus of our work is on one specific computational resource- randomness. As a result, we sometimes compromise on other resources (as we do here) to better understand the fundamental limits of the main one.
Pr(A(S) E O] < ef Pr(A(s") E
+ O]+
In recent work, (Canonne et al., 2024) introduce the DP complexity of a task M, denoted Cn, 3,,, measur- ing the minimum number of random bits required to con- struct an (c, 5)- algorithm on n samples solving M with 3-confidence. Unlike our prior notions, DP complexity is parametrized due to the fact that there is no clear 'threshold' to set for the privacy parameters (c, 5) as in the replicabil- ity setting (i.e. p 1/2). Furthermore, (s, () --privacy is only meaningful when the parameters are taken as functions of the sample complexity n (and therefore confidence 3), leading to the somewhat cumbersome CDr(n, 8).
Nevertheless, since the quantitative statement of Theo- rem 2.2 is fairly cumbersome otherwise, is still worth taking a minute to explain the various dependencies before moving on. Recall our goal: given an 7-globally stable algo- rithm Aglobal on n' samples that succeeds with probability Aglobal as subroutine to construct an
As result of the above, the connection between DP com- plexity and global stability is somewhat more nuanced than the parameter- frraeeter-free equivalence in Theorem 1. We will con- sider two variants of the connection. In the first, we compare DP complexity to analogously defined parametrized g-stable and certificate complexities CGios (n,, 33 and CRep(ri, 3) (see Appendix A.2 for formal definition).
- B¹, we wish (s, 5DP algorithm solving the same problem with slightly worse probability 1-3 3 and using slightly more (л1 samples. As in prior work, the key to doing this is to build a large database of Agiotal 's 17-hevv--hitte appear with probability at least 17. By standard concentra- tion bounds, this can be done by running Aglobal roughly
Theorem 2.2 (Stability vs DP (Informal Theorem D.1)). There exists universal constant > O such that for any statistical task M:
outputs of Agiobal that
1. (Stability to DP): (n S (nl, 88) + log(l/e) + log((10)) + Ó(1)
o (log # times and looking at empirical output probabili- n/2
ties. Outputting one of these heavy-hitters privately actually requires us to run this estimation process O Ing NE
for any n 2 n' exp(Craos (8) log( log( 4)
times
to ensure the resulting 'dataset' of heavy hitters isn' too strongly affected by changing any single input sample in the
and B f . exp((ernoo() (8)) log(2)
lo(())
3

---

The Role of Randomness in Stability
process. In total, the above uses n n' losk log( 1) samples and setting y to be the best achievable replication probability (2 (2-Caua(" (n' ) gives the stated dependence. The decay of the success probability 3 can similarly be thought of as coming from bounding the probability any individ- ual subroutine Agiobal fails, though we give a better bound through more careful analysis in the main body.
775 total
that for any statistical task M:
(Stability to DP): CDP (2Cou S1 log 2 ,,,) S Colob +
log(1/e) + 1og(1/)) + 0(1)
2. (DP to Stability): Caiob I CDP(TT,,,) + O(),
Of course the basic procedure described above, which is similar to prior DP-to-stability reductions in the literature (Bun et al., 2023), is not randomness-efficiee (indeed it may even use an unbounded number of random bits!) As we discuss in Section 4.2, our randomness-efficient variant relies on carefully discretizing this type of transform to optimize the number of random bits without sacrificing correctness and privacy.
where the latter holds for any (T, satisfying E S TTog((T) and 5 <
We remark that the parameter dependencies here follow exactly the same explanation as in Theorem 2.2, with T = 2Caa e1 log 1 in (Item 1) appearing due to finding heavy hitters of Aglabat, and the (T, s, 6) dependency in (Item 2) needed to imply the corresponding DP algorithm has a heavy hitter.
In the reverse direction (Item 2), we directly prove any suffi- ciently private algorithm (i.e. one with the stated dependen- cies on (n, E, 6)) that uses random bits automatically has a heavy-hitter of weight roughly exp(-k). We then show how to transform any 3'-correct randomized algorithm A on n' samples with an 1--heavy-hitee hhtteer into deterministic 7-globally stable algorithm at the cost of running A roughly (og(1/8) times, resulting in similar parameter blowups as in 4/*
2.0.1. THE STABLE COMPLEXITY OF PAC LEARNING
Having established our stability boosting theorems, we turn to the randomness complexity of binary classification. We focus on the standard PAC Learning model (Valiant, 1984; Vapnik & Chervonenkis, 1971). A PAC Learning classifica- tion problem consists of a data domain X and hypothesis class H = (h : X - {0, 1}} of potential labelings of X. Given a distribution D over labeled samples X x {0, 1). the classification error of hypothesis is
Item I. We remark that the constraints on (n, E, 5) are also in general fairly mild. The assumption on is extremely weak (an algorithm is not considered private unless 8 $ n -()).. The assumption e is more restrictive, but is satisfied by many basic DP mechanisms, and, moreover, it is almost always possible to amplify a weak DP algorithm to one sat- isfying this constraint (though it may cost many additional random bits). We discuss this further in Section 3.
(h) = Pr [h(z) # v). (a.,)~
An algorithm is said to (agnostically) PAC learn the class (X, H) if for every a, 3 > 0 there exists n = n(a, E N such that given n samples, A outputs an a-optimal hypothe- sis with probability at least 1 1-3: -3:
Moving on from Theorem 2.2, we'd we'd also like a way to compare randomness complexity in DP to our original parameter-free variants of Cais and CReP- It turns out this is possible by considering a slight generalization of vanilla differential privacy called user-level DP. In user- level DP there are ' 'users', each of whom contributes a (sub)-dataset S,. Neighboring datasets are defined with re- spect to swapping an entire user rather than a single example. In other words, in user-level DP we view the total size-n dataset S as being comprised of T components ('users') ST) E (X*"/TTT, and must maintain (s, 6) prrvaacy under swapping out an entire S; subsample. Critically, in this setting (s, d) are now functions of T rather than of n. This allows us to define the user-level DP complexity, CD e, 8), a way that is independent of sample com- plexity and confidence as the smallest number of random bits such that there exists T-user (e, 8)-DP algorithm solv- ing M. We then get the following cleaner "parameter-free free" version of Theorem 2.2:
VD
Pr [err (err)(((S)) > min errp + a] S B. S-D"
kEH
In our framework, PAC Learning can be viewed as a se- quence of statistical tasks {Ma} parameterized by the er- ror a, where X = X x {0, y is the set of all labelings of X, and GD is the set of a-optimal labelings.
Due to its close connection with differential privacy, sta- bility is quite well studied in the PAC setting. In (Bun et al., 2020), the authors show that under the assumption that mingeh err = (called the 'realizable setting') ), the g-stable complexity of [Ma) can be universally upper bounded by 20(d) for any class (X, H) with finite Little- stone dimension d. In the error-dependent setting, the best known bound is of (Ghazi et al., 2021 who improve the g- g-stable complexity to poly(d) + Ollog( )
Contrary to the above, (Chase et al., 2024) show the for- mer type of enror-indeeendent bound is impossible in the agnostic setting, and ask whether an error-dependent bound
Theorem 2.3 (Stability vs User-Level DP (Informal Theo- rem D.2)). There exist universal constants C1, 02 > such
4

---

The Role of Randomness in Stability
like (Ghazi et al., 2021a) can be extended to this case.* 4 We resolve this problem: not only is such bound possible, the complexity scales essentially as in the realizable setting up to factor in the VC dimension.
3. Discussion and Open Problems
Before moving to the formal details, we take some space to further discuss the parameter restrictions in Theorem 2.2 and Theorem 2.3, related open problems, and provide some further justification why counting internal random bits is sensible for statistical tasks where 'external" randomness is also available via samples.
Theorem 2.4 (The Certificate Complexity of Agnostic Learning (Theorem E.1)). Let (X, H) be a hypothesis class with Littlesoone dimension Then (X, H) has a better than
2 -repllicable learner with
DP Complexity and the Pareto Frontier: Recall both Theorem 2.2 and Theorem 2.3 require variant of the fol- lowing guarantee the privacy parameters (T)
1. Sample Complexity:
exp(poly(d)) poly(a"), poly(a"",oog(1BB) (18(11B))
2. Certificate Complexity:
1 T
5
Volog
poly(d) + LoV) ())
where T is the number of users (in the vanilla DP setting, T is then just the number of samples), Our first main question is to what extent such requirement is necessary. Can we characterize for what triples (T, e, 5) the inequality CGlob S CD,(TT,, + O(1) holds?
Conversely if = 0o, then CRepla)= 3o for any < 5. In other words, there is no globally stable, DP, or replicable algorithm for (X, H) better than random guessing.
While we defer the definition of Littlestone dimension itself to Appendix (the notion is not needed for our arguments which use prior work to this end as a black box), is use- ful to mention a few concrete examples for intuition. For instance, the class of k-dimensional affine subspaces of TRd has Littlestone dimension k + 1, and the class of 7-margin halfspaces in Rdd has Littlestone dimension at most + In both cases Theorem 2.4 gives the first randomness-efficee replicable algorithm for learning these classes (and in fact the first globally stable algorithm for the problem at all).
Toward this end, it is worth briefly discussing why this con- straint occurs, and to what extent it is normally achievable. Regarding the first, Equation (I) are exactly the constraints required to achieve strong notion of stability called perfect generalization (Cummings et al., 2016; Bassily & Freund, 2016), which promises that on most input datasets S, A,S: :) is actually statistically close to the distribution -): All known transforms between DP and replicability go through perfect generalization (Bun et al., 2023; Kalavasis al., 2023) (we note prior transforms combine this with method called correlated sampling which ruins the certificate size, so do not recover our results). At a high level, it would be inter- esting to give a transform between DP and list-replicabilityy without going through perfect generalization, potentially bypassing this barrier. In some sense such a transformation is actually possible in the PAC Learning setting using the fact that Littlestone dimension characterizes learning, but this results in tower-type dependence in the certificate size.
We remark if all one wants is heavy-hitter global stability, the sample complexity of Theorem 2.4 can be improved to poly(d, a 1o)(1/3)) while maintaining (poly(d) + complexity. It is an interest-
(VC((H) ()) ing question whether poly(d, a 1 ()) samples is achievable in the replicable case while maintaining good certificate complexity. This cannot be achieved using cur- rent sample-efficient methods which all rely correlated sampling (Ghazi et al., 202 bb; Bun et al., 2023) and have certificate size scaling with [H). Simultancously achieving randomness and sample efficiency therefore seems to re- quire new ideas in the theory of replicable algorithm design.
Regarding the achievability of Equation (1), in most cases such constraints are fairly mild. In fact, normally Equa- tion (I) is hardly a barrier at all since it is always possi- ble to amplify a T-user (O(1), poly(T))-DP algorithm to T -user 1/ (T)) algorithm simply by ap- plying the former on random size-T sub-sample of the latter's users (Balle et al., 2018). Setting < + then satisfies Equation (I). The catch here is that this pro- cess uses T (og(1/)) additional random bits, a heavy cost when known settings seem to only require logarithmically many bits in T (Canonne et al., 2024). This leads to an interesting question: is it possible derandomize subsam- pling techniques in differential privacy? Can amplify
In recent independent work, (Blonda et al., 2025) also prove a variant of Theorem 2.4 for global stability with g-stable Their work also addresses second open problem of (Chase et al., 2024) which we do not consider. See Section 3.1 for further discussion.
complexity exp(d)- - poly(a
"Again, we note (Chase et al., 2024) is phrased in terms 'list- replicability', but (Chase et al., 2023) prove the a-dependent (log) list-size Cua(a) satisfies (as)(aa) < Cus((a) < Ceuosay 22) so it is asympotically equivalent to characterize Cawa (ax) We refer the reader to Section of (Chase et al., 2023) and Section 2 of (Chase et al., 2024) for details and the formal definitions.
'I.e. a dependence of type T(n) = 21--1)
5

---

The Role of Randomness in Stability
an (O 1/ poly(T))-DP algorithm 1/ (e,1/poly(7) poly(T))- DP using only (T)))())e)) additional random bits?
oracle, relying on its output to ensure privacy leaves it open to attacks corrupting the oracle, or even privacy failure stemming from benign issues such as light failure of the i..d assumption in real-world data (see e.g. discussion in (Gold- wasser et al., 2022) regarding possible breaches in security from corruption of a learning algorithm's 's randomness). To avoid such scenarios, when defining differential privacy for statistical tasks we always apply privacy at the level of the fixed sample, so the same motivation and context as in the empirical case holds.
Measuring Randomness in Statistics: Certificate and DP complexity count the number of internal random bits used by an algorithm solving a fixed statistical task M. Unlike the empirical setting (as studied e.g. in (Canonne et al., 2024)), algorithms in the statistical setting also have access to external randomness in the form of i. samples from the underlying data distribution D. It is reasonable to then ask: why do such algorithms need internal randomness at all, and (assuming they do) why does make sense to measure it?
3.1. Further Related Work
Stability and Replicability: Global stability was intro- duced in (Bun et al., 2020) to upper bound the sample complexity of private PAC Learning. Replicability was introduced independently in (Impagliazzo et al., 2022) and (Ghazi et al., 2021b) as a relaxation of global stability, in the former towards addressing the crisis of replicability in science, and in the latter towards achieving upper bounds on the sample complexity of user-level private learning. Since these works, great deal of effort has gone into understand- ing what statistical tasks admit replicable algorithms (Kar- basi et al., 2023; Esfandiari et al., 2024; Eaton et al., 2024; Esfandiari et al., 2022; Komiyama et al., 2024; Hopkins et al., 2024; Kalavasis et al., 2024), as well as their connec- tion to other notions of stability such as differential privacy (Ghazi et al., 2021b; Bun al., 2023; Kalavasis et al., 2023; Moran et al., 2023; Chase et al., 2023). Our work is most related to this latter line, especially Theorem 2.2 and Theo- rem 2.3 which rely on new monddmmess-effciien variants of the transforms introduced in these works.
For certificate complexity, this question was naturally ad- dressed in the seminal works of (Impagliazzo et al., 2022; Dixon et al., 2023). Recall that in replicability, the internal randomness of .A plays special role apart from the sample because it is shared between the two runs of the algorithm. is not hard to argue that most natural problems (namely any problem where there is a continuous path between two distributions D and D' with disjoint solution sets) require at least one shared random bit to achieve better than 1/2 replication probability." 6 Another natural interpretation of the certificate complexity is as a measure of the 'communi- statistical task - it is the number of bits that must be published publicly to ensure external parties can verify the result of the algorithm.
cation complexity"
In differential privacy, the situation is more nuanced. In (Canonne et al., 2024), the authors focus on empirical tasks, meaning the dataset is fixed (not drawn i.i.d from some distribution) and the only source of randomness is internal. In this case it is obvious that any non- con-trivial DP algorithm must be randomized, and there strong motivation to bound the extra number of random bits required since 1) clean randomness is expensive, and 2) prior implementations of DP in practice such as the U.S. Census used an astronomical number of clean random bits, thought to be upwards of 90 terabytes (Garfinkel & Leclere, 2020). Understanding to what extent this cost can be mitigated is then a question of significant theoretical and practical interest.
Replicability is substantially stronger than classical stability notions in the literature (see e.g. (Bousquet & Elisseeff, 2002)) which generally require that similar inputs result in close rather than equivalent outputs. While this may seem too strong guarantee to ask for in statistical analysis, it's worth highlighting that requiring true equivalence comes with a host of benefits not enjoyed by prior notions. This is discussed extensively in prior work (see e.g. (Impagliazzo et al., 2022; Bun al., 2023)), and we will mention just a few such examples here:
In the statistical setting, we argue that despite our additional access to external randomness, any useful notion of dif- ferential privacy must still inherently rely only on internal randomness to protect user data. This is because differential privacy should always protect users in the worst-case, even for average-case problems studied in statistics. In partic- ular, since the algorithm has no control over the sample
1. Replicability is closely related to other 'strong' no- tions of stability in computer science (DP, adaptive data analysis, and more). Several open problems in DP (sample-efficiet user-level DP, amplification of DP) were only resolved through studying replicability (Ghazi et al., 2021b; Bun et al., 2023).
'The argument is simply that if the algorithm is correct, it must be outputting different solutions on D and D', but then there is some interior distribution the path which is non-replicable. See (Dixon al., 2023; Impagliazzo al., 2022; Chase al., 2023) for more detailed examples.
2. Replicability is testable. It is not always easy to test whether an algorithm is stable (e.g. testing DP is known to be computationally hard (Gaboardi et al., 2020)). By requiring equivalence, replicability is trivially verifi-
6

---

The Role of Randomness in Stability
able.
question on error-dependent global stability in agnostic PAC- learning, proving a variant of Theorem 2.4 with randomness complexity exp(d) + poly(a-"). Beyond this, (Blonda et al., 2025) also prove impossibility for error- arror-nddependnt global stability when OPT is bounded above by some known constant 7, generalizing the error-independent stability im- possibility result of (Chase et al., 2024). We do not consider the latter model in our work.
3. Replicability is preserved under arbitrary post- processing. Even applying very sensitive function to the output of replicable algorithm remains replicable, while such procedure will not preserve weak stability.
4. Replicability is easily amplified. Given a constantly replicable algorithm, there is a simple and computa- tionally efficient procedure to amplify it to arbitrarily high replication probability.
4. Technical Overview
5. Replicability is model independent. Different statis- tical tasks naturally have different notions of weak stability and closeness, or, in the case of testing prob- lems with binary outputs, may have no natural notion of weak stability (see (Hopkins al., 2024) for further discussion). Replicability gives unified definition for studying stability for all statistical tasks.
In this section we overview of the main ideas in the proofs of Theorem 2.1, Theorem 2.2 and Theorem 2.3, and Theo- rem 2.4 respectively. We emphasize the below are not full proofs, and refer the reader to Appendix C, Appendix D, and Appendix E for the full details.
4.1. Global Stability and Certificate Complexity
In general, it is interesting to understand the tradeoffs in- herent between weaker classical notions and replicability. If one wants very high probability stability or is handling very high dimensional data, weaker notions will be com- putationally and statistically cheaper. On the other hand in low-dimensional settings ensuring strong replicability of- ten has little to no asymptotic overhead (Impagliazzo al., 2022), and when safety, testability, or privacy is paramount, it is necessary to use such a strong notion. Developing a better understanding of both is critical to help us decide when each should be used in practice.
We start with the forward direction: given (3 + 7)- replicable algorithm ARep for M on é CRsp random bits, transform it into a deterministic 7-globally stable algo- rithm for M for any 1) < 2- Since the g-stable complexity of M is the infinum of log for all achievable nlglobblly stable algorithms, this implies Cr S GRep-
Our first step is to use ARcp to build a (randomized) algo- rithm with a nearly 2-f-heavy-hitter We will then trans- form this algorithm into deterministic one with nearly 2- replication probability. Toward this end, observe that by av- eraging for every distribution D there exists random string TD such that Arep has a 'canonical solution' hD occurring with probability at least 2 + +
Certificate and DP Complexity: Certificate complexity was introduced in (Dixon et al., 2023), where the authors prove essentially tight bounds for the basic task of estimat- ing the bias of d coins and learning classes via non-adaptive statistical queries. Related to our results, (Dixon et al., 2023) observe (at least implicitly) the basic connection that any p-replicable algorithm on {p) bits has 2 -f(r) -hhhahaavtttte a basic component of the (replicability -> global stability) direction of Theorem 2. They also use discretized round- ing, which is the core component of the reverse direction, but focus in particular on d-dimensional space while we give generic discretized rounding scheme based on access to a 'weakly replicable' subroutine over any domain.
Pr [ARe rp) = hp) 2 1/2+7- +
S~Dn
By running (:r) roughly log(y/r) times over fresh sam- ples and taking the majority output, we therefore get an algorithm Amaj with nearly 2 2hevy hitter
Pr (0,10 .. D
Amay (S:r) hpl 2 (1-(1-
since r = rD with probability -- and conditioned on this event Amaj almost always outputs hD by Chernoff.
We now transform Amuj into deterministic algorithm with nearly 2 replication probability. This follows in two steps. First, we construct a new randomized algorithm A which runs Amuy 20(9) times (over fresh samples and random- ness) and output the most common response. Standard concentration then ensures the output of AMll( is a nearly 2 --heavy-hitter of Anaj with very high probability over S and r. Second, we derandomize AHH (S;r) by tak- ing AlllI-de(S) to be the plurality response of A (S;)) over all random strings. simple Markov-type argument
DP complexity was introduced recently in (Canonne et al., 2024), where the authors study the number of random bits re- quired to perform counting queries under (e, diifferrrlli privacy on fixed empirical dataset. The authors lower bound techniques use similar methods to those used to bound certificate complexity in (Dixon et al., 2023), but they do not give any generic connection between the two.
Stability in Agnostic Learning: In recent independent work, (Blonda et al., 2025) also resolve (Chase et al., 2024)'s
7

---

The Role of Randomness in Stability
4.2. Global Stability and Differential Privacy
nY
n2yy..
We now overview the main ideas behind Theorem 2.2 and Theorem 2.3 in more detail. We start with the forward direction: given an 7-globally stable algorithm, we'd like to construct an (c. 6)-DP algorithm using roughly fog(1/n) + log(1/e) + log(1/0) random bits. The key to doing this is to first construct an (s, 6/2) - -ll-ooorihhhhm App satisfying the following properties
plyn...
Figure 1. Thresholding procedure for Calub = 2 and T = 7. Blue dots denote the 1 heavy hitters, one of which p(v1) is known be far from any threshold. This leaves 4 (green) thresholds with no nearby heavy-hittor out of 7, so p = 4/7 }. and Ckep S 3.
1. Bounded Support:
(=) 7/0
AS : [Supp(Anp(S))
shows that Attl--o also almost always outputs a nearly 2 2-<-heavy-hiter of Amaj over the randomness of S, and since there are at most 2 such heavy hitters this implies Attl-de((S) is (nearly) 2 -gl-bbobl stable as desired. maj
2. Strong Correctness:
5 Pr(Supp(ADP(S)) C cGp) 2 1- - 8.
We remark that correctness is maintained throughout all the above transforms so long as our initial confidence 3 I 2-((() was sufficiently small, since then any heavy hitters of the original algorithm must have been correct in the first place, and we almost always output such hypothesis.
In other words, the algorithm should always have small sup- port, and that support should almost always be completely correct. The only issue is that AdP might use too many random bits. We address this via an elegant observation of (Canonne et al., 2024): any distribution of support T can be 8 //aapproxe (i.e. we can produce another dis- tribution within 5/2 2 in total variation distance) using only log(T) + log(2/5) random bits and without adding any new elements to the support. Given the above conditions. this results in a 8-confident (s, 6)-D algorithm as desired.
To prove the reverse direction, we need to show how to am- plify an gloobbyyy stable algorithm Agiobal to p-replicable one using log 1 + log J random bits. The key is again to look at the set of heavy-hitters of Aglohat. For y E Y, let p(y) denote the probability Aglobal outputs y. Running Agtobal suf- ficiently many times, we get empirical estimates p(y) such that [Ø(N) - -(w)] < 3 with very high probability for some small 7 < poly(pn)-
Building on prior work, we construct our base DP algorithm using the 'DP Selection' primitive of (Korolova et al., 2009; Bun et al., 2016; 2018), which, roughly, given a dataset M, provides an (s. 8DP procedure to output some y E y that appears no fewer than log(1/ā] times less than the most fre- quent element in M. As discussed in the previous sections, given Aglobal we can build such a dataset M by 1) build- ing an algorithm that outputs one of Aglobal 's heavy hitters with high probability 2) running this procedure O loo times. To ensure bounded support of the algorithm over all possible inputs, we additionally add log log(1/5//s copies of some fixed 'dummy hypothesis' y )' to the dataset, so DP selection always outputs something in M by design. While this dummy hypothesis y may not be correct, strong correctness still holds because the only way y ends up in the support is if many non non-heavy hitters lie in M as well, a low probability event as long as the initial heavy-hitter sub- routine succeeds with high probability. Finally, we remark the entire procedure is user-level private since swapping out full sample to the heavy-hitter estimation procedure (one user) only changes one element in the database M.
1. and consider the set of thresholds (n - 77 Fix T ~ App 27....,7! f] T7}. Our final algorithm simply selects one of the 7' thresholds at random, and outputs the first y (with respect to some fixed order on 3") satisfying p(v) 2 t.
We now argue the above procedure is p-replicable. To see this, observe that because Agiabal only has heavy hitters of weight more than T"y (and moreover one of weight at least 17). it must be the case that at most 1 1 of these thresholds are within 7/3 of some p(y) for any y E Y. On the other hand, conditioned on the fact (p(y) - - < 7/3,, choosing any of the T 1 + 1 thresholds f without such a nearby heavy hitter results in a completely replicable output, since the list of y with p(y) > is always the same. The > 1 p-p, so taking the failure probability of our empirical estimates sufficiently small gives a p-replicable algorithm desired. See Figure! I for example diagram of this procedure.
me
probability of selecting such a threshold is - T-1+1
Similar to before, correctness is also maintained as long as our original algorithm is 3 < O()) confident, as then every heavy hitter must be correct and the algorithm almost always outputs a heavy hitter of Agtobul-
In the reverse direction, we are given a (T, e, uueerrllllell DP algorithm ADP on random bits which, by (Ghazi et al., 2024), we may also assume is (.5, perrffftyyy
8

---

The Role of Randomness in Stability
generalizing. We refer the reader to Definition D.6 for the exact definition, and for now note this implies the existence of a sample S such that for all O C y we have PIy[App(S:.) E O I e!/2 Pr [ADP((A)p))))) E O 1/2 Since App (S) has support size at most 2", setting O = Supp(Apr(S)) (and therefore the LHS to 1) implies Prsv.-A((,. E Supp(Anp(S))] 2 ((I), or equivalently, that ADP has a O "--hevy-hittter We may then use the same procedure in Section 4.1 to transform this into deterministic 0 --goobagyy stable algorithm desired.
heavy hitter hD occurs in the with probability least 3. Naively are then back at the same problem, since the output set has size T Tn(a, (VvC), but the key is to re- alize that hD not only occurs with high probability, it occurs at least ((n7)) times with high probability. This means we can prune all hypotheses from the resulting list that don't ton'to oc- cur Q(1TT) times, cutting the total number down to at most 1 nn(a, 1) n) O(VC(()) This results in an agnostic learner with 1 nn(a, m) (o(vc())) heavy-hittt,, which can be converted into globally-stable learner by our prior procedure.
"
As written, the above has exponential sample complexity in the Littlestone dimension - this can be fixed in the heavy- hitter setting by exploiting a stronger guarantee of (Ghazi et al., 1a)ss algorithm which in reality outputs list of exp((oly(dd)e -0(1) pears in the list with probability least 2(2)). We can then perform the same procedure about but set T = poly B) to get the same result with improved sample complexity.
4.3. The Stability of Agnostic Learning
Our agnostic globally stable learner is based on the agnostic- to-realizable reduction framework of (Hopkins et al., 2022), in particular a variant for replicable algorithms in (Bun et al., 2023). In other words, starting with an n-globally stable learner Arcc for the 'realizable setting' (where it is assumed the underlying distribution is labeled by a hypothesis in H), we will build a globally stable agnostic learner AAga for arbitrary distributions. Our starting point is therefore the realizable setting, where we rely on the following result of (Ghazi et al., 2021a): every class (X, H) with finite Littlestone dimension dl has an 17 = 20olyld) a 0(1) -globbaly stable learner on n(a, B3) = poly(d, a, log((11/))) samples in the realizable setting.
(()))=0(()) hypotheses such that some hp ap-
The core idea behind the reduction is simple: we draw a large unlabeled sample Sy of size n(a,,)) (3) and run Apac across all possible labelings of Sy in the class, then output random hypothesis in the resulting set of outputs with low empirical error (tested across a fresh batch of labeled samples from the underlying agnostic distribution). This is an agnostic learner because the first stage always runs APAC over the labeled sample (Su, horr(Su)) for some optimal hypothesis PO by design, and therefore with high prob- ability has output that is close to the best hypothesis in H. Moreover, because APAC is globally stable, there is even some fixed good hypothesis hD close to hOPT that appears in the set with probability at least 17, and therefore is given as the final output with probability //|SS ( ((VC(H)) where V VCHH)& is the VC dimension and the divisor |So (O()C(H) is an upper bound on the number of possible labelings of Sy by H (see Lemma A.13).
This procedure almost works, but it has a core issue: to achieve confidence 8, we have to set |Sy| scaling with 8, but then the global stability depends on 3 as well which is not allowed. We fix this by running ApAC only with confidence roughly 77, ensuring at least its heavy hitter is an o-optimal hypothesis. Unfortunately, this means are no longer guar- anteed the resulting set of outputs will have c-optimal hypothesis with high probability, breaking the argument. We fix this by running the procedure over T log(1/2) inedene- dent unlabeled samples, which ensures the nearly-
")
9

---

The Role of Randomness in Stability
Acknowledgements
Bun, M., Gaboardi, M., Hopkins, M., Impagliazzo, R., Lei, R., Pitassi, TT,, Sorrell, J., and Sivakumar, S. Stability is stable: Connections between replicability, privacy, and adaptive generalization. arXiv preprint arXiv:2303. /292/, 2023.
We thank Zachary Chase for many helpful discussions on list stability and differential privacy, especially for refer- ring us to (Ghazi et al., 2021a)'s list-stability bound with polynomial dependence in excess error in the realizable regime, and suggesting how to make list-replicable learners deterministic.
Canonne, C. L., Su, F. E., and Vadhan, S. P. The randomness complexity of differential privacy. 2024.
Impact Statement
Chase, Z., Moran, S., and Yehudayoff, A. Replicability and stability in learning. arXiv preprint arXiv:2304.03757, 2023.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chase, Z., Chornomaz, B., Moran, S., and Yehudayoff, A.
Local borsuk-ulam, stability, and replicability. In Pro- ceedings of the 56th Annual ACM Symposium on Theory of Computing, pp. 1769-1780, 2024.
References
Alon, N., Livni, R., Malliaris, M., and Moran, S. Private pac learning implies finite littlestone dimension. In Pro- ceedings of the 51 Anmual ACM SIGACT Symposium on Theory of Computing, pp. 852-860, 2019.
Cummings, R., Ligett, K.. Nissim, K., Roth, A., and Wu, Z. S. Adaptive learning with robust generaliza- tion guarantees. In Feldman, V., Rakhlin, A., and Shamir, O. (eds.), Proceedings of the 29th Confer- ence on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, volume 49 of JMLR Workshop and Conference Proceedings, pp. 772-814. JMLR.org, 2016. URL ht:p: http:///oocceeee..eeeeeee/s /ttptpp//ppooeeeiinn v49 wwwccmggsssis html.
Balle, B., Barthe, G., and Gaboardi, M. Privacy amplifica- tion by subsampling: Tight analyses via couplings and divergences. Advances in neural information processing systems, 31, 2018.
mlr. press/
Bassily, R. and Freund, Y. Typec stability and privacy. CoRR, abs/1604.03336, 2016. URL http: //aaxiiv...///////eee.aaa...aaaa .rg/ abs 1044/ 03336.
Dixon, P., Pavan, A., Woude, V., and Vinodchandran, N. List and certificate complexities in replicable learning. arXiv preprint arXiv:2304.02244 2023.
Blonda, A., Gao, S., Hatami, H., and Hatami, P. Stability and list-replicability for agnostic learners. arXiv preprinl arXivv2501.0533: 2025.
Dwork, C., Kenthapadi, K., McSherry, F. Mironov, I., and Naor, M. Our data, ourselves: Privacy via dis- tributed noise generation. In Advances in Cryptology- EUROCRYPT 2006: 24th Annual International Confer- ence on the Theory and Applications of Cryptographic Techniques, St. Petershurg, Russia, May 28-June 1, 2006. Proceedings 25, pp. 486-503. Springer, 2006a.
Bousquet, O. and Elisseeff, A. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
Bun, M., Nissim, K., and Stemmer, U. Simultancous private learning of multiple concepts. In Proceedings of the 2016 ACM Conference on Innovations Theoretical Computer Science, pp. 369-380, 2016.
Dwork, C., McSherry, F., Nissim, K., and Smith, A. Cali- brating noise sensitivity in private data analysis. In The- ory of cryptography conference, pp. 265-284. Springer, 2006b.
Bun, M., Dwork, C., Rothblum, G. N., and Steinke, T. Com- posable and versatile privacy via truncated CDP. In Di- akonikolas, I,, Kempe, D., and Henzinger, M. (eds.), Pro- ceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pp. 74-86. ACM, 2018.
Eaton, E., Hussing, M., Kearns, M., and Sorrell, J. Replica- ble reinforcement learning. Advances in Neural Informa- tion Processing Systems, 36, 2024.
Esfandiari, H., Kalavasis, A., Karbasi, A., Krause, A., Mir- rokni, V., and Velegkas, G. Replicable bandits. arXiv preprint arXiv:2210.01890 2022.
Bun, M., Livni, R., and Moran, S. An equivalence between private classification and online prediction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pp. 389 389-402. IEFF, 2020.
Esfandiari, H., Karbasi, A., Mirrokni, V., Velegkas, G., and Zhou, F. Replicable clustering. Advances in Neural Information Processing Systems, 36, 2024.
10

---

The Role of Randomness in Stability
Gaboardi, M., Nissim, K., and Purser, D. The complex- ity of verifying loop-free programs as differentially pri- vate. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, pp. 129. Schloss Dagstuhl-Laabbizz-Zennru fur Informatik GmbH, Dagstuhl Publishing, 2020.
20 24, 2022, pp. 818-831. ACM, 2022. doi: 10. 1145/3519935.3519973. URL https: pestpa://dol /tdo:./rorooooooooooo .org/ 10. 10.1145/3519938 35114///33199933.31997.... 3519973.
Kalavasis, A., Karbasi, A., Moran, S., and Velegkas, G. Sta- tistical indistinguishabbiity of learning algorithms. In In- terattional Conference on Machine Learning, pp. 15586- 15622. PMLR, 2023.
Garfinkel, S. L. and Leclere, P. Randomness concerns when deploying differential privacy. In Proceedings of the 19th Workshop on Privacy in the Electronic Society, pp. 73-86, 2020.
Kalavasis, A., Karbasi, A., Larsen, K. G., Velegkas, G., and Zhou, F. Replicable learning of large-margin halfspaces. arXiv preprint arXiv:2402.13883 2024.
Ghazi, B., Golowich, N., Kumar, R., and Manurangsi, P. Sample-efficient proper pac learning with approximate differential privacy. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp- 183-196, 2021a.
Karbasi, A., Velegkas, G., Yang, L., and Zhou, F. Repli-
cability in reinforcement learning. Advances in Neural Information Processing Systems, 36:74702-77735, 2023.
Komiyama, J., Ito, S., Yoshida, Y., and Koshino, S. Replica- bility asymptotically free in multi-armed bandits. arXiv preprint arXiv:2402.0739, 2024.
Ghazi, B., Kumar, R., and Manurangsi, P. User-level differentially private learning via correlated sampling. In Ranzato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P. and Vaughan, J. W. (cds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2,21, December 6-14, 2021, virtual, pp. 20172- 20184, 2021b. URL https: /ptpceeeeengg...... neurips ca/ httpppppr/2222//eaa a89c a89cf525e 1 d9 6ce -5b1139abb-bbbtaacc html.
Kontorovich, A. and Painsky, A. Distribution estimation under the infinity norm. arXiv preprint arX:v22402.08422, 2024.
Korolova, A., Kenthapadi, K., Mishra, N., and Ntoulas, A. Releasing search queries and clicks privately. In Proceed- ings of the 18th international conference on World wide web, pp. 171-180, 2009.
Levy, D., Sun, Z., Amin, K., Kale, S., Kulesza, A., Mohri, M., and Suresh, A. T. Learning with user-level privacy. Advances in Neural Information Processing Systems, 34: 22466-12477 2021.
Ghazi, B., Kamath, P., Kumar, R., Manurangsi, P., Meka, R., and Zhang, C. User-level differential privacy with few examples per user. Advances in Neural Information Processing Systems, 36, 2024.
Moran, S., Schefler, H., and Shafer, J. The bayesian stability 700. Advances in Neural Information Processing Systems, 36:61725-61746, 2023.
Goldwasser, S., Kim, M. P., Vaikuntanathan, V.. and Zamir, O. Planting undetectable backdoors in machine learn- ing models. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 931-942. IEEE, 2022.
Sauer, N. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145-147, 1972.
Shelah, S. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247-261 1972.
Hopkins, M., Kane, D. M., Lovett, S., and Mahajan, G. Realizable learning is all you need. In Loh, P. and Ra- ginsky, M. (eds.), Conference on Learning Theory, 2- July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pp. 3015-3066 PMLR, 2022. URLhttps: / /ttp///eeeengs...cpee/p//ce...se mlr. press// v1 v178/hopkins221 html.
Valiant, L. G. A theory of the learnable. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pp. 436-445. ACM, 1984.
Vapnik, V. and Chervonenkis, A. On the uniform conver- gence of relative frequencies of events their probabili- ties. Theory of Probability and Its Applications, 1971.
Hopkins, M., Impagliazzo, R., Kane, D., Liu, S., and Ye, C. Replicability in high dimensional statisties. arXiv preprint arXiv:2406.0261 2024.
Vapnik, V. and Chervonenkis, A. Theory of pattern recogni- tion, 1974.
Impagliazzo, R., Lei, R., Pitassi, T., and Sorrell, J. Re- producibility in learning. In Leonardi, S. and Gupta, A. (eds.), STOC '22: 54th Annual ACM SIGACT Sym- posium on Theory of Computing, Rome, Italy, June
Woude, J. V., Dixon, P., Pavan, A., Radcliffe, J., and Vin- odchandran, N. Geometry of rounding: Near optimal bounds and a new neighborhood sperner's 's lemma. arXiv preprint arXiv:2304.04837 2023.

---

The Role of Randomness in Stability
A. Preliminaries
We now cover our notions stability and general setting more formality. Most of our results are proved for the following standard and widely applicable notion of statistical task (see e.g. (Bun et al., 2023)):
Definition A.1 (Statistical tasks). A statistical task M consists of:
1. A data domain X
2. An output domain y
3. For every distribution D over X, subset GD C. y of "accepted solutions'
An algorithm solving M is (possibly randomized) mapping A: X + y such that for all 8 > 0 (the 'confidence') ) there a function n = n3) (the 'sample complexity') such that
VD Pr (A(S) E GDl 2 S-Da
We remark that some statistical tasks (e.g. realizable PAC Learning), one only considers a restricted family of distributions D over the data domain. All our results extend immediately to this generalized setting- we have chosen to focus on the distribution-fiee definition only for simplicity exposition.
A.1. The Stability Zoo
now overview the main notions of stability studied in this work. We remark that our definitions differ slightly from some prior works studying stability in learning which typically comes with an additional accuracy parameter. We discuss this distinction further in Appendix A.4.
We start with the core notion of global stability, which measures the best replication probability achieved by any determinstic algorithm solving the task.
Definition A.2 (Global stability). Let M be statistical task. An algorithm A solving M is said to be 7-globally stable if for large enough and every distribution D)
(A(S) = A(S') S
Pr
The g-stable complexity of M, denoted CM is the infinum of log(t) taken over all deterministic 7lgllbbllyy stable algorithms solving M. If the set of such algorithms is empty, we write Cciab
As mentioned previously, this differs from the 'traditional' notion of global stability in (Bun et al., 2020), which only requires A to have an hy-heav-hittter (and may use unshared internal randomness), seemingly weaker requirement. We show these notions are fully equivalent in Appendix B.
Global stability can never achieve replication probability beyond 1/2 for any non-trivial statistical task (Chase et al., 2023). Motivated by this fact, (Impagliazzo et al., 2022) introduced replicability, allowing the use shared internal randomness to boost replication success beyond the } barrier.
Definition A.3 (Replicability). Let M be statistical task. An algorithm AA solving M is said to be p-replicable if for all distributions D:
Pr (A(S:)) A(S' 21-p. D
In (Dixon et al., 2023), the authors introduce certificate complexity measuring the least number of shared random bits required to achieve p-replicability. Since we are interested in comparing certificate complexity to global stability, we will instead work mostly with a natural 'parameter-fres version of this definition. In particular, we will study the number of random strings required to achieve replicability strictly better than This is the natural threshold at which many random strings are forced to have unique 'canonical' hypothesis, and can easily amplified to arbitrary p.
12

---

The Role of Randomness in Stability
Definition A.4 (Certificate Complexity). The certificate complexity of statistical task M, denoted CRop(M), is the smallest number of shared random bits over which there exists a 2 -rreliccable algorithm solving M, i.e some A satisfying:
Pr r--00,1) S, DD
[A(S:)) = A(S'rr)] 1/2
If no such algorithm exists for any finite CRep, we write CRep = 0c.
We remark that once one has achieved > 1 replicability, Theorem 2.1 implies an amplification procedure to achieve any p-replicability parameter using an additional log 2 random bits.
For the rest of the work, we usually omit M and just write Cciob and CRep when clear from context.
A.2. Differential Privacy
Global stability (Bun et al., 2020) and replicability (Ghazi et al., 2021b) (known as -ocudd stability' in this context) were both introduced as a tool study the widely influential notion of differential privacy, a powerful algorithmic guarantee promising an algorithm has similar output distributions over neighboring samples.
Definition A.5 (Differential Privacy ((wwrrk et al., 2006b;a)))- Let M be a statistical task, and e, > 0. Two samples 8,5' E (X") are said to be neighboring if they differ in exactly one coordinate. An algorithm A solving M is said to be (e, diffferrrre private if for any neighboring samples S,S' and measurable events O ):
Pr(A(S) E EO]= S E Pr(A(S") E EO] +
We will sometimes use the notation A(S) (c.5) A(S") to denote the above closeness guarantee.
In early works (Bun et al., 2020; Ghazi et al., 202 2024; Bun et al., 2023), global stability and its variants played a key role in bounding the sample complexity of differentially private PAC learning. Quite recently, (Canonne et al., 2024) expanded this connection by using techniques developed for certificate complexity (Dixon et al., 2023; Woude et al., 2023) to bound the number of random bits needed to achieve differential privacy, a parameter we'll call DP complexity.
Definition A.6 (Parametrized DP Complexity). The (n, 8,,8,e, E, 6DP Complexity of a statistical task M is the smallest integer Cp (n, 8,e, 6) such that there exists an (e, 6DP algorithm on n samples solving M with confidence 3 using only Cpr(n, 8, e, 8) random bits. If no such algorithm exists for any finite Cpr(n, 3, e, d), we write Cpr(n, 3, e, 6) = co.
Unlike certificate complexity, it is not clear there is a natural 'parameter-free' variant of DP complexity, especially since the concept frequently is used at many different scales of (c, in theory and practice, themselves dependent on n and B. As such, we will focus mostly on parameter-dependent translations in this setting, and define the following 'parametrized' variants of g- gtabable and certificate complexity.
Definition A.7 (Parametrized g- g-Stable Complexity). The (n, -tt-ll-tablle complexity of a task M, denoted CGlobl (n, (3), is 1 where 17 is the largest global stability achieved by any 8-confident algorithm on samples solving M. If no such log 7j
algorithm exists, we write CGlob (n, B) = xc.
Definition A.8 (Parametrized Certificate Complexity). The (n, certtiiie complexity of a task M, denoted CRop(n, B), the smallest number of random bits such that there is 8-confident, better than 1 -rreplicable algorithm on n samples solving M. If no such algorithm exists, we write CRep(n, B) 00. xc.
A.3. User Level Privacy
In (Ghazi et al., 2021b; Bun et al., 2023), the authors take advantage of the strong stability guarantees of replicability to build "user-level' private algorithms (Levy et al., 2021), a stronger notion of privacy which each user is thought of as providing many data points and the goal is to protect against an adversary swapping out a single user's entire dataset. Formally, the input dataset S is actually split into subsets Si,..., ST coming from T-separate users, and we bound the algorithms deviation upon switching out one such S,:
Definition A.9 (User-Level Differential Privacy). Let M be a statistical task, n, T E N such that T' divides n, and call samples (5,,...,ST)) (SI,..., ST)) E (X"/TT"" neighboring if S Sj for all but one j E [T]. We call an algorithm A solving M T-user (c, DDP A(S) (c.6) A(S') for all such neighboring data-sets S,
13

---

The Role of Randomness in Stability
User-level DP allows tighten the connection between DP complexity and certificate complexity, giving tight transformation between the two up constants for reasonable regimes of and 6.
Definition A.10 (User-Level DP Complexity). The (T, E, -)--use--eeel--D Complexity of a statistical task M is the smallest integer CDp(T,, 8) such that there exists T'-user (e, 6D-DP algorithm solving M using only ET, 6) random bits. If no such algorithm exists for any finite CDP(T, 6), write CD,(T,E,0) co.
A.4. PAC Learning
Having established close quantitative connections between globally stable, certificate, and DP complexity, our second focus is to concretely determine the randomness complexity of fundamental statistical task: binary classification. We will focus
on the standard PAC framework, in which we have data domain X and hypothesis class H (h. X + {0,1)), collection of possible labelings of X. Let D be a distribution over labeled samples (X x {0, (0) and h X + 10 potential labeling. The error of h under D is
(h) = Pr [b(x)) # v). (ar,)~~
Similarly the empirical error of h on a labeled sample S is
errs(h) Pr [h(x)) + v]-
(a.2)E8"
We write the best possible error achieved over H
OPTD
inf errp (h). hEH
We call hypothesis h a-optimal if it achieves error at most OPT + An algorithm is said to (agnostic) PAC learn the class (X, H) if for every a, 3 > 0, on sufficiently many samples A outputs an a-optimal hypothesis with probability at least 1 - B.
Definition A.11 ((Agnostic) PAC Learning.. We say class (X, H) is PAC-Learnable if Va, B > 0 there exists = =m(a, B) and a (possibly randomized) algorithm A: x + P(x') satisfying
Pr (errp(((SS)) > OPTp + < 3. So
Note that PAC-Learning, formalized above, corresponds to an infinite sequence of statistical tasks (M(X,H) (a) parametrized by the accuracy namely where the data domain is X' = X x {0, 1}. the output space is all possible labelings y = (h- : x + {0, }}} and the set of accepted solutions is GD == {h E H erTp(H) S OPT + aa. With this in mind, we may therefore define the 'error-dependent" stabe/cctifficce/PP-coppeee
(a))
of a class (X, H) as
Calas(a) = Caian
and likewise for certificate and DP complexity. We emphasize this differs from prior works (Bun et al., 2020; Chase et al., 2024) that focus on g-stable complexity bounds that are independent of the excess eитоr (a distinction we will discuss further shortly).
The sample complexity of PAC learning (with no stability constraints) is tightly controlled by a combinatorial parameter called the VC-dimension:
Definition A.12 (VC Dimension). We say a subset S= (......, me is shattered by (X, H) if all possible 24 labelings of can be achieved by H. The VC dimension of (X, H) is the size of the largest shattered set.
We will need the following classical lemma bounding the number of labelings of any subset of data as a function of the VC dimension.
Lemma A.13 (The Suuer-Shelah-Pere Lemma (Vapnik & Chervonenkis, 1974; Sauer, 1972; Shelah, 1972)). Let (X, H) be a hypothesis class. For any n E N and C X of size n, the number of labelings of S by hypotheses in is at most O(VC((H)
14

---

The Role of Randomness in Stability
Unlike standard learning, learning under replicability or DP constraints is not possible for every VC class. Instead, these notions are characterized by stronger definition arising from online learning called the Littlestone dimension (Bun et al., 2020; 2023). The notion is based on mistake trees, complete binary trees in which every internal node is labeled by an element 2 E X. Every root to leaf path in a depth d + 1 mistake tree then corresponds to sequence (æ1. V1)........ (Iz, Ba), where yi E {0, 1} indicates whether the right or left path is taken down the tree. A hypothesis class (X, H) shatters the tree if for every such path there exists a hypothesis h E such that k(x;;) = y; for all S d. The Littlestone dimension is the largest depth of any shattered mistake tree:
Definition A.14 (Littlestone Dimension). The Littlestone dimension of a class (X, H) is the largest depth of any mistake tree shattered by H.
We note that the Littlestone dimension is always at least as large as the VC dimension.
In (Bun et al., 2020), the authors prove that any class with finite Littlestone dimension d has a universal upper bound on the g-stable complexity of 20(d) under the assumption that OPT 0. (Chase et al., 2024) showed this result cannot extend in the full agnostic setting, and indeed that error-independent bound is possible for any infinite class. They ask whether it is possible to give an error-dependent bound, a question we resolve in the positive in Theorem 2.4.
B. Global Stability: Replication vs Heavy-Hitters
In this section we prove that Definition A.2 (replication global stability) equivalent to the traditional randomized 'heavy- hitters' variant studied in (Bun al., 2020; Chase al., 2023). Given a distribution D over some domain X, an element X is called an 1--havy-hitte hitter if the measure of in D is at least 17. Traditional global stability promises the existence of a heavy hitter over the output distribution of the algorithm.
Definition B.1 (Heavy-Hitte Hitter Global stability (Bun et al., 2020)). Let M be statistical task. An algorithm A solving M is said to be -hhhevy- globally stable if for large enough n and every distribution D there exists hD such that:
Pr D
(A(S) hpl2
The HH-stable complexity of M, denoted CGlob m1I is the infinum of log( ( taken over all (possibly randomized) 1--heavy- hitter globally stable algorithms solving M.
In (Chase al., 2023), the authors observe that HH-global stability and global stability in Definition A.2 differ by most quadratic factor. We prove they are actually the same quantity, a fact we will use later both to move between randomized and deterministic algorithms, and to move from heavy-hitter bounds to global stability.
Theorem B.2 (Global Stability vs HH-Global Stability). For any statistical task M: GGiob- CGiob
Proof. We remark that any 7-globally stable algorithm is automatically 1--heavy-hitter globally stable, so CGiob-HH 2 Calob is immediate. Thus it remains to prove Cawb 2 CCia--II-
Write = GC For any 3,3 > 0, we are promised a 3-correct, possibly randomized algorithm A such that for any distribution there exists a hypothesis hp satisfying
Pr [A(S) = hp] 2 ワ T.S
Naively, .A only has replication probability approaching 2 To improve this, the idea is to build a new algorithm that outputs one of A's (17 - 2-))-eevv--htters with probability at least 7. By standard concentration bounds (see e.g. (Kontorovich & Painsky. 2024)) this can be done simply by running A on O log( (2) fresh samples and outputting the most common hypothesis in the list (breaking ties arbitrarily). Toward this end, denote the list of (17 2ry--hevy-hitterss by LD. and observe that for small enough 7 < O()), |LD| :
Taking 3 < O1)) sufficiently small, we can also ensure all elements of Ln are correct solutions, i.e. that LD GD- We have therefore arrived at algorithm ALis with the following property: for any distribution D, there exists a list Lp C GD of size at most 1 such that
Pr S,SDDa
(ALi((S;))
Lp] 2 1 y
15

---

The Role of Randomness in Stability
We note algorithms satisfying this guarantee called '| -istereii--pll (Chase al., 2023; Dixon al., 2023).
We now almost done since conditioned landing in Lp in both runs, the replication probability of Alist is at least Lo 2 7, and the probability of being outside the list can be taken to arbitrarily small. The only issue is that Aris is randomized. Thus it is sufficient argue we can de-randomize ALia the cost of increasing the list-failure probability y some corresponding y also arbitrarily small.
We do this simply by passing to the most likely output of ALis- Namely define Ause by
Adet (S) = yE>
=y}=
and note that Ader (S) can be easily computed by simply running rS; for all choices of internal randomness r and outputting the most common result (breaking ties arbitrarily). We claim:
27 1
P (S) [.] Pr 5
(rggax(PPr(Auuua WEY
w}} E L.D 2
This follows from the observation that for any sample S whose maximal output is not in LD, the probability of outputting an element outside of Lp is then at least ア (either the maximum probability, by assumption achieved by an element outside of Ln is at least _ in which case we are done, or is at most in which case the list elements make up only 1/2 the mass by assumption). Finally since we may take y arbitrarily small with respect to taking a large enough sample we may make Adet - 7 globally stable for any y > 0, implying CG 2 log CGlob-HH as desired.
will also be useful to have a parametrized version of the above transform:
Corollary B.3. For any statistical task M and 3 > O, given an n-HH globally stable, B-confident algorithm for M on samples, the transform in Theorem B.2 gives an -(nnaalbb stable 3' o'-confident algorithm for M on n' samples, where 3' S (B/m)) and n' Sn. δ log 3
Proof. Note that the statement is trivial if B > 17, and take 7,76 S ((Sn) in the proof of Theorem B.2. For such parameters Ase runs A most Ô log times, and has confidence 8 < 27/n S B/n (since outputs element in Lp with at least
n
this probability, which are correct by the assumption on (8).
C. Global Stability and Certificate Complexity
In this section, we prove Theorem 2.1, the (near) equivalence of g-stable and certificate complexity. We repeat the main result of the section here for convenience.
Theorem C.1 (Global Stability vs Certificate Complexity). For any statistical task M:
Cruab S CRep S CGiob + 1.
Moreover, the number of random bits required to achieve p-replicability is at most [Cotos + log(1/p)1
We start with the easy direction: certificate complexity to global stability. It is easy to see that any better-than-half replicable algorithm on é-bits is automatically 2 f 2 -globally stable (albeit randomized), since there must exist some r E {0, 1) which has 2 replication probability. This can be amplified to probability 2 - for any vj > 0 simply by running the algorithm many times and taking majority, then made deterministic by Theorem B.2.
Proof of Theorem C.I (Lower Bound). Recall by Theorem B.2, is enough to prove for any T > 0 the existence of a randomized algorithm A solving M such that for any distribution
Pr 8.8 D.
(A(S:r) = A(S": 2 Cue -
where r and r' are independent random strings.
16

---

The Role of Randomness in Stability
Now by assumption there exists ( -)-reliiaable algorithm solving M using RRep random bits. By averaging, then have that for any distribution D, there exists string rp [0, CR such that
Pr [A(S:)) = A(S"; + 8,8'DD
and therefore that there exists a 'canonical hypothesis" hD such that
Pr [A(S:)) = hpl + S.
Given this, consider the 'majority amplified' algorithm Amaj-T on nT samples and the same internal randomness defined as breaking ties arbitrarily. Taking T O log
Amaj-r (eeer((S (S,...., ST;r) = (lusality((((((:)))
large enough, Chernoff promises
Pr S~D
(mjjr((;)) = hD) 2
2'
so the total collision probability over two runs on independent strings least
Pr(A(S:r)=AGG))
2 Prfr = =r' r-==rr= rD] Pr(A(S:rp) A(S'rrD)) r== =rp
2 2 Cun (1-(11))
as desired.
We now prove the reverse direction, which follows from careful discretization of (Impagliazzo et al., 2022)'s random thresholding method. We first give the algorithm in pseudocode.
Algorithm Global Stability - Certificate Complexity
Result: (p -'epliabel, ;-confident algorithm 12 random strings
Input: (2-Cas -)-glbbalyy stable and O --confident algorithm A, total ordering & of V.
Parameters:
Threshold number T 2'aa -11
P
Heavy-Hitter parameter 17 2 -Cabb
Threshold offset r < 7 < !)
Amplification parameter (1,, 3, +')
Algorithm:
1. Run A across N fresh samples ~ D and let 9r denote the empirical density of each h e y
2. Select i (T) uniformly random, and let
H (h: pn 1 i7}
Return argmin ya (breaking ties via @) or L. if H, = Ø
H,
Proof of Theorem C.I (Upper Bound). We prove slightly stronger result: for any 7' > 0, there is a (p re)-rrrrirreelleeeee 1
learner using T
200m random strings. Achieving p > goreaus can therefore be done Cruob random bits,
17

---

The Role of Randomness in Stability
and general p may be achieved using [Caiob + log(1/p)] bits desired.?
To prove the stronger statement, first observe that by standard concentration incqualities (see e.g. (Kontorovich & Painsky,
2024)), for large enough Ti I 0 log( go7 with probability at least 1 Br' all empirical estimates fy in Step (1) of
Algorithm satisfy
Ph - pll < 4/33.
(2)
Condition on Equation (2) occurring. Choosing S 0()) S O(T²²) sufficiently small, there are at most 1 hypotheses
of empirical weight greater than 7 - Tyy Since A must have an (17 - -)-heayy hitter, there also exists at least one P 2 1) - T 10---1 7/3 > 1) 23/3, so the set of empirical heavy hitters H; (defined in Algorithm 1 Step 2) is non-empty for any i and Algorithm 1 will not output 1.
Now consider the set of T thresholds (1) 111-10 7/ 27, 27, 7. By assumption, at most ; of these thresholds have hypothesis with true weight within 7/3 of their value. Thus choosing random threshold, the probability we select one with no nearby hypothesis is at least 1 - 7 Conditioned on selecting such threshold & and Equation (2), the set of hypotheses with empirical measure greater than is always the same, so the algorithm always outputs the smallest such element in the list according to o as desired. In total, it follows the algorithm is
2 -1 12 1)1
replicable
Finally, since the algorithm is assumed to be O22-Caa) ((2-Caa))conffdeeeel --onfident, any true -heayy hitter must also be correct. Conditioned on Equation (2) Algorithm always outputs such a heavy hitter, so the final algorithm is 8-confident as well.
We note that in the setting of achieving strictly greater than 2 replicability, the sample overhead in Theorem C.1 can be taken as worst 20(Cau), since all parameters T, T 7 can be set to 2 2-O(Caua) and still achieve the desired replicability. We will use this fact proving Theorem 2.4.
D. Stability and Differential Privacy
We now prove Theorem 2.2 and Theorem 2.3 connecting global stability and the randomness complexity of differential privacy. We restate the results in more formality.
Theorem D.1 (Stability Boosting (DP)). There exists a universal constant c 0 such that for any statistical task M:
1. (Stability to DP): CD 8, < (n' 3¹) + log log (1/) + log log (1/0) + O(1)
for any n 2 nl -0( 20 log 1 log t ) Ie (0 log
05 (82Cammt.3))+)00 lex
and
2. (DP to Stability): Coto (n, B) S (,,,,),,,,,,0)++++
for any < log(ne) and 8 G. n 2 n' Ô 2200n log 4 and 3 2 0(32Cor(mBBs.d))
Theorem D.2 (Stability Boosting (User-Level DP)). There exist universal constants C1, C2 > 0 such that for any statistical task M:
1. (Stability to DP): Cpp (2 et log e, S Cous +
+ log log
2. (DP to Stability): CGtob & (Dp((T,e)) O(L)
where the latter holds for any (T, satisfying <
(TlgT( and ó < 4
Formally, note there is some discrepancy here in sampling a random threshold for T' not power of 2 when r is a bit-string. However, in the argument helow increasing the number of random strings/thresoolds the nearest power of 2 only helps replicability, this is not an actual issue.
18

---

The Role of Randomness in Stability
Both Theorem D.1 and Theorem D.2 follow corollaries of the same underlying stability DP and DP stability transformations. We start by proving the forward direction: randomness efficient stability-to- transform. The key to achieving low randomness is the following useful observation of (Canonne et al., 2024): any distribution with small support can be approximately sampled using few random bits.
Lemma D.3 ((Canonne et al., 2024), Lemma 2.10 (rephrased)). For any randomized algorithm M : X - Y and > O. there exists an algorithm M' using max, log( (Supp((((()))) + log(1/1) random bits such that for every input n, M satisfies:
1. (Closeness): drv (Mr) Σ
2. (Subset Support): Supp( (x)) S (ux)(M(x))
The result will now follow if we can prove stability-to-DP transformation with two key properties
1.
For every S, the support of A(S) is small
2. With high probability over S, Supp(A(S)) C GD.
where we recall GD the set of correct solutions for the task M. The stronger correctness property is needed since applying Lemma D.3 might otherwise ruin the correctness of our algorithm.
To build such transformation, we will use the following DP Selection algorithm also used as the main subroutine in the standard stability-to-DP transformation of prior works (Bun et al., 2020; Ghazi et al., 2021b; Bun et al., 2023).
Theorem D.4 (DP Selection (Korolova et al., 2009; Bun et al., 2016; 2018), as stated in (Bun et al., 2023)). There exists some e > O such that for every s, 5 > 0 and m E N, there is an (s, 6)-DP algorithm that on input S E X outputs with probability 1 element X that occurs in S at most clog 5-1
fewer times than the mode of S.
e
We state and prove our bounded support, strong correctness stability-to-Di transform:
Lemma D.S. Let M be statistical lask, n, 5 > 0, and T 0
[oo((1/) ). Given v-globblll stable algorithm Afr
M on n = n(3) samples, there exists T-user (e, 8DDD algorithm ADp on n' = n(e, 5, B) samples satisfying:
1. Bounded Support: YS (Supp(ADr(S:))) ST
2. Strong Correctness: Prs-
Gpl>>> BB'
loe and n' S ((3) 1og(1/9))og(1) for 3 s 02
1
Proof. By assumption we are given access to a f-confident algorithm A on = =33) samples that has an 17-heavy hitter ht. In order to ensure strong correctness, we will first need to transform A into so-called "list-replicable algorithm Aria, that is one such that there exists a small list C GD of correct hypotheses such that for a large enough m:
Pr [ALia (S) E L. 2 8.
SwDm
Assume 3
n1/ (else the Lemma statement is trivial 8' > 1). Then every heaih of A must lie in GD- fresh samples and outputting the most common result. By standard
We build ALis by simply running on O lox( concentration (Kontorovich & Painsky, 2024), the probability that the output of this procedure is not n/ n/2- 22hhevyy hitter of A (of which there are at most? ?)) is at most as desired, and the algorithm uses at most m = O(n (og(1/8) samples.
x/ah
We will now use ALis to generate dataset of output hypotheses on which to apply DP selection. More formally, fix some arbitrary 'dummy' output y E } (we use this to ensure the end support is bounded) and consider the following procedure generating dataset to run DP- DP-Selection:
1. Draw T T= =0 (og((1/))
independent size-m samples from D
ms
19

---

The Role of Randomness in Stability
2. Add the output of Aiit on every sample in T to the dataset
3. Add clog & copies of y for e as Theorem D.4.
Finally, define ADp(S) to be the algorithm that outputs the result of DP-Selection on the above dataset.
We first analyze correctness. Note is enough argue that with probability at least 1- 3", the support is contained in L, since L C GD. By Theorem D.4, the only way the support of (DP(S) contains hypothesis outside L is if A outputs h $ T, in Step 2 at least O(log(1 /6) times. Since the samples are independent, the probability of this occurring is at most
( 8d ST T-
25 7
O(log(1/5)/s)
Σ
(=0((o((//)))))
as desired.
It is left to bound the (user-level) differential privacy and support. is clear the algorithm is Tusser (c, 6)-DP by construction, taking each user's data to be full sample given to Alia in Step 2. Furthermore, because the generated dataset always has a hypothesis appearing more than clog J times by construction, Theorem D.4 promises the output lies in the constructed dataset which has size at most T as desired.
The forward direction of both Theorem D.1 and Theorem D.2 are now essentially immediate:
Proof of Theorem D.I and Theorem D.2 (Item 1). Write C Cn () for notational simplicity, and let A be the promised 2 2-C++--loball) -globally stable algorithm. By Lemma D.5, can convert A into T-user (E.6 algorithm App on samples with T S O 2Cas. log(1/6) such that for all S, [Supp(A(S:-)) < T, and with probability at least 1- 3, 3, (upp(App(S::)) C Gp. Applying Lemma D.3 with 5/2 then gives the desired result, where correctness is maintained since the output of the algorithm on any sample S where Supp(Anr(S::)) C GD remains entirely inside Gn by the subset support property.
We now move on to the reverse direction of both results, which follows from the equivalence of approximate diffcrential privacy with another strong notion of stability known as perfect generalization (Cummings al., 2016; Bassily & Freund, 2016; Bun et al., 2023; Ghazi al., 2024).
Definition D.6 (Perfect Generalization (CCummings et al., 2016; Bassily & Freund, 2016))). Fix e, > 0. An algorithm A: Xm + > is called (8, pelpfeecttyy-ggeeraiiiigg if for any distribution D over X, there exists a "canonical distribution' SIMp s.t.
Pr (A(S) (c.6) SIMp] 2 1 3 S
In (Ghazi et al., 2024), the authors show any sufficiently DP algorithm is automatically perfectly generalizing. Theorem D.7 ((Ghazi et al., 2024) (Theorem 31, rephrased)). There exists a universal constant >> such that if A T-user VTlog(ry' DDPD, then A is (5,, 5, -peerfecyyl generalizing. Moreover SIMp p can be taken to be the distribution A(,,), laken over samples and internal randomness.
We remark that as written Theorem 31 in (Ghazi et al., 2024) is only stated for item-level DP, but the result follows immediately from viewing the user-level DP guarantee as standard DP over input space X"/T,, Combined with Theorem B.2, it is then elementary to move from DP to global stability:
Proof of Theorem D.I and Theorem D.2 (Item 2). The proof is exactly the same for Theorem D.1 and Theorem D.2, with the exception that we do not need to handle sample and confidence decay in the latter. We therefore argue just the former.
By assumption,
given 3' -'-oofiide (e, 8)DP DD algorithm A on l CDp(n', 8 ,',,,)) random bits and n' samples whose privacy parameters meet the requirements of Theorem D.7. A is therefore 5,...).. generalizing with
Formally there may be some other measure set of outputs given the exact statement of Theorem D.4, but these can be safely removed with no loss in parameters since we are the approximate DP setting.
20

---

The Role of Randomness in Stability
respect to A(++). Fix an input sample S where A(S,-) -) is (.5, -5)-close A(s-). Write L Supp(A(S,) :), and observe have the trivial bound [T|] < 24. On the other hand, distributional closeness implies
= Pr[A(S.-) E S Pr (A(S,)) + 2 S-D",
and re-arranging, that
Pr (A(S,)) E 2 2e1/2" Sr
Thus A has 2/ heavy-hhavv. We may now apply our parametrized heavy-hitter to globally stable conversion
(Corollary B.3) to convert A to a conconiee deterministic globally stable algorithm on n = =n'= Ō log(1/8)
samples for
s (() desired.
E. The Stable Complexity of Agnostic Learning
In this section we bound the certificate complexity of PAC-Learning, resolving a main open question of (Chase et al., 2024) (stated in the equivalent language of global- staiiittiiiisstteepichhhiiii We restate the theorem here for convenience.
Theorem E.1 (Certificate Complexity of Agnostic Learning). Let (X, H) be a hypothesis class of Littlestone dimension d. There exists a 3-confident better than 1 --replicable learner with
1. Sample Complexity: m(a, (3 S exp(poly(d)) poly(a, log(1/B))
2. Certificate Complexity: (xep((x) S poly(d) + O(VC((H) =
Moreover, if = 00, CRep(a) = xo every a <
Our proof is inspired by (Bun al., 2023)'s version of (Hopkins et al., 2022)'s tottzabll--o-agoosiii reduction for replicable learners. (Bun al., 2023) cannot be used directly due its substantial reliance on additional randomness (indeed they actually have randoness scaling not only with confidence 8, but with the size of the concept class H which may be infinite in our case). Nevertheless, we build off the core idea, which uses the following realizable-case 'list-stable' learner of (Ghazi et al., 2021a;b):
Theorem E.2 (Realizable List-Stable Learning (Ghazi et al., 2021a;b)), Let (X, H) be hypothesis class of Littlestone dimension d. There exists a algorithm on n(a,3) S poly(d, d, a, lo)(1/3)) samples which outputs a list of a-accurate hypotheses of size at most exp(poly (d))a- -0)) with probability at least 3. Moreover, for every distribution D, the list has S1(1 /d) -dy-heavy-hiter ie,, some hypothesis hn such that
Pr(hD A(S) Ω (
Given the above, the core idea to run this list-stable learner over all possible labelings of large enough unlabeled data sample and return commonly appearing element with high accuracy the agnostic distribution. This results in randomized learner with good heavy hitter, which can then be converted to globally stable learner by Theorem B.2 and finally replicable learner with good certificate complexity by Theorem C.I.
Proof of Theorem F. I. Fix 3' = exp(poly(d)a 0(1) to be sufficiently smaller than the list size from Theorem E.2 and let A be the corresponding promised learner. Consider the following process generating list of potential hypotheses from A::
1. Draw T log(1/3) unlabeled samples of size ((a/8,88) B") from D. denoted S
2. Run over all labelings of each s(i in the class and denote the resulting hypothesis (multi)set
C(Sy) = (A(S() Ms( E H, i [T]}
We remark this is not quite stated in (Ghazi al., 20221), which only claims exponential dependence on However, polynomial dependence as stated here is immediate from (Ghazi et al., 2021a)
21

---

The Role of Randomness in Stability
Note that by Lemma A.13, the size of C(Su) as a multiset is at most
IC(Su)] s 8t exp(poly(d)) - polly(d, -0a)) exp(poly(d)). (xppot)))))pp)))
The idea is now that C(Sv) should contain many copies of a heavy hitter from the output list of some optimal labeling hoPt (which furthermore must be a/2-correct by our confidence assumption). The only issues are 1) C(Sv) may also contain many bad hypotheses, and 2) [C(S)) ) currently depends on T' (which depends on the confidence $), so is too large for our purposes. We can fix both of these problems via a pruning step that removes any high error or non-heavy-hitter hypotheses. Denote by whh) the number of times h appears in C(Sv), ), and consider the following procedure:
1. Draw new labeled sample Sy, of log [C(S6)]+oo
samples
0²
2. Remove any hypothesis h E C(Sv) with high error or low empirical probability:
Pruned(C(So)) = { Th ((S)) :erss)))rssul (h) S min errsz (h') WEC(Su)
3 and w(h) 2 T d
4
3. Output random hypothesis in Pruned(C(Se))
where d' O is some constant to be chosen. Note that now, by construction, Pruned(C(Se)) has at most poly(d/a) VC(H) exp(poly(d)) hypotheses since at most this many can appear 22(T/d) times.
We now argue correctness and (heavy-hitter) global stability of the procedure (certificate complexity will then follow from Theorem B.2 and Theorem C.I). By standard uniform convergence bounds, we have that with probability at least - 3/2 the empirical and true error of every h E C(Su) are close:
(errD(h) errs, (h)) S
Conditioned on the above, correctness follows as long as C(Su) actually contains good hypothesis:
min MEC(SU)
ertsy (h') < OPTD
since pruning then only keeps hypotheses with empirical error at most Fa and therefore of true error at most a as desired.
In fact we will argue not just that this event occurs with probability at least 1 - -3/2, but that there exists a fixed a/8-optimal hypothesis to that appears with this probability. Since our final algorithm outputs a random hypothesis in Pruned (C((e)(((S))) (CS))) )), this implies both our desired accuracy and global stability. To see this, fix some optimal hypothesis ho in the class, and observe that the original set C(Sg) contains T independent runs of A on samples labeled by hoPT (since we run over all labelings). A is promised have an o88-optimal 12(1 / d))-hevv-hitter hp with respect the distribution Dx hort where the marginal over data is given by D and the labeling is given by horr. As result hD itself is a-optimal with respect to the true distribution D. Moreover, since T poly (d, log(1 (1/ B)), a standard Chernoff bound implies hn appears at least d'T/d times with probability at least 1 - 3/2 for the appropriate choice of constant c' > 0, completing the argument.
The above analysis promises the given algorithm is 3-correct and has an ((cxp(poly(d))a convert this into the desired replicable learner using Theorem B.2 and Theorem C.I with sample overhead at worst polynomial in the stability parameter as desired.
hitter. We can
It is left show that when d co, there is no replicable (equivalently, globally stable) learner with better than error. To see this, first observe that replicable agnostic learner with better than error implies replicable learner in the realizable case with better than 1 еrгor. By (Impagliazzo et al., 2022), this can be boasted to a replicable realizable learner with arbitrary error a, then transformed to a differentially private one by standard cubblity-ttoprivacee reductions (e.g. (Bun et al., 2020) or the transforms presented in this work). The existence of this final learner then violates the impossibility of private realizable learning of infinite Littlestone classes (Alon et al., 2019), completing the proof.
22

---

The Role of Randomness in Stability
F. Amplifying Replicability
particularly useful property of replicability that it can be easily amplified. the main body, we implicitly gave a randomness-efficien procedure to amplify better than replicability to any p based on converting to and from global stability, Here, we give a randomness inefficient but sample-efficient transform with the added benefit of starting from any starting replicability parameter The transform is similar that in (Kalavasis al., 2023) for so-called iiniiisstinguihaall algorithms, but has improved sample complexity.
Lemma F.1 (Generic Amplification of Replicability). Fixv, O, and let be an (1- replicabl,, 3-correct algorithm on n(v, B) samples. For any p O. there exists an efficient blackbox procedure amplifying A to p-replicable, 3' corrrtt algorithm A' on n DF
1og(1/3) samples for 3 S Ō (8 (og(1/1)
Proof. Since A is (1 - 2) -eerellbabbll, by Markov's inequality there must be at least a 2-frr-ction of A's random strings for which the distribution A;r) r) has an (vv/2)-heary hheyy-yhhhe Draw a set of O (log(1/) random strings. The probability that at least one drawn string has (v)/2) (eea))eaaa--iiiee hitter is at least 1 - (1 2/2) 2 1-p/2.
Condition on this event and consider the algorithm which, given a sample S, outputs a list containing the result of A on S across all random strings T:
M(S) = (A(S:))
By assumption, M satisfies the following properties, together called "list-stability" (Ghazi al., 2021b; Bun al., 2023):
1. (S) Outputs a list of size
[T'
2. 3h s.t. h (S) with probability at least (1r).
3. With probability at least 3' = (T) all are correct.
We now appeal to Theorem 6.7 in (Bun et al., 2023), which gives p/2-replicable procedure that runs M on
m = Ô @ (bo8(1/3) p2u²
independent size-n samples, and outputs some hypothesis lying in one the resulting (S) with probability at least 1- By union bound, all such hypotheses are correct except with probability [T' mm,, and the entire procedure is p-replicable desired.
H0Her Ô hides (at most cubic) logarithmic factors and v.
23


Reviews:
[{"review_id": "Eyxv0zxmf9", "reviewer": "Reviewer_poww", "summary": "This paper studies a type of stability for algorithms and its connections to differential privacy (DP). It is argued that such stability requires randomization of the algorithm, and results are given for translating between different measures of complexity. The theoretical results are explained with intuition, and proof sketches are given in the main text with complete proofs in the appendices.\n\nI am not familiar with this field, so my lower score mostly reflects a lack of confidence.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and questions and will make all suggested fixes\n\nWe hope the below clarifications (and positive impressions of the area expert reviewers) raises the reviewer’s confidence in our work, and respectfully ask they consider using the confidence score rather than a lower main score to reflect any remaining lack of confidence due to field familiarity.\n\n**Q1:** “The idea that randomness is required for stability is not self-evident.  I don't understand how an interpolation argument would apply.”\n\n**A1:** Good catch. The footnote only formally makes sense for DP (where “similar” means trading out one example in your discrete data-set, so one can always interpolate by trading out points one by one). In replicability, the argument is similar but one interpolates in *parameter/distribution-space*, not over samples. We will clarify this in the text.\n\nFor example, consider estimating the bias of a coin. The data is discrete (coin flips), but the underlying set of distributions (biases $p \\in [0,1]$) is continuous. Our interpolation is over p. A deterministic replicable algorithm has a single canonical output w.h.p for every $p \\in [0,1]$, but cannot distinguish between close p and p’. Since we can interpolate between any $p,q \\in [0,1]$, the algorithm must have the same canonical solution everywhere so is essentially constant.\n\n**Q2:** “Thm 2.2 gives a result in terms of failure probability $\\beta$ vs $\\beta’$… the blowup in lack of confidence doesn't seem so mild to me”\n\n**A2:** This type of blowup is considered mild in the literature because almost all statistical problems have complexity scaling in $\\log(1/\\beta)$ due to Chernoff. This means one does not really lose significant generality assuming the initial algorithm has small $\\beta$. More generally, we can usually amplify a constant success algorithm to $1-\\beta$ success just by repeating it $\\log(1/\\beta)$ on independent samples and taking the best output. We will clarify this in the text.\n\nIt is also worth remembering $C_{\\text{glob}}$ is log scale, so, combined with the above, the blowup we incur is only, e.g., $loglog(1/\\eta)$ for $\\eta$-stability, which is mild even when $\\eta$ is exponential (as in PAC Learning).\n\n**Q3:** “Can you better motivate the particular definition of stability for people who are not familiar with this area?”\n\n**A3:** Absolutely. This critical question has been discussed extensively in prior work (e.g. in Impagliazzo et al.). We’ll summarize here and add discussion in the paper as well as on weaker stability notions. We’ll focus on replicability, since presumably DP (widely adopted in industry and hugely impactful in theory) does not need more motivation.\n\nReplicability comes with a substantial list of advantages due to requiring truly equal outputs. Here is a representative sample:\n\n1) Replicability is *closely related to other core notions of stability in computer science* (DP, adaptive data analysis, and more, see e.g. “Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization” or “The Bayesian Stability Zoo”). Several open problems in DP (sample-efficient user-level DP, amplification of DP) were resolved through studying replicability.\n\n2) Replicability is *testable*. It is not always easy to test whether an algorithm is stable (e.g. testing DP is known to be computationally hard). By requiring equivalence, replicability is trivially verifiable.\n\n3) Replicability is *preserved under arbitrary post-processing*. One can apply any desired algorithm to the output of a replicable procedure, and the result will always remain replicable. This is an extremely useful property in algorithm design.\n\n4) Replicability is *easily amplified*. Given a constantly replicable algorithm, there is a simple and computationally efficient procedure to amplify it to arbitrarily high replication probability.\n\n5) Replicability is *model independent*. Different statistical tasks naturally have different notions of weak stability and closeness, or, in the case of testing problems with binary outputs, may have *no* natural notion of weak stability (see “Replicability in High Dimensional Statistics” or “Replicable Uniformity Testing” for a discussion of replicability in these settings). Replicability gives a **unified definition** for studying stability for all statistical tasks. \n\nIt is also critical to understand when replicability is possible, and its overhead compared to weaker notions of stability. This has been the topic of a substantial number of works, and efficient replicable algorithms are known for many tasks (statistical queries, hypothesis testing, mean estimation, RL, learning large margin halfspaces…). This is not the main focus of our work, but we feel combined with the above more than justifies the study of replicable algorithms.\n\n**Q4:** Could you shorten the abstract?\n\n**A4:** We’ll shorten the abstract in the next version to be less repetitive with the intro.", "claims_and_evidence": "Most claims are theoretical; see below.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "Overall, the results sound fairly reasonable to someone who isn't an expert. I did not check the correctness of the proofs in the appendices.\n\nA few things stood out to me, however:\n* The idea that randomness is required for stability is not self-evident, even after reading footnote 1. In many cases data are discrete (say inputs are binary strings) so I don't understand how an interpolation argument like that given here would apply.\n* Thm 2.2 gives a result in terms of failure probablity $\\beta$ versus $\\beta'$. Since the confidence takes the form of a probablity $1-\\beta$ (line 071), it would seem to me that your results could easily become vacuous if that grows exponentially as in Thm 2.2 (parts 1 & 2). In other words, the blowup in lack of confidence doesn't seem so mild to me.", "experimental_designs_or_analyses": "The authors did not perform any numerical experiments.", "relation_to_broader_scientific_literature": "I am not familiar with this literature, so I don't have much to add. However, it would be good for the authors to address other kinds of stability, e.g. that used in numerical analysis and its differences from the current form in the introduction.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The claim that \"stability,\" in the colloquial sense, is important for algorithms seems self-evident. However, I have a philosophical quibble with the form of stability that the authors study here. My background is applied mathematics and I'm familiar with the type of stability studied in numerical analysis where the output of an algorithm is required to be close for close inputs. In the current work, the authors require the output to be the *same* for different inputs, which seems a very strong requirement. It would help convince people with backgrounds like mine if the authors would motivate better why they've chosen such a strong type of stability. In my opinion, requiring the exact same outputs for different datasets is more than anyone practically would want, but I'm willing to admit I could be wrong.", "other_comments_or_suggestions": "* $\\rho$-replicable definition: the distribution for $r$ is never stated\n* line 084 col 2: $\\ell$ is never defined\n* line 088 col 2: \"$\\ell$-random\" should be \"$\\ell$ random\"\n* explicit formulae for $C_\\mathrm{Rep}$ and $C_\\mathrm{Glob}$ should be given in the main text\n* Thm 2.2: In item 2 (DP to stability) it seems like the prime on $\\beta$ is swapped from where it should be; is this a typo?\n* line 240 col 2: \"tower-type dependence\" this wasn't familiar to me, you might want to explain what you mean by this\n* line 348 col 1: there is a typo with the first argument missing from $\\mathcal{A}_\\mathrm{Rep}(;r)$", "questions_for_authors": "* Can you better motivate the particular definition of stability for people who are not familiar with this area?\n* Could you shorten the abstract? It is very long.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xjx0wnFWpF", "reviewer": "Reviewer_6PrE", "summary": "The authors study the randomness complexity of private and replicable algorithms, showing that this complexity is tightly related to the best global stability parameters of an algorithm for the same task. Letting $\\eta_M$ be the best achievable replication probability for a deterministic algorithm solving problem $M$, they define the globally-stable complexity of a problem, $C_{Glob} = \\log \\tfrac{1}{\\eta}$. They then show that the certificate complexity of $M$ is lower-bounded by $C_{Glob}$ and upper-bounded by $C_{Glob} + 1$. The similarly give upper and lower bounds on the DP complexity of a problem $M$ by a function  of $C_{Glob}$ and privacy parameters $\\varepsilon, \\delta$. Finally, they show that the certificate complexity of agnostic PAC learning for classes with finite Littlestone dimension (ensuring they are replicably learnable) is $poly(d) + O(VC(H)\\log(1/\\alpha))$. Thus, the certificate complexity for agnostic PAC learning resembles that of realizable learning, up to O(VC(H)) factors.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our work and helpful comments (we will fix the minor issues noted).\n\nThe trade-off between sample and randomness efficiency is a very interesting question, and is not well understood even for the most basic examples (see e.g. “Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma” and “The Randomness Complexity of Differential Privacy”). Our transformations have an overhead scaling polynomially in the stability parameter, which can be efficient for low-dimensional problems but is indeed costly in settings like PAC learning. In the PAC case, this can be circumvented when one does not care about randomness by looking at certain variants of global stability, and it would be interesting to understand if there is an inherent trade-off here. However, given the substantial difficulty in resolving this problem even for, say, estimating the bias of d coins, we feel this is reasonably outside the scope of our work.", "claims_and_evidence": "All claims are supported with proof.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not go carefully through the proofs in the appendices, but the explanation of proof approach is clear enough that they imply the stated results.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The authors do a very thorough job of connecting their results to the existing literature, highlighting how their work extends prior work on DP complexity, certificate complexity, and answers open questions regarding agnostic learning raised in prior work.", "essential_references_not_discussed": "All essential references are discussed.", "other_strengths_and_weaknesses": "The paper was very well-written and a pleasure to read. The results represent a significant contribution to our understanding of the randomness complexity of stable algorithms.\n\nOne weakness (acknowledged by the authors) is the fairly significant tradeoff between sample and randomness efficiency in the results. The randomness complexity is likely to be a secondary or tertiary consideration in most applications, after sample and computational complexity, so understanding the randomness complexity of sample and/or computationally efficient stable algorithms seems like the kind of result we’d really love to have. This is of course a much more significant ask (particularly the computational efficiency piece).", "other_comments_or_suggestions": "Page 3 - Double close parens in the first paragraph after Theorem 2.1\n\nIn the text preceding Theorem 2.3, I was a bit confused about what happened to the confidence parameter in moving from DP to user-level DP, until I got to the appendix. \n\nPage 4 - “Not only is such a bound is possible”\n\nPage 7 - “occurring probability”", "questions_for_authors": "No questions for the authors.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KpQKvtEwAZ", "reviewer": "Reviewer_jLTx", "summary": "This paper addresses the randomness complexity of an algorithm: how many random bits an algorithm requires to satisfy certain property. Two properties are studied: replicability and differential privacy. It is shown that the randomness complexities of these properties are closely connected to the global stability of the algorithm. The latter can be formulated as a property of a deterministic algorithm. Two main results follow from the boosting from deterministic globally-stable algorithms to replicable or private (necessarily) randomized algorithms.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our work and helpful comments. We will make the suggested minor fixes.\n\n*Regarding the end of the proof of Thm B.2:*\n\nThe $L$ in line 771 is a typo and should be $L_D$, our apologies. The point here is to bound the measure of the set of samples $S$ on which $A_{\\text{List}}$'s majority output is not in $L_D$; in particular, we want to show this bad set has measure at most $\\frac{2\\gamma}{\\eta}$.\n \nTo see this, we observe that for any *fixed* sample S whose majority output is not in $L_D$, it must be the case that $A_{\\text{List}}(S;\\cdot)$, over the randomness of $r$, outputs a hypothesis *outside of* $L_D$ with probability at least $\\eta/2$. But then if there is a $\\frac{2\\gamma}{\\eta}$ measure of such samples S, the overall probability that $A_{\\text{List}}$ outputs something outside of $L_D$ (now over the randomness of both S and r) is more than $\\gamma$. This contradicts $A_{\\text{List}}$’s list-replicability (the guarantee on Line 752) and completes the proof.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I checked results in Appendix B in detail. Modulo clarity of expositions, the theoretical claims are correct.", "experimental_designs_or_analyses": "Not applicable", "relation_to_broader_scientific_literature": "This work contributes to the recent line of research on randomness complexity of stable algorithms. While prior results (e.g. Canonne et al., 2024) look at particular algorithmic tasks, this work provides a general equivalence between stability properties, such as global stability, replicability and differential privacy.", "essential_references_not_discussed": "Not to the best of my knowledge.", "other_strengths_and_weaknesses": "The paper is well-written and provides an important contribution by showing a sharp relation between fundamental algorithmic properties.\n\nA weakness: Theorem 2.3 only considers the high-privacy regime ($\\varepsilon = O(1 / \\sqrt{n' \\log n'})$).", "other_comments_or_suggestions": "Line 774: should be $C_{\\mathrm{Glob}} \\leq \\log \\frac{1}{\\eta}$", "questions_for_authors": "Please clarify the end of the proof of Theorem B.2. For example, what is $L$ in line 771?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Xe2WWl4v0W", "reviewer": "Reviewer_3UmF", "summary": "This paper studies the notion of stability, which is defined (through various definition) as the probability of an algorithm to give the same result on two datasets sampled from the data distribution. More precisely, the authors aim at quantifying the amount of randomness needed to achieve stability, as randomness has been commonly seen as an important factor for stability. \nThe amount of randomness is considered in two settings (replicability and differential complexity) through two notions of \"randomness complexity\", namely certificate complexity and DP complexity, which have been introduced in prior works. \nThe two main results are to provide tight guarantees of these two notions of randomness complexity in terms of the globally-stable complexity, which quantifies the probability of a deterministic algorithm to output replicable results.\nThe authors then apply their framework to PAC-learning, for which they characterise the certificate complexity and the sample complexity of an algorithm achieving at least $\\frac1{2}$-replicability.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our work, comments, and questions. Below we clarify a few possible misunderstandings about our definitions, explain our writing choices, and discuss several minor modifications we will make to address the reviewers concerns: \n\n**Q1: Missing Definitions** We respectfully disagree that there are substantial missing definitions in the paper (outside of Littlestone dimension which we chose to exclude for reasons explained below, but will include in the next version). \n\nThe term “shared randomness” refers informally to the random string $r$ in the definition of replicability — it is not a standalone definition. Replicability promises that over independent samples $S$ and $S’$ and the *same random string* r:\n\n$Pr_{r,S,S’}[A(S;r)=A(S’;r)] \\geq 1-\\rho$\n\n$r$ is usually called the “shared randomness” since it is used in both runs of A. This is the standard way to express this notion in the literature — it is not usually defined on its own. There is, however, a confusing typo after this equation regarding the domain of $r$ for which we sincerely apologize. The sentence “the smallest $\\ell$ s.t. there exists a better than $\\frac{1}{2}$-replicable algorithm solving $\\mathcal{M}$” should say “solving $\\mathcal{M}$ *using $\\ell$ random bits*”. We will fix this and clarify the domain in the text.\n\n*Regarding Littlestone:* the connection between Littlestone dimension and stability is very involved and largely orthogonal to our work. We do not use the definition in any of our proofs, so excluding it should not make any of our results harder to check. We use as a blackbox that any finite Littlestone class has a globally stable realizable learner (see Thm E.2). Our contribution thus has very little to do with Littlestone dimension, and we thought including the definition would only confuse readers as its connection to stability is fairly mysterious without deep knowledge of prior work.\n\nThis said, we absolutely see the reviewer’s counterpoint that stating the definition and (perhaps more importantly) giving concrete examples would help the unfamiliar reader understand what types of classes Thm 2.4 applies to. We will include these in the text (see Q2 below) as well as add references to prior work discussing the above in more detail.\n\n**Q2: Concrete Examples** There are many nice examples of classes with finite Littlestone dimension to which Thm 2.4 applies. Two classical examples are affine subspaces in $\\mathbb{R}^n$ (or more generally algebraic varieties), and half-spaces with margin (semialgebraic varieties with margin). Thm 2.4 gives the first randomness-efficient stable learners for both of these families. We will add discussion of this in the text.\n\n**Q3: Thm 2.4, Dominating Term**. This depends on how good accuracy you want, but if one only wants (say) 99% accuracy over the data, the first term will always dominate (e.g. this term would be polynomial in the dimension of the affine subspace).\n\n**Q4: Continuous Output Spaces** we do not make any assumptions about the output domain of $\\mathcal{A}$. However, it is true that if the output distribution of $\\mathcal{A}(\\cdot)$ is continuous, then $\\mathcal{A}$ is not globally stable for any $\\eta>0$. The definitions we consider measure the performance of the *best* algorithm over the domain/output, so this is not an issue for working over uncountable and non-discrete domains.\n\n**Q5: Relation to [BE02]** Replicability and Differential Privacy are only loosely related to the classic stability notions of [BE02], which are generally much weaker (e.g. these notions can be satisfied for any VC class, whereas DP and replicability cannot). It is true there are some connections: e.g. replicability implies generalization by a similar Hoeffding-style argument, and uniform stability [BE02] is related to a substantial relaxation of DP known as private prediction. To the best of our knowledge, however, there is no real formal comparison between [BE02] and the models we study, though the work is certainly worth mentioning as a seminal investigation into stability in learning.\n\n**Other Writing Comments**: Our citation style in the abstract is a conscious choice ensuring all authors of the major relevant papers are listed (the ICML citation format does not seem to allow this directly). This is because theory papers have alphabetical author order and all authors should be credited equally. We also note it is relatively common for theory papers to have a “discussion/open-problem” section as we do rather than a traditional conclusion and respectfully disagree this is an indicator of poor writing.\n\nThis said, we do agree the abstract is on the long side for the ICML format and repetitive with the intro, so we will shorten it as the reviewer suggests and ensure the early definitions are as clear as possible.", "claims_and_evidence": "The main claims are (i) tight bounds of certificate complexity and DP complexity in terms of globally-stable complexity and (ii) a characterisation of the certificate complexity of PAC learning in terms of the Littlestone dimension.\n\nThese claims are supported by proofs in the appendix and sketches of proofs are provided, which improve the readability of the paper.\n\nHowever, several concepts such as Littleton dimension or share random bits are not defined formally in the paper (please correct me if I am wrong). As I am not an expert in this literature, it makes the statement look a bit informal and it is hard to assess their correctness.", "methods_and_evaluation_criteria": "The proposed proof strategies, based on boosting theorems for stability, make sense for the problem at hand.\n\nMost result are rather abstract, the clarity could be greatly improved by providing an instantiation of the results on a more practical/explicit example.", "theoretical_claims": "The authors provide in Section 4 an overview of the technical elements involved in their proofs. However, I did not check the proofs in the appendix carefully, as it is a bit far from my expertise.\n\nI find it confusing that several concepts, such as Littleton dimension, are not formally define in the text. I makes it hard to check the results and to get intuition about them. Adding a definition in the appendix could improve the clarity for readers that are not used to these notions.\n\nI had one general remark about the framework: The complexity notions are defined via statements of the form $\\mathrm{Pr}(\\mathcal{A}(S) = \\mathcal{A}(S')) \\geq \\eta$. Does this kind of definition implicitly assume that $\\mathcal{A}$ takes values in a finite or countable space. For instance, if the hypothesis class is $R^d$ (eg, for stochastic optimizers such as SGD), then $\\mathcal{A}$ could have a continuous PDF and the previous probability would always be 0. In general, I think the introduction of these notions could be made more formal (the notion of shared random bits is not clearly introduced in my opinion).\n\nMinor remark: the notation $\\mathcal{X}^\\star$ is not defined.\n\nAt line 156 (second column), shouldn't the denominator be $\\eta^3 \\epsilon$?", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper is strongly related to existing literature on stability, certificate complexity and DP complexity, which have all been relatively recently introduced.", "essential_references_not_discussed": "I think a comparison with the literature of algorithmic stability (eg, Bousquet & Elisseeff, 2002) could be beneficial, as it is also quantifying the similarity of the output of the algorithm on similar dataset. Algorithmic stability is a major tool in the modern study of generalization error in learning theory and it would be beneficial to discuss it quickly, if it is relevant.", "other_strengths_and_weaknesses": "The writing could be largely improved in my opinion, here are a few comments:\n\n - the first two paragraphs of the abstract and of the introduction are almost copy past of each other.\n - The abstract is very long (half a page), reducing it would improve clarity\n - Some citations, especially in the abstract, are not written using the standard bibliographic tools in latex but instead written in plain text in a format that is not consistent with the other citations. It makes it look like the paper is not finished.\n - some formulations are a bit informal, e.g., \"taking a minute to explain\",  \"we'd also like\", \"an astronomical number of\"\n - the paper has no conclusion\n - the section \"further related works\" seems to repeat several things already discussed in the introduction, in general a small part of the paper is dedicated to the presentation of the main result. I believe it would improve the clarity to compress a bit the related works to include more technical background on the mathematical setup.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. In the certificate complexity bound of theorem 2.4, which term is typically dominating in practice?\n\n2. The results, while interesting, are presented in a quite abstract way, could it be possible to apply them on more explicit examples, like a specific classification setting for PAC-Learning?\n\n3. Are there formal links between your stability notions and the algorithmic stability that is classically studied in learning theory.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a randomness complexity theory for PAC learning under two popular notions of algorithmic stability: replicability and differential privacy. After discussions, the reviewers unanimously agreed that this is a theoretically solid paper that reveals some new and important connections between algorithmic stability, replicability and differential privacy. In their intial reviews, the revidwers also expressed some minor concerns regarding the significant trade-off between sample and randomness complexity in the results, as well as the writing quality which I agree still has room for improvement. The authors managed to address some of these in their thorough responses. Overall, this is a nice learning theory paper worth to be accepted for presentation at ICML 2025. The authors are encouraged to make the promised changes in the camera-ready version to address the reviewer's comments as much as possible.
Decision: Accept (spotlight poster)