The Role of Randomness in Stability

We thank the reviewer for their careful reading of our work, comments, and questions. Below we clarify a few possible misunderstandings about our definitions, explain our writing choices, and discuss several minor modifications we will make to address the reviewers concerns:

Q1: Missing Definitions We respectfully disagree that there are substantial missing definitions in the paper (outside of Littlestone dimension which we chose to exclude for reasons explained below, but will include in the next version).

The term “shared randomness” refers informally to the random string $r$ in the definition of replicability — it is not a standalone definition. Replicability promises that over independent samples $S$ and $S’$ and the same random string r:

$Pr_{r,S,S’}[A(S;r)=A(S’;r)] \geq 1-\rho$

$r$ is usually called the “shared randomness” since it is used in both runs of A. This is the standard way to express this notion in the literature — it is not usually defined on its own. There is, however, a confusing typo after this equation regarding the domain of $r$ for which we sincerely apologize. The sentence “the smallest $\ell$ s.t. there exists a better than $\frac{1}{2}$-replicable algorithm solving $\mathcal{M}$” should say “solving $\mathcal{M}$ using $\ell$ random bits”. We will fix this and clarify the domain in the text.

Regarding Littlestone: the connection between Littlestone dimension and stability is very involved and largely orthogonal to our work. We do not use the definition in any of our proofs, so excluding it should not make any of our results harder to check. We use as a blackbox that any finite Littlestone class has a globally stable realizable learner (see Thm E.2). Our contribution thus has very little to do with Littlestone dimension, and we thought including the definition would only confuse readers as its connection to stability is fairly mysterious without deep knowledge of prior work.

This said, we absolutely see the reviewer’s counterpoint that stating the definition and (perhaps more importantly) giving concrete examples would help the unfamiliar reader understand what types of classes Thm 2.4 applies to. We will include these in the text (see Q2 below) as well as add references to prior work discussing the above in more detail.

Q2: Concrete Examples There are many nice examples of classes with finite Littlestone dimension to which Thm 2.4 applies. Two classical examples are affine subspaces in $\mathbb{R}^n$ (or more generally algebraic varieties), and half-spaces with margin (semialgebraic varieties with margin). Thm 2.4 gives the first randomness-efficient stable learners for both of these families. We will add discussion of this in the text.

Q3: Thm 2.4, Dominating Term. This depends on how good accuracy you want, but if one only wants (say) 99% accuracy over the data, the first term will always dominate (e.g. this term would be polynomial in the dimension of the affine subspace).

Q4: Continuous Output Spaces we do not make any assumptions about the output domain of $\mathcal{A}$. However, it is true that if the output distribution of $\mathcal{A}(\cdot)$ is continuous, then $\mathcal{A}$ is not globally stable for any $\eta>0$. The definitions we consider measure the performance of the best algorithm over the domain/output, so this is not an issue for working over uncountable and non-discrete domains.

Q5: Relation to [BE02] Replicability and Differential Privacy are only loosely related to the classic stability notions of [BE02], which are generally much weaker (e.g. these notions can be satisfied for any VC class, whereas DP and replicability cannot). It is true there are some connections: e.g. replicability implies generalization by a similar Hoeffding-style argument, and uniform stability [BE02] is related to a substantial relaxation of DP known as private prediction. To the best of our knowledge, however, there is no real formal comparison between [BE02] and the models we study, though the work is certainly worth mentioning as a seminal investigation into stability in learning.

Other Writing Comments: Our citation style in the abstract is a conscious choice ensuring all authors of the major relevant papers are listed (the ICML citation format does not seem to allow this directly). This is because theory papers have alphabetical author order and all authors should be credited equally. We also note it is relatively common for theory papers to have a “discussion/open-problem” section as we do rather than a traditional conclusion and respectfully disagree this is an indicator of poor writing.

This said, we do agree the abstract is on the long side for the ICML format and repetitive with the intro, so we will shorten it as the reviewer suggests and ensure the early definitions are as clear as possible.

We thank the reviewer for their careful reading of our work and helpful comments. We will make the suggested minor fixes.

Regarding the end of the proof of Thm B.2:

The $L$ in line 771 is a typo and should be $L_D$, our apologies. The point here is to bound the measure of the set of samples $S$ on which $A_{\text{List}}$'s majority output is not in $L_D$; in particular, we want to show this bad set has measure at most $\frac{2\gamma}{\eta}$.

To see this, we observe that for any fixed sample S whose majority output is not in $L_D$, it must be the case that $A_{\text{List}}(S;\cdot)$, over the randomness of $r$, outputs a hypothesis outside of $L_D$ with probability at least $\eta/2$. But then if there is a $\frac{2\gamma}{\eta}$ measure of such samples S, the overall probability that $A_{\text{List}}$ outputs something outside of $L_D$ (now over the randomness of both S and r) is more than $\gamma$. This contradicts $A_{\text{List}}$’s list-replicability (the guarantee on Line 752) and completes the proof.

We thank the reviewer for their careful reading of our work and helpful comments (we will fix the minor issues noted).

The trade-off between sample and randomness efficiency is a very interesting question, and is not well understood even for the most basic examples (see e.g. “Geometry of Rounding: Near Optimal Bounds and a New Neighborhood Sperner's Lemma” and “The Randomness Complexity of Differential Privacy”). Our transformations have an overhead scaling polynomially in the stability parameter, which can be efficient for low-dimensional problems but is indeed costly in settings like PAC learning. In the PAC case, this can be circumvented when one does not care about randomness by looking at certain variants of global stability, and it would be interesting to understand if there is an inherent trade-off here. However, given the substantial difficulty in resolving this problem even for, say, estimating the bias of d coins, we feel this is reasonably outside the scope of our work.

We thank the reviewer for their careful reading and questions and will make all suggested fixes

We hope the below clarifications (and positive impressions of the area expert reviewers) raises the reviewer’s confidence in our work, and respectfully ask they consider using the confidence score rather than a lower main score to reflect any remaining lack of confidence due to field familiarity.

Q1: “The idea that randomness is required for stability is not self-evident. I don't understand how an interpolation argument would apply.”

A1: Good catch. The footnote only formally makes sense for DP (where “similar” means trading out one example in your discrete data-set, so one can always interpolate by trading out points one by one). In replicability, the argument is similar but one interpolates in parameter/distribution-space, not over samples. We will clarify this in the text.

For example, consider estimating the bias of a coin. The data is discrete (coin flips), but the underlying set of distributions (biases $p \in [0,1]$) is continuous. Our interpolation is over p. A deterministic replicable algorithm has a single canonical output w.h.p for every $p \in [0,1]$, but cannot distinguish between close p and p’. Since we can interpolate between any $p,q \in [0,1]$, the algorithm must have the same canonical solution everywhere so is essentially constant.

Q2: “Thm 2.2 gives a result in terms of failure probability $\beta$ vs $\beta’$… the blowup in lack of confidence doesn't seem so mild to me”

A2: This type of blowup is considered mild in the literature because almost all statistical problems have complexity scaling in $\log(1/\beta)$ due to Chernoff. This means one does not really lose significant generality assuming the initial algorithm has small $\beta$. More generally, we can usually amplify a constant success algorithm to $1-\beta$ success just by repeating it $\log(1/\beta)$ on independent samples and taking the best output. We will clarify this in the text.

It is also worth remembering $C_{\text{glob}}$ is log scale, so, combined with the above, the blowup we incur is only, e.g., $loglog(1/\eta)$ for $\eta$-stability, which is mild even when $\eta$ is exponential (as in PAC Learning).

Q3: “Can you better motivate the particular definition of stability for people who are not familiar with this area?”

A3: Absolutely. This critical question has been discussed extensively in prior work (e.g. in Impagliazzo et al.). We’ll summarize here and add discussion in the paper as well as on weaker stability notions. We’ll focus on replicability, since presumably DP (widely adopted in industry and hugely impactful in theory) does not need more motivation.

Replicability comes with a substantial list of advantages due to requiring truly equal outputs. Here is a representative sample:

1. Replicability is closely related to other core notions of stability in computer science (DP, adaptive data analysis, and more, see e.g. “Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization” or “The Bayesian Stability Zoo”). Several open problems in DP (sample-efficient user-level DP, amplification of DP) were resolved through studying replicability.

2. Replicability is testable. It is not always easy to test whether an algorithm is stable (e.g. testing DP is known to be computationally hard). By requiring equivalence, replicability is trivially verifiable.

3. Replicability is preserved under arbitrary post-processing. One can apply any desired algorithm to the output of a replicable procedure, and the result will always remain replicable. This is an extremely useful property in algorithm design.

4. Replicability is easily amplified. Given a constantly replicable algorithm, there is a simple and computationally efficient procedure to amplify it to arbitrarily high replication probability.

5. Replicability is model independent. Different statistical tasks naturally have different notions of weak stability and closeness, or, in the case of testing problems with binary outputs, may have no natural notion of weak stability (see “Replicability in High Dimensional Statistics” or “Replicable Uniformity Testing” for a discussion of replicability in these settings). Replicability gives a unified definition for studying stability for all statistical tasks.

It is also critical to understand when replicability is possible, and its overhead compared to weaker notions of stability. This has been the topic of a substantial number of works, and efficient replicable algorithms are known for many tasks (statistical queries, hypothesis testing, mean estimation, RL, learning large margin halfspaces…). This is not the main focus of our work, but we feel combined with the above more than justifies the study of replicable algorithms.

Q4: Could you shorten the abstract?

A4: We’ll shorten the abstract in the next version to be less repetitive with the intro.