List and Certificate Complexities in Replicable Learning
Authors: Peter Dixon
A. Pavan
Jason Vander Woude
N V Vinodchandran
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Replicability
learning algorithms
sample complexity
PAC Learning
TL;DR: We investigate list and certificate complexities in the context of replicable learning algorithms.

Abstract: We investigate replicable learning algorithms. Informally  a learning algorithm is replicable if the algorithm outputs the same canonical hypothesis over multiple runs with high probability, even when different runs observe a different set of samples from the unknown data distribution. In general, such a strong notion of replicability is not achievable. 
Thus we consider two feasible notions of replicability called {\em list replicability} and {\em certificate replicability}. 
Intuitively, these notions capture the degree of (non) replicability. The goal is to design learning algorithms with optimal list and certificate complexities while minimizing the sample complexity.  Our contributions are the following.

1. We first study the learning task of estimating the biases of $d$ coins, up to an additive error of $\varepsilon$, by observing samples. For this task, we design a $(d+1)$-list replicable algorithm. To complement this result, we establish that the list complexity is optimal, i.e there are no learning algorithms with a list size smaller than $d+1$ for this task. We also design learning algorithms with certificate complexity $\tilde{O}(\log d)$.   The sample complexity of both these algorithms is $\tilde{O}(\frac{d^2}{\varepsilon^2})$ where $\varepsilon$ is the approximation error parameter (for a constant error probability).  

2. In the PAC model, we show that any hypothesis class that is learnable with $d$-nonadaptive statistical queries can be learned via a $(d+1)$-list replicable algorithm and also via a $\tilde{O}(\log d)$-certificate replicable algorithm. The sample complexity of both these algorithms is $\tilde{O}(\frac{d^2}{\nu^2})$ where $\nu$ is the approximation error of the statistical query. We also show that for the concept class \dtep, the list complexity is exactly $d+1$ with respect to the uniform distribution.   

To establish our upper bound results we use rounding schemes induced by geometric partitions with certain properties. We use Sperner/KKM Lemma to establish the lower bound results.

In the PAC model, we show that any hypothesis class that is learnable with d- d-nonadaptive statistical queries can be learned via (d + 1)-list replicable algorithm and also via Ölog d) certiifiie replicable algorithm. The sample complexity of both these algorithms is Ō( d where y is the approximation error of the statistical query. We also show that for the concept class d- List and Certificate Complexities in Replicable Learning
Peter Dixon', A. Pavan
Jason Vander Woude', and N. V. Vinodchandran'
IIdeepeneent Researcher
e com
lloa State University
pavangcs. iastate. edu University of Nebraska- Lincoln jasonva unl. edu University of Nebraska-Linoon vinodu unl. edu
Abstract
We investigate replicable learning algorithms. Informally a learning algorithm is replicable if the algorithm outputs the same canonical hypothesis over multiple runs with high probability, even when different runs observe a different set of samples from the unknown data distribution. general, such strong notion of replicability is not achievable. Thus we consider two feasible notions of replicability called list replicability and certificate replicability. Intuitively, these notions capture the degree of (non) replicability. The goal is to design learning algorithms with optimal list and certificate complexities while minimizing the sample complexity. Our contributions are the following.
We first study the learning task of estimating the biases of d coins, up an additive error e, by observing samples. For this task, we design a (d + 1)-list replicable algorithm. To complement this result, we establish that the list complexity optimal, i.e there are no learning algorithms with a list size smaller than d 1 for this task. We also design learning algorithms with certificate complexity Ö(log d). The sample complexity of both these algorithms is Ō where the approximation error parameter (for a constant error probability).
THResHOLD, the list complexity is exactly d + with respect to the uniform distribution.
To establish our upper bound results we use rounding schemes induced by geometric partitions with certain properties. We use Sperner/KKM Lemma to establish the lower bound results.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

1 Introduction
Replicability and reproducibility in science are critical concerns. The fundamental requirement that scientific results and experiments be replicableerrerroduibbe is central to the development and evolution of science. In recent years, these concerns have grown as several scientific disciplines turn to data-driven research, which enables exponential progress through data democratization and affordable computing resources. The replicability issue has received attention from a wide spectrum of entities, from general media publications (for example, The Economist's "How Science Goes Wrong." " 2013 (cco13)) to scientific publication venues (for example, see (JPO5) Bak 16)) to professional and scientific bodies such as the National Academy of Sciences, Engineering, and Medicine (NASEM). The emerging challenges to replicability and reproducibility have been discussed in depth by consensus study report published by NASEM (AST9).
A broad approach taken to ensure the reproducibittyyeppiicabitt of algorithms is to make the datasets, algorithms, and code publicly available. Of late, conferences have been hosting replicability workshops to promote best practices and to encourage researchers to share code (see (PVLS*211 and (MPKT9)). An underlying assumption is that consistent results can be obtained using the same input data, computational methods. and code. However, these practices alone are insufficient to ensure replicability as modern-day approaches use computations that inherently involve randomness.
Computing over random variables results in a high degree of non-replicability, especially in machine learning tasks. Machine learning algorithms observe samples from (sometimes unknown) distribu- tion and output a hypothesis. Such algorithms are inherently non-replicable. Two distinct runs of the algorithm will output different hypotheses as the algorithms see different sets of samples over the two runs. Ideally, to achieve "perfect replicability." we would like to design algorithms that output the same canonical hypothesis over multiple runs, even when different runs observe different set of samples from the unknown distribution.
We first observe that perfect replicability is not achievable in learning, as dependency of the output on the data samples is inevitable. We illustrate this with a simple learning task of estimating the bias of coin: given n independent tosses of coin with unknown bias b, output an estimate of b that is within an additive error of E with high probability. It is relatively easy to argue that there is no algorithm that outputs canonical estimate U6 with probability 2/3 so that |ug bl S e. Suppose, for the sake of contradiction, such an algorithm A exists. Consider a sequence of coins with biases bi b2 b, and b the statistical distance (denoted by drv) between 1 and D. is S 1y), where DV is the distribution of independent tosses of the 2th coin. Let 0:+1 and v be the canonical estimates output by the algorithm for biases b;-1 and b; respectively. Since on samples from distribution D. outputs i, with probability at least 2/3 and drv 14+1) S ny,, ((D must output v; with probability at least 2/3 - ny.. Since A A(D 1) must output a canonical value 0/41 with probability at least 2/3, this implies that e 1i+1 (if not the probabilities will add up to > 1). Thus, on all biases b,,..., Dm. the algorithm A should output the same value. This leads to a contradiction since bn and bm are 22 apart. However, it is easy one of two canonical estimates with high probability using n = O(1/²²) tosses: estimate the bias within eиror of e/2 and round the value to the closest multiple of e. The starting point of our work is these two observations. Even though it may not be possible to design learning algorithms that are perfectly replicable, it is possible to design algorithms whose "non-replicability" is minimized.
< bm where each bx+1 - b. < " 1/10n, and bm bi > 2e. For two adjacent biases
that there is algorithm for bias ctasmmstimation that outputs
We study two notions of replicability called list replicability and certificate replicability which quantify the degree of (non)--eplicabiliity of learning algorithms. They are rooted in the pseudodeterminism- literature (GGIT Gol19 GL.1) which studied concepts known as muulii-pveulodettemmiiis (related to list replicability) and influential bit algorithms (related to certificate replicability). Recently notion of algorithuic stability and its variants such as list global stability, pseudo global stability, and p-replicability have been studied in the context of learning algorithms (BLM20) GKM21, ILPS22). These notions are very similar to each other and Section discusses the similarities and connections.
1.1 Our Results
Informally, an algorithm A is k-list replicable if there is list I. consisting of k (approximately correct) hypotheses so that the output of the algorithms belongs to I. with high probability. This implies that when the algorithm A is run multiple times, we most & distinct hypotheses (with

---

high probability). The value & is called the list complexity of the algorithm. An algorithm whose list complexity is is perfectly replicable. Thus, list complexity can be considered as degree of (non) replicability. The goal in this setting to design learning algorithms that minimize the list complexity & for various learning tasks.
In certificate replicability, the learning algorithm has access an é-bit random string that is indepen- dent of samples and the other randomness that the algorithm may use. It is required that for most f-bit random strings r, the algorithm must output canonical (approximately correct) hypothesis h, that depends only on r. Thus once we fix a good ê-bit random string r. multiple runs of the algorithm will output the same hypothesis with high probability. We call é the certificate complexity of the algorithm. An algorithm with zero certificate complexity is perfectly replicable. Thus é is another measure of the degree of (non) replicability of the algorithm. The goal in this setting is design learning algorithms that minimize the certificate complexity.
A critical resource in machine learning tasks is the sample complexity- number of samples that the algorithm observes. This work initiates a study of learning algorithms that are efficient in list complexity, certificate complexity as well as sample complexity. The main contribution of this work the design of algorithms with an optimal list and certificate complexities with efficient sample complexity for a few fundamental learning tasks.
Estimating the biases of d coins. We consider the basic problem of estimating the biases of coins
simultaneously by observing tosses of each of the coins which we call d-COIN BIAS ESTIMATION PROBLEM. The task is to output an approximate bias vector with probability at least (1 - d) so that ||b - J x s where = (bj.... ba) is the true bias vector, i.c., b, is the true bias of the ith coin. For this task, we establish the following results.
There is a (d + 1i-t replicable learning algorithm for d-COIN BIAS ESTIMATION PROBLEM whose sample complexity (number of observed coin tosses) is O d" log 3) per coin.
There is [log 5 -certificaae replicable algorithm for d-COIN BIAS ESTIMATION PROBLEM with sample complexity n = O
de per coin.
We establish the optimality of the above upper bounds in terms of list complexity. We show that there no d-list replicable learning algorithm for d-COIN BIAS ESTIMATION PROBLEM.
While d-C I-COIN BIAS ESTIMATION PROBLEM is a basic learning task and is of interest by itself, the techniques developed for this problem are applicable in the context of PAC learning.
PAC learning.
We investigate list and certificate replicable PAC learning algorithms.
We establish the following generic result: Any concept class that be learned using d non- adaptive statistical queries can be learned by a (d + 1)-list replicable PAC learning algorithm with sample complexity 0 llog ) where v is the statistical query parameter. We also show that such concept classes admit [log
[ -crettiiie replicable PAC learning algorithm with sample
42 complexity O ,ل8zz log }
We study the list complexity of the concept class d-THRESHOLD. Each hypothesis hy in this concept class is described via d-dimensional vector ē' E [0, 1]dd For a hypothesis he, he(3) = 1 if and only if x; < f, 1 < < d' We establish that, under the uniform distribution, the list complexity of d T-TRESHHLD is exactly ++1.. 1.
To establish our upper bound results we use rounding schemes induced by geometric partitions with certain properties. We use Sperner/KKM Lemma as tool establish the lower bound results. Due to space restrictions, most of the proofs are given in the supplementary material.
2 Prior and Related Work
Formalizing reproducibility and replicability has gained considerable momentum in recent years. While the terms reproducibility and replicability are very close and often used interchangeably. there
This concept class is the same the class of exis-parallel rectangles in [0, 1]d with Ö as one of the corners.
3

---

has been an effort to distinguish between them and accordingly, our notions fall in the replicability definition (PVLS-21), As mentioned earlier, reproducibility. replicability, and related notions have been of considerable interest in the context of traditional randomized algorithms and learning algorithms. Here we discuss the prior work that is most relevant to the present work. A more detailed discussion of the prior and related work is provided in the supplementary material.
The seminal work of (BLM20) defined the notion of global stability in the context of learning, which is similar to the notion of pseudodeterminism (GGIT) in the context of traditional algorithms. They define a learning algorithm A to be (n, 7) gllobblllyy stable with respect to distribution D if there is hypothesis /t such that Pr (A(S) h) 2 v). here 1y is called the stability parameter. Using this notion as an intermediate tool they established that every concept class with finite I Littlestone dimension can be learned by an approximate differentially private algorithm. The work in (GKM21) extended the notion of global stability to list-global stability and pseudo-global stability. The authors of (GKM2I) used these concepts to design user-level differentially private algorithms. The notion of pseudo-glot goouuo-global stability is similar to the notion of certificate applicability, however, as defined, the notion of list-global stability differs from our notion of list replicability.
The recent work reported in (ILPS22) introduced the notion of p-replicabiliry. A learning algorithm A is p-replicable if Pr(AA(S,rr = A(S2, r)] 2 1 11-- p. where S₁ and S2 samples drawn from distribution 'D and r is the internal randomness of the learning algorithm A. They designed replicable algorithms for many learning tasks, including statistical queries, approximate heavy hitters, median, and learning half-spaces. It is known that the notions of aseudo-globa stability and p-replicability the same up polynomial factors in the parameters (ILPS22) (KM2T).
The present work introduces the notions of list and certificate complexities as measures of the degree of (non) replicability. Our goal is to design learning algorithms with optimal list and certificate complexities while minimizing the sample complexity. The earlier works did not focus on minimizing these quantities. The works of (BLM20 GKM21) used replicable algorithms step to design differentially private algorithms. The work of (ILPS22) did not consider reducing the certificate complexity in their algorithms and also did not study list replicability. The main distinguishing feature of our work from prior works is our focus on designing learning algorithms that are efficient in list, certificate, and sample complexities well as establishing optimality results for list and certificate complexity.
intermediate
A very recent and independent work of (CMY23) investigated relations between list replicability and the stability parameter v, in the context of distribution-free PAC learning. They showed that for every concept class H. its list complexity is exactly the inverse of the stability parameter. They also showed that the list complexity of a hypothesis class is at least its VC dimension. For establishing this they exhibited, for any d. a concept class whose list complexity is exactly d. There some similarities between their work and the present work. We establish similar upper and lower bounds on the list complexity but for different learning tasks: d-THRESHOLA and d-COIN BIAS ESTIMATION PROBLEM. For d- THRESHOLD, our results are for PAC learning under uniform distribution and do not follow from their distribution-indeeeneen results. Thus results, though similar in spirit, are incomparable to theirs. Moreover, their work did not focus on efficiency in sample complexity and also did not study certificate complexity which is a focus of our paper. We do not study the stability parameter.
Finally, would like to point out that there notions of list PAC learning and list-decodable learning in the learning theory literature (see (CP23) and (RY20) for recent progress on these notions). However, these notions are different from the list replicable learning that consider in this paper. List PAC learning and list-decodable learning are generalized models of PAC learning. For example, any learning task that is PAC learnable is trivially list PAC learnable with a list size of 1. However, list replicable learning is an additional requirement that needs to be satisfied by a learner. Thus the notion of list and list-decodable PAC learning are different from the notions of list/certificate replicability.
3 List and Certificate Replicability Notions
We define list and certificate replicability notions for general learning tasks. A learning problem is a family D of distributions over domain X, a set H (representing hypotheses) and an error function err : D x H - [0, oo). The goal is to learn a hypothesis from H by observing samples from a distribution D where D E D with small error Drr h). A learning algorithm A has the following

---

inputs: (i) independent samples from distribution D D and (ii) oc) and (iii) 8 (0, 1) It may also receive additional inputs.
Definition 3.1 (List Replicability), Let k E N, E (0, and 8 E [0, 1]. A learning algorithm A is called (k, e, 8--sist replicable if the following holds: There exists n E N such that for every D D, there exists list L C H. of size at most & such that (i) for all h L, err( h) I E. and (ii)
s~ Pr_
E 2 1 6.
For E N. we call A k-list replicable if for all E E (0, oc) and ó E (0. 1]. A is (k, 6 replicable. We say that is the sample complexity of A and l is the list complexity of A.
Definition 3.2 (Certificate Replicability), Let & E N. E E (0, 20), and 8 E [0. 1]. A learning algorithm A is called (f, e, -ecerttffe replicable if the following holds: There exists n N such that for
1) - H such that every DE E D there exists h: {0,
Pr rE{0,13
Pr LE
[A(,,E,,r)) = h(r) and err(D,h(r) S 12]21-1 11-00 21 1
We can refine the above definition by introducing another probability parameter p and define a notion of (L, e, P, 8) --epeliicablliy. The definition is the same as above except that we require the outer probability to be 1 p. and the inner probability is 1 - 6. For simplicity, we take p to be ō and work with the notion of (f,e, e, 8) replicability
The above definitions generalize the notion of perfect replicability, where it is required that the learning algorithm outputs a canonical hypothesis (with hrr(D, S E) with probability 2 1 8. A motivation for these definitions is to characterize how close we can be to perfect replicability in scenarios where if perfect replicability is not achievable. Note that for list (certificate) replicability. when k = 1 (respectively, e = 0), we achieve perfect applicability. We note that the above definitions are inspired by mulfi-pseadoddetemmiiiss (Gol19) and influential-bit algorithms (GI19...
4 Primary Lemmas
Our upper bounds are based on certain rounding schemes and the lower bound is based on Spemer/KKM lemma. In this section, we state a few key technical lemmas that will be used in the rest of the paper. The proofs are in the supplementary material. We will use the following notation. We use diam, to indicate the diameter of a set relative to the foo norm and B (Ø) to represent the closed ball of radius centered at p relative to the 6oo norm. That is, in gd we have S,P, +
We first state a lemma that gives universal deterministic rounding algorithm that is used in designing list replicable algorithms. The lemma is based on the work in (VWDP+2) 22) and is a byproduct of certain geometric partitions they call secluded partitions.
and e E (0, oo). Let En fa. There is an efficiently computable function fe: Idd + Rd with the following two properties:
Lemma 4.1. Let
1. For any E Rd and any à E Be, (I) it holds that fc(i) E (.)
2. For any E Rd the set {f(()): & E (x) has cardinality at most d + 1.
Item (1) states that if à an Eo approximation of x. then fe is an E approximation of x, and Item (2) states that f. maps every Eo approximation of r to one of at most d + 1 possible values.
The following lemma gives universal randomized rounding algorithm that is used in designing certificate replicable algorithms. We note that randomized rounding schemes have been used in a few prior works (SZ99) DPV18 Gol19 GL19, [LP2). Our rounding scheme is more nuanced is geared towards minimizing certificate complexity.
Lemma 4.2. Let d E N, Eo E (0, oo) and 0 < 8 < 1. There is an efficiently computable deterministic function f (0, 1)2 Rd > I with the following property. For any x E RRd,
Pr r
Ex* E B (x)
Va E B (x) frr, 8) = x²| 21-8
where& l = [log $1 and E (2 1)E0 2d0
5

---

The following result is corollary cubical variant of Sperner's lemma/KKKM lemma initially developed in (DLPES02) and expanded on (VWDP+22 22). We use this to establish our lower bound results.
Lemma 4.3. Let P be partition of [0, 1]d such that for each member X P. it holds that diam, (X) < 1. Then there exists E [0, 1]d such that for all ō we have that Bg (p) intersects
at least + 1 members P.
Replicability of Learning Coins Biases
In this section, we establish replicability results for estimating biases of d coins.
Definition 5.1. The d-COIN BIAS ESTIMATION PROBLEM is the following problem: Design an algorithm (possibly randomized) that gets E E (0, 1), 8 E (0, 1] as inputs, observes independent tosses of an ordered collection of d-many biased coins with bias vector E [0, 1]" and outputs 7 so that ||ō 20 S with probability 2 6.
The d-COIN BIAS ESTIMATION PROBLEM fits in the framework of the general learning task introduced in Section 3 so that we can talk about list and certificate replicable algorithm for d-COIN BIAS ESTIMATION PROBLEM. We describe this now.
For d- d-COIN BIAS ESTIMATION PROBLEM have the following. X' {0, 1)d (where 0 corre-
sponds to Tail and I corresponds to Head) which is the set of representations of all possibilities of flipping d-many coins. The class of distributions D is the set of all d-fold products of Bernoulli distributions. Each distribution D E 'D is parameterized with a vector up = (h,,... ba) E [0, 1| When sampled according UD obtain sample point (x) ..-2a)) We take the class of hypothesis H to be [0, 1j which is the set of all d-tuples representing biases of collection of d-many coins. Lastly, the error function defined as err( D, h) = D hiloo-
X, where Pr(x; 1) b;-
5.1 Replicable Algorithms for d-COIN BIAS ESTIMATION PROBLEM
In this section, we design list and certificate replicable algorithms for d-COIN BIAS ESTIMATION PROBLEM
Theorem 5.2. There exists an (d + 1)-list replicable algorithm for d-COIN BIAS ESTIMATION PROBLEM. For a given e and ö, its sample complexity is n = 0 de log 4), per coin.
Algorithm 1 (d+ 1)-list replicable algorithm for d-COIN BIAS ESTIMATION PROBLEM
Input: E > 0, E (0, 1), sample access to coins with biases E [0, 1jd
Eo def
2d 80 def
def
In(1/6o)
dd In(d/6) for some constant e
Let fe Rd
+ Rdd be as Lemma 4.1
Let Rd
[0, 1 be the function which restricts coordinates to the unit interval (i.e.
Y/
( def
yi
yi E [0, 1]
Y: >
i=1
Take samples from each coin and let ă be the empirical biases. return (())
Proof. Note that when E 2 1/2, a trivial algorithm that outputs a vector with 1/2 in each component
works. Thus the most interesting case is when < 1/2. Our list replicable algorithm is described in
Algorithm We will prove its correctness by associating for each possible bias i E [0, 1]d, a set Lg
with the three necessary properties: (1) Lgl < d (2) Lg B (6) (and also the problem specific

---

restriction that L.g [0, 1J and (3) when given access coins of biases 6, with probability least 1 - the algorithm returns a value in T.g.
Let Lg = { {=)== ZE (C,
(6) By Lemma 4.1 fe takes on at most + values on B (7)
(which means y o fc also takes on at most d values on this ball) which proves that [Tgl - d d This proves property (1).
Next we state the following observation which says that the coordinate restriction function g of Algorithm 1 does not reduce approximation quality. The proof is straightforward.
Observation 5.3. Using the notation of Algorithm 1. if E B (b) then ( E B (b).
We now establish Property (2). We know from Lemma 4.1 that for each F E (b) we have (z) E B (b), and by Observation 5.3 maintains this quality and we have g(fc E B (b).
This shows that Tig C = (6) proving property (2).
independent samples of the coin we can estimate the bias within Eo with probability at least 6g. Thus. by a union bound, we take n samples of each of the d coins, there is a probability of at most d do = ó that at least one of the empirical coin biases not within Eo of the true bias. Thus, by taking samples of each coin, we have with probability at least this occurs, we have by definition of L5 that the value ((f returned by the algorithm belongs to the set Lg. This proves property (3). The sample complexity follows since Eu 2d and do d"
By Chernoff's bounds, for a single biased coin, with n. = 0 (n(11/6))
=8
8 that the empirical biases belong to (b). In the case that
The next result is on certificate replicable algorithm for d-COIN BIAS ESTIMATION PROBLEM. Theorem 5.4. For every and 5, there is (fog (), replicable algorithm for d-COIN BIAS ESTIMATION PROBLEM with sample complexity of n = O &
per coin.
Proof. Let e and ó be the input parameters to the algorithm and b the bias vector. Eo = :b The 2d
algorithm A first estimates the bias of each coin with up Eo with a probability error parameter de
using a standard estimation algorithm. Note that this can be done using O 22 tosses per coin.
Let e' be the output vector. It follows that 전 E B (b) with probability at least 1 - 5. Then it runs the deterministic function f described in Lemma 4.2 with input {0, 1) with f [log g and i and outputs the value of the function. Lemma 42 guarantees that for 5 fraction of the rs, all
J E B (b) gets rounded to the same value by f. Hence algorithm A satisfies the requirements of the certificate-repliaabli The certificate complexity is [log 1
We remark that by using the refined definition of certificate replicability mentioned in Section 3 we de can obtain ([log 11 -'reelica algorithm with sample complexity O 2:p log(1/6)). Note that an é-certificate replicable algorithm leads to 2 -listt replicable algorithm. Thus Theorem 5.4 gives a ) replicable algorithm for d-COIN BIAS ESTIMATION PROBLEM with sample complexity O
((2222) However, this is clearly sub-optimal and Theorem 5.2 gives algorithm with much smaller list and sample complexities. Also from the work Goldrecth (Gol19). it follows that (-list replicable algorithm can converted into a [ -certifiice replicable algorithm. However, this conversion increases the sample complexity. For example, when applied to d-COIN BIAS ESTIMATION PROBLEM, the sample complexity becomes O d0
dat
(. ). In comparison, Theorem 5.4 uses tailored rounding technique to achieve an algorithm with much smaller sample complexity.
5.2 An Impossibility Result
This section establishes the optimality of the list complexity for d-COIN BIAS ESTIMATION PROB- LEM.
Theorem 5.5. For l < d 1, there does not exist a k-list replicable algorithm for the d-COIN BIAS
ESTIMATION PROBLEM.
7

---

Before proving the theorem, need lemma that follows from the Data Processing Inequality; for
more detail see the supplementary material. In the following, we use D A. to denote the distribution of the output of an algorithm for d- C-COI BIAS ESTIMATION PROBLEM.
Lemma 5.6, For biases ã. b E [0, 1] we have drv (DA D PA...) S sn.d. ||--al ae
Proof. We use the basic fact that an algorithm (deterministic or randomized) cannot increase the total variation distance between two input distributions.
The distribution giving one sample flip of each coin in a collection with bias is the d-fold product of Bernoulli distributions II Bern(b;) (which for notational brevity we denote as Bern(b), so the distribution which gives n independent flips of each coin is the n-fold product of this and is denoted
as Bern ()) We will show that for two bias vectors ă and 6, drv (Bern(b) (6) &n Bern(a))n)) n d ||B ae This suffices to establish the lemma. Observe that we have for each E [d].
drv (Born(b.), Bern(a;)) 1b; azl-
Hence we have
d
drv (Beru(b), Bern(a))
Σ 1=1
6. ail S d 16 a|
and
drv (Bern())o on Bern(a) (a)) S n d |b ब م.
Proof of Theorem 5.5 Fix any d E N, and choose and d as <
I. Suppose for 2 and d S Ø42.
contradiction that such an algorithm A does exists for some k < d + 1. This means that for each possible bias vector 5 E [o, 1J", there exists some set L,g C H of hypotheses with three properties: (1) each element of Ly is an c-approximation to hy. (2) LL S k. and (3) with probability at least 1- 8, A returns an element of Lg.
By an averaging argument, this means that there exists at least one element in Lg which is returned by k+2
A with probability at least 1/2 (1- 8) 2 1/- (1- + (1- =
##1 2
k+1
Let f: [0, 1]d + [0, _]d
be a function which maps each bias 5 such an element Lg. Since that 0 < 17
A+1 1 let r be such K41
R+2
A+1 k+2
1
K+1-
The function induces partition P of [0, 1]d where the members of P are the fibers of f (i.e. P= (T) 7 E range([)). By definition, for any member X E P there exists some zj E range(J)
such that for all 5 E X, f(b)- = T. By definition, we have ((b) E Lg S Be (b) showing that ÿ E Bed (z) and by symmetry i E Be (j) This shows that X C B (f), diam (X) S 2c 1.
Let y.d. Since every member of P has foo diameter less than 1, by Lemma 4.3 there exists point e [0, 1] such that B.S (p) intersects at least d + 1 > members of P. Let ((1) " F(++)
n
be points belonging to distinct members of P that all belong to B, (ý). By definition of P, this means for distinct j.j' [d 1] that ((B0)) + 5(b5")).
Now, for each E [d 11, because || 160 S r. by Lemma 5.6 have drv (D., D ,) I n d.r = 77. However, this gives rise to a contradiction because the probability that A with access to biased coins B() returns f(b()) is at least k+1 k+2 and by
Lemma 5.6. it must be that A with access to biased coins F returrns f(55) with probability at least Z 1
1+11 R42
+ notationally, Prp A.. K+T
(((()))))
k+1 1.kt1 and dTv(D) A,DG),,. ,n D D....)) S m. k42
so PIDA.... (f (((0)) # 1. This is a contradiction because a distribution cannot
have d + > k disjoint events that each have probability greater than KFI
8

---

1z -log 4), where v is the approximation error parameter of 6 List and Certificate Replicability in PAC Learning
In this section, we establish replicability results for the PAC model. We first note that PAC model fits in the general learning framework introduced in Section Consider the PAC learning model where we have a domain X", a concept class C (a family of subsets of X"), and a hypothesis class H. (a collection of functions 2" + {0, 1}). For any distribution over X' and any concept indicator / from C, let Dy denote the distribution over 2' {0, 1)d obtained by sampling define the following learning problem in the general learning framework: X = X' x {0, 1). H H. D = (D, f E C and a distribution over )"), }. and err(Dr, h) = Pr [f(x) + h(r)].
D and outputting (ar, fxx)). We
We are interested in statistical query learning which is defined by Kearns (Kaa98).
Definition 6.1. A statistical query oracle STA v) takes as an input a real-valued function 6: X x [0, - (0, 1) and returns estimate such that |V (e (o(x,, y)] I v Kea98)). We say that an algorithm A learns concept class H. via statistical queries if for every distribution D and every function f H. for every 0 E < 1, there exists v such that the algorithm A on input and ST AT as an oracle, outputs a hypothesis & such that err(Dy.h) s ε. The concept class non non-adaptively learnable all the queries made by A the statistical query oracle are non-adaptive.
6.1 Replicable PAC Learning Algorithms
Next we state main results of this section. Due to space limitation, all the proof's are in the supple- mentary material. We first show that any concept class that is learnable with d non-adpative statistical queries has a (d + 1)-list replicable algorithm.
Theorem 6.2. Let H. be a concept class that is learnable with d non- statistical queries, then H. (d + 1)-list replicably learnable. Furthermore, the sample complexity n n(v, 5) of the (d + 1)-list replicable algorithm is O de each statistical query oracle.
We note that we can simulate a statistical query algorithm that makes d adaptive queries to get 2d-list replicable learning algorithm. This can be done by rounding each query to two possible values (the approximation factor increases by 2). The sample complexity of this algorithm will be 0G log 4). Next, we design a certificate replicable algorithm for hypothesis classes that admit statistical query learning algorithms.
Theorem 6.3. Let H be concept class that learnable with d non-adaptive statistical queries, then H is flog _ 1-certificate replicably learnable. Furthermore, the sample complexity = nn(, 6) of this algorithm is O( llog d) where u is the approximation error parameter of each statistical query oracle.
d² pa8
We can also consider the case when the statistical query algorithm makes d adaptive queries. In this case we get the following theorem. Note that the certificate complexity close to linear in d as oppose to logarithmic in the case of non-adaptive queries.
Theorem 6.4. Let H be a concept class that is learnable with d adaptive statistical queries, then H log & -eertiffcaaee replicably learnable. Furthermore, the sample complexity of this algorithm is O da p2 log ) where is the approximation error parameter of each statistical query oracle.
6.2 Impossibility Results the PAC Model
In this section, establish matching upper and lower bounds the list complexity for the concept class d- d-THEESHoL in the PAC model with respect to the uniform distribution. In particular, we establish that this learning task admits (d + 1) 1)-list replicable algorithm and does not admit d-list replicable algorithm.
Definition 6.5 (d- Ad-TURESHOLLD) Fix some d E N. Let X = [0, 1]d For each value i'E [0, 1]d, let hr: X + 10. be the concept defined as follows: h₂(()) = if for every i E [d] it holds that Iz I t4 and 0 otherwise. Let H. be the hypothesis class consisting of all such threshold concepts: H. [hr f's [0, 1]4)

---

We first observe the impossibility of list-replicable algorithms in the distribution-Free PAC model. This follows from known results.
Observation 6.6. There is no k-list replicable algorithm (for any for d- T-THESSHOL in the PAC model even when d = 1.
The above observation follows from the works of (ALMM19) and (BLM20) It is known that d- THRESHOLD has infinite Littlestone dimension. Suppose it admits k-list replicable algorithms in the PAC model. This implies that d- d-THRESHOLD is globally stable learnable with stability parameter 1/k (Please see (BLM20) for the definition of global stability). The work of (BLM20) showed that any class that is globally stable learnable with a constant stability parameter is differentially private learnable. The work of (ALMM19) showed that if concept class differentially private learnable, then it has a finite Littlestone dimension. Putting these results together, we obtain that d- THRESHOLD admits k-list replicable algorithm, then has a finite Littlestone dimension which is a contradiction.
The above result implics that for every k and every learning algorithm A. there is distribution D a such that A is not k-list replicable with respect to DA. However, a natural question is whether lower bound holds for fixed distribution, especially simple distributions such the uniform distribution. We show that this is indeed the case.
Theorem 6.7. In the PAC model under the uniform distribution, there is a + 1-list replicable algorithm for the d-TURESHOLD. Moreover, for any k < d+ there does not exist k-list replicable algorithm for the concept class d- 4-THRESIOOL under the uniform distribution. Thus its list complexity is exactly d + 1.
7 Conclusions
In this work, we investigated the pressing issue of replicability in machine learning from an algorith- mie point of view. We observed that perfect replicability is not achievable and hence considered two natural extensions that capture the degree of (non) replicability: list and certificate replicability. We designed replicable algorithms with small list, certificate, and sample complexities for the d- CoIN BIAS ESTIMATION PROBLEM and the class of problems that can be learned via statistical query algorithms that make non-adaptive statistical queries. We also established certain impossibility results in the PAC model of learning and for d-COIN BIAS ESTIMATION PROBLEM. There are several interesting research directions that emerge from our work. There is gap the sample complexities of the list and certificate replicable algorithms with comparable parameters. Is this gap inevitable? Currently, there is an exponential gap in the replicability parameters between hypothesis classes that can be learned via non-adaptive and adaptive statistical queries. Is this gap necessary? A generic question to explore the trade-offs between the sample complexities, list complexity, certificate complexities, adaptivity, and nonadaptivity.
8 Acknowledgements
We thank the NeurIPS 2023 reviewers for their comments that improved the presentation of the paper. We especially acknowledge reviewer U7Lz for very detailed and insightful comments. We thank an anonymous researcher for pointing out Observation 6.6) We thank Jamie Radcliffe for informative discussions on topics related to this work. We thank authors of (CMY23) for informing about their work and helpful discussions. Part of this work is supported by NSF grants 2130536 and 2130608. Part of the work was done during Pavan and Vinodchandran's visit to Simons Institute for the Theory of Computing. Part of Peter's 's work was done while at Ben-Gurion University of Negev.
10

---

References
[AJJ*22] Kwangjun Ahn, Prateek Jain, Ziwei Ji, Satyen Kale, Praneeth Netrapalli, and Gil 1. Shamir. Reproducibility in optimization: Theoretical framework and limits, 2022.
arXiv:2202 04598
[ALMM19] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 852-860. ACM, 2019.
[AV20] Nima Anari and Vijay V. Vazirani. Matching as easy as the decision problem, in the NC model. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPlcs, pages 54:1-54:25, Schloss Dagstuhl- Leibniz-7eentrum für Informatik, 2020.
[6ak16] Monya Baker. 1 1,500 scientists lift the lid on reproducibility. Nature, 533:452--454 2016.
[BLM20] Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In Sandy Irani, editor, 61st IEFE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 389-402. IEEE, 2020.
[CMY23] 7achary Chase, Shay Moran, and Amir Yehudayoff. Replicability and stability in learning, 2023. 2rx1v:2304.0333
[CP23] Moses Charikar and Chirag Pabbaraju. A characterization of list learnability. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 1713-1726, New York, NY, USA, 2023. Association for Computing Machinery. doi: 111:110.///5522466656 3585190
[DLPES02] Jesus A. De Loera, Elisha Peterson, and Francis Edward Su. A Polytopal General- ization of Sperner's Lemma. Journal of Combinatorial Theory, Series A, 100(1):1- 26, October 2002. URL: https: www. roc.ee/ceedeeet.coooooooooo/ooo
doi:10. 101:10.1006/jeaa
[DPV18] Peter Dixon, Aduri Pavan, and N. V. Vinodchandran. On pseudodeterministic approxi- mation algorithms. Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPlcs, pages 61:1-61:11. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2018
[DPVWV22] Peter Dixon, Aduri Pavan, Jason Vander Woude, and V. Vinodchandran. Pseudo- determinism: promises and lowerbounds. In Stefano Leonardi and Anupam Gupta, editors. STOC '2: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages 1552-1565... ACM, 2022.
[eco13] How science goes wrong. The Economist, pages 25-30, 2013.
[EKK*23] Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas. Replicable bandits, 2023. a arxiv: 2210.01898
[GG] Shafi Goldwasser and Ofer Grossman. Bipartite perfect matching in pseudo- deterninistic NC. In loannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Pro- gramming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LiPles.
[GG11] Eran Gat and Shafi Goldwasser. Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications. Technical Report 136, 2011. URL: https
/ //ecce. wei zmann ac wtw.ac.....poooo. wtt........//geet///000//3......
11

---

[GGHI8] Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden. Pseudo-deterministic proofs. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPlcs, pages 17:1-17:18. Schloss Dagstuhl Leibmiz-Zentrum für Informatik, 2018.
[GGMW20] Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, and David P. Woodruff. Pseudo- deterministic streaming. Thomas Vidick, editor, 1 Ith Innovations in Theoretical Computer Science Conference, ITCS, volume 151 of L/Plcs, pages 79:1-79:25 2020.
[GKM21] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via correlated sampling. In Mare' 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- 20184, 2021.
[GL19]] Ofer Grossman and Yang P. Liu. Reproducibility and pseudo-determinism in log- space. Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 606-620. SIAM, 2019. doi 1131
1137/1. 9T11///..711111178888888
38
[Gol19] Oded Goldreich. Multi-psenuoddeeerminiiiic algorithms. Electron. Colloquium Com- put. Complex., TRI9-01 19-012, 2019. URL: https: //cccc.cccc//////////////.cc wei zmann aweaannacc.... ac. il/
report 20011/12
a arXiv: TR19-01
[ILPS22] 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 818-831. ACM, 2022. doi 1eei111..11555 1ee1111111/13333 3519973
[JPO5] Ioannidis JP. Why most published research findings are false. PLOS Medicine, 2(8), 2005.
[ea998] Michael J. Kearns, Efficient noise-tolerant learning from statistical queries. J. ACM, 45(6):983-1000 1998.
[LOS21] Zhenjian Lu, Igor Carboni Oliveira, and Rahul Santhanam. Pseudodeterministic algorithms and the structure of probabilistic time. In Samir Khuller and Virginia Vas- silevska Williams, editors, STOC '21: 53rd Anmual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 303-316. ACM, 2021.
[MPK19] Harshal Mittal, Kartikey Pandey, and Yash Kant, Iclr reproducibility challenge report (padam Closing the generalization gap of adaptive gradient methods in training deep neural networks), 2019. arxiv: 901, 09517
[NAS19] Reproducibility and Replicability in Science. https: /ttgg/10.1222 25303, 2019. National Academies of Sciences, Engineering, and Medicine.
[OS17] I. Oliveira and R. Santhanam. Pseudodeterministic constructions in subexponential time. In Proceedings of the 49th Annual ACM SIGACT Symposium Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 665-677, 2017.
[OS18] Igor Carboni Oliveira and Rahul Santhanam. Pseudo-deraaddmiizing learning and approximation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, volume 116 of L/Plcs, pages 55:1-55:19, 2018
12

---

[PVIS*21] Joelle Pineau, Philippe Vincent-Lamarre, Koustuv Sinha, Vincent Lariviere, Alina Beygelzimer, Florence d' Alche Buc, Emily Fox, and Hugo Larochelle. Improving reproducibility in machine learning research(a report from the neurips 2019 repro- ducibility program). Journal of Machine Learning Research, 22(164))1-20, 2021.
URL: http::/jmlr. www.:rgg/ppppp.... pwwppr//22/////00//0/// w22/20 303. .html
[RY20]
Prasad Raghavendra and Morris Yau. List decodable learning via sum of squares. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium Discrete Algo- rithms, SODA '20, page 161-180, USA, 2020. Society for Industrial and Applied Mathematics.
[SZ99] Michael E. Saks and Shiyu Zhou. SPACEE() C DSPACE(S3/2) J. Comput. Syst. Sci., 58(2):376-403 1999.
[VWDP*22] Jason Vander Woude, Peter Dixon, Aduri Pavan, Jamie Radcliffe, and N. V. Vinodchan- dran. Geometry of rounding. CoRR, abs/221 wttp/211.000/tt 1,0269,, 2022. aaxivv 2211 02694 : 485::11..50/aaa /ar.vviv/rriii..//. 2211.02694
13

---

A Appendix
A.1 Missing Proofs from Section
To establish Lemmas and 4.3 we build the work of (VWDP+22 and (DLPES02). We first introduce the necessary notion and definitions.
We recall the following notation from the main body of the paper. We use diam to indicate the diameter of set relative to the &o norm and B3 (p) to represent the closed ball of radius e centered relative the &o norm. That is, in Rd we have Be (f) II E, + +
Lemma 4.1 is based on the construction of certain geometric partitions of F called secluded partitions. Such partitions naturally induce deterministic rounding schemes which we use in the proof.
Let be partition of Rd. For point ğ E Rdd let (p) denote the set of members of the partitions that have non-empty intersection with the e-ball around p. That is,
N: (p) [X P
(T)
Definition A.1 (Secluded Partition). Let P be partition of Rdd We say that P is (k, e)-scluded, if for every point p E R [Ne k.
The following theorem from (VWDP+22) gives an explicit construction of secluded partition with desired parameters where each member of the partition is hypercube. For such partitions, we use the following notation. For every ç E IRd, if p E P,, then the representative of p. rep(p), is the center of the hypercube X.
Theorem A.2. For each E N, there exists (d + Zu -sscludded partition, where each member of the partition is unit hypercube. Moreover, the partition is efficiently computable: Given an arbilrary point T Rd. its representative can be computed in time polynomial in d.
A.1.1 Proof of Lemma
4.1
Lemma A.3 (Lemma
4.
Let d E N and e E (0, Let en a.
There is an efficiently
computable function fe Rdd Rdd with the following two properties:
1. For any E Rdd and any & E BB, (a)
) it holds that fe(i) E B (z).
2. For any Rdd the set [f(()): & B,, has cardinality most +
As explained in the main body, intuitively, item (1) states that if å is an eo-approximation of æ, then fe fe( is an E-approximation x, and item (2) states that fs maps every Eo-approximation of x to one of most + possible values.
Proof. A high-level idea behind the proof is explained in Figure We scale the (d + 22 -eecluded unit hypercube partition by E so that each partition member is hypercube with side length Now, for point x, the ball B ao. (ar) intersects at most d hypercubes. Consider point d B (x)), is rounded to eı (center of the hypercube it resides in). Note that ei lies in the ball of radius s around x, this is because distance from i is at most so and the distance from क
is at most e/2.
By triangle inequality e1 belongs to B (x). We now provide formal proof.
Let P be the (d + 1, + -seeluddd partition given by Theorem A.2 Thus P consists of unit cubes
[o, 1)dt with the property that for any point ñ E Rd the closed cube of side length 1/d centered at (7)) intersects at most d + members/cubes of P.
(i.e. B 2J
We first define rounding function f Rd Rdd follows: for every x E fT) rep(x))
Observe that the rounding function f has the following two properties. (1) For every Rd llf(z) Illoo < J. This is because every point r is mapped via f to its representative, which the
center of the unit cube in which lies. (2) For any point ÿ7 E R2d, the set ((x):: x E 8 (p) has
14

---

B 50 (x)
78
c2
c3
Figure Illustration of proof of Lemma 4.1 for
cardinality at most d + 1. This is because B (p) intersects at most d hypercubes of P and for 24
every hypercube X, all the points in X mapped its center by
The function f only gives an 1 a-approximation guarantee. order to get any e-approximation guarantee, scale appropriately. fe is this scaled version of f.
Define the function fc IR > RR follows: for every à RR. fe(0) = E f(. The efficient computability of fc comes from the efficient computability of f.
We first establish that fe has property (1) stated the Lemma. Let x E Rd and E (z). Then have the following (justifications will follow):
| fe(() 1l
||{ !
< [f( _all + +1 _=|1
S |[((a)) dell + b x1100
$ 2 + Pec
The first line is by the definition of fs. the second is the triangle inequality, the third is scaling of norms, the fourth uses the property of ff that points are not mapped a distance more than & along with the hypothesis that & E B (Ir), the fifth uses the definition of so, and the sixth uses the fact that 2 1.
Scaling both sides by and using the scaling of norms, the above gives us (f) xl1o0 S e which proves property (1) of the lemma.
To see that fo has property (2), let r E IRd. We have the following set equalities:
{se(t): & E (1) e ((Ea): & (x)
{ f(a): a B (tx)
{e. f(a): Bi (
2d
The first line is from the definition of fe, the second line is from re-scaling, and the third is from the definition of en-
Because f takes on at most d + distinct values on BY (. the set above has cardinality at most + 1 which proves property (2) of the lemma.
2d
15

---

A.1.2 Proof of Lemma 4.2
Lemma A.4 (Lemma
4.2) Let N, Eo (0) and 0 < < 1. There is efficiently computable
deterministic function functioo
10, x Rd Fdd with the following property. For any R
Pr ref0,13
3x" E B (x) vi B (x) [(r, = x01 21-6
where ( [log & and (2 1)50 0
Proof.
Partition each coordinate of R into wid-width intervals. The algorithm computing the function f does the following simple randomized rounding:
The function f : Choose a random integer r E {1...2%). Note that r can be represented using & bits. Consider the 7th coordinate of denoted by a[d]. Round æ|i] to the nearest * (25o) such that mod? 2 r.
Now we will prove that f satisfies the required properties.
First, we prove the approximation guarantee. Let x'' denote the point in IR obtained after rounding each coordinate â. The ks satisfying & mod 2 r are 2 25D apart. Therefore, x'|i] is rounded by at most s0 That is, [x'[i] - æ|j] < 2 = Ead for every i, 1 S i S d. Since & is an ag-approximation (i.e, each coordinate f[t] is within En of the true value xfi)), then each coordinate of o' is within (2 1)80 of xri)) Therefore x' is (2 jeo-approximation of æ=ii. Thus x' E B. (1) for any choice of r.
Now we establish that for 2 1- 8 fraction of {1.... 2f), there exists x² such every & E B (x) is rounded x². We argue this with respect to each coordinate and apply the union bound. Fix an and a coordinate For z[i], consider the Eo interval around it.
Consider from {1 {1...2%) 2²). When this chosen, then round [(i] to the closest x (25g) such that A mod 2 = Let PS....... Pÿ ... be the set of such points: more precisely PA (j2' + +)) 28g- Note that a|i] is rounded to Py some j. Let my denote the midpoint between pj. and pj+1- Le, m = (pj + 1)/2 We call 'bad' for x|{]] if
[[]] is close to some my, That is, is 'bad' if [e]]]] - -m31 < Eo- Note that for a bad r there exist oi and d2 in B (x) so that their 7th coordinates are rounded to pj and pJ+1 respectively. The crucial point is that r is 'not bad' for x/i]. then for every x' E B (z), there exists canonical p² such that e'ii] rounded to p². We call bad for x, is bad for x, if there exists at least one i, 1 $ i S d such that is bad for æri). With this, it follows that if is not bad for æ, then there exists a canonical x² such that every x' E B cg (z) rounded to x².
With this, the goal is to bound the probability that randomly chosen is bad for x. For this, first bound the probability that r is bad for z[i]. We will argue that there exists at most one bad for æfi]. Suppose that there exist
numbers r and r2 that are both bad for æ=1]] This means that [a[]|] m < Eo and |a]|]] " T2 < éo for some ji and ja. Thus by triangle inequality mm m² < 250- However, note that Ip") p/ is ((1 f2)22 2f (n r2) Since rı # r2, this value at least 25.. This implies that the absolute value of difference between m"! and m is at least 2= leading to contradiction.
Thus the probability that is bad for ari most 1 and by the union bound the probability that is bad for x is at most d
2 < 8. This completes the proof.
A.1.3 Proof of Lemma 4.3
The proof, which is based on Spemer/KKK Lemma, is present in (VDDP*2), Since our setting is slightly difffrrnt, for completeness we give a proof.
We first introduce the necessary definitions and notation.
Definition A.5 (Sperner/KKM Coloring). Let d e N and V = {0, 1)ah denote set of colors (which is exactly the set of vertices of [0, 1]d that colors and vertices are identified), Let x: [0, 1]d V
16

---

be coloring function such that for any face F of [0. 1] (of any dimension), for any I F, it holds that x(xx) E (F) where ((F) is the vertex set of F (informally, the color of x is one of the vertices the face F). Such a function X will be called a Sperner/KKM coloring.
Theorem A.6 (Cubical SPerner/KKM lemma (DLPESO2) Let d E N and V = {0, 1] and X: |0, 1] + V be a Sperner/KKM coloring. Then there exists a subsel J C V with [J] = d 1 and
point ÿ E [0, 1] such that for all j E J, 1 X (j) (informally, there is point ÿ that is touching least 1 different colors).
We will need to relate partitions to Spemer/KKK coloring that we can the Sperner/KKM Lemma.
For any co-ordinate let denote the standard projection map: [0, 1j - [0, 1J defined by ((( def which maps d-dimensional points to the jth coordinate value. We extend this to sets:
(X) = (z) X}.
Definition A.7 (Non-Sp Mion-Spanning partition). Let d E and P be a partition of [o, 1]". We say that P is non-spanning partition if it holds for all X E P and for all [d] that either n; (X) 7 0 or (X) 3 (or both).
Next, we state a lemma that asserts that for any non-spanning partition, there is a Sperner/KKM coloring that respects the partition: that is every member gets the same color.
Lemma A.8 (Coloring Admission). Let d N, and V = {0, 10, and non-spanning partition of [0, 1]s. Then there exists a Sperner/KKM coloring X : [0, 1]dh + V such that for every X for every 2, y E X, x(2) = X3)..
Now we are ready to prove the Lemma
Lemma A.9. (Lemma 4.3) Let P be a partition of [0, 1] such that for each member X E P, holds that diam (X) < 1. Then there exists ç [0, 1] such that for all 8 >> 0 we have that B (p) intersects at least d members of
Proof. Consider an arbitrary X E P. For each coordinate, E [d] the set {z;: x E X) does not contain both 0 and 1 (if did, this would demonstrate two points in X that are lo distance least 1 apart and contradict that diam. (X) < 1). Thus, P is by definition a non-spanning partition of [0, 1]d. Since P non-spanning, by Lemma A.8 there is a SPemnerKKK coloring where each point of [0, 1]d can be assigned one of 2d -many colors and for any member X P, all points in X are assigned the same color. By Lemma A.6 there is point ş E [0, 1] such that ğ j'bbllongs the closure of at least + colors. Since every point of a partition has the same color, each of these d + 1 colors corresponds to at least d + 1 different partitions. From this, it follows that or any d > 0, B3 (p) intersects least d + different members of P.
A.2 Missing Proofs From Section
A.2.1 Proofs of Theorem 6.2. Theorem 6.3
Theorem A.10 (Theorem 6.2 Let H be concept class that is learnable with d non-adaptive statistical queries, then H is (d + 1)-list replicably learnable. Furthermore, the sample complexity
the (d the 1)-list replicable algorithm is O 22 -log g), where is the approximation error parameter of each statistical query oracle.
=n(v, 8)
Our replicable algorithm B works as follows. Let and input parameters and 'D distribution and ʃ E H. Let be the statistical query learning algorithm for H. Let AT (T v) be the statistical query oracle for this algorithm. Let 01. ... . dd be the statistical queries made by A.
Proof. The proof is very similar to the proof of Theorem 5.2
Let 5 = ([[1),[[2,... b(d]] where b[i] = E( (o,((a,))) isis d. Set En = 3/4 The
algorithm B first estimates the values b(() up to an approximation error of eo with success probably
1 - 6/d d for each query. Note that this can be done by a simple empirical estimation algorithm, that
17

---

uses total of n 0 log + samples. Let 전 be the estimated vector. It follows that Ø B (b) with probability at least - 8. Note that different runs of the algorithm will output different U.
Next, the algorithm B evaluates the deterministic function fe from Lemma 4.1 input ह. Let e be the output vector. Finally, the algorithm B simulates the statistical query algorithm with xi]o] as the answer to the query Φ,. By Lemma 4.1 य E By (b). Thus the error of the hypothesis output by the algorithm at most E. Since A is a deterministic algorithm the number of possible outputs only depends on the number of outputs of the function fe. more precisely the number of possible outputs
is the size of the set (T) E Be, (6) which is almost d + 1, by Lemma 4.1 Thus the total number of possible outputs of the algorithm B is at most d + 1 with probability at least 8. O
Theorem A.11 (Theorem 6.3p. Let H. be a concept class that is learnable with d non-adaptive statistical queries, then H. is [log $1 -certificate replicably learnable. Furthermore, the sample
complexity n = n(v, 8) of this algorithm equals O p2gz log 4). where v is the approximation error parameter of each statistical query oracle.
Our replicable algorithm B works as follows, let and ö be input parameters and D be distribution and H. Let A be the statistical query learning algorithm for H. that outputs a hypothesis h with approximation error eD, (h) = E. Let ATD //) be the statistical query oracle for this algorithm. Let 01,..... Od be the statistical queries made by A.
Proof. The proof is very similar to the proof of Theorem 5.4
Let 8 =
, b[d],. where b[i] =
(dr((,,, v))l Set en = w8 The algorithm B 22
first estimates the values b[i], S S d up to an additive approximation error of Eo with success probably 1 for each query. Note that this can be done by a simple empirical estimation algorithm
de سوحz log ) samples. Let e be the estimated the vector. It follows that E Be (b) with probability at least - 5. Next, the algorithm B evaluates the deterministic function f described in Lemma 4.2 with inputs r E {0, 13 where = [log d1 and V. By Lemma 4.2 for at least 1-6 8 fraction of the r's, the function f outputs a canonical o² E B, (b). Finally, the algorithm B simulates the statistical query algorithm A with [i] as the answer the query di. Since A is deterministic algorithm it follows that our algorithm B is certificate replicable. Note that the certificate complexity is == [log $1
that uses total of n O
The following theorem states how to convert adaptive statistical query learning algorithms into certificate replicable PAC learning algorithms. This result also appears in the work of (GKM21 ILPS22), though they did not state the certificate complexity. We explicitly state the result here.
Theorem A.12. ((GKM2T) ILPS22)
6.49 Let H be a concept class that is learnable with d adaptive statistical queries, then H is [dlog $ -certificaaee replicably learnable. Furthermore, the sample complexity of this algorithm equals O 1282 log d), where is the approximation error parameter of each statistical query oracle.
d
Proof. The proof uses similar arguments before. The main difference is that we will evaluate each de query with an approximation error of d with a probability error of d/6. This requires O 0/ log $ per query. We use a fresh set of certificate randomness for each such evaluation. Note that the length of the certificate for each query is [log d/67. Thus the total certificate complexity is [d 1. 0
A.2.2 Proof of Theorem
We first recall the definition of the concept class d' THRESHOLLD
Fix some d E N. Let X [0, 1]d For each value i' E [0, 1]d, let h X + {0,1) 13 be the concept defined as follows: hf(i)) = 1 for every i E [d] it holds that 2; Σ t, and 0 otherwise. Let H. be the hypothesis class consisting of all such threshold concepts: H = [hrl Te 1]]
Theorem A.13 (Theorem 6.7p. In the PAC model under the uniform distribution, there is a d + 1-list replicable algorithm for the d-THRESHOLD. Moreover, for any k < d 1, there does not exist -ist replicable algorüthm for the concept class dl d-THRESHOLD under the uniform distribution. Thus its list complexity is exactly d ++ 1.
18

---

It is easy that d-THRESHOLD is learnable under the uniform distribution by making d non- adaptive statistical queries. Thus by Theorem 6.2, d-THRESHOLD under the uniform distribution admits a (d 1)-list replicable algorithm. So we will focus on proving the lower bound which is stated as a separate theorem below.
Theorem A.14, For < 1+1, there does not exist a k-list replicable Aigorithmfor the d- d-THRESHOLD in the PAC model under uniform distribution.
The proof is similar to the proof of Theorem 5.5 The reason is that sampling d-many biased coins with bias vector d is similar to obtaining a point 7 uniformly at random from [0, 1] and evaluating the threshold function hg on thi corresponds to asking whether all of the coins were heads/1's ss The two models differ though. because in the sample model for the d-COIN BIAS ESTIMATION PROBLEM, the algorithm sees for each coin whether it is heads or tails, but this information is not available in the PAC model for the d- d-THRESHOLD. Conversely, in the PAC model for the d-THRESHOLD, random draw from [o, 1 is available to the algorithm, but in the sample model for the d-COIN BIAS ESTIMATION PROBLEM the algorithm does not get this information.
Furthermore, there is the following additional complexity in the impossibility result for the d- THRESHOLD. In the d-COIN BIAS ESTIMATION PROBLEM, we said by definition that a collection of coins parameterized by bias vector was an e-approximation to a collection of d coins parameterized م
by bias vector if and only if | ----āll- of e-approximation in the PAC model is quite different than this. It is possible to have hypotheses ha and hg in the d- THRESHOLDDuch that |6 a & but with respect to some distribution Dx on the domain X we have errDx (ha, hig) S e. For example, if Dx is the uniform distribution on X = [0, 1| and = 0 and 6 is the first standard basis vector 5 (1, .......0......... 0), and & 1. then | ~
S c, and we used this norm in the proofs. However, the notion
but errpx (ha, Ag) 0 < because ha(ā)) + hg((z) if and only if all of the last 1 coordinates of ē are and the first coordinate is >> 0, but there is probability 0 of sampling such / from the uniform distribution on X 10.
For this reason, we can't 't just partition [0, 1] as we did with the proof of Theorem 5.5 and must do something more clever. It turns out that it is possible to find a subset [a, 1 on which hypotheses parameterized by vectors on opposite faces of this cube [a, 1] have high PAC error between them. A consequence by the triangle inequality of errDy is that two such hypotheses cannot both be approximated by common third hypothesis. This the following lemma states.
Lemma A.15. Let d E N and a ب Let E, [a, 1] such that there exists coordinate io E [d] where & a and ti, 1 (i.e. 5 and i are opposite faces of this cube). Let S 8d" Then there is no point 1" E X such that both erf (hg, hT) S a and errunit(h hp) I E (i.e. there is no hypothesis which is e-approximation both h2 and hz).
({=
i= i0
Proof. Let q=
which will serve as a proxy to g.
+ i0
We need the following claim.
Claim A.16. For each E X, the following are equivalent:
1. hy(T)= + lxz(()
2. hy(ā) and hx,(T) =
3. Nig (yio: Lio] (a. 1] and for all E (d] \ {1o), ar [0, 4..
Furthermore, the above equivalent conditions imply the following:
4. ha(T)) + hz(F).
Proof of Claim A.16
This is trivial.
19

---

Note that because Gio Sig a lio have for all i E [d] that & S 4. If
(T) 0 then for some in E [d] it must be that Fi; > lig- but since Li, 2 di, it would also be the
case that vi, > qi so hz(()) 0 which gives the contradiction that ha(() hz(z). Thus hy(3)
and since hz) # hxx we have h²( 0.
3 We partition [0, 1] into three sets and examine these three cases.
Case 1: 2i E (9ba t4,] = (a, 1] and for all i E [d] \ fdo), 24 [0]. In this case, 9io < 2%o so hz( 0 and for all i E [d] 24 S tú, so hz(()) 1, so hg(2)) * hz(
Case 2: Tip & (Tio) [io] = (a, 1] and for all i E [d] \ {(o) 24 E [0, 4.]. In this case, because
Tio E [0, 1] and Tip E (a, 1] we have Tig I
lie I to and also for all other i E [d] {da), T; S t, = q: (by definition of q). Thus hr((F) = h)(
Case 3: For some i E [d] {1o). Zi
$ [0, 4.]. In this case, because Hi. E [0, 11, we have
Ty > 111 = Zb Thus hT(3) = hT(
Thus, is the case that hz) # (z) if and only if is E (gta tiol = (a, 1] and for all i E [d] \ fio..
Iy [0. t.].
By 2 we have Tio > Qio and since ti = 8io by definition of q. it follows that Fig Sig which means hT(TT) = O. By hT( = 1 which gives hs( # hT)
2 3
Li
We also need the following Lemma.
Lemma A.17. Let d E N and d-1 d
= 1 1 3. Then (1 a) d- 1
4d'
Proof. If d = 1, then = 0 so (1 a) ad1 2 1 4a (see footnote
If d 2 2, then we utilize the fact that (1 - 1/)²²² 2 in the following:
(1 - a) a d-1 = =1) - 2
(1) (1 1 )
1 d
1/2²
d-1
4(d
4d
This completes the proof. As an aside, a = d is the value of a that maximizes the expression
(1 - a) d-1 which is why that value was chosen.
With the above Claim and Lemma in hand, we return the proof of Lemma A.15 Our next step will be two prove the following two inequalities:
2e < erFauit h2) S erfunit (ha, h2).
For the second of these inequalities, note that by the 1 part of claim above, since hi((d) # h,(z) implies hz(ā) & h,(z²) we have
erfunit (hq, hr)
Pr
hg((3) # hx
# (
<
Pr 1)((T) * h (7)
x xni
err (n h2)
"This uses the interpretation that 0º = 1 which is the correct interpretation in the context in which we will the lemma.
20

---

Now, for the first of the inequalities above, we will use the ① hypothesis that i E [a, 1] (which implies for each E [d] that (0, S [0, a:), will use
3 portion of the claim, will
the hypothesis that E I &d and we will use Theorem A.17
Utilizing these, we get the following:
errunit hnp)
Pr # ~ unil(X)
(1)( # h₂(z)
Pr
Tii E [a, A V (io) xi E [0,44]
-~ fmmif((X)
d II
Pr
Iho E (a, L]]
Pr unif((
[x E [0, t.]]
21 unii((()11)
Pr
Tio E (a, 1]]
II
Pr
[ [0,
Fi ([,,1
# ~ (0.
(1 aa) a0 d-1
1
4d
2 28.
Thus, we get the desired two inequalities:
2e < erTuuit(h hT) S errunit (hg, ht)
This nearly completes the proof. If there existed some point F E X such that both err hp) S E and errunit (h2s h1p) S e, then would follow from the triangle inequality of errunif that
erF (hz, hT) S errumit (hg, hp) errunit (hg, hT) hx) 2c
but this would contradict the above inequalities, so no such F exists.
Equipped with the Lemma A.15 we are now ready to prove Theorem A.14
Proof of Theorem A. Fix any E N, and choose & and as E id d-1
1 S 1 and 5 S a+2
We will use the
constant a _ and consider the cube (ax, 1jd.
Suppose for contradiction such an algorithm does exists for some d This means that for each possible threshold f E [0, 1]d, there exists some set L C H of hypotheses with three properties: (1) each element of L is an e-approximation to h&g (2) L1 < k, and (3) with probability at least 1 1- 6, A returns an element of Lz-
By the trivial averaging argument, this means that there exists at least one element in Lr which is returned by A with probability at least F (1 - 6) 2 1 (1 Ø42) = 1 2+2 2
d+1
k+1 Let R42
f: (a, 1] - [0, 1)d be a function which maps each threshold / E (a, 1] to such an element (the maximum probability element with ties broken arbitrarily) of T.p. This is slightly different from the proof of Theorem becauee we are defining the function on only very specific subset of the possible thresholds. The reason for this was alluded to in the discussion following the statement of Theorem A.14
The function ff induces a partition P of [a, 1]d where the members of P are the fibers of f (i.e. P= ()) z E range(f))). For any member W E P and any coordinate E [d], it cannot be that the set {w, v W} contains both values a and 1-if it did, then there would be two points E W such that s; = a and f; = 1, but because they both belong to W, there is some j E [0, 1]d such that f(3) = T = ft). but by definition of the partition, hy would have to an e-approximation (in the PAC model) of both by and hG. but by Lemma A.15 this is not possible.
Thus, the partition P is a non-spanning partition of [a. 1]d as in the proof of Lemma 4.3 so there is
some point E [a, 1]d such that for every radius > 0, holds that B," (p) intersects at least d + 1
21

---

members of P. In fact, there is some radius such that ||7-81| S v. then dTv DA..D DAT S n for v/ that lies between O and 1
A+1
A+2
K+I
Now we get the same type of contradiction as in the proof of Theorem 5.5g for the special point p we have that D A. is distribution that has d + 2 k + 1 disjoint events that each have probability greater than EIT Thus, no k-list replicable algorithm exists.
B Expanded Prior and Related Work
We give more detailed discussion prior and related work. This section is an elaboration of the Section [ from the main body of the paper.
Formalizing reproducibility and replicability has gained considerable momentum in recent years. While the terms reproducibility and replicability are very close and often used interchangeably, there has been an effort to distinguish between them and accordingly, our notions fall in the replicability definition (VLLS+21)
In the context of randomized algorithmss, various notions of reproducibiittyyeepiicbbbii have been investigated. The work of Gat and Goldwasser (GGII) formalized and defined the notion of pseu- dodeterministic algorithms. A randomized algorithm A is pseudodeterministic if, for any input n, there is a canonical value Us such that Pr[A(z) vnl Z 2/3. Gat and Goldwasser designed polynomial-tine -imme pseudodeterministt algorithms for algebraic computational problems. such as finding quadratic non-residues and finding non-roots of multivariate polynomials (GGIT) Later works studied the notion of pseudodeterminism in other algorithmic settings, such as parallel com- putation, streaming and sub-linear algorithms, interactive proofs. and its connections to complexity theory (GG) GGHH8) 18 OS17 OSTR: AV20, GGMW20 LOS21 DPV
In the algorithmic setting, mainly generalizations of pseudodeterminism have been investigated: algorithms (Gol19) and inftuential bit algorithus (GL19). A randomized algorithm A is k-pseudodeterministic if, for every input x, there set S, of size most k such that the output of A(x) belongs to the set S₂ with high probability. When k = 1, we get pseudodeterminism. A randomized algorithm for most of the strings of length f. there exists canonical value Uzrr such that the algorithm A on inputs x and r outputs Uz.r with high probability. The string is called the inftuential bit string. Again, when f = O, we get back pseudodeterminism. The main focus of these works has been to investigate reproducibility in randomized search algorithms.
é-influential-bit algorithm if, for every input æ,
Very recently, pseudodeterminism and its generalizations have been explored in the context of learning algorithms to formalize the notion of replicability. The seminal work of (BLM20) defined the notion of global stability. They define a learning algorithm A to be (n, -globbaly stable with respect to distribution D if there is hypothesis l such that Prs-n- (A(S) = h) Z 1), here 1) is called the stability parameter. Note that the notion of global stability is equivalent to Gat and Goldwasser's notion of pseudodeterminism when r 2/3. Since Gat and Goldwasser's motivation is to study pseudodeterminism in the context of randomized algorithms, the success probability is taken as 2/3. In the context of learning, studying the stability parameter 1) turned out to be useful. The work of Bun, Livny and Moran (BLM20) showed that any concept class with Littlestone dimension d has an (m, m) -llobally stable learning algorithm with error of h (with respect to the unknown hypothesis) is < a. Then they established that a globally stable learner implies differentially private learner. This, together with earlier work of Alon, Livny, Malliaris, and Moran (ALMM19.. establishes an equivalence between online learnability and differentially private PAC learnability.
Ö(2?") /a) and 1 Õ(2- 2²), where the
The work of Ghazi, Kumar, and Manurangsi (GKM21) extended the notion of global stability to pseudo-global stability and list-global stability. The notion of pseudo-giobal stability is very similar to the earlier- mentionde notion of influential bit algorithms of Grossman and Liu (GL19) when translated to the context of learning. The work of (GKM2I) used these concepts to design leer- differentially private algorithms.
The recent work reported in (LPS22 introduced the notion of p-replicability. A learning algorithm A p-replicable if Prs,,s..r ( = A(2,, r)] 2 1-p. p. where S₁ and S2 are samples drawn from a distribution D and r is the internal randomness of the learning algorithm A. They designed replicable
22

---

algorithms for many learning tasks, including statistical queries, approximate heavy hitters, median, and learning half-spaces. It is known that the notions of pseudo-globa stability and p-replicability are the same up to polynomial factors in the parameters (ILPS22 GKM21).
In this work, we study the notions of list and certificate complexities as a measure the degree of (non) replicability. Our goal is to design learning algorithms with optimal list and certificate complexities while minimizing the sample complexity. The earlier works (BLM20, GKM21 [LPS222 did not focus minimizing these quantities. The works of MBLM20 GKM21 used replicable algorithms as an intermediate step to design differentially private algorithms. The work of (ILPS22) did not consider reducing the certificate complexity in their algorithms and also did not study list-replicability. Earlier works (GKM21 (S22) studied how to convert statistical query learning algorithms into certificate replicable learning algorithms, however, their foeus was not on the certificate complexity. Here, we study the relationship among (nonadaptive and adaptive) statistical query learning algorithms, list replicable algorithms, and certificate replicable algorithms with a focus on list, certificate and sample complexities.
A very recent and independent work of (CMY23) investigated relations between list replicability and the stability parameter v, in the context of distribution PAC learning. They showed that for every concept class H. its list complexity is exactly the inverse of the stability parameter. They also showed that the list complexity of a hypothesis class is at least its VC dimension. For establishing this they exhibited, for any d, a concept class whose list complexity is exactly d. There some similarities between their work and the present work. We establish similar upper and lower bounds on the list complexity but for different learning tasks: d- d-THRESHOLD and d-COIN BIAS ESTIMATION PROBLEM. For d- THRESHOOLD our results are for PAC learning under uniform distribution and do not follow from their distribution-indeeeddee results. Thus our results, though similar in spirit, are incomparable to theirs. Moreover, their work did not focus on efficiency in sample complexity and also did not study certificate complexity which a focus of our paper. We do not study the stability parameter.
The study of notions of repproducibliityyeppiiaabbii in various computational fields is emerging topic. The article (1) discusses the differences between replicability and reproducibility. In (E the authors consider replicability in the context of stochastic bandits. Their notion is similar to the notion studied in (LPS222). In (AJJ+ 22), the authors investigate reproducibility in the context of optimization with inexact oracles (initaliizationgraadinnt oracles). The setup and focus of these works are different from ours.
Finally, would like to point out that there notions of list PAC learning and list-decodable learning in the learning theory literature (see (CP23) and (RY20) for recent progress on these notions). However, these notions are different from the list replicable learning that consider in this paper. List PAC learning and list-decodable learning are generalized models of PAC learning. For example, any learning task that is PAC learnable is trivially list PAC learnable with a list size of 1. However, list replicable learning is an additional requirement that needs to be satisfied by a learner. Thus the notion of list and list-decodable PAC learning are different from the notions of list/certificate replicability.
23


Reviews:
[{"review_id": "p5pymfafCO", "reviewer": "Reviewer_Hncd", "summary": "This work studies the theoretical property of replicability of machine learning algorithms. The paper's authors introduce two notions of list and certificate complexity used to quantify the replicability of such algorithms. They also establish replicable algorithms for the coin bias estimation problem and in the general setting of PAC learning, proving theoretical guarantees on the properties of these algorithms.\n\n---\nPost-rebuttal update: after reading the author response, I am increasing by confidence in the score of 6 by 1 point. I have not worked in the field of working theory, but the results are sensible to me and the rebuttal has addressed some of my questions.", "questions": "* Could you provide some intuition into the certificate complexity, for example, into the meaning of the certificate $r$? The proof of Lemma 3.2 in the appendix contains a constructive description of what $r$ does and how it is used, but the work might be easier to understand if we had an example for any standard machine learning problem in a more practical setting (e.g., binary classification of real-valued vectors) that would use $r$ as an input.\n* The introductory section provides useful insight into the motivation behind studing reproducibility, but (unless I am mistaken) it does not address two important real-world considerations. First, while machine learning algorithms observe samples from a distribution, in a supervised offline setting (which is the most popular one) they are trained on a fixed finite-sized sample from that distribution (usually called the training dataset). If the reproducing party trains on the same open dataset, that factor of randomness does not influence the resulting model. Second, all other hardware-based factors of randomness are usually also fixed by setting the random seed at the beginning of training. Would the analysis of replicability be still useful in such a case?", "limitations": "There is a discussion of limitations in the conclusion section, which was helpful in understanding the scope of the work.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The work studies an important problem of having not only sample-efficient, but also replicable algorithms that would arrive to a narrow set of hypotheses after training on different samples from the data distribution.\n* Although I am not an expert in learning theory, the theoretical analysis appears to be sound and the reasoning steps are explained in sufficient detail\n* The paper covers the related work well, connecting the contributions of the authors to the existing results in a clear way", "weaknesses": "* I feel the work would strongly benefit from an improvement of its presentation. For example, the abstract is several paragraphs long. Furthermore, the introduction contains an example illustratory statement along with its full proof, which makes this section of the paper a bit dense.\n* Some parts of the paper could also be improved by providing more insight into the motivation behind the introduced notions of replicability. It is not fully clear if the certificate complexity has any specific advantages over previous measures of replicability discussed in the CMY23 reference that would make it of interest to the community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the review. We will first address the questions and then briefly address the weakness concerns. \n\nQ1: One can think of the certificate as a \"certificate of replicability.\" The definition captures the intuition that (1) most of the certificates should be good (2) once we fix a good certificate, the rest of the computation is strongly replicable.  In particular, after fixing a good certificate, the output of the algorithm doesn't depend on the samples drawn from the distribution. The proof of Lemma 3.2 indeed proves that a randomly chosen $r$ will be a good certificate. Proof of Theorem 4.6 uses Lemma 3.2 in the concrete setting of d-Coin Bias Estimation.  \n\nQ2: In supervised learning, even though the data set is fixed, a typical algorithm will randomly select a subset of the data set for training, and the rest for validation and testing.  The randomly chosen training data set can be thought of as coming out of a distribution. The proposed framework of the paper applies to this scenario.  If we choose to view the data set and the random seed as fixed and there is no randomness involved, then the learning is a deterministic task. In this case, the notions of replicability introduced in this and related works are trivially achieved. The study of replicability in learning is an emerging research area and in this work, we focus on the PAC-style learning algorithms where the algorithm observes randomly chosen samples from a distribution. \n\nAddressing Weakness: The example given in the introduction shows that strong replicability is not possible even for very simple tasks. This sets the stage and motivation for the rest of the paper. Since Reviewer xjoj also raised this concern, we will seriously consider moving the proof from the introduction to the technical part and give more motivation in the final version."}, {"review_id": "lkleFJawjV", "reviewer": "Reviewer_HcY8", "summary": "The paper investigates replicable learning algorithms by proposing two notions of replicability, i.e. the list replicability and the certificate replicability. For the problem of estimating the biases of $d$ coins, it designs a $(d+1)$-list replicable algorithm and complements the result by showing that the list size is optimal. For PAC learning model, it shows that any hypothesis class that is learnable with $d$ non-adaptive SQs can be learned by a $(d+1)$-list replicable algorithm or a $\\tilde{O}(\\log d)$-certificate replicable algorithm.\n", "questions": "To what extent is the notion of list-replicability related to the notion of list PAC learning or list-decodable learning? Since the PAC learning model is considered in this paper, it would be interesting if these notions could be compared.\n", "limitations": "No concerns.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Designing replicable algorithms is of interest to both the theoretical and applicational community. Empirically, it is important for the models to be reproducible under slight changes in the environment. From the theoretical side, the problem itself is interesting whether provable guarantees can be achieved for algorithmic replicability. The paper generalized the idea of replicability by proposing two notions, allowing the algorithms to be list-replicable or certificate replicable, which characterize the replicability of a broader class of problems from bias estimation of multiple coins to PAC learning thresholds.\n", "weaknesses": "Some parts of the presentation can be improved. For example, as major notions, the definition of list-replicability and certificate-replicability can be placed in Section 1. To now, the ideas seem to be implied from the definition of specific problems instead of standalone definitions, which makes the paper less clear.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the review and pointers to related literature. We will first address the question and then address the weakness concern.\n\nQ: Thank you for pointing us to these notions of list PAC learning and list decodable PAC learning. We will discuss these notions and contrast them with the list/certificate replicability notions, in the final version. List PAC learning and list-decodable learning are generalized models of learning. For example, any learning task that is  PAC learnable is trivially list PAC learnable with a list size of 1. However, list/certificate replicable learning is an additional requirement that needs to be satisfied by a learner. Thus the notion of list and list-decodable PAC learning are different from the notions of list/certificate replicability.\n\nAddressing Weakness: We agree that it is indeed possible to place all definitions in a single section and define the notions of list/certificate replicability as properties of algorithms rather than making problem specific. Two other reviewers suggested the same. Hence we have made an attempt to do so. The generalized definitions can be found in the global rebuttal. \n"}, {"review_id": "7Q2OQvYe2q", "reviewer": "Reviewer_xJoj", "summary": "This paper considers two notions of complexity for stable algorithms: list complexity for list replicable algorithms and certificate complexity for pseudo-globally stable/replicable algorithms. They give matching upper and lower bounds for the list and certificate complexities of the d-coin bias estimation problem. They extend these results to obtain upper bounds on the complexities of adaptive and non-adaptive SQ algorithms and upper and lower bounds on the list complexity of learning d-dimensional thresholds under the uniform distribution. ", "questions": "As already mentioned, I think these complexity definitions need more motivation. They seem interesting, but how does minimizing list and certificate complexity facilitate replicability? How does list replicability compare to pseudo-global stability?", "limitations": "Yes, the authors address broader societal impacts. ", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "This paper has a novel perspective on the study of replicable algorithms, by considering how much randomness is required to achieve replicability, and it continues the study of list bounds for list replicability. The rounding techniques and application of Sperner’s lemma used to prove their results are interesting, and I think the fact that they are able to obtain several results for fundamental learning problems from variations of these techniques speaks to their usefulness. I enjoyed reading the paper. \n", "weaknesses": "Though I enjoyed the paper overall, it was structured in a way that frequently made it difficult to understand or contextualize their results. \n- Formal definitions of the complexity measures studied appear in the context of a particular problem, rather than being properties of general algorithms, which was a bit confusing.\n-  The motivation for these complexity measures is not very clear to me.\n- The explanation of how to simulate a statistical query algorithm making d adaptive queries is not specific enough to be enlightening. Either expanding it or omitting it would make the section more readable.\n- As a reader, I didn’t gain much from the exposition on page 2 showing that perfectly replicability isn’t achievable, and I think it took space away from expanding on why list and certificate complexity are useful notions of non-replicability to minimize. \n\nThe techniques used seem interesting, but seem mostly to have been developed in VWDPRV22. The novel contribution of this paper appears to me to be the adaptation of these results to the problem of certificate and list complexity, and so I think the usefulness of these complexity measures needs much more attention in the paper. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the review. We are glad that you enjoyed reading the paper. We will first address the question and then address the weakness concerns.\n\nQ Part 1: We will include additional motivation in the final version to the extent possible. As noted in the introduction, strong replicability is not achievable in the learning setting even for simple learning tasks. Consequently, a few natural and foundational questions are the following: Can we \"measure\" the degree of (non)-replicability of learning tasks? Are some learning tasks more non-replicable than others? The notions of list complexity and certificate complexity are two different ways to formalize the degree of (non)-replicability and answer these questions.  \n\nFor example, a $1$-list replicable algorithm is strongly replicable (i.e. with a high probability a single canonical answer is given over multiple runs). With a $2$-list replicable algorithm we see at most $2$ distinct answers, and with a $100$-list replicable algorithm we could see up to $100$ distinct answers. While a $1$-list replicable algorithm is the most desirable, when this is not possible, it is natural to desire a $2$-list replicable algorithm as opposed to, say a $100$-list replicable algorithm. For certificate replicability, once the certificate is fixed, the rest of the algorithm is strongly replicable; thus, an algorithm with zero certificate complexity is strongly replicable. A small certificate complexity implies that the learning task is closer to being strongly replicable than an algorithm with a higher certificate complexity.\n\nQ Part 2: The notion of pseudo-global stability is similar to the notion of certificate replicability, and as proved in the paper, a list replicable algorithm can be converted into a certificate replicable algorithm. Thus, a list replicable algorithm can be made pseudo-globally stable with a bound on the amount of randomness. However, this generic conversion is sub-optimal in terms of sample complexity. \n\nAddressing Weaknesses: \n\nW1: We agree that it is indeed possible to place all definitions in a single section and define the notions of list/certificate replicability as properties of algorithms rather than making problem specific. Two other reviewers suggested the same. Hence we have made an attempt to do so. The generalized definitions can be found in the global rebuttal.\n\nW2 & W4: Our purpose in this exposition was to demonstrate that strong replicability is not achievable even in simple settings, and we felt that this was necessary to justify why we study these weaker forms of replicability. This sets the stage and motivation for the rest of the paper. Since Reviewer Hncd also raised this concern, we will seriously consider moving the proof from the introduction to the technical part and give more motivation in the final version.\n\nW3: Thanks for the comment. We think it is an interesting result and we will give more details in the final version. \n"}, {"review_id": "IcZ4SfWl2B", "reviewer": "Reviewer_U7Lz", "summary": "In this work the authors study the problem of replicability in machine learning from a mathematical point of view. They first show that even in the simple problem of estimating the bias of a coin, a strong notion of replicability which asks for an algorithm to output the same answer on independent i.i.d. samples from the true coin as input (and independent internal randomness) is not possible, unless the accuracy guarantees are trivial. Motivated by that, they propose two definitions that aim to capture the degree of non-replicability of the underlying statistical task.\n * The first one is called $L$ list-replicability and, roughly speaking, asks that the algorithm outputs at most $L$ different answers under independent executions, with high probability. Moreover, the answers that belong to this list need to be $\\epsilon$-accurate for the specific application.\n  * The second definition they propose is called $\\ell$ certificate replicability. Under this definition, the algorithm has access to internal random strings of length $\\ell$, and it is required that, for most of the random strings there is a ``canonical'' output $\\mathcal{o}_r$ that is $\\varepsilon$-accurate, i.e., with high probability over the draw of the dataset, when the random string of the algorithm is $r$ its output will be $\\mathcal{o}_r$.\n\nThe authors illustrate the usefulness of these definitions by designing algorithms that satisfy them for various statistical tasks. The bulk of their technical work is to prove Lemma 3.1, Lemma 3.2, and Lemma 3.3, which are later used to establish various results. In particular, Lemma 3.1 is a more fine-grained version of a result from [VWDP+22], Lemma 3.2 is a randomized rounding scheme, that unlike the one proposed in [ILPS22], using a (relatively) small number of random bits, and Lemma 3.3 is a straightforward modification of Sperner's/KKM that has appeared in the literature. \n\nFirst, they consider the problem of estimating the bias of $d$ independent coins from samples. They design a deterministic and efficiently computable algorithm that is $d+1$-list replicable and requires $O\\left(\\frac{d^3}{\\epsilon^2}\\cdot \\log(d/\\delta)\\right)$ samples in total, where $\\epsilon$ is the accuracy parameter and $\\delta$ is the confidence parameter. At this point it is worth mentioning (even though not explicitly stated in the paper) that there exists a (trivial) $2^d$-list replicable algorithm whose sample complexity is $O\\left(\\frac{d}{\\epsilon^2}\\cdot \\log(d/\\delta) \\right)$ -- the authors use this algorithm for a different task (more details on this later). For the same task, they design a $\\log(d/\\delta)$-certificate replicable algorithm with sample complexity $O(\\frac{d^3}{\\varepsilon^2\\delta^2}$ in total. Notice that the sample complexity w.r.t. $\\delta$ is $poly(1/\\delta)$, whereas for the list replicable algorithm it is $poly(\\log(1/\\delta)$. They complement their upper bounds by showing that there is no $k$-list replicable algorithm for this task, for any $k < d+1$, and no $k$-certificate replicable algorithm for any $k < \\log(d)$. This implies that the list complexity parameter is optimal and the certificate complexity parameter is optimal up to a factor of $\\log(1/\\delta)$, but it does not imply that the sample complexity of the algorithms is optimal.\n\nThen, the authors consider the canonical learning task of binary classification in the PAC setting. They first show that any class $H$ that is learnable in the well-known SQ model by non-adaptive queries admits a $d+1$-list replicable algorithm whose sample complexity is $O\\left(\\frac{d^2}{\\varepsilon^2} \\log(d/\\delta)\\right)$. They further show that there is a $\\log(d/\\delta)$-certificate replicable algorithm for this task with sample complexity $O\\left(\\frac{d^2}{\\delta^2\\varepsilon^2} \\log(d/\\delta)\\right)$. In the case of adaptive queries, the only list-replicable algorithm they present is the trivial one with $L=2^d$, but they design a $d\\log(d/\\delta)$-certificate replicable algorithm with sample complexity $O\\left(\\frac{d^3}{\\delta^2\\varepsilon^2} \\log(d/\\delta)\\right).$\n\nFinally, they consider the task of learning $d$-dimensional thresholds on $[0,1]^d$. They observe that if the marginal distribution on $X$ is unknown, there is no list-replicable algorithm for this task. Thus, they restrict the problem by fixing this distribution be uniform. They prove that this restriction helps circumvent the lower bound by showing that there exists a $d+1$-list replicable algorithm for this problem. Moreover, the list replicability parameter cannot be decreased. \n\n\n[VWDP+22]: Jason Vander Woude, Peter Dixon, Aduri Pavan, Jamie Radcliffe, and N. V. Vinodchandran. Geometry of rounding.\n\n[ILPS22]: Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning.", "questions": "1) I don't really understand what is the benefit of studying the coin estimation problem in Section 4 separately from the SQ learning problem in Section 5. In particular, as far as I can tell, all the proofs in Section 4 related to estimating the bias of coins hold verbatim for SQ estimation tasks. In fact, they can be phrased as general reduction: given a potentially non-replicable algorithm A that gives answers that are $\\epsilon$-close to the true one in the $\\ell_\\infty$ norm, using the rounding schemes your propose one can get list\\certificate replicable algorithms with the stated sample complexities/number of oracle calls to A. For instance, this can be used to replicably estimate potentially unbounded quantities that concentrate, such as averages of subgaussian random variables etc. Am I missing something?\n\n2) As you have also pointed out in the manuscript, there is a trivial 2^d-list replicable algorithm for the coin estimation problem that needs O(d) samples (assume that $\\epsilon,\\delta$ is a constant) and your algorithm is $d$-list replicable but requires $O(d^3)$ samples. Are you aware of any $poly(d)$-list replicable algorithm that uses $o(d^3)$ samples?\n\n3) Relatedly, do you believe that the $O(d^3)$ sample complexity is necessary to get the $d+1$-list replicability?\n\n4) The dependence of the sample complexity of certificate replicability on the confidence $\\delta$ is a bit unsatisfactory since it is $poly(1/\\delta)$ and not $poly(log(1/\\delta))$. I believe this is, to some extent, an artifact of the way you have defined certificate replicability. You can consider a two-parameter version of the definition that gives rise to more fine-grained sample complexity bounds. To be more precise, you can define an algorithm to be $(\\ell, \\rho)$-certificate replicable if $(1-\\rho)$-fraction of the $\\ell$-bit random strings $r$ have a canonical output $\\mathcal{o}_r$. As in the non-replicable case, an algorithm is $(\\epsilon,\\delta)$-accurate if with probability $1-\\delta$ it outputs an answer whose \"error\" is at most $\\epsilon$. To define what it means to be $(\\ell, \\rho)$-certificate replicable and $(\\epsilon, \\delta)$-accurate you simply require that the algorithm satisfies both definitions. In your definition, you essentially treat the parameters $\\delta, \\rho$ in the same way. The advantage of the definition I suggest is that it will lead to sample complexities of the certificate replicable algorithms you propose that are of the form $poly(1/\\epsilon, 1/\\rho, \\log(1/\\delta)$. These are also the \"correct\" sample complexities that appear in this line of work (see, e.g., [ILPS22], [KKMV23]). Am I missing something?\n\n5) In Line 211, shouldn't the randomness $r$ in the inner probability be fixed? In other words, shouldn't the inner probability be only wrt the random samples of the coins? (as you do in Def. 5.3)\n\n6) In Theorem 5.9, why do you only consider the uniform distribution? I believe that the result should hold for any fixed distribution, but the way to construct the rounding scheme would depend on the distribution (i.e., it will not in general be the one you are proposing).\n\n7) In the proof of Lemma 3.1, line 446, second equality, did you mean to write $\\bar{B}_{\\epsilon_0/\\epsilon}^\\infty(x/\\epsilon)$? If I am not missing something, you can see that by picking $x=1$ for example, what you have currently written is not true.\n\n\n\n[ILPS22]: Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning.\n\n[KKMV23]: Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishability of learning algorithms.", "limitations": "The limitations are adequately addressed. ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This work is trying to address a very important problem in ML from a theoretical point of view. It is important to have algorithms with provable replicability guarantees and not just rely on empirical replicability of experimental findings. \nRecently, there has been an interest from the TCS/theoretical ML community to design algorithms with mathematical replicability guarantees. The authors do a good job of placing their work in the literature. \n\nI think the most exciting contributions of the paper are the replicability definitions they propose, which are novel and I find them quite natural and interesting. Moreover, even though the main technical challenges to establish Lemma 3.1, and Lemma 3.3 were already solved in prior work, the use of the rounding scheme of Lemma 3.1 based on secluded partitions in the replicability literature is novel and I believe that it can have further applications in this line of work. Similarly, using Sperner's/KKM lemma to establish lower bounds for list-replicable algorithms could be used to derive lower bounds for other replicability definitions that researchers might come up with in future work. The randomized rounding scheme that is proposed in Lemma 3.2 is a clever, though not very hard, tweak of the one in [ILPS22] that reduces the (potentially infinitely many) random bits that the naive application of [ILPS22] requires.\n\nThe paper is in general well-written and the proof sketches in the main body are easy to follow. The same thing is true for the appendix as well. That being said, I think there are some inaccuracies and some nuances that are not addressed appropriately, which I elaborate on in the Weaknesses/Questions section. \n\n[ILPS22]: Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning.", "weaknesses": "The biggest weakness of the paper is that the results are somewhat limited to simple problems. In particular, the results in Section 4 and Section 5.1 can be unified and stated as list/certificate-replicability results for SQ learning (see also my first question to the authors). The next result that the authors prove in the binary classification setting is restricted since it holds for a particular hypothesis class under a particular distribution on the feature space. One immediate extension the authors could consider would be to prove this result for any fixed distribution on $X$ and not just the uniform distribution. Please see below why I believe that this is true. Another obvious direction is to establish sample complexity lower bounds for the various algorithms you have developed.\n\n\nSome inaccuracies/issues in the exposition:\n\n-Line 140: As far as I can tell the notion of list-global stability [GKM21] does not coincide with the notion of list replicability. In particular, a list-globally stable learner outputs a list of hypotheses (not just a single one) and it is required that at least one of the elements of the list will be the canonical output, i.e., it will appear with high probability after every execution. On the other hand, a list replicable algorithm outputs a single element, but whp, this single elements belongs to a canonical list. \n\n-Line 155-156: \"Establishing the optimality of these measures\". As far as I can tell, you didn't establish the optimality of the sample complexity.\n\n-Observation 5.8: Not sure what it means for $k$ to be \"constant\". Even if we allow it to depend on parameters of the class or on $d$ the result is true. \n\n-Proof of Observation 5.8: First of all, I think it is important to state the results of [ALMM19], [BLM20] that prove the claim (at least in the appendix) since many readers might not be familiar with these works. Moreover, to the best of my knowledge, the statement \"any class $H$ has finite Littlestone dimension if and only if for some ``constant'' $k$ there is a $k$-list replicable algorithm for $H$\" does not follow immediately from these two works. The direction that I can see as a direct result is that if $H$ has infinite Littlestone dimension then there does not exist a $k$-list replicable algorithm for $H$. \nIn particular [ALMM19] showed that every class that is approx-DP learnable has finite Littlestone dimension. Subsequently, [BLM20] showed that every Littlestone class has a globally stable learner with appropriate global stability parameters. Assume that H has infinite Littlestone dimension but admits a $k$-list replicable learner. Then, this gives rise to a globally stable learner with stability parameter at most something like $1/k$, which means that the class is approx-DP learnable, hence a contradiction. The converse direction can be obtained by Theorem 2 of [CMY23], however I do not see an immediate way to obtain it from [ALMM19],[BLM20]. Notice that a globally stable learner is not 1-list replicable.\nPlease let me know if I'm missing something.\n\n-Line 368-369. This is not accurate. Be careful with the order of the quantifiers. [ALMM19] did not show that there exists a single \"hard'' distribution $\\mathcal{D}^\\star$ for the class of one-dimensional thresholds. They showed that for any approx-DP learning algorithm $A$, there exists a hard distribution $\\mathcal{D}_A$, i.e., the distribution depends on the algorithm. In fact, it is known that for any fixed $\\mathcal{D}$, any VC class is approx-DP learnable.\n\n-It is a bit confusing to refer to the distribution-dependent learning setting as the PAC learning setting, because most readers would assume that the PAC setting is distribution-free.\n\nTypos and other comments that didn't affect the score/evaluation.\n\n-Line 72 \"multi-pseuodeterminism\" -> multi-pseudodeterminism.\n\n-Line 333, 342, 349, 547, 567, 589 \"reproducibly\" -> replicably.\n\n-Line 100: \"with at least\" -> \"with probability at least\".\n\n-Line 201: \"randomize\" -> randomized.\n\n-Line 201: maybe you can restrict $\\varepsilon$ to be at most one, outside this range it is trivial to satisfy the definition.\n\n-Line 187-188: use singular form for the rounding scheme.\n\n-It might be useful to state the formal definitions of replicability in section 1.1 (see also the next comment).\n\n-Instead of having two separate definitions of an \"accurate\" list replicable and certificate replicable learner based on the statistical task (coins/PAC learning), it might be better to have one definition that captures just what list replicability/certificate replicability means and then specify what \"correctness\" means based on the underlying task, separately -- i.e., have definitions that say what it means for the learner to be list replicable/certificate replicable, have an (application specific) definition on what it means to be accurate and then the accurate list replicable/certificate replicable replicable algorithm is simply the composition of these definitions. \n\n-It might be good to point out the difference between global stability [BLM20] and 1-list replicability. Global stability asks for one canonical output that appears with non-zero probability, whereas 1-list replicability asks for the canonical output to appear whp.\n\n\n-Line 256-263: Maybe you can have it as a Remark/Observation.\n\n-Line 272: You could have an one-line comment that this follows from the data-processing inequality. Also, it looks like the two subscripts of $\\mathcal{D}$ are not aligned. \n\n-Line 406: did you mean if $\\vec{p} \\in X$?\n\n-Line 475: \"are round\" -> are rounded .\n\n-Line 480: \"almost\" -> at most.\n\n-Line 494: you mean $(d-1)$-dimensional face?\n\n-Line 499-500: maybe it's good to define the closure formally (even though the reader can understand what it means).\n\n-Line 698: set notation for $W$ missing.\n\n-Line 704: \"us\" -> is.\n\n-Line 705: \"the\" -> that.\n\n[GKM21]: Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via correlated sampling.\n\n[ALMM19]: Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension.\n\n[BLM20]: Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction.\n\n[CMY23} Zachary Chase, Shay Moran, and Amir Yehudayoff. Replicability and stability in learning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and very insightful comments, questions, and suggestions. We will take care of all typographic edits. We will first address the question and then address the weakness concerns.\n\nQ1: You are correct; a generic result as you suggested could be stated. We felt that the $d$-Coin Bias Estimation problem is a simple and natural problem that we could use to develop and introduce our techniques. Also, while the reduction from this problem to SQ learning gives upper bounds on other learning tasks, it does not give the lower bound which we establish in the paper. In our view the lower bound for the $d$-Coin Bias Estimation Problem (Theorem 4.7) is clean and fundamental.  The lower bound technique developed is generic and the lower bound for the $d$-Threshold builds on these techniques. \n\nQ2 & Q3: These are very interesting questions that we have been investigating. We can say that this is not possible if you use *rounding techniques* in the style of Lemma 3.1. Morally, rounding-based algorithms require $\\Omega(d^3)$ samples up to polylog factors, even for ${\\rm poly}(d)$-list replicability. \n\nQ4: Thank you for pointing this out. It is true that by using the suggested definition, we will obtain sample complexity of ${\\rm poly}(1/\\rho, 1/\\varepsilon,\\log (1/\\delta))$. In fact, this is one of the choices we made while defining certificate complexity in order to reduce the number of parameters involved. \n\nQ5: Yes, $r$ should be fixed in the inner probability. Thank you for pointing this out. We will clarify this.\n\nQ6: We do not see how to extend the result to other distributions. Consider the case when $d = 1$. For this to work, we need the following: Given $\\varepsilon$, divide the interval $[0, 1]$ into $1/\\varepsilon$ intervals of equal probability mass. While such a division exists, we do not know how to compute it efficiently for arbitrarily fixed distributions in a uniform manner. An approach would observe samples from the distributions and try to get an approximate division. However, we do not know how to do this in a replicable manner. In general, the notion of $\\varepsilon$-close threshold with respect to the uniform distribution corresponds to $\\ell_{\\infty}$ norm, and the secluded partitions can be used to do the rounding. When the distribution changes, the corresponding norm changes and it is not clear how to do the rounding.\n\nQ7: You are correct. We will fix this in lines 2 and 3. As you probably noted, this does not affect the correctness of the lemma.\n\nAddress Weaknesses:  We really appreciate the detailed comments and suggestions. We will address them in the final version, especially Observation 5.8 and the discussion of results from ALMM19 and BLM20. Also as you point out, the list global stability, while similar, does not  coincide with list replicability. We will clarify this. In addition, taking your suggestion for unifying definitions,  and also based on two other reviewers suggestions, we have made an attempt to unify the definitions. These new  generalized definitions can be found in the global rebuttal."}]

Author rebuttal:
As three of the reviewers suggested unifying replicability definitions for d-Coin Bias Estimation and PAC learning, we have made an attempt to do so. We present it below. Let us know your thoughts on whether this is better as opposed to what is in the submission. 

A learning problem is a family $\mathcal{D}$ of distributions over a domain $X$ along with a set $H$ (representing hypotheses) along with an error function ${err}: \mathcal{D} \times H \rightarrow [0,\infty)$. The goal is to learn a hypothesis from $H$ based on some $D\in\mathcal{D}$, and we focus on the realizable case. 

A learning algorithm $A$ has the following inputs: (i) $m$ independent samples from a distribution $D\in\mathcal{D}$ and (ii) $\varepsilon\in(0,\infty)$ and (iii) $\delta\in(0,1]$. It may also receive additional inputs.

**List-Replicability**

Let $k \in\mathbb{N}$, $\epsilon\in(0,\infty)$, and $\delta\in[0,1]$.
A learning algorithm $A$ is called $(k, \varepsilon, \delta)$-list replicable if the following holds: There exists $m \in \mathbb{N}$ such that for every $D\in\mathcal{D}$, there exists a list $L\subseteq H$ of size at most $k$ 
such that (i) for all $h \in L$, $err(D, h) \leq \varepsilon$, and (ii)

$$\Pr_{s \sim D^m} [A(s, \varepsilon, \delta) \in L] \geq 1 -\delta. $$
   
For $k\in\mathbb{N}$, we call $A$ $k$-list replicable if for all $\epsilon\in(0,\infty)$ and $\delta\in(0,1]$, $A$ is $(k,\epsilon,\delta)$-list replicable.

**Certificate Replicability**

Let $\ell\in\mathbb{N}$, $\epsilon\in(0,\infty)$, and $\delta\in[0,1]$. A learning algorithm $A$ is called $(\ell,\epsilon,\delta)$-certificate replicable if the following holds: There exists $m\in\mathbb{N}$ such that for every $D\in\mathcal{D}$ there exists $h:\\{ 0,1\\}^\ell\to H$
such that 

$$
    \Pr_{r \in \\{0,1\\}^{\ell}}\Big[
        \Pr_{s \sim D^m}\big[
            A(s, \varepsilon, \delta, r) = h(r) \text{ and } err(D,h(r))\leq\epsilon
        \big] \geq 1-\delta
    \Big] \geq 1- \delta.
$$

**$d$-Coin Bias Estimation Problem**
    For the $d$-Coin Bias Estimation Problem, we have the following. $X=\\{Head,Tail\\}^d$ which is the set of representations of all possibilities of flipping of each of $d$-many coins. $H=[0,1]^d$ which is the set of all $d$-tuples representing biases of a collection of $d$-many coins. $\mathcal{D}$ is the set of all $d$-fold products of Bernoulli distributions over the symbols $\\{Head,Tail\\}$, so each distribution $D\in\mathcal{D}$ can be represented by a vector $v_{D} = \langle b_1, \dots, b_d\rangle \in [0,1]^d$ which is the vector of probability parameters of the $d$ Bernoulli distributions. Lastly, the error function is defined as $err(D,h)=\Vert{v_D-h}\Vert_\infty$.  

**PAC Learning Model**
    For the PAC learning model we have a domain $X'$, a hypothesis class $H$ which is some collection of functions $X'\to\\{0,1\\}$. 
    For any distribution $D$ over $X'$ and any  $f \in H$, let $D_f$ denote the distribution over $X'\times\\{0,1\\}$ obtained by sampling $x\sim D$ and outputting $\langle x, f(x)\rangle$. We define the following learning problem in our context: $X=X'\times\\{0,1\\}$, $H=H$, $\mathcal{D}=\\{D_f:f\in H\text{ and }D\text{ a distribution over }X'\\}$, and $err(D_f, h)=\Pr_{x \sim \mathcal{D}'} [f(x) \neq h(x)]$.



Meta-review: This paper studies notions of replicability in learning and relies on interesting links with topology to study them. The reviewers agreed that this paper should be accepted. We decided to accept it as a spotlight.
Decision: Accept (spotlight)