On the Computational Landscape of Replicable Learning
Authors: Alkis Kalavasis
Amin Karbasi
Grigoris Velegkas
Felix Zhou
Venue: NeurIPS 2024 poster (2024)
Keywords: Statistical Learning Theory
Replicability
Reproducibility
Primary area: learning_theory
TL;DR: We study computational aspects of algorithmic replicability with the aim of better understanding the computational connections between replicability and other learning paradigms.

Abstract: We study computational aspects of algorithmic replicability, a notion of stability introduced by Impagliazzo, Lei,
Pitassi, and Sorrell [STOC, 2022]. Motivated by a recent line of work that established strong statistical connections between
replicability and other notions of learnability such as online learning, private learning, and SQ learning, we aim to
understand better the computational connections between replicability and these learning paradigms.
Our first result shows that there is a concept class that is efficiently replicably PAC learnable, but, under standard
cryptographic assumptions, no efficient online learner exists for this class. Subsequently, we design an efficient
replicable learner for PAC learning parities when the marginal distribution is far from uniform, making progress on a
question posed by Impagliazzo et al. [STOC, 2022]. To obtain this result, we design a replicable lifting framework inspired by
Blanc, Lange, Malik, and Tan [STOC, 2023], that transforms in a black-box manner efficient replicable PAC learners under the
uniform marginal distribution over the Boolean hypercube to replicable PAC learners under any marginal distribution,
with sample and time complexity that depends on a certain measure of the complexity of the distribution. 
Finally, we show that any pure DP learner can be transformed in a black-box manner to a replicable learner, with time complexity polynomial in the confidence and accuracy parameters, but exponential in the representation dimension of the underlying hypothesis class.

On the Computational Landscape of Replicable Learning
Alkis Kalavasis
Amin Karbasi Yale University amin.karbasi @ yale.edu
Yale University
alvertos.kllvvsiii@akeeek.
Grigoris Velegkas
Felix Zhou
Yale University
Yale University
grigoris..elegkas @aaeeeleegga@@@@e..... yale.edu
felix.zhou @ yale.edu
Abstract
We study computational aspects of algorithmic replicability, a notion of stability introduced by Impagliazzo, Lei, Pitassi, and Sorrell [2022]. Motivated by recent line of work that established strong statistical connections between replicability and other notions of learnability such as online learning, private learning, and SQ learning, we aim understand better the computational connections between replicability and these learning paradigms. Our first result shows that there is a concept class that is efficiently replicably PAC learnable, but, under standard cryptographic assumptions, no efficient online learner exists for this class. Subse- quently, we design an efficient replicable learner for PAC learning parities when the marginal distribution is far from uniform, making progress on question posed by Impagliazzo et al. [2022]. To obtain this result, we design replicable lifting framework inspired by Blanc, Lange, Malik, and Tan [2023] that transforms in a black-box manner efficient replicable PAC learners under the uniform marginal distribution over the Boolean hypereube replicable PAC learners under any marginal distribution, with sample and time complexity that depends on certain measure of the complexity of the distribution. Finally, show that any pure DP learner can be transformed to a replicable one in time polynomial in the accuracy, confidence parameters and exponential in the representation dimension of the underlying hypothesis class.
Introduction
The replicability crisis is omnipresent in many scientific disciplines including biology, chemistry, and, importantly, AI [Baker, 2016, Pineau et al., 2019]. A recent article that appeared in Nature [Ball, 2023] explains how the reproducibility crisis witnessed in AI has cascading effect across many other scientific areas due to its widespread applications other fields, like medicine. Thus, a pressing task is to design a formal framework through which we argue about the replicability of experiments MI. Such an attempt was initiated recently by the pioneering work of Impagliazzo al. (2022), who proposed definition of replicability a property of learning algorithms.
Definition 1.1 (Replicable Algorithm; Impagliazzo et al., 2022). Let R be distribution over random strings. A learning algorithm A is n-sample p-replicable under distribution D if for two independent sets S' n it holds that Prs,s (r. (A(S.r) # A(S', ,)) S p. We will say that A is replicable if the above holds uniformly over all distributions D.
We emphasize that the random string is shared across the two executions and this aspect of the definition is crucial in designing algorithms that have the same output under two different i.i.d. inputs. Indeed, both Dixon et al. [2023] and Chase al. [2023b] demonstrated learning tasks for which there
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

are no algorithms that satisfy this strong notion of replicability when the randomness is not shared across executions. This shared random string models the random seed of a learning algorithm in practice, and sharing internal randomness can be easily implemented by sharing said random seed.
Closer our work, Impagliazzo et al. [2022], Ghazi al. [2021b], Bun et al. [2023], Kalavasis et al. [2023] established strong statistical connections between replicability and other notions of algorithmic stability and learning paradigms such as differential privacy (DP), statistical queries (SQ), and online learning. Although several of these works provided various computational results, these connections are not as well understood the statistical ones.
1.1 Our Contributions
In this work, we aim to shed further light on the aforementioned computational connections. In particular, provide both negative and positive results. Negative results are manifested through com- putational separations while positive results are presented through computational transformations. will see shortly. We emphasize that whenever we work within the PAC learning framework consider the realizable setting.
Replicability & Online Learning. The results of Ghazi et al. [2021b], Bun et al. [2023], Kalavasis et al. [2023] established statistical connection between replicability and online learning. In particular, in the context of PAC learning, these works essentially show that replicable PAC learning statistically equivalent to online learning since learnability in both settings characterized by the finiteness of the Littlestone dimension of the underlying concept class. From the above, the first natural question is the following:
Q1. How does replicability computationally relate to online learning?
We show that under standard cryptographic assumptions, efficient replicability separated from efficient online learning.
Theorem 1.2 (Informal, see Theorem 2.1). Assuming the existence of one-way functions, there is concept class that is replicably PAC learnable in polynomial time, but is not efficiently online learnable by any no-regret algorithm.
In order to prove the above result, we provide an efficient replicable PAC learner for the concept class of One- Way Sequences OWS over {0, 1]d introduced by Blum [1994]. This algorithm, which relies on a novel replicable subroutine for quantile estimation (cf. Theorem B.6), combined with the cryptographic hardness result of Bun [2020] for online learnability, gives the desired computational separation. For further details, we refer to Section 2.
Replicability & SQ. The Statistical Query (SQ) framework is expressive model of statistical learning introduced by Kearns [1998]. This model of learning is a restricted class of algorithms that is only permitted indirect access samples through approximations of certain carefully chosen functions of the data (statistical queries). The motivation behind the introduction of the SQ framework was capture a large class of noise-resistant learning algorithms. As such, any SQ algorithm enjoys some inherent stability properties. Since replicability also captures some notion of algorithmic stability, it is meaningful ask:
Q2. How does replicability computationally relate to SQ learning?
For some background about the SQ framework, we refer the reader to Appendix C.2. A manifestation of the intuitive connection between SQ and replicability can be found one of the main results of Impagliazzo et al. [2022], which states that any efficient SQ algorithm can be efficiently made replicable. In this paper, we investigate the other direction of this connection.
A particularly interesting computational separation between (distribution sppcciiiippeec replicability and SQ learning was noticed by Impagliazzo et al. [2022], in the context of realizable binary classification: if we consider the uniform distribution 24 over the Boolean hypercube (0. 1)dd then the concept class of parities SQ-hard to learn under 2/ [Kearns, 1998] but admits an efficient PAC learner that is replicable under 24. Indeed, with high probability over the random draw of the data, Gaussian elimination, which is the standard algorithm for PAC learning parities under U, gives unique solution and, as a result, is replicable.

---

Based on this observation, Impagliazzo et al. [2022] posed as an interesting question whether parities are efficiently learnable by replicable learner under other marginal distributions, for which Gaussian elimination is "unstable", i.e., it fails to give unique solution (see e.g., Proposition C.4).
Transforming DistributtionSSpecfie Replicable Learners. Inspired by the question of Impagli- azzo et al. [2022], we ask the following more general question for realizable binary classification:
Q3. For a class & C {0, 11 and marginal distributions Di, D2 over X. how does replicable PAC learnability of'6 6 under 'D, and under '22 relate to one another compulationally?
Our main result is a general black-box transformation from replicable PAC learner under the uniform distribution over X' = (0, 1|d dd a replicable PAC learner under some unknown marginal distribution D. The runtime of the transformation depends on the decision tree complexity of the distribution DD complexity measure that comes from the recent work Blanc et al. [2023] and is defined as follows:
Definition 1.3 (Decision Tree Complexity; Blanc et al., 2023). The decision tree complexity of distribution D over [0, is the smallest integer such that its probability mass function (pmf) can be computed by depth-L decision tree (cf. Definition D.1).
A decision tree (cf. Definition D (0, 13d - IR is binary tree whose internal nodes query particular coordinate F2, E [d] (descending left if x;; = 0 and right otherwise) and whose leaves are labelled by real values. Each coordinate of internal nodes, and its value T(x) is the value stored at the root. For some 'D over the Boolean hypercube, we say 'D is computed by a decision tree T of depth f if, for any x E {0, it holds that (ax)) = (xx).
{0, 1 follows unique root-to-leaf path based on the queried
As an example, note that the uniform distribution requires depth & = since its pmf is constant while distribution whose pmf takes 2d different values requires depth l = d. However, various natural (structured) distributions have tree complexity much smaller than d. Importantly, the running time overhead of our lifting approach scales proportionally the decision tree complexity of 'D and hence can be used to obtain novel efficient replicable PAC learners.
Our replicable lifting framework informally states the following:
Theorem 1.4 (Informal, see Theorem 3.2). Let X = {0, 1]2 and m poly (d). Consider a concept class '6 S {0, 13 and assume that A is a PAC learner for '6' that is m-sample replicable under the uniform distribution and runs in time poly (m). Then, for some (unknown) monotone' distribution D with decision tree complexity f, there exists an algorithm A' that is a PAC learner for '6 that is (mly) sample replicable under 'D and rans in time poly((mE))
This implies for instance that for e = 0(1), the blowup is polynomial in the runtime of the uniform learner while if & = Ollog d), the running time is molsi-polynomial in d. We note that our result can also be extended to general (non-monotone) distributions if we assume access to a (subcube) conditional sampling oracle. For formal details, we refer the reader to Section 3.
As an application of this framework, we show how to black-box transform replicable learners for parities that work under the uniform distribution to replicable learners that work under some other unknown distribution D, where the sample complexity and running time of the transformation depends on the decision tree complexity of D. This result is hence related to the question of Impagliazzo et al. [2022] since we can design distributions D over {0. 1)d with small decision tree complexity for which Gaussian elimination fails to be replicable. We refer to Section 4 for the formal statement.
Corollary 1.5 (Informal, see Corollary 4.3 and Theorem C.5). Let X = {0. 1 and m = poly(d) Then, for any (unknown) monotone distribution D with decision tree complexity e, there exists a PAC learner for parities that is (mL)f-sample -sample replicable under D and runs in time poly(me))
Moreover, for any m' m ((1), there exists some monotone distribution D over {0, 1]d with decision tree complexity = (1) so that Gaussian elimination, with input m labeled examples, fails to PAC learn parities replicably under D with constant probability.
Recall that D over {0, 13 is monotone if whenever > y in the partial order of the poset, we have D(e) 2 D(y).
3

---

Replicability & Privacy. Returning to the works of Ghazi et al. [2021b], Bun et al. [2023], Kalavasis al. [2023], it is known that replicable PAC learning statistically equivalent approximate differentially private PAC learning. We hence ask:
Q4. How does replicability computationally relate to private learning?
The recent work of Bun et al. [2023] provided a computational separation between approximate differential privacy and replicability. In particular, they showed that replicable learner can be efficiently transformed into an approximately differentially private one, but the other direction is hard under standard cryptographic assumptions. To be more specific, they provided concept class that efficiently learnable by an approximate DP learner, but not efficiently learnable by replicable learner, assuming the existence one-way functions. Based on this hardness result, ask whether we can transform a pure DP algorithm into a replicable one. We show the following result.
Theorem 1.6 (Informal: see Theorem 5.2). Let Dxy be distribution on X x (0. 1) that is realizable with respect to some concept class 6. Let be an efficient pure DP learner for 6. Then, there is replicable learner A' for '6 that runs in time polynomial with respect to the error, confidence, and replicability parameters but exponential in the representation dimension of
We reiterate that this transformation is efficient with respect to the correctness, confidence and replicability parameters a, 3, but it could be inefficient with respect to some parameter that captures the complexity of the underlying concept class &6 (such as the representation dimension of the class, e.g.. the margin parameter in the case of large-margin halfspaces). To the best of our knowledge, the same holds for the transformation of pure DP learner to an online learner of Gonen et al. [2019] and it would be interesting to show that this is unavoidable.
The Computational Landscape of Stability. Our work studies several computational aspects of replicability and its connections with other stability notions such online learning, SQ learning, and differential privacy. Combining our results with the prior works of Blum et al. [2005], Gonen al. [2019], Ghazi et al. [2021b], Impagliazzo al. [2022], Bun al. [2023], Kalavasis et al. [2023] yields the current computational landscape of stability depicted below.
This work, Theorem 5.2
e-DP
[Gonen et al., 2019]
Replicability
This work, Theurem
Online
[Impagliazzo 2022]
(Ghazi et al., 2021b:
Kalavasis et 2023]
Bun al., 2023:
[Bun 2024]
By definition
[Bun, 2020]
Iimpagliazzo 2022), This work, Corollary 1.5
SQ
[Ban 2023]
(s, DDP
al., 2005]
"The representation dimension is a combinatorial dimension, similar to VC dimension, that characterizes which classes PAC learnable by pure DP algorithms [Beimel al., 2013].

---

The computational landscape of stability. A green double arrow (=) from tail to head indicates that an efficient learner for a task in the setting of the arrow tail can be black-box transformed into an efficient learner for the same task in the setting of the arrow head. Meanwhile, an orange dashed double arrow (==>) from tail to head indicates that an efficient learner for a task in the tail setting can be black-box transformed into an efficient learner for the same task in the head setting, under some additional assumptions. Finally, a red slashed single arrow (-r) from tail to head indicates that there is learning task for which an efficient learner exists the setting of the arrow tail but no efficient learner can exist in the setting of the arrow head, possibly under some cryptographic assumptions.
Figure 1.1:
The computational landscape of "stable" learning depicted in Figure 1.1 is a byproduct of the following results connecting (i) replicability, (ii) approximate DP, (iii) pure DP, (iv) online learning, and, (v) statistical queries.
Black-Box Transformations.
1. Pure DP can be efficiently" transformed to Online [Gonen et al., 2019].
Replicability can be efficiently transformed to Approximate DP [Ghazi et al., 2021b, Bun et al.,
2023, Kalavasis et al., 2023].
SQ can be efficiently transformed to Approximate DP [Blum et al., 2005].*
4. SQ can be efficiently transformed to Replicable [Impagliazzo al., 2022].
5. Pure DP can be efficiently" transformed to Replicable (this work, Theorem 5.2).
Caveats of Transformations. The transformations from pure e- E-DP learners to replicable and online learners may incur exponential computation time in the represenlation dimension [Beimel et al., 2013] of the underlying hypothesis class.
Regarding the approximate DP reduction to replicability: The transformation provided by Bun et al. [2023] uses correlation, which necessitates that the output space of the algorithm is finite. To be more precise, based [Bun et al., 2023], there is an efficient transformation from approximate DP to perfectly generalizing algorithms. Next, the authors use correlated sampling to obtain a replicable learner follows. Given perfectly generalizing algorithm A and sample S, the correlated sampling strategy is applied to the distribution of outputs of A(S). Hence, the output space of A should be finite. In the PAC learning setting, to ensure that the algorithm has finite output space, sufficient condition is that the domain is finite. The correlated sampling step can be explicitly implemented via rejection sampling from the output space of A. The acceptance probability is controlled by the probability mass function of A(S). As a result, in general, it is not computationally efficient. For instance, if the finite input space to the correlated sampling strategy is {0, 1,dd then the runtime the algorithm could be exp(d), since the acceptance probability is exponentially small in the dimension in the worst case.
For the specific case of PAC learning, there is another transformation from approximate DP to replicability that holds for countable domains X' that was proposed by Kalavasis et al. [2023], but this approach goes through the I. Littlestone dimension of the class and might not even be computable in its general form.
Separations. There is a concept class that can be learned efficiently
1. by replicable PAC learner (this work, Theorem 2.1), but not efficient online one under OWF [Blum, 1994];
2. by an approximate DP PAC learner, but not efficient online under OWF [Bun, 2020];
3. by an online learner, but not an efficient approximate DP PAC one under cryptographic assump- tions [Bun et al., 2024];
4. by a replicable PAC learner under uniform marginals (Impagliazzo et al. [2022]) or more general marginals (this work, Corollary 1.5), but not efficient SQ one;
'The transformation is efficient with respect to the correctness and confidence parameters but could be inffficient with respect to other parameters of the class such as the representation dimension.
*The reduction is efficient as simply requires adding Gaussian noise to each statistical query. However, it is impractical for most tasks of interest as the resulting privacy guarantees are relatively weak.
'The transformation is efficient with respect the correctness and confidence parameters but could be inefficient with respect to other parameters of the class.
'The specific assumptions are technical and we omit the specific statements. Roughly, the assumptions lead to the possibility to build indistinguishability obfuscation for all circuits.
5

---

5. by an approximate DP PAC learner, but not an efficient replicable one under OWF [Bun et al., 2023].
1.2 Related Work
Replicability. Pioneered by Impagliazzo al. [2022], there has been growing interest from the learning theory community in studying replicability as an algorithmic property. Esfandiari et al. [2023a.b] studied replicable algorithms in the context of multi-armed bandits and clustering. Later, Eaton et al. [2023], Karbasi et al. [2023] studied replicability in the context of Reinforcement Learning (RL) and designed algorithms that achieve various notions of replicability. Recently, Bun et al. [2023] established statistical equivalences and separations between replicability and other notions of algorithmic stability such as differential privacy when the domain of the learning problem is finite and provided some computational and statistical hardness results to obtain these equivalences, under cryptographic assumptions. Subsequently, Kalavasis et al. [2023] proposed a relaxation of the replicability definition of Impagliazzo et al. [2022]. showed its statistical equivalence to the notion of replicability for countable domains" and extended some of the equivalences from Bun et al. [2023] to countable domains. Chase et al. [2023b], Dixon et al. [2023] proposed notion of list fist-reliccbbiity, where the randomness is not shared across the executions of the algorithm, but the outputs are required to belong to list of small cardinality instead of being identical. Both of these works developed algorithms that work in the realizable setting, and later Chase et al. [2023a] showed that, surprisingly, it is impossible to design list-replicable learning algorithms for infinite classes in the agnostic setting. Recently, Moran et al. [2023] established even more statistical connections between replicability and other notions of stability, by dividing them into two categories consisting and
of cetributiiondepeendd
definitions. Recent work by Kalavasis et al. [2024] studies replicable algorithms for large-margin halfspaces.
Computational Separations & Transformations in Stability. The seminal result of Blum [1994] illustrated a computational separation between PAC and online learning. Later, Bun [2020] obtained a similar separation between private PAC and online learning. More recently, Bun et al. [2023] showed that there exists a concept class that admits an efficient approximate DP learner but not an efficient replicable one, assuming the existence of OWFs. Contributing this line of work, our Theorem 2.1 is of similar flavor.
Shifting our attention to SQ learning, there is an intuitive similarity between learning from noisy examples and private learning: algorithms for both problems must be robust to small variations in the data (see also Blum al. [2005]). Parities are canonical SQ-hard problem, meaning that no efficient SQ algorithm for this class exists. Kasiviswanathan et al. [2011] designed an efficient private learner for learning parities, which dispels the similarity between learning with noise and private learning. Georgiev and Hopkins [2022] showed that while polynomial-tne time private algorithms for learning parities are known, the failure probability of any such algorithm must be larger than what can be achieved in exponential time, or clse NP = RP. Finally, recent work by Bun et al. [2024] gives a concept class that admits an online learner running polynomial time with a polynomial mistake bound, but for which there is no computationally efficient approximate differentially private PAC learner, under cryptographic assumptions.
Moving on to transformations, our Theorem 1.4 builds upon the result of Blanc et al. [2023] who designed a framework that transforms computationally efficient algorithms under uniform marginal distributions, to algorithms that work under some other distribution, where the complexity of the transformation scales with some particular notion of distance between the two distributions. Essentially, our result can be viewed as a replicable framework of the same flavor, with small additional computational and statistical overhead that scales with the replicability parameter. Finally, approach to transform a pure DP learner into a replicable learner (cf. Theorem 1.6) is inspired by Gonen et al. [2019], who provided a transformation from pure DP learners to online learners.
1.3 Notation
In general, we use to denote an algorithm. For unsupervised problems, we usually denote by D the distribution over input examples. In the case of supervised problems, use E to denote the concept class in question, D to denote the marginal distribution of the feature domain X,, and Dxy to refer to the joint distribution over labeled examples (z, y) E X x y. Throughout our work, we use a, B to refer to the error and failure probability parameters of the algorithm, E, 5 to denote the approximate
We remark that this equivalence for finite domains can also be obtained, implicitly, from the results of Bun al. [2023]. Connections between replicability and the Littlestone dimension go back Ghazi et al. [2021b].

---

DP parameters, and p for the replicability parameter. In most cases, the feature domain X' is a subset of high-dimensional space and we use denote the dimension of that space.
2 Efficient Replicability and Online Learning
Our first main result shows that replicabiliiy and online learning are not computationally equivalent, as- suming the existence of one-way functions. This hardness result is based on a construction from Blum [1994], who defined concept class denoted by OWS, which is efficiently PAC learnable but not on- line learnable in polynomial time, assuming the existence of one-way functions. Blum's construction builds upon the Goldreich-Gollwaseer
pscudorandom function generator [Goldreich et al., 1986] to define families of "one way" labeled sequences (01 b1),.... ..... (or,,,, b,) E {0, 1)dh x {0, 1), for some r = (polydd)). These string-label pairs can be efficiently computed in the forward direction, but are hard to compute in the reverse direction. Specifically, for any i < j. it is easy to compute Jj. by given og. On the other hand, it is hard to compute d;, b, given jj. The essence of the difficulty in the online setting is that an adversary can present to the learner Then, the labels by are not predictable by
the sequence in reverse order, i.e., oy, Or-........ JT- polynomial time learner. However, in the PAC setting, for any distribution over the sequence {(a,, be) hegr). a learner which is given n labeled examples can identify the string d;- with smallest index 1" in the sample. Then, it can perfectly and efficiently predict the lahel of any string that comes after it. This approximately amounts to (1 - 1/n) fraction of the underlying population.
It not hard see that the PAC learner for OWS not replicable, since the minimum index of a sample can vary wildly between samples. The high-level idea of our approach to making the algorithm replicable
show that we can replicably identify an approximate minimum index and output the hypothesis that (efficiently) forward computes from that index. Our main result, proven in Appendix B, as follows.
Theorem 2.1. Let d e N. The following hold:
(a) [Bun, 2020] Assuming the existence of one-way functions, the concept class OWS with input domain {0, 1] cannot be learned by an efficient no-regret algorithm, i.e. an algorithm that
some 1j > O achieves expected regret [E] S poly(d) T1- using time poly (d, T) in every iteration.
(b) (Theorem B.7) The concept class OWS with imput domain {0. 1)dd can be learned by a p-
replicable (e,8))PACC learner with sample complexity m poly 1/a, 1/2, log(+/o) and (mly(m) running time.
3 Lifting Replicable Uniform Learners
In this section, we present our replicable lifting framework in further detail. First, we will need the following technical definition.
Definition 3.1 (Closed under Restrictions), A concept class E functions f (0, 10. - {0, is closed under restrictions for any f E i E [d] and b E {0, 1}, the restriction fr=b remains in C, where f==)(x)= = ..., Z4., b, Fi+1, ..., vt) for any x E 10.
Our replicable lifting result works for concept classes that satisfy the closedness under restrictions property. Also, recall that a distribution 'D over {0. 1)d is monotone (Definition D.4) if whenever y (æ is greater than in the partial ordering of the poset), it holds D(x) D(y). Our algorithm for lifting replicable uniform learners to replicable learners under some unknown distribution D is presented in Theorem 3.2. This lifting approach is inspired by the work of Blane al. [2023], who designed the non-replicable variant of this transformation. We note that our algorithm, similar to the algorithm of Blanc al. [2023], only requires sample access to D for monotone distributions, while, for arbitrary non -on-ooote probability measures, our algorithm requires access to a conditional sampling oracle (cf. Definition D.5). Our replicable lifting theorem reads as follows.
Theorem 3.2 (Lifting Replicable Uniform I Learners). Consider concept class & of functions f : {0, 1 + 1) closed under restrictions. Suppose we are given black-box access to an algorithu such that for any a',p' p',, ,3' E (0,1), 1), given poly(d, (d, 1/a', 1/e (/e//oo()//))) samples from U, (i) is p'rreplicable with respect to the uniform distribution U,
(ii) PAC learns 6 under the uniform distribution to accuracy a' and confidence B,, and,
(iii) terminates in time poly(d, 1/a', 1/9 (loo(//))))
'We remark that this stronger requirement in regret is necessary since the trivial random guessing algorithm achieves o(I') regret in finite domains (cf. Appendix A.3).
7

---

Let a,p E (0.1) and B E P/. For m poly(d, 1/a, 1/8, log(1/3)) and M poly(d, 1/a 1/8 (o)( the following cases hold:
(a) If D is monotone distribution over {0. 1] representable by depth-E decision tree, there is an algorithm that draws M samples from D, is p-replicable with respect to D, PAC learns E under D with accuracy a and confidence 3, and terminates in poly(M) time.
(b) If D is an arbitrary distribution over {0. 1 representable by a depth-l decision tree, there is an algorithm that draws M labeled examples as well as M conditional samples (cf. Definition D.5) from DD is p-replicable with respect to DD PAC learns &6 with respect to 'D with accuracy a and confidence B3, and terminates in poly(M) (M) time.
The high-level idea of the reduction proceeds as follows. Let us consider the realizable PAC setting, ie., the labels are consistent with some f E '6. Let us assume black-box access to a replicable uniform learner Ay for E and access to i.i.d. samples of the form (x,, (xx), where goal is to (efficiently) obtain algorithm Ale. that achieves small misclassification error with respect to the unknown distribution DD and target I* and is also replicable under D. The promise is that 'D
D. Our
has decision tree representation of depth f.9
The first step is to draw enough samples fr,
~ DD and compute the decision tree represen- tation of D. This is an unsupervised learning task and it only uses the feature vectors of the training set. We design a replicable algorithm for this step (cf. Theorem E.7), which could be of independent interest. The next observation is crucial: any discrete distribution on {0, 1]dd can be expressed as a mixture of uniform distributions conditioned on non-overlapping sub-cubes. To see this, notice that any root-to-leaf path in the estimated decision tree representation corresponds to a sub-cube of {0, 11 and, conditioned on this path, the remaining coordinates follow a uniform law. Hence, after an appropriate samplll procedure, one can employ the black-box replicable learner Aye to any one of the leaves t of the tree decomposition of 'D and obtain a classifier ft- For this step, the fact that E' is closed under restrictions is crucial. Intuitively, we wish to implement this idea in a replicable manner and need overall replicability parameter p. it suffices to use the uniform replicable algorithm in each leaf with parameter (e/22) since we make at most 2 calls to the uniform PAC learner (the decision tree complexity of the target is f). Finally, given a test example ~ D. one computes the leaf that corresponds to the sub-cube that æ falls into and uses the (replicable) output fi of the associated uniform PAC learner to guess the correct label. For the formal analysis, we refer to Appendix D and Appendix E.
4 Efficient Replicability and SQ Learning: Parities
In this section, we provide an application of the general lifting framework we described in Section 3. One of the main results of the seminal work of Impagliazzo et al. [2022] is that any SQ algorithm can be made replicable. This result allows a great collection of tasks to be solved replicably since the SQ framework is known to be highly expressive [Kearns, 1998].
The primary motivation of this section comes from the question of Impagliazzo et al. [2022] on whether the class of parities can be PAC learned by an efficient replicable algorithm when the marginal distribution D not uniform over (0, 1]d Let us define our concept class of interest." 10
Definition 4.1 (Affine Parities). Let S C [d] be some subset of [d] and b E {0,1) a bias term. Define fs.. : {0, 1 - {0, 1} to be the biased parity of the bits in S. namely fs,((x) = b+ Eves Tz- The concept class of affine parities over {0, 1]d is the set '6 = {fss : S C [d] b {0,1]}, For any distribution 'D over 1] 4 we consider the supervised learning problem AffParity, where the learner observes i.i.d. samples of the form (x, (x:), where D and 1 E E.
As observed by Impagliazzo et al. [2022], there a replicable algorithm for PAC learning parities (i.e., the subclass Parity obtained by setting 0 in AffParity) under the uniform distribution: draw roughly (dd) samples so that with high probability the dataset will contain a basis. Then, in two distinct executions, the sets that standard Gaussian climination outputs will be the same. A similar approach works for the class of affine parities and is described below.
'y performing an iterated doubling if necessary, we may assume without loss of generality that E known. Je consider superset of parities which we call affine parities as we would like our concept class to be closed under restrictions (cf. Definition 3.1).
8

---

Lemma 4.2. The concept class of affine parities AffParity over f0. admits a p-replicable algorithm that perfectly learns any concept with respect to the uniform distribution U with probability of success at least 1 - 3. The algorithm has ((poly (d, log //88) sample and time complexity.
The algorithm that attains the guarantees of Lemma 4.2 is a simple adaptation of the Gaussian elimination for learning standard parities. We provide the pseudocode in Algorithm C.1 and defer the proof of correctness to Appendix C.I.
Application of Theorem 3.2 Since the class of affine parities over {0, 1]d is closed under re- strictions (cf. Lemma C.8) and there is learner for this class under uniform marginals that is replicable and efficient (cf. Lemma 4.2), we can obtain an algorithm that replicably PAC learns the class AffParity under more general distributions. In particular, the following result is immediate application of our lifting framework.
Corollary 4.3. Let a.p E (0,1) and B E (0, Let X
{0, 10 For M
poly(d, V/. 1/3)010), the following cases hold: (a) For any (unknownn) monotone distribution 'D over X with decision tree complexity E, there exists an algorithu that is p-replicable learner for the concept class AffParity under DD and requires M samples and running time poly(M) to get accuracy a and confidence B.
(a) For any distribution D over X with decision tree complexity E, there exists an algorithm that is a p-replicable learner for the concept class AffParity under DD and requires M labeled examples, M conditional samples from DD and running time poly(M) to get accuracy a and confidence B..
Back to the Question of Impagliazzo et al. [2022]. Impagliazzo et al. [2022] raised the question of when parities over {0. 1) can be efficiently PAC learned by replicable algorithm under some marginal distribution that is not uniform or, more broadly, that causes Gaussian elimination to be non-replicable. Our Corollary 4.3 makes progress on this question. First, we note that in our setting, we do not require knowledge of DD Second, one can design examples of (monotone) distributions for which our lifting framework produces a replicable polynomial time PAC learner but naive Gaussian elimination" 1! fails to be replicable with constant probability (cf. Theorem C.5). Note that even PAC learning parities for the distribution described in Theorem C.5 is SQ-hard. We believe that our lifting framework can be seen as systematic way of bypassing some instabilities arising from the algebraic structure of standard Gaussian elimination.
d
As final remark, we note that one could potentially design much more complicated (still monotone) distributions than the one of Theorem C.5, where even various adaptations of Gaussian elimination (e.g.. pre-processing of the dataset, data deletion) would fail to be replicable but our lifting framework would guarantee replicability (and efficiency, provided small decision tree complexity). On the other hand, it is not evident whether parity learning remains SQ-hard under these "harder" distributions.
5 Efficient Replicability and Private Learning
In this section, we study connections between efficient DP learnability and efficient replicable learn- ability of concept class. As mentioned in the introduction, Bun et al. [2023] and subsequently Kalavasis et al. [2023] established a statistical equivalence between approximate DP learnability and replicable learnability of concept class when the domain is finite [Bun et al., 2023] countable (Kalavasis et al., 2023]. Moreover, Bun et al. [2023] showed that this equivalence does not hold when one takes into account the computational complexity of these tasks.
Proposition 5.1 (Section 4.1 in Bun et al. [2023]). There exists class that is efficiently PAC learnable by an approximate DP algorithm but, assuming one-way functions exist, it cannot be learned efficiently by a replicable algorithm.
We remark that there is an efficient converse transformation, i.e., a computationally efficient transfor- mation from a replicable learner to an approximate DP learner [Bun et al., 2023]. Inspired by Gonen et al. [2019], we ask whether one can transform pure DP learner to replicable one. Our main result, proven in Appendix F, is the following.
Theorem 5.2 (From Pure DP Learner Replicable Learner). Let X be some input domain, ) = {0, 1,, and Dxy be a distribution on X x y that is realizable with respect to some con- cept class C. Let A be a pure DP learner that, for any a, e, E (0, 1), needs m(a, e, 3,6)*
We note that the examples we design are difficult instances for the standard Gaussian elimination algorithm but some pre-poe peepprccssing of the dataset (e.g., deleting some constant fraction of samples) could potentially make Gaussian elimination replicable.

---

poly(Va, l/e, (s)) dim(6)) i..dd. samples from Dxy and poly(m) running time to outpur a hypothesis that has error at most a, with probability 1- in an E-DP way. Then, for any d'. d',p,'' E (0.1) 1) there is a p-replicable learner A' that ouiputs hypothesis with error at most a' with probability least - 33' and requires poly(Ya', 1/p (o,)lo((//)) dim(m)))))))) (6)) i..d. samples from Dxy and poly(1/o,, 1/p, log(3/5") exp(dim(6)) running time.
In the above, we denote by dim(E) some dimension that describes the complexity of the concept class & that arises in the sample complexity of our pure DP learner. A natural candidate is the representation dimension [Kasiviswanathan et al., 201 1J. As we alluded to before, this transformation efficient with respect the parameters a, 3, p. On the other side, the sample complexity is polynomial in the representation dimension but the running time is exponential. We leave as an open question if it possible to avoid this dependence.
We remark that in principle, one could use the reduction from Bun et al. [2023]. The catch is that this reduction based on correlated sampling so it requires i) the output space of the algorithm be finite and ii) even under finite output spaces, it needs exponential time in the size of that space.
6 Conclusion
In this work, we have studied the computational aspects of replicability and several connections to other important notions in learning theory including online learning, SQ learning, and DP PAC learning. We believe that there are several interesting questions left open from our work. First, it would be interesting to see if there is a computationally efficient transformation from online learners to replicable learners. Then, it would be important to derive replicable learners from pure DP learners which are efficient with respect to the complexity of the underlying concept class. Regarding parities, it is still open whether we can design efficient replicable algorithms for every distribution D.
Acknowledgments
Alkis Kalavasis was supported by the Institute for Foundations of Data Science Yale. Amin Karbasi acknowledges funding in direct support of this work from NSF (115-1845032, ONR (N00014- 19-1- 2406), and the AI Institute for Learning-Enabled Optimization at Scale (TILOS), Grigoris Velegkas was supported in part by the AI Institute for Learning-Enablle Optimization at Scale (TILOS). Felix Zhou acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC).
References
Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private pac learning implies finite littlestone dimension. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 852-860, 2019.
Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private and online learnability are equivalent. ACM Journal of the ACM (JACM), 69(4):133, 2022.
Monya Baker. 1,500 scientists lift the lid on reproducibility. Nature, 533(7604), 2016.
Philip Ball. Is ai leading to a reproducibility crisis in science? Nature, 624(7990);22-25, 2023.
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of private learners. In Robert D. Kleinberg, editor, Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013, pages 97-110. ACM, 2013. doi: 10.1145/2422436. 2422450. URL https: pettpps://di.. /to.doo..oor.o..oooo.......o.... /00 1145/2422436 2422450.
Guy Blanc, Jane Lange, Ali Malik, and Li- Yang Tan. Popular decision tree algorithms are provably noise tolerant. In International Conference on Machine Learning, pages 2091-2106. PMLR, 2022a.
Guy Blanc, Jane Lange, Mingda Qiao, and Li- Yang Tan. Properly learning decision trees in almost polynomial time. Journal of the ACM, 69(6):1119, 2022b.
Guy Blanc, Jane Lange, Ali Malik, and Li- Yang Tan. Lifting uniform learners via distributional decomposition. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1755-1767, 2023.
10

---

Avrim Blum, Adam Kalai, and Hal Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506-519) 2003.
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq symposium on framework. In Proceedings of the twenty-fourth ACM
Principles of database systems, pages 128-138, 108,, 2005.
Avrim L Blum. Separating distribution- and mistake-bound learning models over the boolean domain. SIAM Journal on Computing, 23(5):900-1000, 1994.
Mark Bun, A computational separation between private learning and online learning. Advances in Neural Information Processing Systems, 33:20732 2020.
Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In 2020 IEEE 6lst Annual Symposium on Foundations of Computer Science (FOCS), pages 389-402. IEEE, 2020.
Mark Bun, Marco Gaboardi. Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell. Stability is stable: Connections between replicability, privacy, and adaptive generalization. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023, pages 520-527. ACM, 2023. doi: 10.1445/36424633555444 URL https: 35852446.
//doi.org/10 org/10. 10.
Mark Bun, Aloni Cohen, and Rathin Desai. Private PAC learning may be harder than online learning. In Claire Vernade and Daniel Hsu, editors, International Conference on Algorithmic Learning Theory, 25-28 February 2024, La Jolla, California, USA, volume 237 of Proceedings of Machine Learning Research, pages 362-389. PMLR, 2024, URL https: v237 v237/bun24a. html.
https::/ppoceeednnggg pttp///eoccee...ee.ce mlr aal.ppre presa/
Clément L Canonne, Dana Ron, and Rocco A Servedio. Testing probability distributions using conditional samples. SIAM Journal Computing. 44(3):540 616,0-6666660 2015.
Clément L Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten. Random restrictions of high dimensional distributions and uniformity testing with subcube conditioning. In Proceedings of the 202/ ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 321-336. SIAM, 2021.
Zachary Chase, Bogdan Chornomaz, Shay Moran, and Amir Yehudayoff. Local borsuk-ulam, stability, and replicability. arXiv preprint arXiv:2311.01599 2023a.
Zachary Chase, Shay Moran, and Amir Yehudayoff. Stability and replicability in learning. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 2430-2439, IEEE, 2023b. doi: 10. 10.1 10011000F555799022030000
URL https: / /doi. www.lo.ro///..oooooooooooooo..o. ooog/oo//// 10. 1109/FCC557990 2023. 2023.00148.
Peter Dixon, Aduri Pavan, Jason Vander Woude, and N. V. Vinodchandran. List and certificate complexities in replicable learning. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10- 16, 2023, 2023.
Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 1956.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. Theory of Cryptogruphy: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
Eric Eaton, Marcel Hussing, Michael Kearns, and Jessica Sorrell. Replicable reinforcement learning. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annuul Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.

---

Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits. In The Eleventh International Conference on Learning Representa- lions, 2023a.
Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou. Replicable clustering. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023b.
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S Vempala, and Ying Xiao. Statistical algorithms and a lower bound for detecting planted cliques. Journal of the ACM (JACM), 64(2): 1-37, 2017.
Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos. Efficient parameter estimation of truncated boolean product distributions. In Conference on Learning Theory, pages 1586-1600. PMLR, 2020.
Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos. Efficient algorithms for learning from coarse labels. In Conference on Learning Theory, pages 2060-2079. PMLR, 2021.
Dimitris Fotakis, Alkis Kalavasis, and Christos Tzamos. Perfect sampling from pairwise comparisons. In Sanmi Koyejo. S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, 35: Annual Conference Neural Information
Advances in Neural Information Processing Systems Processing Systems 2022, NewrlPS 2022, New Orleans, IA, USA, November 28- December 9, 2022, 2022.
Kristian Georgiev and Samuel Hopkins. Privacy induces robustness: information-computtiionn and sparse mean estimation. Advances in Neural Information Processing Systems, 35:6829-6842. 2022.
computation gaps
Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Sample-efficient proper pac learning with approximate differential privacy. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 183-196, 2021a.
Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via correlated sampling. In Marc Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 20172-201 2210044 2021b.
Surbhi Goel, Aravind Gollakota, and Adam Klivans. Statistical-query lower bounds via functional gradients. Advances in Neural Information Processing Systems, 33:2147-2158, 2020.
Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM (JACM), 33(4):792-807, 1986.
Alon Gonen, Elad Hazan, and Shay Moran. Private learning implies online learning: An efficient reduction. Advances in Neural Information Processing Systems, 32, 2019.
Themistoklis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Faster sublinear algorithms using conditional sampling. Proceedings of the Eventy-Eighte Annual ACM -IAM Symposium on Discrete Algorithums, pages
SIAM, 2017.
Anupam Gupta, Moritz. Hardt, Aaron Roth, and Jonathan Ullman. Privately releasing conjunctions and the statistical query barrier. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 803 812, 2011.
Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages 3511997. URL httph: //tsi.//do..ee org/ httg//0.114450 /145/3519935...
ACM, 2022. doi:
1411145/5519955.55/
Svante Janson. Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters, 135:1-6, 2018.
12

---

Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishabiliy of learning algorithms. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICMI. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 15586-15622. PMLR, 2023, URL kalavasis23a. html.
mlr, www.press///ee..........mm wwwppersesooo /v22//
Alkis Kalavasis, Amin Karbasi, Kasper Green Larsen, Grigoris Velegkas, and Felix Zhou. Replicable learning of large- margin halfspaces. arXiv preprint arXiv:2402.13885,, 2024.
Amin Karbasi, Grigoris Velegkas, Lin Yang, and Felix Zhou. Replicability in reinforcement learning. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793-88) 826, 2011.
Michael Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 1500);983-1006, 1998.
Michael J Kearns and Umesh Vazirani, An introduction to computational learning theory. MIT press, 1994.
Nick Littlestone.
Learning quickly when irrelevant attributes abound: A new lhneao-threshold algorithm. Machine learning, 2:285-318, 1988.
Pascal Massart. The tight constant in the dvoreesy--iieferwwollwviz inequality. The annals of Probability, pages 1269-1283, 1990.
Shay Moran, Hilla Schefler, and Jonathan Shafer. The bayesian stability zoo. Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Anmual Conference on Neural Information Processing Systems 2023, NeurlPS 2023. New Orleans, LA, USA, December 10 16, 2023, 2023.
Joelle Pineau, Koustuv Sinha, Genevieve Fried, Rosemary Nan Ke, and Hugo Larochelle. Iclr reproducibility challenge 2019, ReScience C, 5(2):5, 2019.
13

---

A Notation and Preliminaries
For standard PAC learning definitions, we refer to the book of Kearns and Vazirani [1994].
A.1 Replicable Learning
Following the pioneering work of Impagliazzo et al. [2022], we consider the definition of replicable leamnigg algorithm.
Definition 1.1 (Replicable Algorithm; Impagliazzo et al., 2022), Let be a distribution over random strings. A learning algorithu A is n-sample p-replicable under distribution 'D for two independent We will say that A is
sets S.S' ~ "D' it holds that PIs.s replicable the above holds uniformly over all distributions D.
r)) * A(SS', S
In words, A is replicable if sharing the randomness across two executions on different i.i.d. datasets yields the exact same output with high probability. We can think of A as a training algorithm which is replicable if by fixing the random seed, it outputs the exact same model with high probability. One of the most elementary statistical operations we may wish to make replicable mean estimation. This operation can be phrased more broadly using the language of statistical queries.
Definition A.1 (Statistical Query Oracle; Kearns, 1998). Let 'D be a distribution over the domain
X and Φ : X TR. be a statistical query with true value v lim,-tox Φ (X,....;; X,) E TR. Here X; ri..id D and the convergence is understood in probability or distribution. Let a, 3 E (0, 1) A statistical query (SQ) oracle outputs a value v such that | v²1 S a with probability at least
B. The SQ framework appears in various learning theory contexts (see e.g., Blum et al. [2003], Gupta et al. [2011], Goel et al. [2020]. Fotakis et al. [2021] and the references therein). In the SQ model, the learner interacts with an oracle in the following way: the learner submits a statistical query to the oracle and the oracle returns its true value, after adding some noise to it.
The simplest example of statistical query is the sample mean o(X1......
- E Impagliazzo et al. [2022] designed a replicable SQ-query oracle for sample mean queries with bounded co-domain. Esfandiari et al. [2023b] generalized the result to simultaneously estimate the means of multiple random variables with unbounded co-domain under some regularity conditions on their distributions (cf. Theorem B.4). The idea behind both results is to replicable rounding technique introduced in Impagliazzo et al. [2022] which allows one to sacrifice some accuracy of the estimator in exchange for the replicability property.
A.2 Private Learning
Differential Privacy. A foundational notion of algorithmic stability is that of Differential Privacy (DP) [Dwork et al., 2006]. For a, b, E, E (0, 1), let a #e,5 b denote the statement a S eb + and b e a + 8. We say that two probability distributions P, Q are (s, indistinguuishabbl if P(E) 25,5 ((E) for any measurable event E.
Definition A.2 (Approximate DP Algorithm; Kasiviswanathan al., 2011). A learning algorithm is an n nample (e, 5) diffferenttially private for any pair of samples S, S' E (X' x {0. 1})" " that disagree on a single example, the induced posterior distributions A(S) and A(S') are (E, (e.d)-iidiitiinniishablll
In the previous definition, when the parameter& 8 O, say that the algorithm satisfies (pure) E-DP. We remind the reader that, in the context of PAC learning. any hypothesis class '6 can be PAC-leamed by an approximate differentially private algorithm if and only if it has finite Littlestone dimension, i.., there is a qualitative equivalence hetween online learnability and private PAC learnability [Alon et al., 2019, Bun et al., 2020, Ghazi et al., 2021a, Alon et al., 2022].
A.3 Online Learning
We consider the no-regret model of online learning. Recall Littlestone's model of (realizable) online learning [Littlestone, 1988] defined via a two-player game between a learner and an adversary. Let & be a given concept class. In each round of the game t 1,..,, where T is a time horizon known to a (randomized) learner, the interaction is the following:
1) The adversary selects some features x, E 10.
2) The learner predicts a label b, E (0, 1). potentially using randomization,
3) The adversary, who observes the distribution of the choice of the learner but not its realization, chooses the correct label b, = c(ar.) under the constraint that there exists some of E 8 such that et (œ+) br, for all r < t.
14

---

The goal of the learner is to minimize its regret, defined by
T
RT == max NEW
Σ
1(b, + d(x))) - 1(h(z)) & c(ail]]
E 1bb + c(xx))
h
Σ 1(b c(x)))-
Thus the learner aims compete with the best concept in hindsight from the class 8. However, realizabilityy ensures that the best such concept makes no mistakes so the regret defined only in terms of the number of mistakes of the learner.
We now introduce the definition of an efficient no-regret learning algorithm used by Bun [2020]. In the definition below, write |c] to denote the length of a minimal description of the concept c. Definition A.3 (Efficient No-Regret Learning; [Bun, 2020]), We say that learner efficiently no-regret learns & if there is some r) > 0 such that for every adversary, achieves expected regret
E R[ = p |c))
using time poly(d, [cl. T) in every round.
There are non-standard features of this definition. First, no-regret algorithms are typically only required to achieve sublinear regret o(T) in T, whereas we require it to be strongly sublinear 71-1 stronger condition like this needed to make the definition nontrivial since the sample space is finite. Indeed, suppose T = 2d, then the trivial random guessing algorithm attains a regret bound of
T df
2d
dT
2 T = poly(d)o(T).
Many no-regret algorithms such the multiplicative weights update algorithm achieve strongly sublinear regret.
Second, would be more natural to require the learner to run in poly(log T) time, the description length of the time horizon, rather than the value of 7 itself. The relaxed formulation only makes the separation stronger.
B Efficient Replicability and Online Learning
B.1 One-Way Sequenees
Our exposition follows that of Bun [2020]. For every dimension d E N, Blum [1994] defines concept class OWS, consisting of functions over the domain {0. 10,11 1] that can be represented using (oly(d) bits and evaluated in poly(d) time. The concepts of OWS, are indexed by bit strings
E {0, 13*, where
[Vd]
OWS (c. : (0, 1)
We will usually omit the index d when is clear from the context. Each c, 10, - {0, 1) is defined using two efficiently representable and computable functions
G: 10 10
10-
f: 1)
10, [0
that are based on the Goldreich-Golldwaseee Seehhh-ooowwwwwswiiiiiiee Micali pseudorandom function family [Goldreich et al., 1986]. We omit the definition these functions since it does not impede us towards our goal and refer the reader to Blum [1994] for details. Intuitively, G(i, s) computes the string a; described in the introduction and f(i, s) computes label b;- We can think of as the random seed which generated from some source of true randomness which is then used to construct G, f.
15

---

For convenience, we identify {0, 1 =22). Then is defined as
es (1, = [1. ( else.
G(i, s) o, f(i
We see that e, (i) encodes both the string of well as its label b, for every random seed {0, 1)*. The two relevant properties of the strings o, are summarized below.
Proposition B.1 (Forward is Easy; Blum, 1994). There is an efficiently computable function
ComputeForward: {0, 1}ah x {0, 13 x 10, - 10,11-== x {0, 1}
such that for every j i
ComputeForward i, s))
((..))
Proposition B.2 (Reverse is Hard; Blum, 1994). Assuming the existence of one-way functions, there
exist functions G 10, 1] 10,1] {0,1) 1] and f {0, 1] x {0, 1 {0, satisfying the following. Let O be an oracle that on input (j. i, ()), ouputs (G(j, 8), 8)) ()) for any j > i. Let A be any polynomial time randomized algorithm and let A denote the algorithm with access to the oracle O. For every E (0, 1)*
Pr [i Gi,G(i))) [(1,)) S neg((d),
where the probability is taken over the internal randomness of and uniformly random 8 ~ U (4001)%)
The above proposition states that efficient algorithm can outperform random guessing when trying determinew the label string, even given access to a "compute-forward"" forward" oracle.
B.2 Hardness of Efficiently Online Learning OWS
Blum [1994] used Proposition B.2 to show that OWS cannot be learned in the mistake bound model, more stringent model of online learning compared the no-regret setting. Later, Bun [2020] adapted the argument to the no-regret setting, making the separation stronger.
Theorem B.3 ([Bun, 2020]). Assuming the existence of one-way functions, OWS cannot be learned by efficient no-regret algorithm.
Let |c| denote the length of minimal description of the concept Recall that learner efficiently no-regret learns class '6 if there exists > 0 such that for every adversary and any a E V, achieves E R poly (d, cc] T (strongly sublinear) using time poly(d, |c], T)) in every round. As mentioned in Appendix A.3, this requirement of strongly sublinear regret is necessary to make the definition non-trivial as the random guessing algorithm attains o(T) regret in finite domains.
B.3 Replicable Query Rounding
Impagliazzo et al. [2022] designed replicable statistical query oracles (cf. Definition A.1) for bounded co-domains and Esfandiari et al. [2023b] generalized their results to multiple general queries with unbounded co-domain (cf. Theorem B.4), assuming some regularity conditions on the queries. We illustrate the idea behind the rounding procedure applied to the task of mean estimation. An initial observation is that across two executions, the empirical mean concentrates about the true mean with high probability. Next, we discretize the real line into equal-length intervals with random shift. It can be shown that both points fall into the same random interval with high probability and outputting the midpoint of said interval yields the replicability guarantee.
For completeness, we include the pseudocode and a proof of the replicable rounding procedure.
Theorem B.4 (Replicable Rounding: Impagliazzo al., 2022, Esfandiari al., 2023b). Let 'D be distribution over some domain X. Let P E (0, 1) and 3 E (0,P)s). Suppose we have sequence of statistical queries 91....,9T 9r X + R with true values μ1, HT and sampling n independent
points from D ensures that
max ge (x.,..,,, mel S (E|7]
with probability at least 1 1 B.
16

---

Then there is a polynomial-time time postprocessing procedure rRound (cf. Algorithm B.1) such that each composition rRound a. p) is p-replicable. Moreover, the outputs fi rRound (I,, 0, p) satisfy
4a
max p4 te[T]
He S
with probability at least 1
Note that if we wish for the sequence of rounding steps to be p-replicable overall, we can simply run each rounding step with parameter o/r.
Algorithm B.1 Replicable Rounding
1: ruuund(query values .......9r: accuracy a, replicability p):
2: L f p
3: Sample To ~ U0 L.)
4: Discretize the real line ..... [Lo I, Lo), [To, Lo + L). [To + L, Lo 2L).... into disjoint
intervals
5: for = I,..., do
6: Round 9, to the midpoint of the interval, jrr
7: end for
8: return j E
Proof (Theorem B.4). Discretize the real line disjoint intervals.
- 0), [0, L), (L...).....
We will choose the value of later. Consider adding a uniformly random offset Lo ~ U10, so the discretization becomes
LLo - L, Lo). [Lo Lo + L), [Lo L, Lo + 2L).
For each t E T, we round the estimate (z( ) := 9r (z Fn,) ) to the midpoint of the interval it falls into. Let fú be rounded estimate that we output. From hereonforth, we condition on the event max./g:(x)....... (x Mel S
Replicability of Algorithm B.1. Fix & E T. Consider the output across two runs Ae. Pl. As long as the raw estimates 9r (Z1.m) (een)))g((( (2( fall in the same interval, the outputs will be exactly the same. This occurs with probability
[9((x1m) go (nn
2a T.
Choosing L 6azp ensures this value is most P/3. Accounting for the 23 2//3 probability of the estimates Gr (x1m.) failing to concentrate, the output fū, p-replicable.
Correctness of Algorithm B.1. The rounding incurs additive error of most 1/2. The choice of L= 60/p means the total error at most
4a
a
<
B.4 Replicable Quantile Estimation
In this section we provide algorithm that replicably estimates quantiles of distribution. This will be useful in providing the computational separation between replicable PAC learning and online learning. We believe that it can have applications beyond the scope of our work.
We first present a well-known concentration inequality regarding CDFs of random variables due to Dvoretzky, Kiefer, and Wolfowitz.
Theorem B.5
Inequality; Dvoretzky et al., 1956, Massart, 1990). Let XI,...y Xn be i.i.d. random variables with CDF F. Let F,, denote the empirical distribution function given by Fa(x) = - 1(X: < x}. For any > 0,
Pr
supl Fr (x) F(x) a < 2 eexp -2na?)
17

---

In other words, we require at most n. (4/2²2 (2/s)) samples to ensure that with probability at least 1 8, the empirical CDF uniformly estimates the true CDF with enror at most a.
The replicable quantile estimation algorithm for discrete and bounded distributions can be found in Algorithm B.2. The high-level idea perform (replicable) binary search over the support of the distribution and to check whether the empirical CDF evaluated at some point is above or below the target quantile q.
Algorithm B.2 Replicable Quantile Estimation
quantile q, accuracy a, replicability p, confidence 3): 1: rQuantileEst(samppll Fi..... . Zn.
2: (i) + ΣØ=1 [zz I i} // Implicitly for all E [R]
3: l + R
4: while l < -o
5: m - (1+h1/2
6:
Fm(m) + rRound(F, (m)), o0/110s, (B), (R))
7:
if (m) 2 q then
8:
h (--m m
9:
else
10:
L +-- m
11:
end if
12:
end while
return h.
Theorem B.6 (Replicable Quantile Estimation). Let a, E (0 1) and B E (0, Suppose we have
access
log2 (R)
(log log
1
m
2a
In =
B
a² p² B
i.dd samples from some distribution over [R] with CDF F and q [0. is the desired quantile level. Algorithun B.2 terminates in (pooy((n)) time, is p-replicable, and with probability at least B, outputs some E [R] such that
2(x)2q-0
- <
Our replicable quantile estimation differs from the replicable median algorithm [Impagliazzo et al., 2022] in at least two ways. Firstly, the replicable median algorithm of [Impagliazzo et al., 2022] seems to rely heavily on properties of (approximate) medians in order to satisfy the approximation guarantees. On the other hand, our algorithm works regardless of the desired quantile. Secondly, their median algorithm relies on non-trivial recursive procedure while our replicable quantile algorithm considerably simpler and is based concentration of the CDF through the DK W inequality.
Proof (Theorem B.6). By the DKW inequality (Theorem B.5), sampling
In 2 m 2 ((00/4l0g,(11)3
B
points from our distribution ensures that
ap (l)g.(R)
sup <E(R]
with probability at least our algorithm and then argue about its replicability.
The proof divided into two steps. We first show the correctness of
Correctness of Algorithm B.2. The loop invariant we wish to maintain is that
F(N) a
F(l) q +
This is certainly initially true since our distribution is over [R] {l, R} and hence there is no mass at or below f while all the mass is at or below h R.
Let mi...., mer denote the midpoints chosen by binary search with T (R). By Theorem B.4, we condition on the success of all executions of rRound (m)), ap/ (o), (f)) then their
outputs F, (m:) estimate F(m)) with additive error at most
400/4 log, (R)
a.
1R10g2())
18

---

We update h t- only if
q S Fn (mi) S F(m)) +a = - S F(m:).
Similarly, we update + My only
q> F. (mi) 2 F(mm) aa = 9 F(m:).
Hence the loop invariant is maintained. At termination, with
F(h) 2 9- F(h 11 <
by the loop invariant desired.
Replicability of Algorithm B.2. By Theorem B.4, assuming all prior branching decisions are identical, each new branching decision Algorithm B.2 is (R)peial Since we make at most loga R) decisions, the entire algorithm is p-replicable.
B.5 An Efficient Replicable Learner for OWS
Equipped with the replicable quantile estimator from Theorem B.6, we are ready to present our efficient replicable OWS& PAC learner. We outline below a high-level description of our algorithm which can be found in Algorithm B.3.
1) We first replicably estimate the mass of all the elements that have positive labels. If it is much smaller than some threshold (a)), then we output the zero hypothesis.
2) Then we take sufficiently many samples to get enough data points with positive label and we run the replicable quantile estimation on the marginal distribution of features with positive label to get some [2*].
3) Next, we take sufficiently many samples to get positive point at or below x and then we forward compute the label of æ.
4) The hypothesis we return is the following: its input (i, o)) has index less than i" outputs O. If its input is exactly (i*, o"), it outputs the previously computed label. Otherwise, it forward computes the label using i, a.
Algorithm B.3 Replicable Learner for OWS&
(1,,0),.... (ins m.), accuracy a, replicability p. confidence (3): o, (i,,,,,,,... (1)m, oj,) ) be the subsequence of positive samples, where ij. S i8441* 3: p i IRoundd"/m,, pa/18, P/3)
1: rLearnerOWSdd
2: Let S :=
4: i < 4/2 then
5: return All-zero hypothesis.
6: end if
7: i" rrQunnillEss((( .......................... i., 0/2, 9/3,)/
8: if i;, 2 i" then
9: return "FAILURE"
10: end if
(a", b²) +- ComputeForward(11 (i),
12: return hypothesis h(i, ;=
if < i" output O.
if i" output 6² o and 0 otherwise.
If: r", get (G,b) ComputeForward(i, ("")") and output if â and 0 otherwise."
Theorem B.7. Let p. a E (0, 1) and 3 E (0. p/s). Algorithm B.3 is an efficient p-replicable (a. B)- PAC learner for OWS& with sample complexity
392 In 9216A2
6 32
6 $) = -0 d
(a In 1 1 a3p
= max
In
In
2 3" a p2
a²
and time complexity
O(poly(m)).
19

---

Proof (Theorem B.7). The indicator random variable 1; := 1{0, = 1 is bounded random variable
and its sample mean precisely r/m. Let p E [0. 1] denote the probability mass of the positively labeled elements. By an Hoeffding inequality, 1f/m pl Σ a with probability at least
2 exp (-2ma²)
Since we have
392 6
m 2
In 3'
a² p²
then m//n - pl I po/48 with probability least P/6. By Theorem B.4, the rounded estimate is 9/s-replicable and satisfies
p pl S a/4 with probability at least 9/6. From hereonforth, we condition on the success of this event. Correctness of Algorithm B.3.
First suppose 9/2. Then
ps p
Then Algorithm B.3 always returns the all-zero hypothesis. In this case, the returned hypothesis only makes mistakes on most a fraction of the population and we are content. Otherwise, suppose that p 2 4/2. Thus
p 2 p
2
po
a
2 p
m
16
8
n 2 a
m
8"
1152
6
In
a²p²
8
Let F denote the CDF of the conditional distribution over the positively labeled samples. By
Theorem B.6, the output of rQuantileEst is an index i* E [24] such that with probability at least 8/6.
F(i") 2
a
a
2
a
2
4
2 a
F(i" - 1)
Sa.
We proceed conditioning on the success of the call rquantilesst. Since F(i*) 2 a/s, the probability that ij. > i at most
(1-2) a
g S SE-5 S 8/6.
The last inequality due to n 2 am/e (4/) In(/s)) ij < i" So either i,, i' and we know its string a" and label b", or ij and Proposition B.1 assures that we can obtain the string o" and label b* through forward computation
We proceed conditioning on the event
(o (o*,b") ComputeForward( -
Now, consider the hypothesis we output and action on an input o): If < 1", then always answers 0 so it is incorrect only the positive labels. But this happens at most F(i 1) of the time. If 2 i", h is always correct. Hence the total population error is at most a as desired.
We conditioned probability of failure is at most 8/2.
three events, each of which has failure probability most 8/6. Hence the total
Replicability of Algorithm B.3. By Theorem B.4, the output f f/3 replicable. By Theorem B.6, the output i is 8/3 replicable. From our analysis above, i < with probability at most 8/6 in each of two executions. Thus the total probability of outputting different classifiers is most
0
0
23
2p
p S.p. p.
+
3
3
6
3
9
20

---

B.6 Proof of Theorem 2.1
We now restate and prove Theorem 2.1.
Theorem 2.1. Let d N. The following hold:
(a) [Bun, 2020] Assuming the existence of one-way functions, the concept class OWS with input domain {0, 1] cannot be learned by an efficient no-regret algorithm, i.e., an algorithm that for some yj > Q achieves expected regret [[[r]] S poly(d) TT' using time poly (d, T) in every iteration."
(b) (Theorem B.7) The concept class OWS with input domain {0, 1)d can be learned by p-
replicable (a, -PAC learner with sample complexity m poly(d, Va, \o2 log(1/)) and poly(m) running time.
Proof (Theorem 2.1). Combining the hardness of efficiently online learning OWS (cf. Theorem B.3) with the efficient replicable learner of Theorem B.7 completes the the proof of Theorem 2.1. D
C Efficient Replicability and SQ Learning: Parities
C.1 The Proof of Lemma 4.2
Algorithm C.1 Replicable Learner for Affine Parities [(x) T x+ under the Uniform Distribution
rAffParityyaccurrr a, replicability p. confidence (3):
2: Draw single sample fx("), f(x
where zo U.
3: Draw (d log({/o3) samples (zr, f()) so that with probability at least 1-3, we obtain d' linearly
independent offsets (2,y) := (x + , [xx) + ()) say (z(*), y ,)()),,.... ..... (2(4), yd()).
4: Run Gaussian climination to obtain the unique solution w such that w 2, = ys for each E [d].
5: Compute b = f()(0) + w x(0)
6: Return (w, b).
We now repeat and prove Lemma 4.2, which states the correctness of Algorithm C.I.
Lemma 4.2. The concept class of affine parities AffParity over {0, 1] admits a p-replicable algorithm that perfectly learns any concept with respect to the uniform distribution U with probability of success at least - 3. The algorithm has O(poly (d, log 1/33) sample and time complexity.
Proof (Lemma 4.2). For any E [cl, observe that
( = f(x + f(x = w T xZ + b T (0) + b = --b--we Txx + (0)) = w Tx(0)
Thus the dataset of offsets {( (() y { uniquely determines the linear function w. Having Iearned w, recover the value of 6 by evaluating at any point in the original dataset, say at the first point.
C.2 Background on Parities and SQ
Statistical Queries We start with some background on the SQ model.
Definition C.1 (SQ Learning.. A concept class 6 with input space (0, 1)d is learnable from statistical queries with respect to distribution 'D if there is a learning algorithm A such that for any E & and any a > A produces an a-approximation of e from statistical queries; furthermore, the running time, the number of queries asked, and the inverse of the smallest tolerance used must be polynomial in d and 3/a.
Definition C.2 (SQ Hardness). Consider a concept class & with input space (0, 13d. Fix a tolerance =poly(1/a) and accuracy = O(1). We say that E is SQ-hard under distribution 'D if any SQ algorithm requires (poly(d)) queries of tolerance at least a-learn E.
The standard way show SQ hardness is by showing lower bounds the so-called SQ dimension [ellman et al., 2017] of the corresponding problems (we omit the formal definition of SQ dimension as it is beyond the scope of the present work). Such lower bounds this dimension establish lower bounds on the running time of any SQ algorithm for the problem not on its sample complexity.
We remark that this stronger requirement in regret is necessary since the trivial random guessing algorithm achieves o(I') regret in finite domains (cf. Appendix A.3).
21

---

PAC and SQ Learning Parities The standard class of parities Parity is given by the subset {fs.o S S [d] of AffParity. The standard algorithm for learning parity functions works by viewing a set of n. labelled examples as set of n linear equations over the finite field with two elements E2. Then, Gaussian elimination is used to solve the system and thus find a consistent parity function. This algorithm is extremely brittle to noise: even for the uniform marginal distribution DD = M. the problem of learning parities over {0, 1 does not belong to SQ. In particular, a standard result is the following:
Fact C.3 ([Kearns, 1998)). Even learning parities Parity C AffParity with input space (0, 13 1ddd is SQ SQ-hard under the uniform distribution U.
C,3 Gaussian Elimination is not Replicable
In this section, we give simple example where Gaussian elimination fails be replicable.
Proposition C.4. For any d 2 3 and S S [d] with 2 & S S [d], the following holds: There is some na 2 1, such that for any n 2 Rdd, there exists a distribution 'D such that the n-sample Gaussian elimination algorithm for PAC-learning parities (xx Eies Ti in the realizable setting fails be //1t-repiccabe.
Proof (Proposition C.4). Let e1,..., Rd be the standard basis of zg, p E (0, and consider the distribution D such that
2 -P. ((e²)
D(e))= p
D(e;) 3(d 2) i 2 3.
The probability not observing any ei after n samples is (1 - p)". We set = 4/2 S 1/2 so that (1 (1- p)a 1/2.
For sufficiently large na E N, we observe all e,, 2 3 with probability at least 3/4 after n samples. Thus with probability observe e3...., Ed but not 61. In the first case, we fully recover since we are promised that 2 & S. In the second case, algorithm is unable to determine if 1 E S since we do not observe e and the best it can do randomly guess. Thus the probability we output different classifiers is at least 2 1/4. 1/4 1/2 1/16.
least 1. we observe e1, . Cd and with probability at least 1/4,
Proposition C.4 shows that Gaussian elimination fails in general to be replicable regardless of the number of samples requested.
C.4 Replicably Learning Affine Parities Beyond the Uniform Distribution We restate our main result.
Theorem C.5. For any dimension d, accuracy a, confidence 3 and replicability p. there exists some
pooyydd, 1/a,//o, log(?/3) such that there exists monotone distribution D over {0, 1]d which
(a) Gaussian elimination is not n-sample replicable with probability (2(1) under D for the class AffParity,
(b) there exists n-sample p-replicable algorithm for (a:, (e.33)PACC learning the class AffParity with respect to 'D with poly(1) runtime, and
(c) even learning the class Parity is SQ-hard under the distribution DD
Before proving Theorem C.5, we derive three useful lemmas. Fix dataset size be defined later. We pick the distribution D to be a Boolean product distribution (pi...., Pa) E [0, 1]d such that the first d coordinates are unbiased (p: = 1/2) for i [d 1] and the last coordinate to be highly biased towards In particular, pick pa = Da((1) = 1/2 2 1/2. This distribution is monotone by construction.
The naive n-sample Gaussian elimination algorithm to be replicable with constant probability over the distribution D =
Lemma C.6.
Proof. Consider two independent draws S1 and S, from D of size n. With constant probability 1/2 1/2 = 1/4, S1 will contain vectors that have only I's in the last coordinate while Sy will contain at least one vector with a zero in the last direction. Then there are exactly two hypotheses that satisfy Si. one that contains the last coordinate and one that does not. This can be seen by reducing to an instance of the (d 1) dimmennsional parities problem obtained by ignoring the last coordinate and flipping the bits of the labels.
22

---

On the other hand, for sufficiently large, the subset of vectors 5222 C S2 that have I's in the last direction is satisfied by the same hypotheses as S1. However, only one of the two hypotheses also satisfies the other subset 2 S S2 consisting of entries with 0 in the last direction.
Thus the candidate hypotheses that satisfy Si, S2 differ and the algorithm can at best output a random guess for S1, which will be inconsistent with the output on S2 with overall probability at least 1/2 =//==/8.
Lemma C.7. The decision tree complexity of is (
Proof. Since D is a product distribution, the pmf only takes on different values and thus has depth ((1).
Lemma C.8. The class of affine parities AffParity with imput space {0, 13ah is closed under restriction.
Proof. Let f be an arbitrary affine parity function, i.e., f(x)= = b Eies 2; for some b {0, 1) and S S [d]. We remark that the operator + is in Z2. Consider an arbitrary direction E [d] and arbitrary bit V/ E {0, 1}. We will verify that fi=o' remains the class of affine parities. If $ S, then fi=v = AffParity. Now, if E S and = 0, it holds that fi b Eies(( 2, AffParity and if B' 1, it holds that fi- (b+1)) EiESr(1) 24 AffParity. Hence, affine parities are closed under restriction.
We are now ready to prove Theorem C.5.
Proof (Theorem C.5).
(a) By Lemma C.6.
(b) We can employ the lifting algorithm of Theorem 3.2 to replicably and efficiently learn affine parities since (i) the decision tree complexity is constant, (ii) the distribution is monotone, (iii) affine parities are closed under restriction and (iv) we have an efficient replicable algorithm for affine parities with respect to the uniform distribution (cf. Lemma 4.2).
(c) we consider the subclass 6² = {fs.u : S S [d - 1]], we have that [x)gg((())(())) for any pair of distinct functions f.g E '6" due to the product structure and the unbiasedness of the first d - 1 coordinates of D. This implies the SQ-dimension of the class of parities is at least 2d-1 (222) and so learning parities is SQ-hard under D.
D Lifting Replicable Uniform Learners
In this section, we will provide our general lifting framework for replicable learning algorithms that is needed in order show Theorem C.5.
D.I Preliminaries for Replicable Uniform Lifting
We start this section with some definitions which are necessary formally state main result of Theorem 3.2.
Definition D.1 (Decision Tree (DT)), A decision tree T 10, - TR is a binary tree whose internal nodes query a particular coordinate, and whose leaves labelled by values. Each instance x E {0, 1)dd follows a unique root-to-leaf path in T: at any internal node, it follows either the left or right branch depending on the value of the queried coordinate, until leaf is reached and its value T(x) is returned.
Definition D.2 (Decision tree distribution). We say that distribution D over {0, 1]a is representable by a depth-l l decision tree, if its pmf is computable by a depth-E decision tree T. Specifically, each leaft t is labelled by value Pt- that D(x) Pt for all x E t. This means that the conditional distribution of all points that reach a leaf is uniform.
Let us consider distribution over {0, 1]d, The definitions above suggest natural measure the complexity of DD The decision tree complexity.
Definition D.3 (Decision Tree Complexity). The decision tree complexity of distribution D over
(0. 1)dd dd is the smallest integer & such that its probability mass function (pmf) can be represented by depth-l decision tree.
23

---

Next, we define useful structured family of distributions. Let the binary relation > denote pointwise comparison.
Definition D.4 (Monotone Distribution). A probability distribution D over {0, 1 is called monotone for any x ž y holds that D(x) 2 D(v).
Just in Blanc et al. [2023], for arbitrary non-monotone probability measures, algorithm requires access to a conditional sampling oracle (cf. Definition D.5) defined below.
Definition D.5 (Conditional Sampling Oracle; Blane et al., 2023). A conditional sampling oracle for distribution 'D over {0, 1 proceeds as follows: suppose we condition on some subset I of the d variables having a fixed value E (0.1)', that case, the oracle generates a sample from the tree
conditionnl distribution, i.e., draws sample I-1 DD- 1 b).
Definition D.6. For tree T and leaves 8 E T, E(E) = Σter 2 2-1 f(), where |e] is the depth of the path to reach leaf f.
As an example of this notation, note that
[())((a)
BIE E Bf El] ETET
Σ LE
U(E)
where u(t) is the uniform mass of the leaf f, i.e., u(()) = 2 2- This implies that
(eer/E (x) E 4] = E since the set of leaves partitions the set {0, 1]d.
D.2 Main Result: Lifting Replicable Uniform Learners
We now restate our main result Theorem 3.2. For the sake of presentation, we defer its proof to Appendix E.
Theorem 3.2 (Lifting Replicable Uniform Learners). Consider a concept class & of functions : {0, 1} + 1) closed under restrictions. Suppose we are given black-box access to algorithm such that for any ,', E (0, 1), given poly (d, 1/d', log(2//²) samples from U,
(i) is g'-replicable with respect to the uniform distribution U,
(û) PAC learns 6 under the uniform distribution to accuracy a' and confidence 3r, and, (iii) terminates in time poly(d, 1/2,, 3/8 log()/a')).
Let a,p E (0,1) 1) and B E (/)) For m = poly(d, 1/a, 1/. log(1/)) and M poly(d, 1/a, 2/, (og)))))//)))0000 the following cases hold:
(a) D is a monotone distribution over {0, 1)d representable by a depth-f E. decision tree, there is an algorithm that draws M samples from DD is p-replicable with respect D, PAC learns E under D with accuracy a and confidence 3, and terminates in poly(M) time.
(b) D an arbitrary distribution over {0, 1] representable by a depth-& decision tree, there an algorithm that draws M labeled examples well as M conditional samples (cf. Definition D.5) from D, p-replicable with respect to D. PAC learns '6 with respect to D with accuracy a and confidence B, and terminates in poly(M) time.
We emphasize that our result for monotone distributions D only requires sample access to D. For arbitrary non-monotone probability measures, our algorithm requires access to conditional sampling oracle (cf. Definition D.5)
E
Proof of Theorem 3.2
E.1 Preliminaries
We start this section with some useful definitions, coming from the work of Blane et al. [2023]. Definition E.1 (Weighting function of distribution). Let D be arbitrary distribution over {0, 1)
We define the weighting function (Dr Dzx)...
Remark that the scaled pmf satisfies
E [=-
Σ 2-d 2d =
DE @0(0.11
For E {0, 1]d and e [d], we write xi to denote the binary vector obtained from æ by flipping its i-th bit.
24

---

Definition E.2 (Influence of Variables on Distributions). Let DD be a distribution over {0, 1 and fD( = (a) be its pmf scaled up by the domain size. The influence of a coondinate E [d] on Sd is the quantity
a distribution D over {0, 1]
Infl;(fD) Ex-il -
We also define the total influence Infl(fr) -iejal Inf);(fo).
Intuitively, the influence of variable measures how far that variable is from the uniform distribution. Suppose fo is computable by depth-& decision tree 7', Then we can write for any a E 1)
(
PE 1/x E E}.
RET
where the sum is taken over the leaves of T and pt D(y) is the (same) mass D assigns to every y E E. Then we have
Infl;(Dp) = PeawulDCC - [0(x
Σ
(D(x) D(
=011111
Σ REE
- E
=
If i is not queried by any internal node of T, then x always belongs to the same leaf and this value O. Otherwise, we can trivially bound this value by 2 using the triangle inequality. This discussion leads to the following observation.
Fact E.3. If ID is computable by a depth-l decision tree, then its total influecce most Infi(f)) S 26.
For monotone distributions over the Boolean hypercube, influences have convenient form: Proposition E.4 (Lemma 6.2 in Blanc et al. [2023]). If the distribution 'D over {0, 1 is monotone, then for any E [d]
Infl,ff) = Ep[xx)
Definition
E.S (Restrictions). Given a sequence of (coordinate, value) pairs (i1,, bi),... (in, by)), we use to represent x. with the coordinates in overwritten/iserted with their respective values. For function f: (0, - R, we let fn be the function that maps x to f(xx)
Definition E.6 (Everywhere r-influential; Definition 4 in Blanc et al. [2022b]). For any function f: 10, + R. influence threshold T > and decision tree T {0, 13d + I. we say that T is everywhere r-influential with respect to some I for every internal node v T, we have
Infla(e)(f)) 2T.
Here i(u) denotes the variable queried and fo denotes the restriction of f by the root-to-u path in T, iee. the variables in the path are fixed to the corresponding internal vertex values.
E.2 Replicable Proper Learner for Decision Tree distributions
Our algorithm that achieves the bounds of Theorem 3.2 proceeds two-stage manner: we first replicably learn the decision tree structure of 'D and then use the replicable uniform-distribution learner learn f restricted to each of the leaves of the tree. carry out the first stage, we give an algorithm that replicably learns the optimal decision tree decomposition of a distribution D:
Theorem E.7 (Replicably Learning DT distributions). Fix a, E (o, 1) and B E (0, f/3). Let D distribution over (0, 1)dd that representable by depth-l decision tree. There is an algorithm that
(a) is p-replicable with respect to D, (b) returns depth-l tree representing a distribution D' such that TV(D, D') S with proba- bility at least 33 over the draw of samples, (c) and has running time and sample complexity
= = poly(d, 1/2, l/p, log( (24/2)010 -
25

---

For monotone distributions, the algorithm only uses random samples from D, and for general distributions, it uses subcube conditional samples (cf. Definition E.12).
Proof (Theorem E.7). The proof of this result follows directly by applying either Lemma E. 1 (for monotone distributions) Lemma E.13 (for general distributions with subcube conditional sample access) to Theorem E.8, which are provided right after.
Essentially, making the decision tree learning routine replicable boils down to estimating influences on D in a replicable manner. This is the content of the upcoming results.
Theorem E.8 (Replicable Influence = Replicable Decision Tree). Let be a distribution that is rep- resentable by depth-L decision tree. For any E (0, assume access to p' p'-replicable algorithm r InfflEst for estimating influences of distributions over 10, using poly(d, 1/o///// log(1/)) samples and runtime. Then, for any p E (0, 1), there an algorithm rBuildDT (cf. Algorithm E. that
(a) is p-replicable with respect to D, (b) returns depth-L tree representing a distribution such that TV D') s a, with probability at least 1 B over the draw samples, (c) and has running time and sample complexity
M p d. 1
d(24/a)01)
log d(28/a)01))
d (22/)0010)
P
B
( (24a)
(2t/a)
+0
log
(22/a)010
a²pp
B
poly(d, 1/, 1/, log(/8)) (2%/
Algorithm E.1 Replicably Building Decision Tree for D
1: rBuildDT:
2: Input: Access to D and fo as in Definition E.1, restriction π (cf. Definition E.5), access to rInflEst, depth f, influence threshold т, accuracy a, confidence 3, replicability p.
3: Output: A decision tree T that minimizes Ere (Lfr[[n where E T is the collection of leaves (each corresponding some restriction) of I' among all depth-E, everywhere 7-influential (cf. Definition E.6) trees.
4: for i E [d] do
5:
+InflEst(ffomn.l
rInflEst ((f)) min(7/4, a/2d), 2002 20111))01))
6: end for
7: Let S C [d] be the set of variables i so that rInflEst(((o)))). 2 3r/1.
8: if S = or é then
9:
// reppiccabyy estimate Ps. = 2| ProwD [a consistent with
(cf. Theorem B.4)
Ωx - a//2aacurrate, p/ ((0) (attaubble///((///aaaaaaa 8/12(2/aa00()) conffddenn
confident estimate of px
11: return new leaf node with value P.
else
13:
i S do
14:
construct the tree T; with (o))( + 24
15:
leftSubtree(T.) + Bu - 17: rightSublree((.)) <- rBuilaDT(P,, x Ut, -1--1,,,,1111, 1,,,,,,,,,,,p
16:
18: end for
19: I/ Among (Ti return the one that minimizes the estimated total influence
20:
I/ Exer,
Ejela rInflEst((Jp):.]] where (Jp); (JD)a())
21:
I/ for the restriction (() corresponding to path from the root the leaf /
22: Let g(l) = Eye(g rInf IInflEst(((( [Inff]ss((/Dpss]]]
23: it + argmingss EIeT [g(() Σier, 2 2-14)((() 2=
24: return Ti-
25: end if'
26

---

Before proving Theorem E.8, we state Theorem 3 of Blanc et al. [2023], from which the correctness of Algorithm E.1 follows. Let BuiltDT be the algorithm obtained from rBuildDT (cf. Algorithm E.1) with the following adjustments.
(i) Replace the replicable influence estimator rInflEst with any (possibly non-replicable) influence estimator and
(ii) replace the replicable mean estimator of ps with simple (non-replicable) sample mean.
Proposition E.9 (Theorem and Claim 5.5 in Blanc et al. [2023]). Fix a, E (0, 1). Let D be distribution that is representable by a depth-L decision tree. Given oracle access to an estimator for influences, the algorithm BuildDT with the choice of "/sê returns depth-l tree representing distribution D' such that (D, D') I a with probability at least 1 - B. If the oracle terminates in unit time, the running time of the algorithm is d (f/a)0(t)
Remark E.10. A few remarks are in order regarding Algorithm E.I.
1. Blanc et al. [2023] identify the task of learning of decision tree for distribution 'D with learning its scaled pmf f DdD In order to remain consistent with their convention, the values the tree leaves produced by our replicable decision tree algorithm (cf. Algo- rithm E. also correspond to the scaled pmf. Note that we do not directly use the values at the leaves and hence this convention is immaterial to our application.
2. Estimating the inftuences to an accuracy of 7/4 ensures that any variables in S has inftuence at least 7/2 and every variable with influence at least T is captured in S. Estimating the inftuences to an accuracy of af2d ensures that the estimated total inftuences are accurate up to error at most a. Note that the computation for ERET, [g())] (ef. Definition D.6) does not incur additional error since the weights of the sum are appropriately chosen.
3. Pr is the mean of a [0, 2|x |-bonded random variable. By an Hoeffding bound and Theo- rem B.4, consuming poly(2', 1/a, 1/8", (ar) samples from D suffices estimate this quantity up to a a/12- 2 -accuracy, p o'rreliccability, and 3' d''oofideece.
4. Taking into account the estimation error of influences, each variable in S has influence at least 7/2. For any depth-l decision tree, the sum of all variable influences is at most 26 (ef. Fact E.3). For any restriction π, (fD)z is depth-l decision tree and thus has at most 40/7 variables of influence at least 7/2. For the choice of = a/sl', there can be at most (48/=)* (21/a)(0) recursive calls within Algorithm E.I.
Each recursive call estimates d influences and at most 1 mean of a bounded random variable. All in all, we need to replicably estimate d (21/))0(0) variable influences and at most (21/a)0(0) bounded means.
We are now ready to prove Theorem E.S.
Proof (Theorem E.8). By assumption, for any o' E (0, 1), rInflEst is p'rreplicable and returns a-accurate estimates for influences with confidence 3 using pdly /o, log(l/))))))))) 1/p)) samples and runtime.
The replicability of Algorithm E.1 follows directly from the replicability of the influence estimators and the replicability of the standard rounding scheme (cf. Theorem B.4). By Remark E. 10, it suffices to call the replicable influence estimator and the replicable mean estimator for p- with replicability parameter p' / p/[2d(2%/)) jO(] for the union bound and similarly for the confidence parameter. The sample complexity follows from our remark above.
Let us now condition on the event that each call of rInflEst and estimation of expected total influence is successful. Conditioned on this event, the correctness of the algorithm rBuildDT directly follows from Proposition E.9. In particular, if we condition on the event that each call to rInflEss and each replicable estimate of pr is successful, our algorithm reduces to the BuildDT algorithm of Blanc et al. [2023].
E.3 Replicable Influence Estimator for Monotone Marginals
In this section, we provide the main subroutine of our replicable DT distribution learning algorithm. We begin with replicable influence estimator for monotone distributions.
Lemma E. (Replicable Influence Estimator for Monotone Marginals). Fix i E [d]. For any a, G, p E (0, 1)3, there is an efficient p-replicable algorithun r Inf (D, a, 3, p) such that given
27

---

an unknown monotone distribution D over {0. 1]. computes an estimate of Infi;(fD) up to accuracy with probability at least 3 using O(a 2p 2 (oo((/)) time and random samples from D.
Proof (Lemma E.11). By Proposition E.4, since D is monotone, we know that Inft,(f)) ED [z:]. Thus we can replicably estimate this expectation with 0(a-2p=2 log()))) samples and sample- polynomial runtime through replicable query rounding (cf. Theorem B.4).
E.4 Replicable Influence Estimator for Arbitrary Distributions
We further design replicable influence estimator for arbitrary distributions 'D over {0, 1] using subcube conditional sampling.
Definition E. A (subcube) conditional sampling oracle for distribution D over {0, receives as input a subset (subcube) S = {0, 1) and generates a sample from the conditional distribution
Ds(x) = D(x S) D(x) far E
D(S)
This conditional distribution is essentially the truncated distribution Ds with truncation set S. The subcube conditioning oracle is well studied by prior work in distribution testing and learning [Canonne et al., 2015, 2021, Fotakis et al., 2022, 2020, Gouleakis et al., 2017].
Algorithm E.2 Replicable Influence Estimation for Arbitrary Distributions via Conditional Sampling
1: rInf
2: Input: Distribution D over {0, 1] conditional sampling oracle for D, desired accuracy a, desired confidence B, desired replicability
d and fo as in Definition E. coordinate i E [d], access to
P.
3: Output: A estimate v of Infl; such that |u [nf]; S a with probability B.
4: n < 0 log()/))
5: for j < 1..,, n do
6: Draw a fresh random sample xo55) ~ DD
5( + (x(1)) U ((x()))=), where (z( is xτ6 with its i-th coordinate flipped
7:
8: Draw (aa-)) independent samples from the conditional on 8(3) distribution D(-1SU))
9:
Let Letp() E [0, be the fraction that we observe .()
10: q0)) + +pp6) - (1 (1-12) )
end for
12: q - 1 - 9(5)
13: return rRound(y, ((ound( p) (see Theorem B.4 with T 1)
An adaptation of the proof of Proposition 6.5 in Blanc et al. [2023] combined with the replicability properties of Theorem B.4 gives the following result, which we provide for completeness but do not use in our applications. The algorithm is presented Algorithm E.2.
Lemma E.13 (Replicable Influence Estimator for Arbitrary Marginals). Let DD be a distribution over {0, 132, fo as in Definition E. and, assume sample access to a subcube conditional oracle as Definition E. For any a, 8. p (0, 1) and E [d], Algorithm E.2 p-replicable and, given O(a +p 3 (1/)) subcube conditional samples from D, it computes in pooyll--o time an estimate v that satisfies | Tnfll (fx) S a with probability least B.
As proof sketch, let us call the above algorithm deplInfEst(DDi..co a.) The correctness of the algorithm follows from the observation that for any distribution D, coordinate i and a E (0. 1). for any execution [n]]. holds that [Eq()) Inft, (fr)) < a. Hence obtain high probability estimator. suffices obtain ((a log()/)) copies of (65)) and take the average q. Finally, make the algorithm replicable, it suffices to estimate the average q replicably. This can be accomplished at an extra cost of order 1/p² using the standard rounding routines (cf. Theorem B.4). Since each iteration requires 1/a2 subcube samples, the sample complexity of our algorithm follows.
E.5 Useful Subroutines & Results
In this section, we provide a set of useful results that we will use in our proofs. Proposition E.14 (Corollary D.21 in Esfandiari et al. [2023b]). Let a., p E (0,1) and B E (0, p/3). There a p-replicable algorithm FFiniteDistrEst((.. a. 9, () that outputs parameter estimates p for a finite distribution D of support size N such that
28

---

(a) pp0)) -p S for every E [M] with probability at least - B.
(b) plu) 2 for all [N].
(c) E
Moreover, the algorithm has sample complexity
In 1/3 + N
=0
-0 a²p² 3
( log
m =0
(p - 3)))
and poly(m) time complexity.
Proposition E.15 (Jannso, 2018]). Let Y, be geometric variable with success rate q. Then Y > = Y, is the number of draws until we obtain m successes. Then
P P
m I (xp(1-1A
In other words, suffices to perform ((m/1 log()/s)) Poisson trials before succeeding m times with probability least 1 BB
Proposition E.16 (Replicable Boosting of Success Probability). Let E (0, E (/s)/s), and A 2 O. Suppose A is a p'-replicable (a + A, 1/CC learner for the concept class E under fixed distribution D over {0, 1) that m(a, poly(d, 1/a, 1d²) samples for any p' E (0, 1). There is a p-replicable (2xx + A, BPC learner ABoostA(D, (D, a, B, p) for '6 under D for any a, P E (0.1) that has sample complexity
(22oo((/o) . (10g) 1 !) 3
log (1/B) (4/)) a²p² log
log(4/s)
d. P and comple-polynomide running time.
+0
poly (d. 1/a, 1/e, log(l//))))))) (1a)).
Proof. Let r be the algorithm that runs A for n = O(log 1/8) times (each with m m(+/a, 9/2n) samples), replicably estimates the population error of each hypothesis, and outputs the hypothesis which has the lowest estimated error. Running A for */pn-replicable so the first step is 9/2-replicable. Moreover, at least one of the hypotheses we output (a + A)-close the optimal hypothesis with probability at least 111//22 $/2.
Olog 1/z) times with samples per run guarantees that each execution is
By an Hoeffding bound on the empirical error of hypothesis, we can estimate the population error of hypothesis an accuracy of 0p/4-2n and confidence f/2n using Onn2a -2p-~2lo(("///" log("/s)) samples. By Theorem B.4, we can make this estimate r/2n-repl at the cost of reducing the accuracy to while maintaining the confidence parameter 8/2n.
It follows that the output hypothesis is p-replicable and with probability at least 1 3, its population error at most 2xx A.
E.6 Proof of Theorem 3.2
In this section, we show how to lift replicable algorithms that learn over the uniform distribution to replicable algorithms that learn with respect to arbitrary distributions, where the sample complexity and running time depend on the decision tree complexity of the target distribution. Let D(- T') denote the conditional distribution on leaves, i.c., D(1 | TT) == Exer D(x).
Now, our learning algorithm is designed for an exact tree distribution. However, we can only estimate the tree representation of the actual distribution, i.e., the conditional distribution at a leaf subcube is uniform in the tree representation but not necessarily uniform in the input distribution. To show that our learning algorithm can accommodate slight errors in the tree distribution estimation, we introduce the following definition.
Definition E.17 (Robust Learning). For any concept class E and algorithm A, we say that A (o.,8 B, robuussyyy learns & using m samples under the uniform distribution for any nj >> O and class
2n = {distribution D over {0, 1]d TV(U, < <n}
it holds that A(a en, learns 6 using m samples with respect to the distributions in 2xy Proposition F.18 (Proposition 7.2 from [Blanc et al., 2022b]). For any concept class & and algorithm A. A (a,, PAC learns & using m samples under the uniform distribution, then the exact same algorithm A also (a, 3 + 1/3, 3m) robussly learns E using samples.
29

---

Algorithm E.3 Replicable Lifting
1:
rLift
2: Input: decision tree 7' (from (BuildDT), algorithm A for p' p'reepicabble 3'',,'"--eannnn under the uniform distribution using m(a', p (3)) samples, distribution D, accuracy a, confidence 3, replicability p.
3: Output: A hypothesis h: [0, [0.
4:
5: M1 < poly(22, 1/a 1/8 log(1/))
6: M2 t- mm(//o,//2 1/0) poly(d, 2-, //, 1/, log
7: // Estimate leaf distribution (ef. Proposition E.14)
T),, 9/12.2', 8/2, 9/3) using M1 samples 9: Draw dataset S ~ Da of size M2.
8: D(- [T) IFiniteDistrEst(DD
10: for each leaf t < do
11: if (t T) 2 //4-2' then
12:
Let S, be the subset of samples in S that reach t.
13:
Create a set Si consisting of points in St but where all coordinates queried on the root-to-leaf
path for l. are re-randomized independently, making the marginal distribution uniform.
14:
For p' E (0, 1), choose its parameters so that A A(a/e, p', 1/6) is p'-replicable and (a/s, 1/6 + 1/3, d') rrobustly learns '6
15:
Get h4 by calling rBoost (S", 9/6, P/3-2', 9/2-2*) (cf. Proposition E.16).
else
17:
Get h that outputs random guess according to shared randomness.
end if
19:
end for
Return the hypothesis h such that given input z, finds the leaf & that xr follows and outputs hx(x).
We are now ready to state the main result of this section, from which the proof of Theorem 3.2 closely follows.
Theorem E.19. Consider concept class o of functions f 10, d restrictions. Fix a, B, c, > and m, E N. Suppose we are provided black-box access to an algorithm A that
{0,1} closed under
(i) is p'-replicable with respect to the uniform distribution for any p' E (0, (ii) (a',8' 1/3 -yrbuusyyy learns '6 for any a',3' 3' E (0, 1), and
(iil) consumes mla', ,,', (3) poly(d, (/a, 1/8' (2) samples and computation time under the uniform distribution.
Let M1 = poll(22 1/2 l/e, log(1/3)). M2 1000=m(/aaaa m(a/6, //2", , 1/6) poly(d, 28, 1/a, log(//))) and : M, M2 S poly(d, 2 1/a. 1/e, log(1/)).
For any function f 6, distribution D over {0, 13d, depth-& decision tree T computing the pmf of distribution DDT where TV(D, Dr) < o/6c, the following holds. The algorithm rLift(T, A, D.,a,,a. ()P) p) (ef. Algorüthm E.3) is p-replicable, has O(M) sample com- plexity, terminates in (M)y(M) time, and its output is a-close to f with respect to D with probability at least 1 -
Before we prove Theorem E.19, we state two useful lemmas.
(0, A 0. and E N. Let MyBoost poly(d, 2 1/, 1/, log(1/s) be the number of samples that rBoost (cf. Proposition E. E.1 requires to boost a p² -rereccie (7/6 + A, 1/2)-correct learner (that uses poly(d, 1/a, 1/d)) samples and run- ning time) to a 2/3-2'-replicue
Lemma E.20. Fix a. p'p.3'
learner with accuracy a/s + A +a/s a/3 + A and confidence 8/22'. Condition on the success of :FiniteDistrEst in Algorithm E.3. Then with probability at least 1 1 8/2, every E T with ((t)) 7) 2 a/42", , we observe at least MzBoost samples reaching t. from S.
Proof. Condition on the success of the call to FFiniteDistreat. Then for every T with D(t () 2 a/4.2,, we have Dit (T) a/622. The probability of not observing such in a dataset
30

---

of size is at most (1 2/6--1" I cxp(-no/6:²") By union bound over the at most 6-2%/a such t,
the probability failing to collect each such is at most
6.
exp(-na/62'")
To drive this below the constant 2/2, it suffices to take suffices take sample of size
By Proposition E.15,
MrBooetl 2 log -
log )) - M2
Om log 1/8) =0
a
to collect copies of each such with probability at least 18/2.
Lemma E.21 (Lemmaa B.4 from [Blanc et al., 2022a], Fact 7.4 from [Blanc et al., 2023)). For any distribution and decision tree computing the pmf of another distribution Dr.
Σ Pr [x reaches 8] (V; (Dr).) S (EV(D,Dr), RND
1ET
where (Dr), (resp. D.) is the conditional of DT (resp. D) the subcube induced by the leaf I. Note that in the statement of the lemma above, PIa-D (æ reaches = D(t | T) and (Dr)e is the uniform distribution on the subcube represented by the leaf t. We are finally ready to prove Theorem 1.
Proof (Theorem E.19). We first note that the sample complexity of the call to the routine FFiniteDistrEst is M1 poly(2', (aayy22,144 1/a, 1/p, log(1/)) (cf. Proposition E.14). Throughout this proof, we condition on the 1 1- #/2 probability of rFiniteDistrEst succeeding. Let be the output of rLift(T, A, S). We now argue separately about the accuracy and replicability of the algorithm.
The accuracy of the learner h = rLift(T, AA, AA is analyzed follows. For any leaf I. of the tree T, let ht the associated predictor. We have that
Accuracy.
Pr [b(x) + fx))) Σ Pr Ia reaches znD
Pr a~D:
[h((2) + f(()))
xnD
Each hypothesis h4 is obtained either by running rBoost (ef. Proposition E.16) on the sample S given that D( T) 2 a/4.2" or corresponds random guess otherwise.
On the other hand, from the choice of estimation error to the call for IFiniteDistrEst. each leaf t on which output the random guess hypothesis must satisfy Præ-D[ reaches t] < a/3-2f. The
overall error contribution of such leaves is thus at most o/3. It follows that total error is at most
Pr f()) Z~D
Σ
Pr [ar reaches Pr [he(z) (z)) awDD
LET (ET:
Fix a f. E 7 on which we run rBoost,-- Recall that D; and (Dr), denotes the conditional distribution on the leaf subcuhe over the coordinates not fixed by T (t) where is the restriction corresponding to t. Here the underlying distributions are the input distribution D and tree distribution Dy. Let Di, (Pr) denote the distributions over {0, 1)dd obtained from D., (Dr)² by re-randomizing the coordinates from æ. Then (Dr), Y is precisely the uniform distribution U4 over (0, 1)d and D/ satisfies
TV(D),u) TV(D,, (D+))
Σ [P((x) (Dr)(t))
2()(
(2((x) (Dr)(())
(2)()) - (Dr),(z)
D'(x)) 2 (z), (PT){((
ZEt = (DT)).
31

---

Based on the re-sampling step of the algorithm, we know that any point in S is an i..dd sample from Dj and labeled by the function fü. which lies in 6 thanks to closedness under restrictions.
By (9/6, 1/6 + 1/a, c)-robust learnability, A in fact (0/6- + cTV 2)) 1/2)-PAC learns 8 under the distribution D/- We now apply Lemma E.20 with A = (D; L):: the leaves on which we run r have at least MyBoost samples where MyyBoost poly(d, ( 2 1/a, 1/p, log()/)) is the number of samples that rBoost requires to boost p'-replicable (*/6 + cTV (T, L1), coorect learner (that uses poly(d, (d, !/a, 1/p²) samples and running time)
r/s-2f-replicable leamnrr with accuracy a/6 cTV( ) + 9/6 = a/3 + cTV 2) and confidence #/2.²'.
Then by Proposition E.1 with probability least 0/2-2' over the data S/. the hypothesis h, output by A satisfies
Pr (m)( + ["))] S a/3 + +cTV(,) = 0/3 + TV(D,, (Dr).) IND,
All in all, Combined with the expression of total error above, this means that with probability at least 1 B.
Pr [h(x) + (x)) S 20/3 + Σ Pr Pr reaches 8) (V(D,,(Dr).) RnD
anD 1ET
We finish by applying Lemma E.21, which ensures that the sum over leaves above is upper bounded by 2TV(D, Dr) I 8/3c and so the total misclassification error is at most a with probability least 1- B.
Replicability. We assume we are given the same decision tree in both executions. Next, we note that #FiniteDistrsst is s/a-replicable and succeeds in two executions with probability at least 1 1-2 2- 1-2-8/2 > 1 p/3. Conditional on the events above, it suffices to show that for any leaf of the tree, the algorithm rBoost, replicably outputs a hypothesis. Since there are at most 2 leaves and each call of rBoost has replicability parameter p/3-2', the entire procedure is p-replicable.
Before moving on to the proof of Theorem 3.2, we state one final lemma.
Lemma E.22. For any concept class E and algorithm A, if A p-replicably (ar,8 (3-learns b using m samples under the uniform distribution, then the exact same algorithm A also p-replicably (a. 3 + 1/s, 3mbburuustly learns '6 using m samples under the uniform distribution.
Proof (Lemma E.22). The proof follows directly from the analysis of Proposition 7.2 in Blanc et al. [2023] (cf. Proposition 18). The replicability of the algorithm is trivially preserved since the algorithm does not change.
We restate the statement of Theorem 3.2 below for convenience before its formal proof.
Theorem 3.2 (Lifting Replicable Uniform Learners). Consider concept class ' of functions
f {0, 1 + 10 closed under restrictions. Suppose we are given black-box access to an algorithm such that for any a' ,',p', .'.'.'' ,B' E (0,1), 1), given poly(d, dd 1/a', 3/e llg((/3)) samples from U, (i) is prrreliccable with respect to the uniform distribution U,
(ii) PAC learns '6 under the uniform distribution to accuracy a' and confidence 3r, and, (iii) terminates in time (d, 1/a,, "aa",1 1/8 log(1/#)))
Let O,P (0, 1) and B P/a) For m poly(d, 1/a, //, log( (oa)) and M poly(d, 1/a 1/2, log(l/)) lo)( the following cases hold:
(a) D is monotone distribution over {0, 1)d representable by depth-& decision tree, there is an algorithm that draws M samples from DD is p-replicable with respect to D, PAC learns b under D with accuracy a and confidence 3, and terminates in pol((M) time.
(b) If D is an arbitrary distribution over {0, 1 representable by a depth-E decision tree, there is an algorithum that draws M labeled examples as well as M conditional samples (ef. Definition D.5) from D, is p-replicable with respect to D, PAC learns 6 with respect D with accuracy and confidence B, and terminates in poly MM time.
Proof (Theorem 3.2). Using Theorem 19, we can prove Theorem 3.2 as follows. First, we use Theorem E.7 to replicably learn the input distribution to total variation distance 0/6.3m with decision tree. Next, Lemma F.22 asserts that A is p-replicable and (a,, 3 + 1/a, 3mm)-rbbstlly learns & under the uniform distribution. The result follows by applying Theorem 19.
D
32

---

F Efficient Replicability and Private Learning
F.1 Replicably Learning Finite Classes
We first state useful result which we later leverage subroutine appears in Bun et al. [2023]. Theorem F.1 (Replicable Learner for Finite Classes; Theorem 5.13 in [Bun al., 2023]). Let
a. E (0, 1)3. Then, any finite concept class & is replicably learnable in the agnostic setting with
log" [86] log p8
m(a, p. B) =
log
a²p²
many samples. Moreover, the running time of the algorithm is polynomial in the number of samples and the cardinality of'6.
F.2 A Transformation from Pure DP to Replicability
Our approach borrows some high level ideas from Gonen al. [2019] who showed transformation from a pure DP PAC learner to an online learner. a nutshell, our algorithm works as follows:
I) First, we create a "dummy" input dataset which has some constant size and we run the
algorithm for θ
( loog (o/a( times on resampling its internal randomness every time.
p
2) With probability
3. one of the hypotheses will have error at most 3/8 [Beimel al.. 2013, Gonen et al., 2019].
3) We run the replicable agnostic learner for finite classes from Bun et al. [2023]-
4) We boost the weak replicable learner using Impagliazzo et al. [2022], Kalavasis et al. [2023].
We begin by presenting adaptation of result that appeared in Beimel et al. [2013], Gonen et al. [2019]. Essentially, it states that when a class is learnable by pure DP learner, one can fix an arbitrary input $ that has constant size, execute the learner on this dataset constant number of times by resampling its internal randomness, and then with some constant probability, e.g., 15/16, the output will contain one hypothesis whose error is bounded away from 1/2 by some constant, e.g., 1/4. This result might seem counter-intuitive at first glance, but learnability by pure DP learner is a very strong property for class and the result crucially depends this property. Below, adaptation of this result which states that the weak learner can be p-replicable and has a probability of success of 1 5. An important element of our derivation is a result from Bun et al. [2023] about the sample and computational complexity of agnostically learning concept class using a replicable algorithm (cf. Theorem F.1).
present
We are now ready to state a key lemma for our transformation.
Lemma F.2 (From Pure DP Learner to Replicable Weak Leamer). Let X be some input domain, y= (0. 1}, and Dxy be distribution on X' x y that is realizable with respect to some concept class 6. Let A be a pure DP learner such that for any az 8, E (0,1)3, A needs m(a, e, 3,8,3 (6) i.i.d. samples from Dxy to output with probability at least 1 - 3 a hypothesis with error at most a in an e-DP way. Let us set mo m(1/4, 2/10, 1/2, E).
Then, for any p. E (0, 1)² there is a p-replicable learner A' that oulputs a hypothesis with error log (1/of) i.i.d. samples from
at most 3/8 with probability at least 1 - 3' and requires Ö (poly(ma)
Dxy and (cxp((ma) log(t/8") oracle calls A (and hence runtime).
Proof (Lemma F.2). We argue about the correctness and replicability of the algorithm separately.
Correctness. Since Dxy is realizable, there exists some c* E 86 such that loss (c*) = 0. Let rAnge(A) = {c: X + (0, ES E Unen(X x 10,1))) 3r E 10,"", s.t. A(S;r) = c) Let also mg = m(1/a, 1/10, 1/2, E) be the number samples A needs to achieve a = 1/4, = 1/10, 3 = 1/2 for the class &. Notice that mg is a constant with respect to at B,,,e. Let also
(Dxr) = fc E range(A): losspxy (c) S 1/4}-
By definition, with probability at least 1/2 over the random draw of an i.i.d. sample of size mo from Dxy and the internal randomness of A, the output of the algorithm belongs to (Dxx)) Thus, there exists sample So E (X x {0, 1) such that
Pr (A((:))))) & (Dxy)) 1/2.
m~R
13 As in Gonen et al. [2019]. the size is constant w.r.t the accuracy. confidence parameters, but it might not be constant w.r.t. parameter the describes the complexity of the concept class.
33

---

Although it is unclear how to identify such a So, notice that any sample S E (X' x {0, mi is an mo neiigbbo of Sg. Since A is pure DP, it holds that
Pr rA(S:)) E (Dxxv)] 1/2 u.1-mo. P>R
In particular, this holds for the dummy dataset we fix before observing any data. Then if we sample N e0 log(?/)") (cexp(mo) (sg( iid. random strings r1 "',,.,.77N from R i.i.d. the probability that none of the hypotheses (A(S:rr) hEI[ is in (Dxx) is at most
3
(1 - (eexpp(0.11mmm (xp((0.1mm))bbeeeee log((//)))
3
We denote the event that one of the outputs is in (Dxy) by & and we condition on for the rest of the correctness proof. The next step is to replicably learn the finite concept class E = (A((S ((S:s) rN) we have constructed using Theorem F.I with accuracy 1/8, confidence
log² N+log + log Ö mb log(11/8)))
///s, and replicability p. Thus, can that O
samples suffice for this task. Let E' be the event that this estimation is correct, which happens with probability at least ///3. Conditioned on that event, outputting the hypothesis generated by the learner gives solution with emorr at most 1/1+11 1/s 3/s. Notice that the good events happen with probability at least 1 2 2 1 - 3, so the correctness condition is satisfied.
Replicability. Notice that the first step of the algorithm where we fix dummy dataset S of size mo and run the algorithm on i.i.d. strings of its internal randomness trivially replicable, since the dataset and the randomness are the same across the two executions. Then, by the guarantees of Theorem F.I, we know that the output of the algorithm will be the same across two executions with probability at least 1 p. Thus, overall we see that with probability at least 1 p. the output of our algorithm is the same across the two executions.
We emphasize that the number of oracle calls to the DP algorithm is constant with respect to the confidence and the correctness parameter, but could, potentially, be exponential with respect to some parameter that depends on the representation of the underlying concept class X.
Equipped with the weak learner from Lemma F.2 we can boost error parameter using the boosting algorithm that appears in Impagliazzo et al. [2022]. For completeness, we state the result below.
Theorem F.3 (Replicable Boosting Algorithm [Impagliazzo et al., 2022]). Let DXY be the joint distribution over labeled examples as in Lemma F.2. Fix a, p. > O. Let A be a p-replicable (7, B)- weak learner with sample complexity mln, P, 8), i.e., its error is at most 1/2 -%, with probability at least 1 - 3. Then, there exists an efficient p-replicable boosting algorithm A' such that with probability at least 1 B¹' it outputs hypothesis h with loss (h) I a. The algorithm runs for T Ō(log( ((log(//)/(app)) rounds and requires oracle calls to the weak learner. Moreover, requires
((mL)
B) 2272
log 3
p²
many samples, where m(y, 9/61, B) is the sample complexity needed for the weak learner to be o/ci-replicable and (1/2- 11/2-110 7, 11 -accuratee
Combining the discussion above, we see that for any a, 3 E (0, 1)3 we can transform a pure DP learner to p-replicable (a, co)-ret (strong) learner where the transformation is efficient with respect to the accuracy a, confidence 3, and replicability p. This proves Theorem 5.2, which we restate below for convenience.
Theorem 5.2 (From Pure DP Learner Replicable Learner). Let X be some input domain, == =0, 1}. and Dxy be a distribution on X x y that is realizable with respect to some con- cept class 6. Let be pure DP learner that, for any a, E, E (0, 1), needs m(a, e, 2.3,6) = poly(+/a, 1/e, log//))) dim())) i...d. samples from Dxy and (oly(m) running time to output a hypothesis that has error at most a, with probubility 3 3 in an e-DP way. Then, for any a', p',,,'' (0.1) there is a p-replicable learner A' that oulputs hypothesis with error at most a' with probubility least 3' and requires poly(Y/a' 1/p, log(1/#) dim (6)) i..d. samples from Dxy and poly(Y/a', 3/2, log(1/3)) exp(dii(())) running time.
34

---

We reiterate that even though our transformation is efficient with respect to the input parameters a, 3, p. might not be efficient with respect to some parameter that depends on the representation of the concept class. This is because the size of the "dummy" dataset mo could depend on the size of that representation and our transformation requires poly(mo) samples but exp(mo) running time. This is also the case for transformation from a DP learner to an online learner [Gonen et al., 2019].
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The main body and appendix of the submission provide proofs for all the claims.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? [Yes]
Answer:
Justification: We formally define the mathematical model our results hold for. Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We present full proofs in the main body and the appendix. Guidelines:
The answer NA means that the paper does not include theoretical results.
36

---

All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof's provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c)
If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.ce cc/
for more details.
37

---

While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips.ae wwtpcccppppcccccccccccccccccccct htapbllcgggiees///eeeeeeee wwwodddeumisssoooooolloooe
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if' applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еттог rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
38

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: httpps:///neriiie /tt///euurrrrr.e httpp//bbbcttthiiccccceeeee..eee
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The work is primarily theoretical and does not have any immediate societal
impact.
Guidelines:
The answer NA means that there no socictal impact of the work performed.
If the authors answer NA or No. they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymennt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
39

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA]
Question:
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. comddatasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
40

---

Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
41


Reviews:
[{"review_id": "yQELRR8dko", "reviewer": "Reviewer_eJSY", "summary": "This work contributes to the recently evolving area of replicable learning. This work establishes three main results\n\n1. It is known that online learning algorithms can be replicable and replicable learning algorithms yield online learning algorithms. The work focuses on the computational complexity of these transformations and establishes a negative result--there exist concept classes that are efficiently, replicably, and learnable but there are no efficient online learning algorithms (assuming the existence of one-way functions).\n2. Recent work showed that PAC learning algorithms under the uniform distribution can be black-box converted into distribution-free PAC learning algorithms. This work shows the transformation can be made replicable.\n3. It is known there exist concept classes that are approximately DP learnable, but not efficiently, replicable learnable.  This work shows that if the concept class is pure DP-learnable, then it is efficiently replicable learnable.", "questions": "Pertains to the weakness. Can you explain the new ideas needed to obtain the results? \n\n1. ILPS22 presents a replicable algorithm for an approximate median. The approximate quantile algorithm seems to build on similar ideas. What are the new ideas in the proof?\n2. Similarly, the critical ingredient in the proof of 3.2 is the replicable influence estimation. Once we have a replicable influence estimation the proof of Blanc et al goes through with minor changes. The design of replicable influence estimatior follows by the randomized rounding technique of ILPS22.  Are there any technical/conceptual challenges?", "limitations": "None", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This solid work clarifies several questions on replicable learning in the context of computational efficiency. The paper is very well written and the proofs are rigorous.", "weaknesses": "Main weakness is that obtained by combining known works. It is not clear to be that there is not that much novelty in the proofs.  for example, \n\n1. Proof of Theorem  2.1 proceeds in two parts.  a) existence of a concept class that is not online learnable, b) designing a replicable learning algorithm for this class. (a) is known by prior works, (b) replicable algorithm follows by the (now) standard technique of random thresholding/rounding. \n2. Please see Q2. \n\nThough the proofs may not be novel, the final results that the authors obtain are interesting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer eJSY for recognizing the importance of our results\nand their suggestions regarding the presentation of our paper.\n\nWe believe that the main contribution of our work, as the reviewer acknowledges, is a collection of interesting conceptual results that are missing from prior work. For instance, while the replicable influence estimator is not overly technically involved, it constitutes a key ingredient for the use of the lifting framework, which we find conceptually interesting. To justify this further, \nthe main result of ILPS22 is that SQ-based algorithms can be made replicable. However, our understanding of replicability beyond SQ algorithms is fairly limited. The main candidate in understanding this question is learning parities. \nIt is clear that under the uniform marginal distribution (or similar nice distributions) the problem is trivially replicable; yet beyond such distributions, it was not clear how to argue about replicable algorithm design for parities. \nWe make progress on this important problem by using the replicable lifting framework. \nThis framework provides a non-trivial conceptual step towards understanding efficient replicable learnability beyond SQ algorithms,\nwhich is a direction we hope the community will further explore.\nIndeed, we provide a concrete\ndistribution where \nwe can obtain a replicable algorithm for learning parities using our framework,\nbut Gaussian elimination, which is the standard\nalgorithm in the absence of replicability, fails\nto be replicable. We view that as evidence\nthat our transformation can indeed lead to replicable\nalgorithms in settings where such results are lacking.\n\nAt a more technical note, our replicable quantile estimation differs from the replicable median algorithm of [ILPS22] in at least two ways.\nFirstly,\nthe replicable median algorithm of [ILPS22] seems to rely heavily on properties of (approximate) medians in order to satisfy the approximation guarantees.\nOn the other hand,\nour algorithm works regardless of the desired quantile.\nSecondly,\ntheir median algorithm relies on a non-trivial recursive procedure\nwhile our replicable quantile algorithm is considerably simpler and is based on a concentration of the CDF through the DKW inequality.\n\nWe will include these discussions in the next version of our manuscript.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "owxxQVaOpg", "reviewer": "Reviewer_npit", "summary": "Replicability is a notion of stability for learning algorithms, recently proposed by Impagliazzo et al. [ILPS22] to address the replicability crisis pervasive in scientific studies using statistical procedures. A learning algorithm $A$ is a function that takes as inputs a dataset $S \\in (\\mathcal{X} \\times \\mathcal{Y})^*$ and a (random) string $r \\in \\\\{0,1\\\\}^*$, and outputs a hypothesis $f: \\mathcal{X} \\to \\mathcal{Y}$. The algorithm is replicable if for independent draws of same sized datasets $S, S’$ and random $r$, $A(S, r) = A(S’, r)$ with high probability. Put simply, if two scientific labs use the same replicable algorithm to analyze independent datasets S and S’, and arrive at different conclusions, they will have a hard time blaming statistical fluctuations in the data.\n\nThis paper presents a variety of results that connect replicability to other well-studied concepts in learning theory, such as (realizable) online learnability and private learning. In particular, the authors show a computational separation between replicability and **online learnability**, assuming the existence of one-way functions. They also present a lifting procedure that transforms an efficient replicable PAC learner for a hypothesis class $\\mathcal{H}$ over the uniform distribution on $\\\\{\\pm 1\\\\}^n$ to replicable learners over any marginal distribution whose sample and time complexity depends on the complexity of the marginal. This lifting procedure is then used to design an efficient replicable algorithms for **learning parities over distributions that are far from uniform**. Furthermore, they show that any **pure DP learner** can be turned into a replicable one in time polynomial in all relevant problem parameters, except for the \"representation dimension\" of the hypothesis class.", "questions": "- What is the \"representation dimension\" of a hypothesis in Theorem 5.2?\n\n- Can we define replicability with continuous random sources? Or are there obstacles to meaningfully defining replicability with respect to continuous sources?", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This is a very well-written paper with solid technical contributions. Though the paper touches on various concepts in learning theory, the polished presentation ensures that the reader is not overwhelmed by the breadth of coverage. As replicability is a relatively new concept in learning theory, I was not familiar with it. However, the connections between replicability and other concepts are rather surprising and pleasing to someone new to the topic. The clear and well-organized proofs, each employing diverse techniques, were relatively easy to follow.\n\nI found the application of the lifting procedure to replicable parity learning and the distinction from Gaussian elimination particularly interesting. For the uniform distribution, it is straightforward to see that Gaussian elimination is replicable for data labeled by parity functions. However, one can define simple distributions on which Gaussian elimination is *not* replicable (though the zero-one loss *is* small with high probability). This highlights the necessity and the non-triviality of the lifting procedure for efficient replicable learners over the uniform marginal. It also shows that computational separation between replicable learning and statistical query (SQ) learning extends to non-uniform marginal distributions.", "weaknesses": "Given that this is a solid and well-polished paper, I did not find any significant weaknesses, only a few minor points below.\n\n- **Elaborating replicability with simplified, realistic statistical examples.** The paper begins by addressing the replicability crisis in scientific fields, but once the authors define replicability within the learning theory setup, the initial narrative gets lost. What would the random strings model in a real-world scientific study? Does it model the PRG seed number that experimenters use in their PyTorch code? Taking a simplified but realistic example (e.g., a hypothetical FDA approval procedure based on clinical data collected by independent labs), and mapping the A's, S's and r's to real-world concepts would be helpful.\n\n- **Ambiguity in the big questions.** I found some of the \"big\" questions Q1-Q4 [page 2-3] too generic to be useful. In particular, questions like \"How does replicable learning *relate to* online/private learning?\" are extremely underspecified because \"relate to\" can have multiple interpretations. It would have been more helpful if the authors posed more specific motivating questions, such as \"Is there a computational separation between replicably learnable classes and online learnable classes?\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer npit for the insightful suggestions regarding the presentation of our paper.\n\nThe random string in the definition of replicability does indeed model the random seed of a learning algorithm in practice\nand sharing internal randomness can be easily implemented in practice by sharing the random seed.\nWe can indeed define\nreplicability with continuous\nrandom sources, but to make \nthe presentation easier to follow and tie\nit to real-world settings,\nwe decided to stick with random binary strings.\nWe will provide other concrete examples for the definition in the next iteration of our manuscript.\n\nWe will also restate the motivating questions with more specific language.\n\nThe representation dimension is a combinatorial dimension, similar to VC dimension, that characterizes which classes are PAC learnable by pure DP algorithms. We will formally give its definition in the next revision of our work and mention how it has been used\nin prior works on pure DP.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "J0SuJTIcff", "reviewer": "Reviewer_iQWb", "summary": "In the paper, the authors discuss the connection and differences among replicability, a novel stability condition for learning algorithms proposed by Impagliazzo et al. [2022], online learning, and differential privacy from a computational perspective. Their first contribution is a computational separation between online learning and replicable PAC learning. In particular, under standard cryptographic assumptions, there is a concept class that can be replicably learned, but no efficient online learning algorithm exists. The second contribution is a method to extend a replicable PAC learner that works under the uniform distribution to ones that work under more complex distributions, whose probability mass functions can be computed by decision trees. The final result is a way to transform a purely differentially private learner into a replicable one. Combining these with some existence hardness/equivalence results provides a figure (Figure 1.1) referred to by the authors as the \"computational landscape of stability.\"", "questions": "As a pure DP algorithm is also an approximate DP algorithm by definition, I imagine that the reduction from Bun et al. [2023] could also transform a pure DP learner into a replicable learner. Could you elaborate more on how the performance of your reduction would differ from theirs quantitatively?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Figure 1.1 is an excellent summary of all known relationships between different notions of algorithmic stability. I believe the communities behind all three areas (replicable, online, DP) could benefit from such a roadmap. All the results are clean and well-motivated. \nThe one I like the most is the lifting result for replicable learner. Intuitively, it feels like replicable learners and statistical query algorithms are almost equivalent as most replicable algorithms we know are based on the idea of making each statistical query fired by the algorithm replicable. The only exception known before is learning parities under the uniform distribution over boolean hypercube. The authors demonstrate the possibility that there may potentially be much larger gaps between SQ algorithms and replicable learners.", "weaknesses": "While the results are conceptually novel and interesting, the techniques used are more or less standard. For example, the lifting result follows from building a replicable version of the routine from Blanc et al. [2023] for learning the decision tree structure of the distributions, and the core of it is just to estimate the influence of distributions in a replicable manner (via random statistical query rounding).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer iQWb for recognizing the contributions of our paper.\n\nThe main result of [ILPS22] is that SQ-based algorithms can be made replicable. However, our understanding of replicability beyond SQ algorithms is fairly limited. The main candidate in understanding this question is learning parities. We make progress on this important problem by using the replicable lifting framework. \nThis framework provides a non-trivial conceptual step towards understanding efficient replicable learnability beyond SQ algorithms,\nwhich is a direction we hope the community will further explore.\nIndeed, we provide a concrete\ndistribution where \nwe can obtain a replicable algorithm for learning parities using our framework,\nbut Gaussian elimination, which is the standard\nalgorithm in the absence of replicability, fails\nto be replicable. We view that as evidence\nthat our transformation can indeed lead to replicable\nalgorithms in settings where such results are lacking.\n\nIt is, indeed, a correct\nobservation that pure DP algorithms\nare also approximate DP algorithms.\nThus, in\nprinciple, one could use\nthe reduction from Bun et al. [2023].\nThe catch is that this reduction \nis based on correlated sampling so it\nrequires i) the output space of the algorithm to be finite and ii)\neven under finite output spaces, it needs\nexponential time in the size of that space.\n\nWe will elaborate on these discussions in the next version of our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": "kZyCCG1c97", "reviewer": "Reviewer_9ean", "summary": "The authors study the computational relationship between *replicable* learning algorithms, a recent notion of algorithmic stability [ILPS22] promising two runs of the algorithm over independent data output the same hypothesis with high probability assuming shared randomness, and other classical notions of algorithmic stability such as SQ-learning and differential privacy (as well as the closely related topic of online learning). The equivalences between such notions are well understood statistically, but this is the first paper to make a systematic attempt to study *computational* aspects of the problem.\n\nMore formally, the authors present both negative results (separations), and positive results (efficient transformations) between these notions:\n\nOn the negative side, the authors show:\n\n1. A concept class based on one-way sequences which has no efficient online learner but can be learned replicably in polynomial time. This result is based on work of Bun separating private and online learning, but requires a new idea on the replicable side. In particular, two independent runs of the algorithm (with fresh samples) must identify a shared early element in the one-way sequence (using their shared randomness) to output the same unique hypothesis on the remainder. This is done via a new replicable quantile estimation lemma that leverages a variant of [ILPS22]'s randomized rounding methods.\n\n2. A separation between SQ learning and replicable learning based on affine parities. While this class was already known to separate the two under the uniform distribution, no separation (or even efficient replicable algorithm) was known for more general distributions. Based on work of Blanc, Lange, Malik, and Tan, the authors give a general procedure to lift an efficient replicable algorithm for the uniform distribution for certain classes to a replicable algorithm for general distributions whose computational efficiency scales with the decision tree complexity. They then give examples of distributions with low decision tree complexity where the trivial `gaussian elimination’ based algorithm for the uniform case fails but their lifted algorithm runs in polynomial time (they also observe these distributions remain hard for SQ). This makes progress on a question of ILPS'22 about replicable algorithms where Gaussian elimination fails.\n\nOn the positive side:\n\n1. There is an algorithm transforming any pure private learner for a class C to a $rho$-replicable learner in time exp(rep-dim(C))*poly(eps^{-1},\\rho^{-1}), where eps is the accuracy parameter and rho is the replicability parameter. Their algorithm uses a classic procedure of Beimel Nissim and Stemmer which generates a finite approximation of C using a pure private learning, then learn this representation with the finite learner of [BGH+23]. To get polynomial dependence, this is run for constant error then boosted afterwords using replicable boosting.", "questions": "Given the above discussion of the apx-DP, perhaps a better way to justify the pure DP transformation would be to exhibit a sequence of concept classes over {0,1}^n with constant representation dimension for which the transformation from apx-DP is inefficient (or at least some evidence can be given for this)? \n\nI will be happy to increase my scores if I have misunderstood something regarding these transformations in the paper and the authors can clarify, or if the authors agree and fix the current presentation.\n\nPOST REBUTTAL: The authors' proposed changes address my concerns in the soundness of the work, and I have updated my overall score accordingly.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 1, "presentation": 3, "contribution": 3, "strengths": "Replicability is a critical notion in machine learning and the sciences in general, and has recently been a fruitful notion more generally in the study of algorithmic stability, leading e.g. to advances in differential privacy. Prior works in the area largely focus on the statistical complexity of replicable learning. Understanding the *computational* cost of replicability, both in general and as compared to other notions of stability, is a critical open problem and clearly of interest to the NeurIPS community. This paper is the first to initiate a systematic study of this problem, and makes initial progress on understanding connections with pure privacy, SQ, and online learning, standard notions in the literature.\n\nRelated to the above, the authors make progress on an open problem of [ILPS’22] to design efficient replicable algorithms for parities beyond the uniform distribution (namely in this case for distributions with constant decision tree complexity). This takes some work to formalize and is a reasonable contribution on its own from a computational standpoint.", "weaknesses": "The work has two main weaknesses.\n\nFirst, the authors seem to have misunderstood prior separation results in the literature, and as a result, the presentation of `computational separations’ with respect to privacy in the paper (namely in Figure 1.1 and the exposition) is wrong. Namely, the authors claim that there is an “efficient transform from pure DP learning to replicable learning” and “no efficient transform from apx DP learning to replicable learning”, where “efficient” is in terms of eps and rho (error and replicability) but not the underlying dimension of the problem, but this seems false.\n\nIn particular, there actually *is* a transformation from approximate DP to replicability that is “efficient” in this sense. Correlated sampling can be run in time roughly scaling with the output domain of the private algorithm, then boosted via ILPS from constant accuracy/replicability in polynomial time in these parameters. In fact, *any* learning problem that is solvable replicably can be solved in time polynomial in eps and rho by boosting/amplifying, so “efficiency” in these parameters is not very meaningful. The question of efficiency instead should be one of domain-size/dimension, which (as the authors to their credit highlight several times) is not efficient in the given reduction.\n\nPart of the confusion here seems to stem from the result of [BGH+23] giving a computational separation between apx DP and replicability. In Prop 5.1, the authors state [BGH+23] exhibit a PAC problem which is efficiently learnable under apx-DP, but cannot be replicable learned assuming one-way functions exist. As far as I can tell, this is not shown in [BGH+23]. First, the separation given by [BGH+23] is not for PAC-learning, it is for a somewhat contrived statistical task; separating the two in the PAC setting is open. Second, the separation has nothing to do with one way functions (which seems to be a different result in their paper), and relies on public key encryption. Third, the separation is in terms of the dimension/size of the space, not accuracy or replicability parameters.\n\nThe second weakness of this paper is that, while extra technical work is certainly required for several of the results in this paper (namely the online bound, and generalizing BLMT23), the ideas in this paper do not go substantially beyond known methods in the study of replicability. The online vs replicability result is not too much of a jump from its use in work of Bun separating privacy and online learning, (the new replicable quantile estimation method takes work but is fairly straightforward from techniques in ILPS22). The SQ/distribution-lifting result also follows largely from combining techniques of [ILPS22] with [BLMT23]’s non-replicable method which already relies mostly on statistical estimation sub-routines.\n\nOverall, the authors have identified an important problem and made some nice partial progress in this front (including progress on an open problem of ILPS22), but combined with the issues above and without introducing substantially new ideas to the study of replicability I cannot recommend the work for acceptance in its current form.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank reviewer 9ean for their thorough review, their suggestions regarding the presentation of the manuscript, and the clarification of results from prior work.\n\nWe apologize for the confusion; indeed\nthere was a misunderstanding on our end about the\nseparation that [BGH+23] provided. We are committed to modifying\nthe manuscript according to the reviewer's recommendation\nand have updated the figure in the \"global\" response section. \n\nMoreover,\nas the reviewer correctly points out, the transformation\nof [BGH+23] from approx DP to replicability requires\nexponential time in the size of the domain, and polynomial time\nin the approximation/confidence parameters. Thus, their\nresult does not subsume ours. We also agree that the question\nthe reviewer mentions is an interesting one, and we can\nmention it as an open problem.\n\nRegarding the second weakness,\nwe believe\nthe replicable lifting framework provides a non-trivial conceptual step towards understanding efficient replicable learnability beyond SQ algorithms,\nwhich is a direction we hope the community will further explore.\nIndeed, we provide a concrete\ndistribution where \nwe can obtain a replicable algorithm for learning parities using our framework,\nbut Gaussian elimination, which is the standard\nalgorithm in the absence of replicability, fails\nto be replicable. We view that as evidence\nthat our transformation can indeed lead to replicable\nalgorithms in settings where such results are lacking.\n\nWe will include these discussions in the next iteration of our paper, and we apologize again for the misunderstanding.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_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": {}}]

Author rebuttal:
Following reviewer 9ean's suggestions, 
we have uploaded a slightly modified figure
of the computational landscape of stability to clarify the computational separation between approximate DP and replicability given in [BGH+23],
which is not for PAC learning but for some other statistical task. 
We will also modify the exposition accordingly.

Meta-review: This work presents several results on the computational complexity of replicable PAC learning, a recently introduced notion of stability of learning. In particular, it gives two separation of efficient replicable learning from online learning and SQ learning. It also discusses the relationship of the notion to differentially private learning although, as pointed out by reviewers, the initial claims were based on a number of misunderstandings. Overall this is nice technical progress even if a purely theoretical setting is likely to substantially limit the appeal of the work.
Decision: Accept (poster)