List and Certificate Complexities in Replicable Learning

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. * 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. * 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$. The 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. First, 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. Then, 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).$ Finally, 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. [VWDP+22]: Jason Vander Woude, Peter Dixon, Aduri Pavan, Jamie Radcliffe, and N. V. Vinodchandran. Geometry of rounding. [ILPS22]: Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning.

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. Recently, 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. I 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. The 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. [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. Some inaccuracies/issues in the exposition: -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. -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. -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. -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$. In 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. Please let me know if I'm missing something. -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. -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. Typos and other comments that didn't affect the score/evaluation. -Line 72 "multi-pseuodeterminism" -> multi-pseudodeterminism. -Line 333, 342, 349, 547, 567, 589 "reproducibly" -> replicably. -Line 100: "with at least" -> "with probability at least". -Line 201: "randomize" -> randomized. -Line 201: maybe you can restrict $\varepsilon$ to be at most one, outside this range it is trivial to satisfy the definition. -Line 187-188: use singular form for the rounding scheme. -It might be useful to state the formal definitions of replicability in section 1.1 (see also the next comment). -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. -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. -Line 256-263: Maybe you can have it as a Remark/Observation. -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. -Line 406: did you mean if $\vec{p} \in X$? -Line 475: "are round" -> are rounded . -Line 480: "almost" -> at most. -Line 494: you mean $(d-1)$-dimensional face? -Line 499-500: maybe it's good to define the closure formally (even though the reader can understand what it means). -Line 698: set notation for $W$ missing. -Line 704: "us" -> is. -Line 705: "the" -> that. [GKM21]: Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via correlated sampling. [ALMM19]: Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite littlestone dimension. [BLM20]: Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. [CMY23} Zachary Chase, Shay Moran, and Amir Yehudayoff. Replicability and stability 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? 2) 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? 3) Relatedly, do you believe that the $O(d^3)$ sample complexity is necessary to get the $d+1$-list replicability? 4) 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? 5) 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) 6) 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). 7) 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. [ILPS22]: Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell. Reproducibility in learning. [KKMV23]: Alkis Kalavasis, Amin Karbasi, Shay Moran, and Grigoris Velegkas. Statistical indistinguishability of learning algorithms.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The limitations are adequately addressed.

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.

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.

Weaknesses

Though I enjoyed the paper overall, it was structured in a way that frequently made it difficult to understand or contextualize their results. - 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. - The motivation for these complexity measures is not very clear to me. - 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. - 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. The 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.

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?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

4 excellent

Presentation

2 fair

Contribution

3 good

Limitations

Yes, the authors address broader societal impacts.

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.

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.

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.

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.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

No concerns.

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. --- Post-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.

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. * 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 * 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. * 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.

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. * 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?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

There is a discussion of limitations in the conclusion section, which was helpful in understanding the scope of the work.

Thank you for your response!

Thank you for the clarifications! They have addressed my questions (although I would prefer an example of a certificate in a more standard machine learning setting, as I mentioned in the initial review); to reflect that, I have increased my confidence in the score by 1 point. I do not feel I am qualified enough in this research area, therefore I can't champion for its acceptance with a higher score than I have currently given

Official Comments by Reviewer HcY8

Thank you very much for your response. I agree it will be helpful to include the comparison in the revision.