# Statistical Indistinguishability of Learning Algorithms

Alkis Kalavasis National Technical University of Athens
<EMAIL_ADDRESS>Amin Karbasi Yale University, Google Research
<EMAIL_ADDRESS>Shay Moran Technion, Google Research
<EMAIL_ADDRESS>Grigoris Velegkas Yale University
<EMAIL_ADDRESS>
###### Abstract

When two different parties use the same learning rule on their own data, how
can we test whether the distributions of the two outcomes are similar? In this
paper, we study the similarity of outcomes of learning rules through the lens
of the Total Variation (TV) distance of distributions. We say that a learning
rule is TV indistinguishable if the expected TV distance between the posterior
distributions of its outputs, executed on two training data sets drawn
independently from the same distribution, is small. We first investigate the
learnability of hypothesis classes using TV indistinguishable learners. Our
main results are information-theoretic equivalences between TV
indistinguishability and existing algorithmic stability notions such as
replicability and approximate differential privacy. Then, we provide
statistical amplification and boosting algorithms for TV indistinguishable
learners.

##  1 Introduction

Lack of replicability in experiments has been a major issue, usually referred
to as the _reproducibility crisis_ , in many scientific areas such as biology
and chemistry. Indeed, the results of a survey that appeared in Nature [Bak16]
are very worrisome: more than $70\%$ of the researchers that participated in
it could not replicate other researchers’ experimental findings while over
half of them were not able to even replicate their own conclusions. In the
past few years the number of scientific publications in the Machine Learning
(ML) community has increased exponentially. Significant concerns and questions
regarding replicability have also recently been raised in the area of ML. This
can be witnessed by the establishment of various reproducibility challenges in
major ML conferences such as the ICLR $2019$ Reproducibility Challenge
[PSF+19] and the NeurIPS $2019$ Reproducibility Program [PVLS+21].

Reproducibility of outcomes in scientific research is a necessary condition to
ensure that the conclusions of the studies reflect inherent properties of the
underlying population and are not an artifact of the methods that scientists
used or the random sample of the population that the study was conducted on.
In its simplest form, it requires that if two different groups of researchers
carry out an experiment using the same methodologies but _different_ samples
of the _same_ population, it better be the case that the two outcomes of their
studies are _statistically indistinguishable_. In this paper, we investigate
this notion in the context of ML (cf. Definition 1), and characterize for
which learning problems statistically indistinguishable learning algorithms
exist. Furthermore, we show how statistical indistinguishability, as a
property of learning algorithms, is naturally related to various notions of
algorithmic stability such as replicability of experiments, and differential
privacy.

While we mainly focus on the fundamental ML task of binary classification to
make the presentation easier to follow, many of our results extend to other
statistical tasks (cf. LABEL:apx:general_definitionind). More formally, the
objects of interest are _randomized_ learning rules
$A:(\mathcal{X}\times\\{0,1\\})^{n}\to\\{0,1\\}^{\mathcal{X}}$. These learning
rules take as input a sequence $S$ of $n$ pairs from
$\mathcal{X}\times\\{0,1\\}$, i.e., points from a domain $\mathcal{X}$ along
with their labels, and map them to a binary classifier in a randomized manner.
We assume that this sequence $S$ is generated i.i.d. from a distribution
$\mathcal{D}$ on $\mathcal{X}\times\\{0,1\\}$. We denote by
$\\{0,1\\}^{\mathcal{X}}$ the space of binary classifiers and by $A(S)$ the
random variable that corresponds to the output of $A$ on input $S$111We
identify with $A(S)$ the posterior distribution of $A$ on input $S$ when there
is no confusion.. We also adopt a more algorithmic viewpoint for $A$ where we
denote it as a _deterministic_ mapping
$(\mathcal{X}\times\\{0,1\\})^{n}\times\mathcal{R}\to\\{0,1\\}^{\mathcal{X}}$,
which takes as input a training set $S$ of size $n$ made of instance-label
pairs and a random string $r\sim\mathcal{R}$ (we use $\mathcal{R}$ for both
the probability space and the distribution) corresponding to the algorithm’s
_internal randomness_ , and outputs a hypothesis
$A(S,r)\in\\{0,1\\}^{\mathcal{X}}.$ Thus, $A(S)$ corresponds to a random
variable while $A(S,r)$ is a deterministic object. To make the distinction
clear, we refer to $A(S)$ as (the image of) a _learning rule_ and to $A(S,r)$
as (the image of) a _learning algorithm_.

##### Indistinguishability.

We measure how much two distributions over hypotheses differ using some notion
of statistical dissimilarity $d$, which can belong to a quite general class;
we could let it be either an Integral Probability Metric (IPM) (e.g., TV or
Wasserstein distance, see Definition 13) or an $f$-divergence (e.g., KL or
Rényi divergence). For further details, see [SFG+09]. We are now ready to
introduce the following general definition of _indistinguishability of
learning rules_.

######  Definition 1 (Indistinguishability).

Let $d$ be a statistical dissimilarity measure. A learning rule $A$ is
$n$-sample $\rho$-indistinguishable with respect to $d$ if for any
distribution $\mathcal{D}$ over inputs and two independent sets
$S,S^{\prime}\sim\mathcal{D}^{n}$ it holds that

$\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}\left[d\left(A(S),A(S^{\prime})\right)\right]\leq\rho\,.$

In words, Definition 1 states that the expected dissimilarity of the outputs
of the learning rule when executed on two training sets that are drawn
independently from $\mathcal{D}$ is small. We view Definition 1 as a general
information-theoretic way to study indistinguishability as a property of
learning rules. In particular, it captures the property that the distribution
of outcomes of a learning rule being _indistinguishable_ under the resampling
of its inputs. Definition 1 provides the flexibility to define the
dissimilarity measure according to the needs of the application domain. For
instance, it captures as a special case the global stability property [BLM20]
(see LABEL:apx:general_definitionind).

##### Replicability.

Since the issue of replicability is omnipresent in scientific disciplines it
is important to design a formal framework through which we can argue about the
replicability of experiments. Recently, various works proposed algorithmic
definitions of replicability in the context of learning from samples [ILPS22,
BGH+23], optimization [AJJ+22], bandits [EKK+22] and clustering [EKM+23], and
designed algorithms that are provably replicable under these definitions. A
notion that is closely related to Definition 1 was introduced by [ILPS22]:
reproducibility or replicability222This property was originally defined as
“reproducibility” in [ILPS22], but later it was pointed out that the correct
term for this definition is “replicability” (see also [BGH+23]). We use the
term replicability throughout our work. of learning algorithms is defined as
follows:

######  Definition 2 (Replicability [ILPS22]).

Let $\mathcal{R}$ be a distribution over random strings. A learning algorithm
$A$ is $n$-sample $\rho$-replicable if for any distribution $\mathcal{D}$ over
inputs and two independent sets $S,S^{\prime}\sim\mathcal{D}^{n}$ it holds
that

$\mathop{\bf
Pr\/}_{S,S^{\prime}\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A(S,r)\neq
A(S^{\prime},r)]\leq\rho\,.$

The existence of a shared random seed $r$ in the definition of replicability
is one of the main distinctions between Definition 1 and 2. This shared random
string can be seen as a way to achieve a _coupling_ (see Definition 12)
between two executions of the algorithm $A$. An interesting aspect of this
definition is that replicability is verifiable; replicability under Definition
2 can be tested using polynomially many samples, random seeds $r$ and queries
to $A$. We remark that the work of [GKM21] introduced the closely related
notion of pseudo-global stability (see Definition 6); the definitions of
replicability and pseudo-global stability are equivalent up to polynomial
factors in the parameters.

##### Differential Privacy.

The notions of algorithmic indistinguishability and replicability that we have
discussed so far have close connections with the classical definition of
approximate differential privacy [DR14]. For $a,b,\varepsilon,\delta\in[0,1]$,
let $a\approx_{\varepsilon,\delta}b$ denote the statement $a\leq
e^{\varepsilon}b+\delta$ and $b\leq e^{\varepsilon}a+\delta$. We say that two
probability distributions $P,Q$ are $(\varepsilon,\delta)$-indistinguishable
if $P(E)\approx_{\varepsilon,\delta}Q(E)$ for any measurable event $E$.

######  Definition 3 (Approximate Differential Privacy [DKM+06]).

A learning rule $A$ is an $n$-sample $(\varepsilon,\delta)$-differentially
private if for any pair of samples
$S,S^{\prime}\in(\mathcal{X}\times\\{0,1\\})^{n}$ that disagree on a single
example, the induced posterior distributions $A(S)$ and $A(S^{\prime})$ are
$(\varepsilon,\delta)$-indistinguishable.

We remind the reader that, in the context of PAC learning, any hypothesis
class $\mathcal{H}$ can be PAC-learned by an approximate differentially-
private algorithm if and only if it has a finite Littlestone dimension
$\mathrm{Ldim}(\mathcal{H})$ (see Definition 14), i.e., there is a qualitative
equivalence between online learnability and private PAC learnability [ALMM19,
BLM20, GGKM21, ABL+22].

##### Broader Perspective.

Our work lies in the fundamental research direction of responsible ML. Basic
concepts in this area, such as DP, replicability, and different forms of
fairness, are formalized using various forms of stability. Therefore, it is
natural and important to formally study the interrelations between different
types of algorithmic stability. Our main purpose is to study statistical
indistinguishability and replicability as properties of algorithms and, under
the perspective of stability, investigate rigorous connections with DP. We
view both replicability and DP as two fundamental blocks in the area of
responsible and reliable ML. Hence, we believe that establishing formal
connections between a priori not clearly related notions of “reliability” is a
way to increase our understanding towards the design of responsible ML
systems.

###  1.1 TV Indistinguishable Learning Rules

As we discussed, our Definition 1 captures the property of a learning rule
having _indistinguishable_ outcomes under the resampling of its inputs from
the same distribution. In what follows, we instantiate Definition 1 with $d$
being the total variation (TV) distance, probably the most well-studied notion
of statistical distance in theoretical computer science. Total variation
distance between two distributions $P$ and $Q$ over the probability space
$(\Omega,\Sigma_{\Omega})$ can be expressed as

$\displaystyle\begin{split}d_{\mathrm{TV}}(P,Q)&=\sup_{A\in\Sigma_{\Omega}}P(A)-Q(A)\\\
&=\inf_{(X,Y)\sim\Pi(P,Q)}\mathop{\bf Pr\/}[X\neq Y]\,,\end{split}$ (1)

where the infimum is over all couplings between $P$ and $Q$ so that the
associated marginals are $P$ and $Q$ respectively. A _coupling_ between the
distributions $P$ and $Q$ is a set of variables $(X,Y)$ on some common
probability space with the given marginals, i.e., $X\sim P$ and $Y\sim Q$. We
think of a coupling as a construction of random variables $X,Y$ with
prescribed laws.

Setting $d=d_{\mathrm{TV}}$ in Definition 1, we get the following natural
definition. For simplicity, we use the term TV indistinguishability to capture
indistinguishability with respect to the TV distance.

######  Definition 4 (Total Variation Indistinguishability).

A learning rule $A$ is $n$-sample $\rho$-$\mathrm{TV}$ indistinguishable if
for any distribution over inputs $\mathcal{D}$ and two independent sets
$S,S^{\prime}\sim\mathcal{D}^{n}$ it holds that

$\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),A(S^{\prime}))]\leq\rho\,.$

For some equivalent definitions, we refer to Section A.3. Moreover, for some
extensive discussion about the motivation of this definition, see Section A.5.
We emphasize that the notion of TV distance has very strong connections with
statistical indistinguishability of distributions. If two distributions $P$
and $Q$ are close in TV distance, then, intuitively, no statistical test can
distinguish whether an observation was drawn from $P$ or $Q$. In particular,
if $d_{\mathrm{TV}}(P,Q)=\rho$, then $\rho/2$ is the maximum advantage an
analyst can achieve in determining whether a random sample $X$ came from $P$
or from $Q$ (where $P$ or $Q$ is used with probability 1/2 each). In what
follows, we focus on this particular notion of statistical dissimilarity.

As a warmup, we start by proving a generalization result for TV
indistinguishable learners. Recall that if we _fix_ some binary classifier we
can show, using standard concentration bounds, that its performance on a
sample is close to its performance on the underlying population. However, when
we train an ML algorithm using a dataset $S$ to output a classifier $h$ we
cannot just use the fact that it has small loss on $S$ to claim that its loss
on the population is small because $h$ depends on $S$. The following result
shows that we can get such generalization bounds if $A$ is a $\rho$-TV
indistinguishable algorithm. We remark that a similar result regarding
replicable algorithms appears in [ILPS22]. The formal proof, stated in a
slightly more general way, is in Appendix F.

######  Proposition 1 (TV Indistinguishability Implies Generalization).

Let $\delta,\rho\in(0,1)^{2}$. Let $\mathcal{D}$ be a distribution over inputs
and $S=\\{(x_{i},y_{i})\\}_{i\in[n]}$ be a sample of size $n$ drawn i.i.d.
from $\mathcal{D}$. Let $h:\mathcal{X}\to\\{0,1\\}$ be the output of an
$n$-sample $\rho$-$\mathrm{TV}$ indistinguishable learning rule $A$ with input
$S$. Then, with probability at least $1-\delta-4\sqrt{\rho}$ over $S$, it
holds that,

$\left|\mathop{\bf E\/}_{h\sim A(S)}\left[L(h)\right]-\mathop{\bf E\/}_{h\sim
A(S)}\left[\widehat{L}(h)\right]\right|\leq\sqrt{\frac{\log(2/\delta)}{2n}}+\sqrt{\rho}\,,$

where $L(h)\triangleq\mathop{\bf Pr\/}_{(x,y)\sim\mathcal{D}}[h(x)\neq y]$ and
$\widehat{L}(h)\triangleq\frac{1}{n}\sum_{(x,y)\in S}1\\{h(x)\neq y\\}.$

###  1.2 Summary Of Contributions

In this work, we investigate the connections between TV indistinguishability,
replicability and differential privacy.

  * •

In Section 2, we show that TV indistinguishability and replicability are
equivalent. This equivalence holds for countable domains333We remark that the
direction replicability implies TV indistinguishability holds for general
domains. and extends to general statistical tasks (cf. Section C.2).

We remark that our transformations between replicable and TV indistinguishable
learners do not change the (possibly randomized) input $\to$ output map which
is induced by the learner; i.e., given a TV indistinguhishable learner
$\mathcal{A}$, we transform it to a replicable learner $\mathcal{A}^{\prime}$
such that $\mathcal{A}(S)$ and $\mathcal{A}^{\prime}(S)$ are the same
distributions over output hypotheses for every input sample $S$.

At this point we would like to highlight a subtle difference between
replicability and other well studied notions of stability that arise in
learning theory such as differential privacy, TV indistinguishability, one-way
perfect generalization, and others. The latter notions of stability depend
only on the input $\to$ output map which is induced by the learner. In
contrast, the definition of replicability has to do with the way the algorithm
is implemented (in particular the way randomness is used). In other words, the
definition of replicability enables having two learning rules
$\mathcal{A}^{\prime},\mathcal{A}^{\prime\prime}$ that compute exactly the
same input $\to$ output map, but such that $\mathcal{A}^{\prime}$ is
replicable and $\mathcal{A}^{\prime\prime}$ is not. Thus, our equivalence
suggests an interpretation of TV indistinguishability as an
abstraction/extension of replicability that only depends on the input-output
mechanism.

  * •

In Section 3, we show that TV indistinguishability and
$(\varepsilon,\delta)$-DP are statistically equivalent. This equivalence holds
for countable444We remark that the direction $(\varepsilon,\delta)$-DP implies
TV indistinguishability holds for general domains. domains in the context of
PAC learning. As an intermediate result, we also show that replicability and
$(\varepsilon,\delta)$-DP are statistically equivalent in the context of PAC
learning, and this holds for general domains.

  * •

In Section 4, we provide statistical amplification and boosting algorithms for
TV indistinguishable learners for countable domains. En route, we improve the
sample complexity of some routines provided in [ILPS22].

###  1.3 Related Work

Our work falls in the research agenda of replicable algorithm design, which
was initiated by [ILPS22]. In particular, [ILPS22] introduced the notion of
replicable learning algorithms, established that any statistical query
algorithm can be made replicable, and designed replicable algorithms for
various applications such as halfspace learning. Next, [AJJ+22] studied
reproducibility in optimization and [EKK+22] provided replicable bandit
algorithms.

The most closely related prior work to ours is the recent paper by [BGH+23].
In particular, as we discuss below in greater detail, an alternative proof of
the equivalence between TV indistinguishability, replicability, and
differential privacy follows from [BGH+23]. In contrast with our equivalence,
the transformations by [BGH+23] are restricted to finite classes. On the other
hand, [BGH+23] give a constructive proof whereas our proof is purely
information-theoretic.

In more detail, [BGH+23] establish a variety of equivalences between different
notions of stability such as differential privacy, replicability, and one-way
perfect generalization, and the latter contains TV indistinguishability as a
special case:

######  Definition 5 ((One-Way) Perfect Generalization [CLN+16, BF16]).

A learning rule $A:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ is
$(\beta,\varepsilon,\delta)$-perfectly generalizing if, for every distribution
$\mathcal{D}$ over $\mathcal{X}$, there exists a distribution
$\mathcal{P}_{\mathcal{D}}$ such that, with probability at least $1-\beta$
over $S$ consisting of $n$ i.i.d. samples from $\mathcal{D}$, and every set of
outcomes $\mathcal{O}\subseteq\mathcal{Y}$

$e^{-\varepsilon}\left(\mathop{\bf
Pr\/}_{\mathcal{P}_{\mathcal{D}}}[\mathcal{O}]-\delta\right)\leq\mathop{\bf
Pr\/}[A(S)\in\mathcal{O}]\leq e^{\varepsilon}\mathop{\bf
Pr\/}_{\mathcal{P}_{\mathcal{D}}}[\mathcal{O}]+\delta\,.$

Moreover, $A$ is $(\beta,\varepsilon,\delta)$-one-way perfectly generalizing
if $\mathop{\bf Pr\/}[A(S)\in\mathcal{O}]\leq e^{\varepsilon}\mathop{\bf
Pr\/}_{\mathcal{P}_{\mathcal{D}}}[\mathcal{O}]+\delta$.

Note indeed that plugging $\varepsilon=0$ to the definition of perfect
generalization specializes the above definition to an equivalent variant of TV
indistinguishability (see also Definition 20). [BGH+23] derives an equivalence
between replicability and one-way perfect generalization with $\varepsilon>0$.
However, in a personal communication they pointed out to us that their
argument also applies to the case $\varepsilon=0$, and hence to TV
indistinguishability. In more detail, an intermediate step of their proof
shows that any $(\beta,\varepsilon,\delta)$-perfectly generalizing algorithm
$A$ is also $(\beta,0,2\varepsilon+\delta)$-perfectly generalizing, which is
qualitatively equivalent with our main definition (see Definition 4). As noted
earlier our proof applies more generally to infinite countable domains but is
non-constructive.

##### Differential Privacy.

Differential privacy [Dwo08, DRV10, Vad17, DR14] is quite closely related to
replicability. The first connection between replicability and DP in the
context of PAC learning was, implicitly, established by [GKM21] (for finite
domains $\mathcal{X}$), via the technique of correlated sampling (see Section
A.4) and the notion of pseudo-global stability (which is equivalent to
replicability as noticed by [ILPS22]):

######  Definition 6 (Pseudo-Global Stability [GKM21]).

Let $\mathcal{R}$ be a distribution over random strings. A learning algorithm
$A$ is said to be $n$-sample $(\eta,\nu)$-pseudo-globally stable if for any
distribution $\mathcal{D}$ there exists a hypothesis $h_{r}$ for every
$r\in\mathrm{supp}(\mathcal{R})$ (depending on $\mathcal{D}$) such that

$\mathop{\bf Pr\/}_{r\sim\mathcal{R}}\left[\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n}}[A(S,r)=h_{r}]\geq\eta\right]\geq\nu\,.$

The high-level connection between these notions appears to boil down to the
notion of stability [BE02, PRMN04, DFH+15, ALMT17, BNS+16a, LM20] (see
[ABL+22] for further details between stability, online learnability and
differential privacy). In particular, [GGKM21] showed that a class of finite
Littlestone dimension admits a list-globally stable learner (see Theorem 18 in
[GKM21]). The work of [GKM21] (among other things) showed (i) how to perform a
reduction from list-global stability to pseudo-global stability via correlated
sampling in finite domains (see Theorem 20 in [GKM21]) and (ii) how to perform
a reduction from pseudo-global stability to approximate DP via DP selection
(see Theorem 25 in [GKM21]). We highlight that this equivalence between
differential privacy and replicability for finite domains was made formal by
[BGH+23] and was extended to arbitrary statistical tasks.

##### TV Stability.

The definition of TV indistinguishability that we propose has close
connections with the definition of TV stability. This notion has appeared in
the context of adaptive data analysis. The work of [BNS+16a] studied the
following problem: suppose there is an unknown distribution $P$ and a set $S$
of $n$ independent samples drawn i.i.d. from $P$. The goal is to design an
algorithm that, with input $S$, will accurately answer a sequence of
adaptively chosen queries about the unknown distribution $P$. The main
question is how many samples must one draw from the distribution, as a
function of the type of queries, the number of queries, and the desired level
of accuracy to perform well? [BNS+16a] provide various results that rely on
the connections between algorithmic stability, differential privacy and
generalization. To this end, they think of differential privacy as max-KL
stability and study the performance of other notions of stability such as TV
stability. Crucially, in their definition, TV stability considers any pair of
neighboring datasets $S,S^{\prime}$ and not two independent draws from $P$.
More concretely, they propose the following definition.

######  Definition 7 (Total Variation Stability [BNS+16a]).

A learning rule $A$ is $n$-sample $\rho$-$\mathrm{TV}$ stable if for any pair
of samples $S,S^{\prime}\in(\mathcal{X}\times\\{0,1\\})^{n}$ that disagree on
a single example, it holds that $d_{\mathrm{TV}}(A(S),A(S^{\prime}))\leq\rho$.

We underline that for any constant $\rho$555In fact, even for $\rho\geq
1/n^{c},0<c<1.$ it is not challenging to obtain a $\rho$-TV stable algorithm
in the learning setting we are interested in. It suffices to just sub-sample a
small enough subset of the data. Hence, any class with finite VC dimension is
TV stably learnable under this definition. As it is evident from our results
(cf. Theorem 4), this is in stark contrast with the definition we propose. We
remind the readers that just sub-sampling the dataset is not enough to achieve
differential privacy. This is because it is required that $\delta=o(1/n).$ We
remark that the definition of total variation stability à la [BNS+16a] also
appears in [RRT+16].

The above definition of TV stability has close connections to machine
unlearning. This problem refers to the ability of a user to delete their data
that were used to train a ML algorithm. When this happens, the machine
learning algorithm has to move to a state as if it had never used that data
for training, hence the term _machine unlearning_. One can see that Definition
7 is suitable for this setting since it states that if one point of the
dataset is deleted, the distribution of the algorithm should not be affected
very much. For convex risk minimization problems, [UMR+21] design TV stable
algorithms based on noisy Stochastic Gradient Descent (SGD). Such approaches
lead to the design of efficient unlearning algorithms, which are based on sub-
sampling the dataset and constructing a maximal coupling of Markov chains for
the noisy SGD procedure.

##### KL Stability and PAC-Bayes.

In Section A.3 we provide some equivalent definitions to TV
indistinguishability. In particular, Definition 20 has connections with the
line of work that studies distribution-dependent generalization bounds. To be
more precise, if instead of the TV distance we use the KL divergence to
measure the distance between the prior and the output of the algorithm we get
the definition of the quantity that is used to derive PAC-Bayes generalization
bounds. Interestingly, [LM20] show that the PAC-Bayes framework cannot be used
to derive distribution-free PAC learning bounds for classes that have infinite
Littlestone dimension; they show that for any algorithm that learns
1-dimensional linear classifiers (thresholds), there exists a realizable
distribution for which PAC-Bayes bounds are trivial. Recently, a similar PAC-
Bayes framework was proposed in [AEMM22], where the KL divergence is replaced
with a general family of Integral Probability Metrics (cf. Definition 13).

##### Probably Eventually Correct Learning.

The work of [MM22] introduced the _Probably Eventually Correct_ (PEC) model of
learning. In this model, a learner outputs the same hypothesis666Except maybe
for a subset of $\mathcal{X}$ that has measure zero under the data-generating
distribution., with probability one, after a uniformly bounded number of
revisions. Intuitively, this corresponds to the property that the global
stability parameter is close to $1$. Interestingly, prior work on global
stability [BLM20, GGKM21] had characterized _Littlestone classes_ as being PAC
learnable by an algorithm which outputs some fixed hypothesis with nonzero
probability. However, the frequency of this hypothesis was typically very
small and its loss was a priori non-zero. [MM22] give a new characterization
to Littlestone classes by identifying them with the classes that can be PEC
learned in a stable fashion. Informally, this means that the learning rule for
$\mathcal{H}$ stabilizes on some hypothesis after changing its mind at most
$L$ times, where $L$ is the Littlestone dimension of $\mathcal{H}$ (cf.
Definition 14). Interestingly, [MM22] manage to show that the well-known
_Standard Optimal Algorithm_ (SOA) [Lit88] is a stable PEC learner, using
tools from the theory of universal learning [BHM+21, BHM+22, KVK22, HKMV22].
Moreover, they list various different notions of algorithmic stability and
show that they all have something in common: a class $\mathcal{H}$ is
learnable by such learners if and only if its Littlestone dimension is finite.
Our main result shows that, indeed, classes that are learnable by TV
indistinguishable learners fall into that category.

##  2 TV Indistinguishability and Replicability

Our information-theoretic definition of TV indistinguishability seems to put
weaker restrictions on learning rules than the notion of replicability in two
ways: (i) it allows for _arbitrary_ couplings between the two executions of
the algorithm (recall the coupling definition of TV distance, see Eq.(1)),
and, (ii) it allows for _different_ couplings between every pair of datasets
$S,S^{\prime}$ (the optimal coupling in the definition of TV distance will
depend on $S,S^{\prime}$ of Definition 4). In short, our definition allows for
_arbitrary data-dependent_ couplings, instead of just sharing the randomness
across two executions. TV indistinguishability can be viewed as a statistical
generalization of replicability (cf. Definition 2) since it describes a
property of _learning rules_ rather than _learning algorithms_.

In this section, we will show that TV indistinguishability and replicability
are (perhaps surprisingly) equivalent in a rather strong sense: under a mild
measure-theoretic condition, every TV indistinguishable algorithm can be
converted into an _equivalent_ replicable one by _re-interpreting_ its
internal randomness. This will be made formal shortly.

We start by showing that any replicable algorithm is TV indistinguishable.

######  Theorem 1 (Replicability $\Rightarrow$ TV Indistinguishability).

If a learning rule $A$ is $n$-sample $\rho$-replicable, then it is also
$n$-sample $\rho$-$\mathrm{TV}$ indistinguishable.

###### Proof.

Fix some distribution $\mathcal{D}$ over inputs. Let $A$ be $n$-sample
$\rho$-replicable with respect to $\mathcal{D}$. For the random variables
$A(S),A(S^{\prime})$ where $S,S^{\prime}\sim\mathcal{D}^{n}$ are two
independent samples and using Eq.(1), we have

$\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),A(S^{\prime}))]=\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}\left[\inf_{(h,h^{\prime})\sim\Pi(A(S),A(S^{\prime}))}\mathop{\bf
Pr\/}[h\neq h^{\prime}]\right]\,.$ (1)

Let $\mathcal{R}$ be the source of randomness that $A$ uses. The expected
optimal coupling of Eq.(1) is at most $\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}\left[\mathop{\bf
Pr\/}_{r\sim\mathcal{R}}[A(S,r)\neq A(S^{\prime},r)]\right]$. This inequality
follows from the fact that using shared randomness between the two executions
of $A$ is a particular way to couple the two random variables. To complete the
proof, it suffices to notice that this upper bound is equal to

$\mathop{\bf
Pr\/}_{S,S^{\prime}\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A(S,r)\neq
A(S^{\prime},r)]\leq\rho\,.$

The last inequality follows since $A$ is $\rho$-replicable. ∎

We now deal with the opposite direction, i.e., we show that TV
indistinguishability implies replicability. In order to be formal, we need to
discuss some measure theoretic properties first. Let us recall the definition
of absolute continuity for two measures.

######  Definition 8 (Absolute Continuity).

Consider two measures $P,Q$ on a $\sigma$-algebra $\mathcal{B}$ of subsets of
$\Omega$. We say that $P$ is absolutely continuous with respect to $Q$ if for
any $E\in\mathcal{B}$ such that $Q(E)=0$, it holds that $P(E)=0$.

Since the learning rules induce posterior distributions over hypotheses, this
definition extends naturally to such rules.

######  Definition 9.

Given learning rule $A$, distribution over inputs $\mathcal{D}$ and reference
probability measure $\mathcal{P}$, we say that $A$ is absolutely continuous
with respect to $\mathcal{P}$ on inputs from $\mathcal{D}$ if, for almost
every sample $S$ drawn from $\mathcal{D}$, the posterior distribution $A(S)$
is absolutely continuous with respect to $\mathcal{P}$.

In the previous definition, we fixed the data-generating distribution
$\mathcal{D}$. We next consider its distribution-free version.

######  Definition 10.

Given learning rule $A$ and reference probability measure $\mathcal{P}$, we
say that $A$ is absolutely continuous with respect to $\mathcal{P}$ if, for
any distribution over inputs $\mathcal{D}$, $A$ is absolutely continuous with
respect to $\mathcal{P}$ on inputs from $\mathcal{D}$.

If $\mathcal{X}$ is finite, then one can take $\mathcal{P}$ to be the uniform
probability measure over $\\{0,1\\}^{\mathcal{X}}$ and any learning rule is
absolutely continuous with respect to $\mathcal{P}$. We now show how we can
find such a prior $\mathcal{P}$ in the case where $\mathcal{X}$ is countable.

######  Claim 1 (Reference Probability Measure for Countable Domains).

Let $\mathcal{X}$ be a countable domain and $A$ be a learning rule. Then,
there is a reference probability measure $\mathcal{P}$ such that $A$ is
absolutely continuous with respect to $\mathcal{P}$.

###### Proof.

Since $\mathcal{X}$ is countable, for a fixed $n$, we can consider an
enumeration of all the $n$-tuples $\\{S_{i}\\}_{i\in\mathbb{N}}$. Then, we can
take $\mathcal{P}$ to be a countable mixture of these probability measures,
i.e., $\mathcal{P}=\sum_{i=1}^{\infty}\frac{1}{2^{i}}A(S_{i})$. Notice that
since, each $A(S_{i})$ is a measure and $1/2^{i}>0$ for $i\in\mathbb{N},$ and,
$\sum_{i=1}^{\infty}1/2^{i}=1$, we have that $\mathcal{P}$ is indeed a
probability measure. We now argue that each $A(S_{i})$ is absolutely
continuous with respect to $\mathcal{P}$. Assume towards contradiction that
this is not the case and let $E\in\mathcal{B}$ be a set such that
$\mathcal{P}(E)=0$ but $A(S_{j})(E)\neq 0$, for some $j\in\mathbb{N}.$ Notice
that $A(S_{j})$ appears with coefficient $1/2^{j}>0$ in the mixture that we
consider, hence if $A(S_{j})(E)>0\implies 1/2^{j}A(S_{j})(E)>0.$ Moreover
$A(S_{i})(E)\geq 0,\forall i\in\mathbb{N},$ which means that
$\mathcal{P}(E)>0$, so we get a contradiction. ∎

We next define when two learning rules $A,A^{\prime}$ are equivalent.

######  Definition 11 (Equivalent Learning Rules).

Two learning rules $A,A^{\prime}$ are equivalent if for every sample $S$ it
holds that $A(S)=A^{\prime}(S)$, i.e., for the same input they induce the same
distribution over hypotheses.

In the next result, we show that for every TV indistinguishable algorithm $A$,
that is absolutely continuous with respect to some reference probability
measure $\mathcal{P}$, there exists an equivalent learning rule which is
replicable.

######  Theorem 2 (TV Indistinguishability $\Rightarrow$ Replicability).

Let $\mathcal{P}$ be a reference probability measure over
$\\{0,1\\}^{\mathcal{X}}$, and let $A$ be a learning rule that is $n$-sample
$\rho$-$\mathrm{TV}$ indistinguishable and absolutely continuous with respect
to $\mathcal{P}$. Then, there exists an equivalent learning rule $A^{\prime}$
that is $n$-sample $\frac{2\rho}{1+\rho}$-replicable.

In this section, we only provide a sketch of the proof and we refer the reader
to Section C.1 for the complete one. Let us first state how we can use the
previous result when $\mathcal{X}$ is countable.

######  Corollary 1.

Let $\mathcal{X}$ be a countable domain and let $A$ be a learning rule that is
$n$-sample $\rho$-$\mathrm{TV}$ indistinguishable. Then, there exists an
equivalent learning rule $A^{\prime}$ that is $n$-sample
$\frac{2\rho}{1+\rho}$-replicable.

The proof of this result follows immediately from 1 and Theorem 2.

##### Proof Sketch of Theorem 2.

Let us consider a learning rule $A$ satisfying the conditions of Theorem 2.
Fix a distribution $\mathcal{D}$ over inputs. The crux of the proof is that
given two random variables $X,Y$ whose TV distance is bounded by $\rho$, we
can couple them using only a carefully designed source of shared randomness
$\mathcal{R}$ so that the probability that the realizations of these random
variables differ is at most $2\rho/(1+\rho).$ We can instantiate this
observation with $X=A(S)$ and $Y=A(S^{\prime})$. Crucially, in the countable
$\mathcal{X}$ setting, we can pick the shared randomness $\mathcal{R}$ in a
way that only depends on the learning rule $A$, but not on $S$ or
$S^{\prime}$. Let us now describe how this coupling works. Essentially, it can
be thought of as a generalization of the von Neumann rejection-based sampling
which does not necessarily require that the distribution has bounded density.
Following [AS19], we pick $\mathcal{R}$ to be a Poisson point process which
generates points of the form $(h,y,t)$ with intensity777Roughly speaking, a
point process is a (general) Poisson point process with intensity $\lambda$ if
(i) the number of points in a bounded Borel set $E$ is a Poisson random
variable with mean $\lambda(E)$ and (ii) the numbers of points in $n$ disjoint
Borel sets forms $n$ independent random variables. For further details, we
refer to [LP17a]. $\mathcal{P}\times\mathrm{Leb}\times\mathrm{Leb}$, where
$\mathcal{P}$ is a reference probability measure with respect to which $A$ is
absolutely continuous and $\mathrm{Leb}$ is the Lebesgue measure over
$\mathbb{R}_{+}$. Intuitively, $h\sim\mathcal{P}$ lies in the hypotheses’
space, $y$ is a non-negative real value and $t$ corresponds to a time value.
The coupling mechanism performs _rejection sampling_ for each distribution we
would like to couple (here $A(S)$ and $A(S^{\prime}))$: it checks (in the
ordering indicated by the time parameter) for each point $(h,y,t)$ whether
$f(h)>y$ (i.e., if $y$ falls below the density curve $f$ at $h$) and accepts
the first point that satisfies this condition. In the formal proof, there will
be two density functions; $f$ (resp. $f^{\prime}$) for the density function of
$A(S)$ (resp. $A(S^{\prime})$). We also refer to Figure 1. One can show (see
Theorem 8) that $\mathcal{R}$ gives rise to a coupling between $A(S)$ and
$A(S^{\prime})$ under the condition that both measures are absolutely
continuous with respect to the reference probability measure $\mathcal{P}$.

This coupling technique appears in [AS19]. We can then apply it and get

$\mathop{\bf Pr\/}_{r\sim\mathcal{R}}[A(S,r)\neq
A(S^{\prime},r)]\leq\frac{2d_{\mathrm{TV}}(A(S),A(S^{\prime}))}{1+d_{\mathrm{TV}}(A(S),A(S^{\prime}))}\,.$

Taking the expectation with respect to the draws of $S,S^{\prime}$, we show
(after some algebraic manipulations) that $\mathop{\bf
Pr\/}_{S,S^{\prime}\sim\mathcal{D}^{n}r\sim\mathcal{R}}[A(S,r)\neq
A(S^{\prime},r)]\leq 2\rho/(1+\rho)$. We conclude this section with the
following remarks.

Figure 1: Our goal is to couple $A(S)$ with $A(S^{\prime})$, where these two
distributions are absolutely continuous with respect to the reference
probability measure $\mathcal{P}$. A sequence of points of the form $(h,y,t)$
is generated by the Poisson point process with intensity
$\mathcal{P}\times\mathrm{Leb}\times\mathrm{Leb}$ where
$h\sim\mathcal{P},(y,t)\in\mathbb{R}^{2}_{+}$ and $\mathrm{Leb}$ is the
Lebesgue measure over $\mathbb{R}_{+}$ (note that we do not have upper bounds
for the densities). Intuitively, $h$ lies in the hypotheses’ space, $y$ is a
non-negative real value and $t$ corresponds to a time value. Let $f$ be the
Radon-Nikodym derivate of $A(S)$ with respect to $\mathcal{P}$. We assign the
first (the one with minimum $t)$ value $h$ to $A(S)$ that satisfies the
property that $f(h)>y$, i.e., $y$ falls below the density curve of $A(S)$. We
assign a hypothesis to $A(S^{\prime})$ in a similar manner. This procedure
defines a data-independent way to couple the two random variables and
naturally extends to multiple ones. In the figure’s example, we set
$A(S)=h_{2}$ and $A(S^{\prime})=h_{4}$ given that $t_{1}<t_{2}<t_{3}<t_{4}$.

######  Remark 1 (General Equivalence).

In Section C.2, we discuss how the above equivalence actually holds for
general statistical tasks beyond binary classification. We first generalize
the notions of indistinguishability, replicability and $\mathrm{TV}$
indistinguishability for general input spaces $\mathcal{I}$ and output spaces
$\mathcal{O}$. We then discuss that replicability and $\mathrm{TV}$
indistinguishability remain equivalent (under the same measure theoretic
conditions) in these more general abstract learning scenarios.

######  Remark 2 (Implementation of the Coupling).

We note that, in order to implement algorithm $A^{\prime}$ of Theorem 2, we
need sample access to a Poisson point process with intensity
$\mathcal{P}\times\mathrm{Leb}\times\mathrm{Leb},$ where $\mathcal{P}$ is the
reference probability measure from 1 and $\mathrm{Leb}$ is the Lebesgue
measure over $\mathbb{R}_{+}$. Importantly, $\mathcal{P}$ depends only on $A$.
Moreover, we need full access to the values of the density $f_{i}$ of the
distribution $A(S_{i})$ with respect to the reference probability measure
$\mathcal{P}$, for any sample $S_{i}$. We underline that these quantities do
not depend on the data-generating distribution $\mathcal{D}$ (since we iterate
over any possible sample).

######  Remark 3 (TV Indistinguishability vs. Replicability).

Notice that in the definition of replicability (cf. Definition 2) the source
of randomness $\mathcal{R}$ needs to be specified and by changing it we can
observe different behaviors for coupled executions of the algorithm. On the
other hand, the definition of $\mathrm{TV}$ indistinguishability (cf.
Definition 4) does not require the specification of $\mathcal{R}$ as it states
a property of the posterior distribution of the learning rule.

##  3 TV Indistinguishability and Differential Privacy

In this section we investigate the connections between TV indistinguishability
and approximate DP in binary classification. Consider a hypothesis class
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$. We will say that $\mathcal{H}$
is learnable by a $\rho$-TV indistinguishable learning rule $A$ if this rule
satisfies the notion of learnability under the standard realizable PAC
learning model and is $\rho$-TV indistinguishable (see Definition 16).

The main result of this section is an equivalence between approximate DP and
TV indistinguishability for countable domains $\mathcal{X}$, in the context of
PAC learning. We remark that the equivalence of differential privacy with the
notion of replicability is formally stated for finite outcome spaces (i.e.,
under the assumption that $\mathcal{X}$ is finite) due to the use of a
specific correlated sampling strategy for the direction that “DP implies
replicability” in the context of classification [GKM21]. Moreover, [BGH+23]
gave a constructive way to transform a DP algorithm to a replicable one for
general statistical tasks and for finite domains. Thus, combining our results
in Section 2 and the result of [GKM21, ILPS22, BGH+23], the equivalence of TV
indistinguishability and DP for _finite_ domains is immediate. We will
elaborate more on the differences of our approach and [GKM21, BGH+23] later
on. We also discuss our coupling and correlated sampling in Section A.4.

Recall that a learner is $(\alpha,\beta)$-accurate if its misclassification
probability is at most $\alpha$ with probability at least $1-\beta$.

######  Theorem 3 ($(\varepsilon,\delta)$-DP $\Rightarrow$ TV
Indistinguishability).

Let $\mathcal{X}$ be a (possibly infinite) domain and
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$. Let
$\gamma\in(0,1/2),\alpha,\beta,\rho\in(0,1)^{3}$. Assume that $\mathcal{H}$ is
learnable by an $n$-sample $(1/2-\gamma,1/2-\gamma)$-accurate
$(0.1,1/(n^{2}\log(n)))$-differentially private learner. Then, it is also
learnable by an $(\alpha,\beta)$-accurate $\rho$-$\mathrm{TV}$
indistinguishable learning rule.

##### Proof Sketch of Theorem 3.

The proof goes through the notion of global stability (cf. Definition 19). The
existence of an $(\varepsilon,\delta)$-DP learner implies that the hypothesis
class $\mathcal{H}$ has finite Littlestone dimension [ALMM19] (cf. Theorem
10). Thus, we know that there exists a $\rho$-globally stable learner for
$\mathcal{H}$ [BLM20] (cf.
LABEL:thm:finite_littlestoneimplies_global_stability). The next step is to use
the replicable heavy-hitters algorithm (cf. Algorithm 1, [ILPS22]) with
frequency parameter $O(\rho)$ and replicability parameter $O(\rho^{\prime})$,
where $\rho^{\prime}\in(0,1)$ is the desired TV indistinguishability parameter
of the learning rule. The global stability property implies that the list of
heavy-hitters will be non-empty and it will contain at least one hypothesis
with small error rate, with high probability. Finally, since the list of
heavy-hitters is finite and has bounded size, we feed the output into the
replicable agnostic learner (cf. Algorithm 2). Thus, we have designed a
replicable learner for $\mathcal{H}$, and Theorem 1 shows that this learner is
also TV indistinguishable.

The formal proof of Theorem 3 is deferred to Section D.2. We also include a
result which shows that _list-global_ stability implies TV
indistinguishability for general domains and general statistical tasks, which
could be of independent interest (cf. Proposition 3).

We proceed to the opposite direction where we provide an algorithm that takes
as input a TV indistinguishable learning rule for $\mathcal{H}$ and outputs a
learner for $\mathcal{H}$ which is $(\varepsilon,\delta)$-DP. In this
direction countability of $\mathcal{X}$ is crucial.

######  Theorem 4 (TV Indistinguishability $\Rightarrow$
$(\varepsilon,\delta)$-DP).

Let $\mathcal{X}$ be a countable domain. Assume that
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ is learnable by an
$(\alpha,\beta)$-accurate $\rho$-$\mathrm{TV}$ indistinguishable learner $A$,
for some
$\rho\in(0,1),\alpha\in(0,1/2),\beta\in\left(0,\frac{1-\rho}{1+\rho}\right)$.
Then, for any
$(\alpha^{\prime},\beta^{\prime},\varepsilon,\delta)\in(0,1)^{4},$ it is also
learnable by an $\left(\alpha+\alpha^{\prime},\beta^{\prime}\right)$-accurate
$(\varepsilon,\delta)$-differentially private learner $A^{\prime}$.

We refer to Section D.4 for the proof. In the above statements, we omit the
details about the sample complexity. We refer to Proposition 3 and Proposition
4 for these details. Let us now comment on the differences between [GKM21,
BGH+23] which establish a transformation from a replicable learner to an
approximately DP learner and our result. The high-level idea to obtain both of
these results is similar. Essentially, the proof of [GKM21, BGH+23] can be
viewed as a coupling between sufficiently many posteriors of the replicable
learning rule using _shared randomness_ in order to achieve this coupling. In
our proof, instead of using shared randomness we use the reference measure we
described in previous sections to achieve this coupling. We remark that we
could have obtained the same qualitative result, i.e., that TV
indistinguishability implies approximate DP, by using the transformation from
replicability to approximate DP of [GGKM21, BGH+23] in a black-box manner
along with our result that TV indistinguishability implies replicability (cf.
Theorem 2). However, this leads to worse guarantees in terms of the range of
the parameters $\alpha,\beta,\delta,\varepsilon,\rho$ than the ones stated in
Theorem 4. Thus, we have chosen to do a more careful analysis based on the
coupling we proposed that leads to a stronger quantitative result. More
concretely, the proof in [GKM21, BGH+23] starts by sampling many random
strings independently of the dataset $\\{S_{i}\\}_{i\in[k]}$ and considers
many executions of the algorithm using the same random strings but different
data. In our algorithm we first sample the sets $\\{S_{i}\\}_{i\in[k]}$ and
then we consider an optimal coupling along the $\\{A(S_{i})\\}_{i\in[k]}$
which is also independent of the dataset, thus it satisfies the DP
requirements. Moreover, our procedure covers a wider range of parameters
$\alpha,\beta,\rho$ compared to [GKM21]. The reason we need countability of
$\mathcal{X}$ is because it allows us to design a _data-independent_ reference
probability measure $\mathcal{P}$, the same one as in 1. Then, using this
reference probability measure for the coupling helps us establish the DP
properties. Nevertheless, we propose a simple change to our approach which we
conjecture applies to general domains $\mathcal{X}$ and we leave it open as an
interesting future direction. For a more detailed discussion, we refer the
reader to Section D.5.

Interestingly, we underline that, as is shown in [GKM21, BGH+23] and as
opposed to Theorem 4, replicability implies DP in general spaces (cf. Theorem
12).

We conclude this section by stating a general equivalence between
$(\varepsilon,\delta)$-DP and replicability for PAC learning, that follows
from the previous discussion, in particular by combining Theorem 12 [GKM21,
BGH+23], and Lemma 9.

######  Theorem 5 (Replicability $\iff$ Differential Privacy in PAC Learning).

Let $\mathcal{X}$ be a (possibly infinite) domain and let
$\mathcal{H}\subseteq\left\\{0,1\right\\}^{\mathcal{X}}$. Then, $\mathcal{H}$
is replicably learnable if and only if it is approximately-DP learnable.

######  Remark 4 (Dependence on the Parameters).

In the case of $\mathrm{TV}$ indistinguishability $\Rightarrow$ $\mathrm{DP}$,
the blowup in the sample complexity is stated explicitly in Proposition 4.

For the direction $\mathrm{DP}$ $\Rightarrow$ $\mathrm{TV}$
indistinguishability it is a bit trickier to state the exact sample complexity
blow-up because we do not make explicit use of the $\mathrm{DP}$ learner.
Instead, we use the fact that the existence of a non-trivial $\mathrm{DP}$
learner implies that the class has finite Littlestone dimension and then we
use an appropriate algorithm that is known to work for such classes. In this
case, it suffices to let the parameters of the $\mathrm{DP}$ learner to be
$\varepsilon\in(0,0.1),\delta\in\left(0,\frac{1}{n^{2}\log(n)}\right),\alpha\in(0,1/2),\beta\in(0,1/2)$
and the parameters of the desired $\mathrm{TV}$ indistinguishable
$(\alpha^{\prime},\beta^{\prime})$-accurate learner are unconstrained, i.e.,
$\rho\in(0,1),\alpha^{\prime}\in(0,1),\beta^{\prime}\in(0,1)$. If we denote
the Littlestone dimension of the class by $L$, then, as shown in Proposition 3
the sample complexity of the $\mathrm{TV}$ indistinguishable learner is
$\textnormal{poly}(L,1/\rho,1/\alpha^{\prime},\log(1/\beta^{\prime}))$888This
holds under the (standard) assumption that uniform convergence holds for
Littlestone classes. If this is not the case, we get
$\textnormal{poly}(2^{2^{L}},1/\rho,1/\alpha^{\prime},\log(1/\beta^{\prime}))$
sample complexity (Corollary 6)..

######  Remark 5 (Beyond Binary Classification).

The only transformation that is restricted to binary classification is the one
from $\mathrm{DP}$ to $\mathrm{TV}$ indistinguishability. All the other
transformations, (and the boosting algorithms that we present in the upcoming
section), extend to general statistical tasks. Let us now shortly discuss how
to extend our result e.g., to the multi-class setting, using results from the
private multiclass learning literature [JKT20, SBG21]. [JKT20] showed that
private multiclass learnability implies finite multiclass Littlestone
dimension and [SBG21] showed how to extend the binary list-globally stable
learner that we use to the multiclass setting. Using these two main
ingredients, the rest of our approach for the binary classification setting
should extend to the multiclass setting. The extension to the regression
problem seems to be more challenging. Even though [JKT20] showed that private
regression implies finiteness of some appropriate Littlestone dimension, it is
not clear yet how to derive a (list-)globally stable algorithm for this
problem.

##  4 Amplifying and Boosting TV Indistinguishable Algorithms

In this section we study the following fundamental question.

######  Question 1.

Consider a weak $\mathrm{TV}$ indistinguishable learning rule both in terms of
the indistinguishability parameter and the accuracy. Is it possible to amplify
its indistinguishability and to boost its accuracy?

For instance, in the context of approximate differential privacy, a series of
works has lead to (constructive) algorithms that boost the accuracy and
amplify the privacy guarantees (e.g., [DRV10, BLM20, BGH+23]). This result
builds upon the equivalence of online learnability and approximate
differential privacy. Our result relating DP to TV indistinguishability
implies the following existential result.

######  Corollary 2.

Let $\mathcal{X}$ be a countable domain. Suppose that for some sample size
$n_{0}$, there exists an $(\alpha_{0},\beta_{0})$-accurate
$\rho_{0}$-$\mathrm{TV}$ indistinguishable learner $A$ for a class
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ with
$\alpha_{0}\in(0,1/2),\rho_{0}\in(0,1),\beta_{0}\in\left(0,\frac{1-\rho_{0}}{1+\rho_{0}}\right)$.
Then, for any $(\alpha,\beta,\rho)\in(0,1)^{3}$, $\mathcal{H}$ admits an
$(\alpha,\beta)$-accurate $\rho$-$\mathrm{TV}$ indistinguishable learner
$A^{\prime}$.

This result relies on connections between learnability by TV indistinguishable
learners and finiteness of the Littlestone dimension of the underlying
hypothesis class that were discussed in Section 3. In particular, Corollary 7
shows that the existence of such a non-trivial TV indistinguishable learner
implies that the $\mathcal{H}$ has finite Littlestone dimension, and
Proposition 3, states that the finiteness of the Littlestone dimension of
$\mathcal{H}$ implies the existence of an $(\alpha,\beta)$-accurate $\rho$-TV
indistinguishable learner, for arbitrarily small choices of
$\alpha,\beta,\rho$. It is not hard to see that we need to constrain
$\alpha\in(0,1/2)$, because the algorithm needs to have an advantage compared
to the random classifier. Moreover, it should be the case that
$\beta\in(0,1-\rho).$ If $\beta\geq 1-\rho$ then the algorithm which outputs a
constant classifier with probability $\beta$ and an $\alpha$-good one with the
remaining probability is $\rho$-TV indistinguishable and
$(\alpha,\beta)$-accurate. An interesting open problem is to investigate what
happens when $\beta\in\left(\frac{1-\rho}{1+\rho},1-\rho\right)$.

We underline that Corollary 2 is existential and does not make actual use of
the weak TV indistinguishable learner that is given as input. Hence, it is
natural to try to come up with sample-efficient and constructive approaches
that utilize the weak learner through black-box oracle calls to it during the
derivation of the strong one. In what follows, we aim to design such
algorithms. We remind the reader that if we constrain ourselves to work in the
setting where $\mathcal{X}$ is countable, then the absolute continuity
requirement in the next theorems comes immediately, due to 1.

##### Indistinguishability Amplification.

We first consider the amplification of the indistinguishability guarantees of
an algorithm. An important ingredient of our approach is a replicable
algorithm for finding heavy hitters of a distribution, i.e., elements whose
frequency is above some given threshold. This algorithm has appeared in
[GKM21, ILPS22]. However, the dependence of the number of samples in the
confidence parameter in these works is polynomial. We present a new variant of
this algorithm that has polylogarithmic dependence on the confidence
parameter. Moreover, using a stronger concentration inequality, we improve the
dependence of the number of samples on the error parameter. We believe that
this result could be of independent interest. We also design an agnostic
learner for finite hypothesis classes. However, the dependence of the number
of samples on $|\mathcal{H}|$ is polynomial. We believe that an interesting
question is to design agnostic learners with polylogarithmic dependence on
$|\mathcal{H}|$. We refer the reader to Appendix E.

######  Theorem 6 (Indistinguishability Amplification).

Let $\mathcal{P}$ be a reference probability measure over
$\\{0,1\\}^{\mathcal{X}}$ and $\mathcal{D}$ be a distribution over inputs.
Consider the source of randomness $\mathcal{R}$ to be a Poisson point process
with intensity $\mathcal{P}\times\mathrm{Leb}\times\mathrm{Leb},$ where
$\mathrm{Leb}$ is the Lebesgue measure over $\mathbb{R}_{+}$. Consider a weak
learning rule $A$ that is (i) $\rho$-$\mathrm{TV}$ indistinguishable with
respect to $\mathcal{D}$ for some $\rho\in(0,1)$, (ii)
$(\alpha,\beta)$-accurate for $\mathcal{D}$ for some
$(\alpha,\beta)\in(0,1)^{2}$, such that
$\beta<\frac{2\rho}{\rho+1}-2\sqrt{\frac{2\rho}{\rho+1}}+1$, and, (iii)
absolutely continuous with respect to $\mathcal{P}$ on inputs from
$\mathcal{D}$. Then, for any
$\rho^{\prime},\varepsilon,\beta^{\prime}\in(0,1)^{3}$, there exists a learner
$\textsc{Ampl}(A,\mathcal{R},\beta^{\prime},\varepsilon,\rho^{\prime})$ that
is $\rho^{\prime}$-$\mathrm{TV}$ indistinguishable with respect to
$\mathcal{D}$, and $(\alpha+\varepsilon,\beta^{\prime})$-accurate for
$\mathcal{D}$.

We remark that the above result makes strong use of the equivalence between
replicability and TV indistinguishability. Our algorithm is a variant of the
amplification algorithm that appeared in [ILPS22], which (i) works for a wider
range of parameters and (ii) its sample complexity is polylogarithmic in the
parameter $\beta^{\prime}$.

##### Accuracy Boosting.

Next, we design an algorithm that boosts the accuracy of an $n$-sample
$\rho$-TV indistinguishable algorithm and preserves its TV
indistinguishability guarantee. Our algorithm is a variant of the boosting
mechanism provided in [ILPS22]. Similarly as in the case of amplification, our
variant improves upon the dependence of the number of samples on the parameter
$\beta^{\prime}$.

######  Theorem 7 (Accuracy Boosting).

Let $\mathcal{P}$ be a reference probability measure over
$\\{0,1\\}^{\mathcal{X}}$ and $\mathcal{D}$ be a distribution over inputs.
Consider the source of randomness $\mathcal{R}$ to be a Poisson point process
with intensity $\mathcal{P}\times\mathrm{Leb}\times\mathrm{Leb},$ where
$\mathrm{Leb}$ is the Lebesgue measure over $\mathbb{R}_{+}$. Consider a weak
learning rule $A$ that is (i) $\rho$-$\mathrm{TV}$ indistinguishable with
respect to $\mathcal{D}$ for some $\rho\in(0,1)$, (ii)
$(1/2-\gamma,\beta)$-accurate for $\mathcal{D}$ for some
$(\gamma,\beta)\in(0,1)^{2}$, and, (iii) absolutely continuous with respect to
$\mathcal{P}$ on inputs from $\mathcal{D}$. Then, for any
$\beta^{\prime},\varepsilon,\rho^{\prime}\in(0,1)^{3}$, there exists a learner
$\textsc{Boost}(A,\mathcal{R},\varepsilon)$ that is
$\rho^{\prime}$-$\mathrm{TV}$ indistinguishable with respect to $\mathcal{D}$
and $(\varepsilon,\beta^{\prime})$-accurate for $\mathcal{D}$.

We can combine the amplification and boosting results for a wide range of
parameters and get the next corollary.

######  Corollary 3.

Let $\mathcal{X}$ be a countable domain and $A$ be an $n$-sample
$\rho$-$\mathrm{TV}$ indistinguishable $(\alpha,\beta)$-accurate algorithm,
for some
$\rho\in(0,1),\alpha\in(0,1/2),\beta\in\left(0,\frac{2\rho}{\rho+1}-2\sqrt{\frac{2\rho}{\rho+1}}+1\right).$
Then, for any $\rho^{\prime},\alpha^{\prime},\beta^{\prime}\in(0,1)^{3},$
there exists a $\rho^{\prime}$-$\mathrm{TV}$ indistinguishable
$(\alpha^{\prime},\beta^{\prime})$-accurate learner $A^{\prime}$ that requires
at most
$O\left(\mathrm{poly}\left(1/\rho,1/\alpha^{\prime},\log(1/\beta^{\prime})\right)\cdot
n\right)$ samples from $\mathcal{D}$.

The proof of this result follows immediately from Theorem 6, Theorem 7, and
from the fact that we can design the reference probability measure
$\mathcal{P}$ for countable domains (cf. 1). This result leads to two natural
questions: what is the tightest range of $\beta$ for which we can amplify the
stability parameter $\rho$ and under what assumptions can we design such
boosting and amplification algorithms for general domains $\mathcal{X}$? For a
more detailed discussion, we refer the reader to Section E.3, Section E.4.

######  Remark 6 (Dependence on the Parameters).

We underline that the polynomial dependence on $\rho$ in the boosting result
is not an artifact of the algorithmic procedure or the analysis we provide,
but it is rather an inherent obstacle in $\mathrm{TV}$ indistinguishability.
[ILPS22] show that in order to estimate the bias of a coin $\rho$-replicably
with accuracy $\tau$ one needs at least $1/(\tau^{2}\rho^{2})$ coin tosses.
Since $\rho$-$\mathrm{TV}$ indistinguishability implies
$(2\rho/(1+\rho))$-replicability as we have shown (without any blow-up in the
sample complexity), we also inherit this lower bound. Our main goal behind the
study of the boosting algorithms is to identify the widest range of parameters
$\alpha,\rho,\beta$ such that coming up with a $\rho$-$\mathrm{TV}$
indistinguishable algorithm switches from being trivial to being difficult.
For example, in PAC learning we know that if the accuracy parameter is
strictly less than $1/2$, then there are sample-efficient boosting algorithms
that can drive it down to any $\varepsilon>0$. In the setting we are studying,
it is crucial to understand the relationship between $\beta,\rho$, see Section
E.3.

##  5 Conclusion

In this work, we studied TV indistinguishability and established connections
to similar notions that have been proposed in the past, i.e., differential
privacy, replicability, global stability, and pseudo-global stability, under
mild measure-theoretic assumptions (e.g., countable $\mathcal{X}$). Our work
leaves the following open problems:

  1. 1.

Does the equivalence between TV indistinguishability and replicability hold
for general spaces, i.e., when the input domain is not countable?

  2. 2.

Does the equivalence between TV indistinguishability and
$(\varepsilon,\delta)$-DP hold for general spaces?

  3. 3.

How can we boost the correctness and amplify the indistinguishability
parameter of a weak TV indistinguishable learner to a strong one in general
spaces?

  4. 4.

What is the minimal condition that characterizes TV indistinguishable PAC
learnability? This is closely related to understanding the limits of TV
indistinguishable boosting algorithms.

##  6 Acknowlegdements

We thank Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei,
Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell for illustrating
discussions regarding the connection of this work with the recent paper
[BGH+23]. We also thank Kyriakos Lotidis for helpful discussions about the
Poisson point process.

## References

  * [ABL+22] Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran.  Private and online learnability are equivalent.  ACM Journal of the ACM (JACM), 2022.
  * [AEMM22] Ron Amit, Baruch Epstein, Shay Moran, and Ron Meir.  Integral probability metrics pac-bayes bounds.  arXiv preprint arXiv:2207.00614, 2022.
  * [AJJ+22] Kwangjun Ahn, Prateek Jain, Ziwei Ji, Satyen Kale, Praneeth Netrapalli, and Gil I Shamir.  Reproducibility in optimization: Theoretical framework and limits.  arXiv preprint arXiv:2202.04598, 2022.
  * [ALMM19] Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran.  Private pac learning implies finite littlestone dimension.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 852–860, 2019.
  * [ALMT17] Jacob D Abernethy, Chansoo Lee, Audra McMillan, and Ambuj Tewari.  Online learning via differential privacy.  2017\.
  * [AS19] Omer Angel and Yinon Spinka.  Pairwise optimal coupling of multiple random variables.  arXiv preprint arXiv:1903.00632, 2019.
  * [Bak16] Monya Baker.  1,500 scientists lift the lid on reproducibility.  Nature, 533(7604), 2016.
  * [BD15] Shai Ben-David.  2 notes on classes with vapnik-chervonenkis dimension 1.  arXiv preprint arXiv:1507.05307, 2015.
  * [BE02] Olivier Bousquet and André Elisseeff.  Stability and generalization.  The Journal of Machine Learning Research, 2:499–526, 2002.
  * [BEHW89] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth.  Learnability and the vapnik-chervonenkis dimension.  Journal of the ACM (JACM), 36(4):929–965, 1989.
  * [BF16] Raef Bassily and Yoav Freund.  Typicality-based stability and privacy.  arXiv preprint arXiv:1604.03336, 2016.
  * [BGH+16] Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L Rivest, and Madhu Sudan.  Optimality of correlated sampling strategies.  arXiv preprint arXiv:1612.01041, 2016.
  * [BGH+23] Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell.  Stability is stable: Connections between replicability, privacy, and adaptive generalization.  arXiv preprint arXiv:2303.12921, 2023.
  * [BHM+21] Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon Van Handel, and Amir Yehudayoff.  A theory of universal learning.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 532–541, 2021.
  * [BHM+22] Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, and Ilya Tolstikhin.  Fine-grained distribution-dependent learning curves.  arXiv preprint arXiv:2208.14615, 2022.
  * [BKW03] Avrim Blum, Adam Kalai, and Hal Wasserman.  Noise-tolerant learning, the parity problem, and the statistical query model.  Journal of the ACM (JACM), 50(4):506–519, 2003.
  * [BLM20] Mark Bun, Roi Livni, and Shay Moran.  An equivalence between private classification and online prediction.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 389–402. IEEE, 2020.
  * [BM02] Peter L Bartlett and Shahar Mendelson.  Rademacher and gaussian complexities: Risk bounds and structural results.  Journal of Machine Learning Research, 3(Nov):463–482, 2002.
  * [BNS+16a] Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman.  Algorithmic stability for adaptive data analysis.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 1046–1059, 2016.
  * [BNS16b] Mark Bun, Kobbi Nissim, and Uri Stemmer.  Simultaneous private learning of multiple concepts.  In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 369–380, 2016.
  * [Bro97] Andrei Z Broder.  On the resemblance and containment of documents.  In Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No. 97TB100171), pages 21–29. IEEE, 1997.
  * [Cha02] Moses S Charikar.  Similarity estimation techniques from rounding algorithms.  In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 380–388, 2002.
  * [CKMY20] Sitan Chen, Frederic Koehler, Ankur Moitra, and Morris Yau.  Classification under misspecification: Halfspaces, generalized linear models, and evolvability.  Advances in Neural Information Processing Systems, 33:8391–8403, 2020.
  * [CLN+16] Rachel Cummings, Katrina Ligett, Kobbi Nissim, Aaron Roth, and Zhiwei Steven Wu.  Adaptive learning with robust generalization guarantees.  In Conference on Learning Theory, pages 772–814. PMLR, 2016.
  * [DFH+15] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth.  Preserving statistical validity in adaptive data analysis.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 117–126, 2015.
  * [DKM+06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor.  Our data, ourselves: Privacy via distributed noise generation.  In Annual international conference on the theory and applications of cryptographic techniques, pages 486–503. Springer, 2006.
  * [DR14] Cynthia Dwork and Aaron Roth.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [DRV10] Cynthia Dwork, Guy N Rothblum, and Salil Vadhan.  Boosting and differential privacy.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 51–60. IEEE, 2010.
  * [Dwo08] Cynthia Dwork.  Differential privacy: A survey of results.  In International conference on theory and applications of models of computation, pages 1–19. Springer, 2008.
  * [EKK+22] Hossein Esfandiari, Alkis Kalavasis, Amin Karbasi, Andreas Krause, Vahab Mirrokni, and Grigoris Velegkas.  Reproducible bandits.  arXiv preprint arXiv:2210.01898, 2022.
  * [EKM+23] Hossein Esfandiari, Amin Karbasi, Vahab Mirrokni, Grigoris Velegkas, and Felix Zhou.  Replicable clustering.  arXiv preprint arXiv:2302.10359, 2023.
  * [FKKT21] Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos.  Efficient algorithms for learning from coarse labels.  In Conference on Learning Theory, pages 2060–2079. PMLR, 2021.
  * [GGK20] Surbhi Goel, Aravind Gollakota, and Adam Klivans.  Statistical-query lower bounds via functional gradients.  Advances in Neural Information Processing Systems, 33:2147–2158, 2020.
  * [GGKM21] Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi.  Sample-efficient proper pac learning with approximate differential privacy.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 183–196, 2021.
  * [GHRU11] Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman.  Privately releasing conjunctions and the statistical query barrier.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 803–812, 2011.
  * [GKM21] Badih Ghazi, Ravi Kumar, and Pasin Manurangsi.  User-level private learning via correlated sampling.  arXiv preprint arXiv:2110.11208, 2021.
  * [HKMV22] Steve Hanneke, Amin Karbasi, Shay Moran, and Grigoris Velegkas.  Universal rates for interactive learning.  Advances in Neural Information Processing Systems, 35:28657–28669, 2022.
  * [Hol07] Thomas Holenstein.  Parallel repetition: simplifications and the no-signaling case.  In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 411–419, 2007.
  * [ILPS22] Russell Impagliazzo, Rex Lei, Toniann Pitassi, and Jessica Sorrell.  Reproducibility in learning.  arXiv preprint arXiv:2201.08430, 2022.
  * [JKT20] Young Jung, Baekjin Kim, and Ambuj Tewari.  On the equivalence between online and private learnability beyond binary classification.  Advances in neural information processing systems, 33:16701–16710, 2020.
  * [Kea98] Michael Kearns.  Efficient noise-tolerant learning from statistical queries.  Journal of the ACM (JACM), 45(6):983–1006, 1998.
  * [KKMN09] Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas.  Releasing search queries and clicks privately.  In Proceedings of the 18th international conference on World wide web, pages 171–180, 2009.
  * [KLN+11] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  SIAM Journal on Computing, 40(3):793–826, 2011.
  * [KT02] Jon Kleinberg and Eva Tardos.  Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields.  Journal of the ACM (JACM), 49(5):616–639, 2002.
  * [KVK22] Alkis Kalavasis, Grigoris Velegkas, and Amin Karbasi.  Multiclass learnability beyond the pac framework: Universal rates and partial concept classes.  arXiv preprint arXiv:2210.02297, 2022.
  * [Lit88] Nick Littlestone.  Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm.  Machine learning, 2(4):285–318, 1988.
  * [LM20] Roi Livni and Shay Moran.  A limitation of the pac-bayes framework.  Advances in Neural Information Processing Systems, 33:20543–20553, 2020.
  * [LP17a] Günter Last and Mathew Penrose.  Lectures on the Poisson process, volume 7.  Cambridge University Press, 2017.
  * [LP17b] David A Levin and Yuval Peres.  Markov chains and mixing times, volume 107.  American Mathematical Soc., 2017.
  * [MM22] Maryanthe Malliaris and Shay Moran.  The unstable formula theorem revisited.  arXiv preprint arXiv:2212.05050, 2022.
  * [MT07] Frank McSherry and Kunal Talwar.  Mechanism design via differential privacy.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 94–103. IEEE, 2007.
  * [PRMN04] Tomaso Poggio, Ryan Rifkin, Sayan Mukherjee, and Partha Niyogi.  General conditions for predictivity in learning theory.  Nature, 428(6981):419–422, 2004.
  * [PSF+19] Joelle Pineau, Koustuv Sinha, Genevieve Fried, Rosemary Nan Ke, and Hugo Larochelle.  Iclr reproducibility challenge 2019.  ReScience C, 5(2):5, 2019.
  * [PVLS+21] Joelle Pineau, Philippe Vincent-Lamarre, Koustuv Sinha, Vincent Larivière, Alina Beygelzimer, Florence d’Alché Buc, Emily Fox, and Hugo Larochelle.  Improving reproducibility in machine learning research: a report from the neurips 2019 reproducibility program.  Journal of Machine Learning Research, 22, 2021.
  * [RRT+16] Maxim Raginsky, Alexander Rakhlin, Matthew Tsao, Yihong Wu, and Aolin Xu.  Information-theoretic analysis of stability and bias of learning algorithms.  In 2016 IEEE Information Theory Workshop (ITW), pages 26–30. IEEE, 2016.
  * [SBG21] Satchit Sivakumar, Mark Bun, and Marco Gaboardi.  Multiclass versus binary differentially private pac learning.  Advances in Neural Information Processing Systems, 34:22943–22954, 2021.
  * [Ser03] Rocco A Servedio.  Smooth boosting and learning with malicious noise.  The Journal of Machine Learning Research, 4:633–648, 2003.
  * [SFG+09] Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert RG Lanckriet.  On integral probability metrics,$\backslash$phi-divergences and binary classification.  arXiv preprint arXiv:0901.2698, 2009.
  * [SSBD14] Shai Shalev-Shwartz and Shai Ben-David.  Understanding machine learning: From theory to algorithms.  Cambridge university press, 2014.
  * [SV16] Igal Sason and Sergio Verdú.  $f$-divergence inequalities.  IEEE Transactions on Information Theory, 62(11):5973–6006, 2016\.
  * [UMR+21] Enayat Ullah, Tung Mai, Anup Rao, Ryan A Rossi, and Raman Arora.  Machine unlearning via algorithmic stability.  In Conference on Learning Theory, pages 4126–4142. PMLR, 2021.
  * [Vad17] Salil Vadhan.  The complexity of differential privacy.  In Tutorials on the Foundations of Cryptography, pages 347–450. Springer, 2017.
  * [Val84] Leslie G Valiant.  A theory of the learnable.  Communications of the ACM, 27(11):1134–1142, 1984.
  * [VC15] Vladimir N Vapnik and A Ya Chervonenkis.  On the uniform convergence of relative frequencies of events to their probabilities.  Measures of complexity: festschrift for alexey chervonenkis, pages 11–30, 2015.
  * [VW97] AW van der Vaart and Jon A Wellner.  Weak convergence and empirical processes with applications to statistics.  Journal of the Royal Statistical Society-Series A Statistics in Society, 160(3):596–608, 1997.

##  Appendix A Preliminaries and Additional Definitions

###  A.1 Preliminaries

##### Probability Theory.

We first review some standard definitions from probability theory.

######  Definition 12 (Coupling).

A coupling of two probability distributions $P$ and $Q$ is a pair of random
variables $(X,Y)$, defined on the same probability space, such that the
marginal distribution of $X$ is $P$ and the marginal distribution of $Y$ is
$Q$.

######  Definition 13 (Integral Probability Metric).

The Integral Probability Metric (IPM) between two probability measures $P$ and
$Q$ over $\mathcal{O}$ is defined as

$d_{\mathcal{F},\mathcal{O}}(P,Q)=\sup_{f\in\mathcal{F}}\left|\int_{\mathcal{O}}fdP-\int_{\mathcal{O}}fdQ\right|=\sup_{f\in\mathcal{F}}\left|\mathop{\bf
E\/}_{x\sim P}[f(x)]-\mathop{\bf E\/}_{x\sim Q}[f(x)]\right|\,,$

where $\mathcal{F}$ is a set of real-valued bounded functions
$\mathcal{O}\to\mathbb{R}$.

IPM distance measures are symmetric and non-negative. Note that the KL-
divergence is not a special case of IPM, rather it belongs to the family of
$f$-divergences, that intersect with IPM only at the TV distance. Such
measures were recently used in order to derive PAC-Bayes style generalization
bounds [AEMM22]. The definition of an $f$-divergence will not be useful in
this work and we refer the interested reader to e.g., [SV16].

##### Learning Theory.

We next review some standard definitions in statistical learning theory. We
start with the definition of the Littlestone dimension [Lit88].

######  Definition 14 (Littlestone Dimension [Lit88]).

Consider a complete binary tree $T$ of depth $d+1$ whose internal nodes are
labeled by points in $\mathcal{X}$ and edges by $\\{0,1\\}$, when they connect
the parent to the right, left child, respectively. We say that
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ Littlestone-shatters $T$ if for
every root-to-leaf path $x_{1},y_{1},\ldots,x_{d},y_{d},x_{d+1}$ there exists
some $h\in\mathcal{H}$ such that $h(x_{i})=y_{i},1\leq i\leq d$. The
Littlestone dimension is denoted by $\mathrm{Ldim}(\mathcal{H})$ is defined to
be the largest $d$ such that $\mathcal{H}$ Littlestone-shatters such a binary
tree of depth $d+1$. If this happens for every $d\in\mathbb{N}$ we say that
$\mathrm{Ldim}(\mathcal{H})=\infty$.

We work under the well-known PAC learning model that was introduced in
[Val84]. Let us denote the misclassification probability of a classifier $h$
by $\mathrm{err}_{\mathcal{D}}(h)=\mathop{\bf
Pr\/}_{(x,y)\sim\mathcal{D}}[h(x)\neq y]$. Also, we say that $\mathcal{D}$ is
realizable with respect to $\mathcal{H}$ if there exists some
$h^{*}\in\mathcal{H}$ such that $\mathrm{err}_{\mathcal{D}}(h^{*})=0.$ Below,
we slightly abuse notation and use the misclassification probability for
distributions over classifiers.

######  Definition 15 (PAC Learnability [Val84, SSBD14]).

An algorithm $A$ is $n$-sample $(\alpha,\beta)$-accurate for a hypothesis
class $\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ if, for any realizable
distribution $\mathcal{D}$, it holds that $\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n}}\left[\mathrm{err}_{\mathcal{D}}(A(S))>\alpha\right]\leq\beta\,.$
A hypothesis class $\mathcal{H}$ is PAC learnable if, for any
$\alpha,\beta\in(0,1)^{2}$, there exist some
$n_{0}(\alpha,\beta)\in\mathbb{N}$ and an algorithm $A$ such that $A$ is
$n$-sample $(\alpha,\beta)$-accurate for $\mathcal{H},$ for any $n\geq
n_{0}(\alpha,\beta).$

For the purposes of this work, an algorithm $A$ should be thought of as a
mapping from samples to a _distribution_ over hypotheses. We want to design
algorithms that satisfy two desiderata: they are PAC learners for some given
hypothesis class $\mathcal{H}$ and they are total variation indistinguishable.
In particular, we consider the following learning setting combining Definition
4 and 15.

######  Definition 16 (Realizable Learnability by TV Indistinguishable
Learner).

An algorithm $A$ is $n$-sample $(\alpha,\beta)$-accurate $\rho$-$\mathrm{TV}$
indistinguishable for a hypothesis class
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ if, for any realizable
distribution $\mathcal{D}$, it holds that $(i)$ $A$ is $n$-sample
$\rho$-$\mathrm{TV}$ indistinguishable and $(ii)$ $\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n}}[\mathrm{err}_{\mathcal{D}}(A(S))>\alpha]\leq\beta$.
A hypothesis class $\mathcal{H}$ is learnable by a $\mathrm{TV}$
indistinguishable algorithm if, for any $\alpha,\beta,\rho\in(0,1)$, there
exist some $n_{0}(\alpha,\beta,\rho)\in\mathbb{N}$ and an algorithm $A$ such
that $A$ is $n$-sample $(\alpha,\beta)$-accurate $\rho$-$\mathrm{TV}$
indistinguishable for $\mathcal{H}$ for any $n\geq n_{0}(\alpha,\beta,\rho)$.

In the above definition, $n$ depends on $\alpha,\beta,\rho$ (and
$\mathcal{H}),$ but _not_ on the distribution.

######  Definition 17 (Uniform Convergence Property).

We say that a domain $\mathcal{X}$ and a class
$\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ satisfy the uniform convergence
property if there exists a function $m^{\mathrm{UC}}:(0,1)^{2}\to\mathbb{N}$
such that for any $\varepsilon,\delta\in(0,1)$, and for every distribution
$\mathcal{D}$ over $\mathcal{X}\times\\{0,1\\}$ it holds that if
$S\sim\mathcal{D}^{m}$ and $m\geq m^{\mathrm{UC}}(\varepsilon,\delta)$, it
holds that
$\sup_{h\in\mathcal{H}}|L_{S}(h)-L_{\mathcal{D}}(h)|\leq\varepsilon$, with
probability at least $1-\delta$, where $L_{S}$ (resp. $L_{\mathcal{D}})$ is
the empirical (resp. population) loss.

The fundamental theorem of learning theory [VC15, BEHW89] states that the
uniform convergence property is equivalent to the finiteness of the VC
dimension of $\mathcal{H}.$ However, one needs to make some (standard)
measurability assumptions on $\mathcal{X},\mathcal{H}$ to rule out
pathological cases. For instance, it is known that there classes with VC
dimension $1$ where uniform convergence does not hold [BD15]999We note that
the proof of the existence of such a class holds under the continuum
hypothesis.. It is known that when $\mathcal{H}$ is countable and has finite
VC dimension uniform convergence holds [BM02].

###  A.2 General Definition of Indistinguishability

While in the main body of the paper, we focused on binary classification,
(most of) our proofs extend to general learning problems and so we first
present a general abstract framework.

For general learning tasks, we can view learning rules (or algorithms) as
randomized mappings $A:\mathcal{I}\to\Delta_{\mathcal{O}}$ which take as input
instances from a domain $\mathcal{I}$ and map them to an element of the output
space $\mathcal{O}.$ We assume that there is a distribution $\mu$ on
$\mathcal{I}$ that generates instances.

A second way to view the learning algorithm is via the mapping
$A:\mathcal{I}\times\mathcal{R}\to\mathcal{O}$. Then $A$ takes as input an
instance $I\sim\mu$ and a random string $r\sim\mathcal{R}$ (we use
$\mathcal{R}$ for both the probability space and the distribution)
corresponding to the algorithm’s _internal randomness_ and outputs
$A(I,r)\in\mathcal{O}$. Thus, $A(I)$ is a distribution over $\mathcal{O}$
whose randomness comes from the random variable $r$, while $A(I,r)$ is a
deterministic object.

The space $\Delta_{\mathcal{O}}$ is endowed with some statistical
dissimilarity measure.

######  Definition 18 (Indistinguishability).

Let $\mathcal{I}$ be an input space, $\mathcal{O}$ be an output space and $d$
be some statistical dissimilarity measure. A learning rule $A$ satisfies
$\rho$-indistinguishability with respect to $d$ if for any distribution $\mu$
over $\mathcal{I}$ and two independent instances $I,I^{\prime}\sim\mu$, it
holds that

$\mathop{\bf
E\/}_{I,I^{\prime}\sim\mu}[d\left(A(I),A(I^{\prime})\right)]\leq\rho\,.$

To illustrate the generality of our definition, we now show how we can
instantiate $\mathcal{I},\mathcal{O},\mu,d$ to recover other definitions about
stability of learning algorithms appearing in prior work.

##### Global Stability.

Global stability [BLM20] is a fundamental property of learning algorithms that
was recently used to establish an equivalence between online learnability and
approximate differential privacy in binary classification. We show how we can
recover the definition of global stability. Let us first recall the
definition.

######  Definition 19 (Global Stability [BLM20]).

Let $\mathcal{R}$ be a distribution over random strings. A learning rule A is
$n$-sample $\eta$-globally stable if for any distribution $\mathcal{D}$ there
exists a hypothesis $h_{\mathcal{D}}$ such that

$\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A(S,r)=h_{\mathcal{D}}]\geq\eta\,.$

In order to recover Definition 19 using Definition 18 we let
$(S,r)\in\mathcal{I},\mu=\mathcal{D}^{n}\times\mathcal{R}$ and
$d(A(I,r),A(I^{\prime},r^{\prime}))=\mathbbm{1}_{A(I,r)\neq
A(I^{\prime},r^{\prime})}.$ Thus, we have that

$\displaystyle\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n},r,r^{\prime}\sim\mathcal{R}}[\mathbbm{1}_{A(S,r)\neq
A(S^{\prime},r^{\prime})}]\leq\rho\implies$ $\displaystyle\mathop{\bf
Pr\/}_{S,S^{\prime}\sim\mathcal{D}^{n},r,r^{\prime}\sim\mathcal{R}}[A(S,r)\neq
A(S^{\prime},r^{\prime})]\leq\rho.$

Notice that this gives us a two-sided version of the definition of global-
stability. So far we have established that $\mathop{\bf
Pr\/}_{S,S^{\prime}\sim\mu,r,r^{\prime}\sim\mathcal{R}}[A(S,r)=A(S^{\prime},r^{\prime})]\geq
1-\rho>0.$ Since two independent draws of the random variable $A(S,r)$ are the
same with non-zero probability it means that it must have point masses.
Moreover, there are countably many such point masses. Let
$\mathcal{H}_{m}=\\{h\in\mathcal{H}:\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A(S,r)=h]\\}.$ Then,

$\displaystyle\mathop{\bf
Pr\/}_{S,S^{\prime}\sim\mu,r,r^{\prime}\sim\mathcal{R}}[A(S,r)=A(S^{\prime},r^{\prime})]$
$\displaystyle=\sum_{h\in\mathcal{H}_{m}}\left(\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A(S,r)=h]\right)^{2}$
$\displaystyle\leq\max_{h\in\mathcal{H}_{m}}\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A(S,r)=h]\cdot\sum_{h\in\mathcal{H}_{m}}\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A(S,r)=h]$
$\displaystyle\leq\max_{h\in\mathcal{H}_{m}}\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A(S,r)=h]$
$\displaystyle=\max_{h\in\mathcal{H}}\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A(S,r)=h]$

Thus, by chaining the two inequalities we have established, we get that
$\max_{h\in\mathcal{H}_{m}}\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A(S,r)=h]\geq 1-\rho$, so the
algorithm $A$ satisfies the notion of global stability.

###  A.3 Alternative Definitions of TV Indistinguishability

We now discuss alternative ways to define TV indistinguishability.

####  A.3.1 TV Indistinguishability with Fixed Prior

First, observe that the definition we propose is two-sided in the sense that
we require drawing two sets of i.i.d. samples. A different way to view TV
indistinguishability is by requiring that the output of the algorithm is
close, in TV distance, to some _prior distribution_ , which depends on the
data-generating process $\mathcal{D}$ but is independent of the sample. Notice
that we could introduce a similar one-sided general definition as a second
viewpoint of Definition 1 (named Indistinguishability with Fixed Prior).

######  Definition 20 (TV Indistinguishability with Fixed Prior).

A learning rule $A$ is $n$-sample $\rho$-fixed prior $\mathrm{TV}$
indistinguishable if for any distribution over inputs $\mathcal{D}$, there
exists some prior $\mathcal{P}_{\mathcal{D}}$ such that for
$S\sim\mathcal{D}^{n}$ it holds that

$\mathop{\bf
E\/}_{S\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})]\leq\rho\,.$

Notice that, using the triangle inequality, we can see that this definition is
equivalent to Definition 4, up to a factor of $2.$ Formally, we have the
following result.

######  Lemma 1.

If $A$ is $\rho$-$\mathrm{TV}$ indistinguishable then it is $\rho$-fixed prior
$\mathrm{TV}$ indistinguishable. Conversely, if $A$ is $\rho$-fixed prior
$\mathrm{TV}$ indistinguishable then it is $2\rho$-$\mathrm{TV}$
indistinguishable.

We remark that if $A$ is TV indistinguishable with respect to a distribution
over inputs $\mathcal{D}$, one can show that it is also fixed prior TV
indistinguishable with respect to $\mathcal{D}$ where the fixed prior is equal
to $\mathcal{P}_{\mathcal{D}}=\int_{S}A(S)d(\mathcal{D}^{n})$.

###### Proof.

For the first direction, we let $\mathcal{P}_{S,S^{\prime}}$ be a distribution
with the property that
$d_{\mathrm{TV}}(A(S),\mathcal{P}_{S,S^{\prime}})=d_{\mathrm{TV}}(A(S^{\prime}),\mathcal{P}_{S,S^{\prime}})=d_{\mathrm{TV}}(A(S),A(S^{\prime}))/2$,
e.g., $\mathcal{P}_{S,S^{\prime}}=1/2\cdot(A(S)+A(S^{\prime}))$, for every
$S,S^{\prime}\sim\mathcal{D}^{n}$. We now define $\mathcal{P}_{\mathcal{D}}$
to be the average of $\mathcal{P}_{S,S^{\prime}}$ with respect to the measure
of the product distribution of $S,S^{\prime}.$ We have that

$\displaystyle\mathcal{P}_{\mathcal{D}}$
$\displaystyle=\int_{S,S^{\prime}}\mathcal{D}^{n}(S)\mathcal{D}^{n}(S^{\prime})\frac{A(S)+A(S^{\prime})}{2}dSdS^{\prime}$
$\displaystyle=\int_{T}\left(\mathcal{D}^{n}(T)1\\{S=T\\}\frac{A(T)}{2}\left(\int_{S^{\prime}}\mathcal{D}^{n}(S^{\prime})\right)+\mathcal{D}^{n}(T)1\\{S^{\prime}=T\\}\frac{A(T)}{2}\left(\int_{S}\mathcal{D}^{n}(S)\right)\right)dSdS^{\prime}=$
$\displaystyle=\int_{T}\mathcal{D}^{n}(T)A(T)dT\,.$

This means that $\mathop{\bf
E\/}_{S\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})]=\int_{S}\mathcal{D}^{n}(S)d_{\mathrm{TV}}\left(A(S),\int_{T}\mathcal{D}^{n}(T)A(T)dT\right)dS\leq\rho.$

For the converse, notice that

$\displaystyle\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),A(S^{\prime}))]$
$\displaystyle\leq\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})+d_{\mathrm{TV}}(A(S^{\prime}),\mathcal{P}_{\mathcal{D}})]$
$\displaystyle=\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})]+\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S^{\prime}),\mathcal{P}_{\mathcal{D}})]$
$\displaystyle=2\mathop{\bf
E\/}_{S\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})]$
$\displaystyle\leq 2\rho.$

∎

####  A.3.2 With High Probability TV Indistinguishability

A different direction in which we can extend the definition of total variation
indistinguishability has to do with replacing the expectation with a high-
probability style of bound. We remark that [ILPS22] provide a similar
alternative definition in the context of their work.

######  Definition 21 (High-Probability TV Indistinguishability).

A learning rule $A$ is $n$-sample high-probability $(\eta,\nu)$-$\mathrm{TV}$
indistinguishable if for any distribution $\mathcal{D}$ there exists some
prior $\mathcal{P}_{\mathcal{D}}$ such that

$\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})\leq\eta]\geq
1-\nu\,.$

Notice that in the above definition we have used the fixed prior version of TV
indistinguishability to reduce the number of parameters, but it can also be
stated in its the two-sided version. It is not hard to see that the “in
expectation” and the “with high probability” versions of the definition are
qualitatively equivalent. Moreover, we can establish a quantitative connection
as follows.

######  Lemma 2.

If a learning rule $A$ is an $n$-sample $\rho$-fixed prior $\mathrm{TV}$
indistinguishable learner (cf. Definition 20) then it is an $n$-sample high-
probability $(\rho/\nu,\nu)$-$\mathrm{TV}$ indistinguishable learning rule
(cf. Definition 21), for any $\rho\leq\nu<1$. Conversely, if a learnigng rule
$A$ is an $n$-sample high-probability $(\eta,\nu)$-$\mathrm{TV}$
indistinguishable learner then it is an $n$-sample
$(\eta+\nu-\eta\cdot\nu)$-fixed prior $\mathrm{TV}$ indistinguishable learning
rule.

###### Proof.

The proof of the first part of claim is a direct consequence of Markov’s
inequality. Notice that $d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})$ is
random variable whose expected value is bounded by $\rho$. Thus, we have that

$\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})\geq\rho/\nu]\leq\nu\,.$

Hence, we can see that $A$ is a high-probability $(\rho/\nu,\nu)$-TV
indistinguishable learning rule.

We now move to the second part of the claim. Let $\mathcal{E}$ be the event
that $d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})\geq\eta.$ Then, we have
that

$\displaystyle\mathop{\bf
E\/}_{S\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})]$
$\displaystyle=\mathop{\bf
E\/}_{S\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})|\mathcal{E}]\mathop{\bf
Pr\/}[\mathcal{E}]+\mathop{\bf
E\/}_{S\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),\mathcal{P}_{\mathcal{D}})|\mathcal{E}^{c}]\mathop{\bf
Pr\/}[\mathcal{E}^{c}]$ $\displaystyle\leq 1\cdot\nu+\eta\cdot(1-\nu)$
$\displaystyle=\eta+\nu-\eta\cdot\nu.$

∎

###  A.4 Coupling and Correlated Sampling

Coupling is a fundamental notion in probability theory with many applications
[LP17b]. The correlated sampling problem, which has applications in various
domains, e.g., in sketching and approximation algorithms [Bro97, Cha02], is
described in [BGH+16] as follows: Alice and Bob are given probability
distributions $P$ and $Q$, respectively, over a finite set $\Omega$. _Without
any communication, using only shared randomness_ as the means to coordinate,
Alice is required to output an element $x$ distributed according to $P$ and
Bob is required to output an element $y$ distributed according to $Q$. Their
goal is to minimize the disagreement probability $\mathop{\bf Pr\/}[x\neq y]$,
which is comparable with $d_{\mathrm{TV}}(P,Q)$. Formally, a correlated
sampling strategy for a finite set $\Omega$ with error
$\varepsilon:[0,1]\to[0,1]$ is specified by a probability space $\mathcal{R}$
and a pair of functions $f,g:\Delta_{\Omega}\times\mathcal{R}\to\Omega$, which
are measurable in their second argument, such that for any pair
$P,Q\in\Delta_{\Omega}$ with $d_{\mathrm{TV}}(P,Q)\leq\delta$, it holds that
(i) the push-forward measure $\\{f(P,r)\\}_{r\sim\mathcal{R}}$ (resp.
$\\{g(Q,r)\\}_{r\sim\mathcal{R}}$) is $P$ (resp. $Q$) and (ii) $\mathop{\bf
Pr\/}_{r\sim\mathcal{R}}[f(P,r)\neq g(Q,r)]\leq\varepsilon(\delta)$. We
underline that a correlated sampling strategy is _not_ the same as a coupling,
in the sense that the latter requires a single function
$h:\Delta_{\Omega}\times\Delta_{\Omega}\to\Delta_{\Omega\times\Omega}$ such
that for any $P,Q$, the marginals of $h(P,Q)$ are $P$ and $Q$ respectively. It
is known that for any coupling function $h$, it holds that $\mathop{\bf
Pr\/}_{(x,y)\sim h(P,Q)}[x\neq y]\geq d_{\mathrm{TV}}(P,Q)$ and that this
bound is attainable. Since $\\{(f(P,r),g(Q,r))\\}_{r\sim\mathcal{R}}$ induces
a coupling, it holds that $\varepsilon(\delta)\geq\delta$ and, perhaps
surprisingly, there exists a strategy with
$\varepsilon(\delta)\leq\frac{2\delta}{1+\delta}$ [Bro97, KT02, Hol07] and
this result is tight [BGH+16]. A second difference between coupling and
correlated sampling has to do with the size of $\Omega$: while correlated
sampling strategies can be extended to infinite spaces $\Omega,$ it remains
open whether there exists a correlated sampling strategy for general measure
spaces $(\Omega,\mathcal{F},\mu)$ with any non-trivial error bound [BGH+16].
On the other hand, coupling applies to spaces $\Omega$ of any size.

[GKM21] studied user-level privacy and introduced the notion of pseudo-global
stability, which is essentially the same as replicability as observed by
[ILPS22]. [GKM21] showed that pseudo-global stability is qualitatively
equivalent to approximate differential privacy. Their main technique was the
use of correlated sampling that allowed users to output the same learned
hypothesis (stability) employing shared randomness. We mention that [GKM21]
provide their results for finite outcome space (i.e., $\mathcal{X}$ is finite
and thus $\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$ is too). In particular,
they need finiteness of the domain in order to apply correlated sampling which
is used during their “DP implies pseudo-global stability” reduction. They
mention that their results can be extended to the case where $\mathcal{X}$ is
infinite and that this does require non-trivial generalization of tools such
as correlated sampling and some measure-theoretic details to that
setting101010To be more specific, the proof of Theorem 20 in [GKM21] requires
to define the correlated sampling strategy over the space $2^{\mathcal{X}}$ a
priori (independently of the observed samples and input algorithm). Hence
while the strategy is applied to distributions with finite support, an
extension to infinite domain in that proof would require some modifications.;
we refer to a discussion in Section 5.3 of [BGH+16] about the assumptions
needed in order to achieve correlated sampling in infinite spaces. Similarly,
the last step of the constructive transformation of a DP algorithm to a
replicable one provided in [BGH+23] uses correlated sampling and is hence also
given for finite domains. For further comparisons between our coupling and the
correlated sampling problem of [BGH+16], we refer to the discussion in [AS19]
after Corollary 4.

A very useful tool for our derivations is a coupling protocol that can be
found in [AS19].

######  Theorem 8 (Pairwise Optimal Coupling [AS19]).

Let $\mathcal{S}$ be any collection of random variables that are absolutely
continuous with respect to a common probability measure111111This result
extends to the setting where $\mu$ is a $\sigma$-finite measure, but it is not
needed for the purposes of our work. $\mu.$ Then, there exists a coupling of
the variables in $\mathcal{S}$ such that, for any $X,Y\in\mathcal{S}$,

$\mathop{\bf Pr\/}[X\neq
Y]\leq\frac{2d_{\mathrm{TV}}(X,Y)}{1+d_{\mathrm{TV}}(X,Y)}\,.$

Moreover, this coupling requires sample access to a Poisson point process with
intensity $\mu\times\mathrm{Leb}\times\mathrm{Leb}$, where $\mathrm{Leb}$ is
the Lebesgue measure over $\mathbbm{R}_{+},$ and full access to the densities
of all the random variables in $\mathcal{S}$ with respect to $\mu.$

An intuitive illustration of how it works can be found in Figure 1.

###  A.5 Discussion on Definition 4

We discuss more extensively the TV Indistinguishability definition. One
important motivation for the definition of TV indistinguishability is to show
that replicability can be equivalently defined using the same high-level
template like the well-studied PAC-Bayes framework, where one shows that the
outputs of the algorithms are close, under the KL divergence, with some data-
independent priors. In other words, our results show how to organize and view
different well-studied notions of stability using the same template.

Moreover, an interpretation of the replicability definition is that two
executions of the algorithm over independent datasets should be coupled using
just shared internal randomness. However, this is one of potentially infinite
ways to couple the two executions. Our definition, which we find quite
natural, captures exactly this observation and allows for general couplings
between two random runs. It is also worth noting that, to the best of our
knowledge, all the notions of algorithmic stability that have been proposed in
the past do not depend on the source of internal randomness of the algorithm.
However, this is not the case with replicability.

Let us now present a concrete algorithm whose stability property is easier to
prove under the new definition. [GKM21] presented a procedure that transforms
a list-globally stable algorithm to a replicable one (Algorithm 1, page 9 in
[GKM21]). Crucially, in the last step of this algorithm the authors use a
correlated sampling procedure to prove the replicability property. This
procedure induces a computational overhead to the overall algorithm, and it is
not clear even if it is computable beyond finite domains. On the other hand,
the TV indistinguishability property is immediate. Thus, the transformation
from list-global stability to TV indistinguishability is computationally
efficient and holds for general domains whereas the transformation from list-
global stability to replicability is not.

To the best of our knowledge, most of the replicable algorithms that have been
developed use their internal randomness over data-independent distributions.
To make this point more clear let us consider the replicable SQ oracle of
[ILPS22]. In this work, the authors use randomness over distributions that are
independent of the input sample $S$. Thus, no matter how the internal
randomness is implemented, when one shares it across two executions the
internal random choices of the algorithm are the same.

However, there are algorithms, like Algorithm 1 in [GKM21], that use internal
randomness over a data-dependent distribution. If the algorithm makes random
choices over data-dependent quantities like in [GKM21], when one shares the
randomness across two executions the internal random choices are not
necessarily the same even if the TV distance between the two distributions is
small, unless one specifies carefully the source of internal randomness (i.e.,
using some coupling). This can lead to significant computational overhead when
the domain is finite, computability issues when the domain is countable, and
for general domains it is not clear yet that going from TV
indistinguishability to replicability is possible. Hence, one advantage of TV
indistinguishability is that it provides a relaxation over the stronger
definition of replicability, which is the notion that our definition builds
upon.

##  Appendix B Useful Replicable Subroutines

In this section we present various replicable subroutines that will be useful
in the derivation of our results.

###  B.1 Replicability Preliminaries

Recall the Statistical Query (SQ) model that was introduced by [Kea98] and is
a restriction of the PAC learning model, appearing in various learning theory
contexts [BKW03, GHRU11, CKMY20, GGK20, FKKT21]. In the SQ model, the learner
interacts with an oracle in the following way: the learner submits a
statistical query to the oracle and the oracle returns its expected value,
after adding some noise to it. More formally, we have the following
definition.

######  Definition 22 ([Kea98]).

Let $\tau,\delta\in(0,1)^{2},\mathcal{D}$ be a distribution over the domain
$\mathcal{X}$ and $\phi:\mathcal{X}\rightarrow[0,1]$ be a query. Let $S$ be an
i.i.d. sample of size $n=n(\tau,\delta).$ Then, the statistical query oracle
outputs a value $v$ such that $|v-\mathop{\bf
E\/}_{x\sim\mathcal{D}}[\phi(x)]|\leq\tau,$ with probability at least
$1-\delta.$

Essentially, using a large enough number of samples, the SQ oracle returns an
approximation of the expected value of a statistical query whose range is
bounded. [ILPS22] provide a replicable implementation of an SQ oracle with a
mild blow-up in the sample complexity.

######  Theorem 9 (Replicable SQ Learner [ILPS22]).

Let $\tau,\delta,\rho\in(0,1)^{3},\delta\leq\rho/3,\mathcal{D}$ be a
distribution over some domain $\mathcal{X}$, and
$\phi:\mathcal{X}\rightarrow[0,1]$ be a query. Let $S$ be an i.i.d. sample of
size

$n=O\left(\frac{1}{\tau^{2}\rho^{2}}\log(1/\delta)\right)\,.$

Then there exists a $\rho$-replicable SQ oracle for $\phi.$

The interpretation of the previous theorem is that we can estimate replicably
statistical queries whose range is bounded.

The following result that was proved in [ILPS22] is useful for our
derivations.

######  Claim 2 ($\rho$-Replicability $\implies(\eta,\nu)$-Replicability
[ILPS22]).

Let $A$ be a $\rho$-replicable algorithm and $\mathcal{R}$ be its source of
randomness. Then for any $\nu\in[\rho,1)$, it holds that

$\mathop{\bf Pr\/}_{r\sim\mathcal{R}}\left[\left\\{\exists
h\in\mathcal{H}:\mathop{\bf Pr\/}_{S\sim\mathcal{D}^{n}}[A(S,r)=h]\geq
1-\frac{\rho}{\nu}\right\\}\right]\geq 1-\nu\,.$

Notice that in the definition of replicability (Definition 2), the learner
shares all the internal random bits across its two executions. A natural
extension is to consider learners that share only _part_ of their random bits,
i.e., they have access to private random bits that are not shared across its
executions and public random bits that are shared. A result in [ILPS22] shows
that these learners are, essentially, equivalent to the ones that use only
private bits. To be more precise, we say that a learner $A$ is
$\rho$-replicable with respect to $r_{pub}$ if

$\mathop{\bf
Pr\/}_{S,S^{\prime}\sim\mathcal{D}^{n},r_{priv},r_{priv}^{\prime},r_{pub}\sim\mathcal{R}}[A(S,r_{priv},r_{pub})=A(S^{\prime},r^{\prime}_{priv},r_{pub})]\geq
1-\rho\,.$

The following result states this property formally.

######  Lemma 3 (Public, Private Replicability $\implies$ Replicability
[ILPS22]).

Let $A$ be an $n$-sample $\rho$-replicable learner with respect to $r_{pub}$.
Then, $A$ is a $n$-sample $\rho$-replicable learner with respect to
$(r_{pub},r_{priv}).$

This result allows us to think of a replicable learner as having access to two
different sources of randomness, one that is private to its execution and one
that is shared across the executions. We will make use of it in
transformations from DP learners to replicable learners and some boosting
results.

###  B.2 Replicable Heavy-Hitters

In the analysis of the replicable heavy-hitter algorithm (cf. Algorithm 1) we
will use the Bretagnolle-Huber-Carol inequality that bounds the estimation
error of the parameters of a multinomial distribution from samples.

######  Lemma 4 (Bretagnolle-Huber-Carol Inequality [VW97]).

Let $p=(p_{1},\ldots,p_{k})$ multinomial distribution supported on $k$
elements. Then, given access to $n$ i.i.d. samples from $p$ we have that

$\mathop{\bf
Pr\/}\left[\sum_{i=1}^{k}|\hat{p}_{i}-p_{i}|\geq\varepsilon\right]\leq
2^{k}e^{-n\varepsilon^{2}/2}\,,$

for every $\varepsilon\in(0,1),$ where $\hat{p}_{i}$ is the empirical
frequency of item $i$ in the sample $S.$

The replicable heavy-hitters algorithm is depicted in Algorithm 1. As we
alluded before, this approach is very similar to [GKM21, ILPS22]. However, in
our approach we treat the confidence parameter and the reproducibility
parameters differently. Moreover, since we make use of Lemma 4, we are able to
reduce the sample complexity of the algorithm.

Algorithm 1 Replicable Heavy-Hitters

1:Input: Sample access to a distribution $\mathcal{D}$ over some domain
$\mathcal{X}$

2:Parameters: Threshold $v$, error $\varepsilon$, confidence $\delta$,
replicability $\rho$

3:Output: List of elements $L$ in $\mathcal{X}$

4:$n_{1}\leftarrow\frac{\log\left(2/(\min\\{\delta,\rho\\}(v-\varepsilon))\right)}{v-\varepsilon}$

5:$S_{1}\leftarrow n_{1}$ i.i.d. samples. from $\mathcal{D}$

6:$\mathcal{X}_{h}\leftarrow$ unique elements of $S_{1}$ $\triangleright$
Notice that $|\mathcal{X}_{h}|\leq n_{1}.$

7:$n_{2}\leftarrow\frac{32\left(\ln(2/\min\\{\delta,\rho\\})+|\mathcal{X}|+1\right)}{\rho^{2}\varepsilon^{2}}$

8:$S_{2}\leftarrow n_{2}$ i.i.d. samples from $\mathcal{D}$

9:$\hat{p}_{x}\leftarrow\mathrm{freq}_{S}(x),\forall x\in\mathcal{X}_{h}$
$\triangleright$ $\hat{p}_{x}$ is the empirical frequency of every potential
heavy hitter

10:$v^{\prime}\leftarrow U[v-\varepsilon/2,v+\varepsilon/2]$ $\triangleright$
Set the threshold for acceptance of a heavy-hitter.

11:$L\leftarrow\\{x\in\mathcal{X}_{h}:\hat{p}_{x}\geq v^{\prime}\\}$
$\triangleright$ Drop the elements of $\mathcal{X}_{h}$ that fall below the
threshold.

12:Output $L$

######  Lemma 5.

Let $\mathcal{D}$ be distribution supported on some domain $\mathcal{X}$ and
denote by $\mathcal{D}(x)$ the mass that it puts on $x\in\mathcal{X}$. For any
$\varepsilon,\delta,\rho,v\in(0,1)^{4}$ such that
$(v-\varepsilon,v+\varepsilon)\subseteq(0,1)$, Algorithm 1 is
$\rho$-replicable and outputs a list $L$ such that, with probability
$1-\delta$, for all $x\in\mathcal{X}$:

  * •

If $\mathcal{D}(x)<v-\varepsilon$ then $x\notin L.$

  * •

If $\mathcal{D}(x)>v+\varepsilon$ then $x\in L.$

Its sample complexity is at most
$O\left(\frac{\log(1/(\min\\{\delta,\rho\\}(v-\varepsilon)))}{(v-\varepsilon)\rho^{2}\varepsilon^{2}}\right).$

###### Proof.

We first prove the correctness of the algorithm with the desired accuracy
$\varepsilon$ and confidence $\delta$. For simplicity, let us assume that
$\delta\leq\rho/4.$ Otherwise, we can simply set $\delta=\rho/4$. After we
pick $n_{1}$ points, the probability that a $(v-\varepsilon)$-heavy-hitter of
the distribution is not included in $S_{1}$ is at most

$(1-(v-\varepsilon))^{n_{1}}\leq e^{-(v-\varepsilon)\cdot
n_{1}}\leq\frac{\delta\cdot(v-\varepsilon)}{2}\,.$

Since there are at most $1/(v-\varepsilon)$ such heavy-hitters, we can see
that with probability at least $\delta/2$ all of the are included in $S_{1}.$
Let us call this event $\mathcal{E}_{1}$ and condition on it for the rest of
the proof.

Let us consider a distribution $\widehat{\mathcal{D}}$ that puts the same mass
on every element of $\mathcal{X}_{h}$ as $\mathcal{D}$ and the remaining mass
on a new special element $e.$ We can sample from $\widehat{\mathcal{D}}$ in
the following way: we draw a sample from $\mathcal{D}$ and if it falls in
$\mathcal{X}_{h}$ we return it, otherwise we return $e$. Thus, we can see that
if we draw $n$ samples from $\widehat{\mathcal{D}}$, they are distributed
according to a multinomial distribution supported on
$\mathcal{X}_{h}\cup\\{e\\}$. Thus, Lemma 4 applies to this setting which
means that if we draw $n_{2}$ i.i.d. samples from $\widehat{\mathcal{D}}$ we
have that

$\mathop{\bf
Pr\/}\left[\sum_{i=1}^{k}|\hat{p}_{i}-p_{i}|\geq\frac{\varepsilon\rho}{4}\right]\leq
2^{k}e^{-n_{2}\varepsilon^{2}\rho^{2}/32}\leq
e^{k}e^{-n_{2}\varepsilon^{2}\rho^{2}/32}=e^{k-n_{2}\varepsilon^{2}\rho^{2}/32}\,,$

where $k=|\mathcal{X}_{h}|+1.$ Thus,
$e^{k-n_{2}\varepsilon^{2}\rho^{2}/32}=e^{-\ln(2/\delta)}\leq\frac{\delta}{2}.$
We call this event $\mathcal{E}_{2}$ and condition on it for the rest of the
proof. Notice that under this event we have that
$|\hat{p}_{x}-p_{x}|\leq\frac{\varepsilon\rho}{4}<\frac{\varepsilon}{2},\forall
x\in\mathcal{X}_{h}.$ Since $v^{\prime}\geq v-\varepsilon/2$ it means that if
$\hat{p}_{x}\geq v^{\prime}\geq v-\varepsilon/2\implies
p_{x}+\varepsilon/2>v-\varepsilon/2\implies p_{x}>v-\varepsilon.$ Similarly,
we get that if $\hat{p}_{x}<v^{\prime}\implies p_{x}<v+\varepsilon.$ Hence, we
see that the algorithm is correct with probability at least
$1-\delta/2-\delta/2=1-\delta.$ This concludes the correctness proof.

We now focus on the replicability of the algorithm. Let $\mathcal{X}_{h}^{1}$
be the unique elements at 6 of the algorithm in the first run and
$\mathcal{X}_{h}^{2}$ in the second run. Notice that if
$x\in(\mathcal{X}_{h}^{1}\setminus\mathcal{X}_{h}^{2})\cup(\mathcal{X}_{h}^{2}\setminus\mathcal{X}_{h}^{1})$
then, with probability at least $1-\delta/2-\delta/2=1-\delta$, the element
$x$ is not a $(v-\varepsilon)$-heavy-hitter, so, with probability at least
$1-\delta/2$, it will not be included in the output of the execution that it
appears in. Let $E=\mathcal{X}_{h}^{1}\cap\mathcal{X}_{h}^{2}$ and denote by
$L_{1},L_{2},$ the outputs of the first, second execution, respectively. We
need to bound the probability of the event $\mathcal{E}=\\{\exists x\in E:x\in
L_{1}\setminus L_{2}\cup L_{2}\setminus L_{1}\\}.$ Let
$\hat{p}_{x}^{1},\hat{p}_{x}^{2}$ the empirical frequencies of $x$ in the
first, second execution, respectively. Due to the concentration inequality we
have used, we have that

$\sum_{x\in\mathcal{X}_{1}\cap\mathcal{X}_{2}}|\hat{p}^{i}_{x}-p_{x}|\leq\frac{\varepsilon\rho}{4},i\in\\{1,2\\}\,,$

with probability at least $1-\delta.$ Under this event, using the triangle
inequality, this means that

$\sum_{x\in\mathcal{X}_{1}\cap\mathcal{X}_{2}}|\hat{p}^{1}_{x}-\hat{p}^{2}_{x}|\leq\frac{\varepsilon\rho}{2},i\in\\{1,2\\}\,,$

Notice that since pick a number uniformly at random from an interval with
range $\varepsilon,$ for some given $x\in\mathcal{X}_{1}\cap\mathcal{X}_{2}$,
we have that $\mathop{\bf Pr\/}[x\in L_{1}\setminus L_{2}\cup L_{2}\setminus
L_{1}]\leq|\hat{p}_{x}^{1}-\hat{p}_{x}^{2}|/\varepsilon.$ Thus, taking a union
bound over $x\in\mathcal{X}_{1}\cap\mathcal{X}_{2}$, we see that

$\mathop{\bf
Pr\/}[\mathcal{E}]\leq\frac{\sum_{x\in\mathcal{X}_{1}\cap\mathcal{X}_{2}}|\hat{p}^{1}_{x}-\hat{p}^{2}_{x}|}{2\varepsilon}\leq\frac{\varepsilon\rho}{2\varepsilon}=\frac{\rho}{2}\,.$

Putting everything together, we see that the probability that the two outputs
of the algorithm differ is at most $\delta+\delta/2+\rho/2<\rho.$ ∎

###  B.3 Replicable Agnostic PAC Learner for Finite $\mathcal{H}$

In this section we present a replicable agnostic PAC learner for finite
hypothesis classes, i.e., a learner whose output is a hypothesis that has
error rate close to the best one in the class. Our construction relies on the
replicable SQ oracle from [ILPS22] (see Theorem 9). The idea is simple: since
the error rate of every $h\in\mathcal{H}$ can be replicably estimated using
Theorem 9, we do that for every $h\in\mathcal{H}$ and then we return the one
that has the smallest estimated value.

Algorithm 2 Replicable Agnostic Learner for Finite $\mathcal{H}$

1:Input: Hypothesis class $\mathcal{H}$, sample access to a distribution
$\mathcal{D}$ over $\mathcal{X}\times\\{0,1\\}$

2:Parameters: accuracy $\varepsilon$, confidence $\delta$, replicability
$\rho$

3:Output: Classifier $h$ that is $\varepsilon$-close to the best one in
$\mathcal{H}$ and its estimated error on $\mathcal{D}$

4:$\hat{\alpha}_{h}\leftarrow\mathrm{ReprErrorEst}(\varepsilon/2,\delta/|\mathcal{H}|,\rho/|\mathcal{H}|),\forall
h\in\mathcal{H}$ $\triangleright$ Theorem 9.

5:$\hat{h}^{*}\leftarrow\arg\min_{h\in\mathcal{H}}\hat{a}_{h}$
$\triangleright$ Break ties arbitrarily in a consistent manner.

6:Output $(\hat{h}^{*},\hat{\alpha}_{\hat{h}^{*}})$

It is not hard to see that Algorithm 2 is $\rho$-replicable and returns a
hypothesis whose error is $\varepsilon$-close to the best one.

######  Claim 3.

Let $\mathcal{H}$ be a finite hypothesis class and
$\varepsilon,\delta,\rho\in(0,1)^{3}$. Given
$O\left(\frac{|\mathcal{H}|^{3}}{\varepsilon^{2}\rho^{2}}\log\left(\frac{|\mathcal{H}|}{\delta}\right)\right)$
i.i.d. samples from $\mathcal{D}$, Algorithm 2 is $\rho$-replicable and
returns a classifier $\hat{h}^{*}$ with
$\mathrm{err}(\hat{h}^{*})<\min_{h\in\mathcal{H}}\mathrm{err}(h)+\varepsilon$,
with probability at least $1-\delta.$

###### Proof.

The replicability of the algorithm follows from the fact that we estimate each
$\hat{a}_{h}$ replicably with parameter $\rho/|\mathcal{H}|$ and we make
$|\mathcal{H}|$ such calls.

Notice that for each call to the replicable error estimator we need
$n_{h}=O\left(\frac{|\mathcal{H}|^{2}}{\varepsilon^{2}\rho^{2}}\log\left(\frac{|\mathcal{H}|}{\delta}\right)\right)$
samples and we make $|\mathcal{H}|$ such calls.

Since the accuracy parameter of the statistical query oracle is
$\varepsilon/2$, using the triangle inequality, we have that
$|\hat{a}_{\hat{h}^{*}}-\min_{h\in\mathcal{H}}a_{h}|\leq\varepsilon.$

Finally, the correctness of the algorithm follows from a union bound over the
correctness of every call to the oracle. ∎

##  Appendix C TV Indistinguishability and Replicability

In this section, we will study the connection between TV indistinguishability
and replicability.

###  C.1 The Proof of Theorem 2

We are now ready to establish the connection between TV indistinguishability
and replicability. The upcoming result is particularly useful because it
provides a _data-independent_ way to couple the random variables.

###### Proof of Theorem 2.

Let $\mathcal{R}$ be Poisson point process with intensity
$\mathcal{P}\times\mathrm{Leb}\times\mathrm{Leb}$, where $\mathrm{Leb}$ is the
Lebesgue measure over $\mathbb{R}_{+}$ (cf. Theorem 8, Figure 1). The learning
rule $A^{\prime}$ is defined in the following way. For every
$S\in(\\{\mathcal{X}\times\\{0,1\\})^{n}$, let
$r=\\{(h_{i},y_{i},t_{i})\\}_{i\in\mathbb{N}}$ be an infinite sequence of the
Poisson point process $\mathcal{R}$ and let
$j=\arg\min_{i\in\mathbb{N}}\\{t_{i}:f_{S}(h_{i})>y_{i}\\}$. The output of
$A^{\prime}$ is $h_{j}$ and we denote it by $A^{\prime}(S,r)$. We will shortly
explain why this is well-defined, except for a measure zero event. The fact
that $A^{\prime}$ is equivalent to $A$ follows from the coupling guarantees of
this process (cf. Theorem 8). In particular, we can instantiate this result
with the single random variable $\\{A(S)\\}$. We can now observe that, except
for a measure zero event, (i) since $A$ is absolutely continuous with respect
to $\mathcal{P}$, there exists such a density $f_{S}$, (ii) the set over which
we are taking the minimum is not empty, (iii) the minimum is attained at a
unique point. This means that $A^{\prime}$ is well-defined, except for a
measure zero event121212Under the measure zero event that at least one of
these three conditions does not hold, we let $A^{\prime}(S,r)$ be some
arbitrary classifier., and, by the correctness of the rejection sampling
process [AS19], $A^{\prime}(S)$ has the desired probability distribution.

We now prove that $A^{\prime}$ is replicable. Since $A$ is
$\rho$-$\mathrm{TV}$ indistinguishable, it follows that

$\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A(S),A(S^{\prime}))]\leq\rho.$

We have shown that $A^{\prime}$ is equivalent to $A$, so we can see that
$\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}[d_{\mathrm{TV}}(A^{\prime}(S),A^{\prime}(S^{\prime}))]\leq\rho$.
Thus, using the guarantees of Theorem 8, we have that for any datasets
$S,S^{\prime}$

$\mathop{\bf Pr\/}_{r\sim\mathcal{R}}[A^{\prime}(S,r)\neq
A^{\prime}(S^{\prime},r)]\leq\frac{2d_{\mathrm{TV}}(A^{\prime}(S),A^{\prime}(S^{\prime}))}{1+d_{\mathrm{TV}}(A^{\prime}(S),A^{\prime}(S^{\prime}))}\,.$

By taking the expectation over $S,S^{\prime}$, we get that

$\displaystyle\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}\left[\mathop{\bf
Pr\/}_{r\sim\mathcal{R}}[A^{\prime}(S,r)\neq A^{\prime}(S^{\prime},r)]\right]$
$\displaystyle\leq\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}\left[\frac{2d_{\mathrm{TV}}(A^{\prime}(S),A^{\prime}(S^{\prime}))}{1+d_{\mathrm{TV}}(A^{\prime}(S),A^{\prime}(S^{\prime}))}\right]$
$\displaystyle\leq\frac{2\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}\left[d_{\mathrm{TV}}(A^{\prime}(S),A^{\prime}(S^{\prime}))\right]}{1+\mathop{\bf
E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}\left[d_{\mathrm{TV}}(A^{\prime}(S),A^{\prime}(S^{\prime}))\right]}$
$\displaystyle\leq\frac{2\rho}{1+\rho},$

where the first inequality follows from Theorem 8 and taking the expectation
over $S,S^{\prime}$, the second inequality follows from Jensen’s inequality,
and the third inequality follows from the fact that $f(x)=2x/(1+x)$ is
increasing. Now notice that since the source of randomness $\mathcal{R}$ is
independent of $S,S^{\prime}$, we have that

$\mathop{\bf E\/}_{S,S^{\prime}\sim\mathcal{D}^{n}}\left[\mathop{\bf
Pr\/}_{r\sim\mathcal{R}}[A^{\prime}(S,r)\neq
A^{\prime}(S^{\prime},r)]\right]=\mathop{\bf
Pr\/}_{S,S^{\prime}\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A^{\prime}(S,r)\neq
A^{\prime}(S^{\prime},r)]\,.$

Thus, we have shown that

$\mathop{\bf
Pr\/}_{S,S^{\prime}\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A^{\prime}(S,r)\neq
A^{\prime}(S^{\prime},r)]\leq\frac{2\rho}{1+\rho}\,,$

so the algorithm $A^{\prime}$ is $n$-sample $\frac{2\rho}{1+\rho}$-replicable,
which concludes the proof. ∎

###  C.2 A General Equivalence Result

In this section, we focus on the following two stability/replicability
definitions.

######  Definition 23 (Replicability [ILPS22]).

Let $\mathcal{R}$ be a distribution over random strings. A learning rule $A$
is $\rho$-replicable if for any distribution $\mu$ over $\mathcal{I}$ and two
independent instances $I,I^{\prime}\sim\mu$ it holds that

$\mathop{\bf Pr\/}_{I,I^{\prime}\sim\mu,r\sim\mathcal{R}}[A(I,r)\neq
A(I^{\prime},r)]\leq\rho\,.$

######  Definition 24 (Total Variation Indistinguishability).

A learning rule $A$ is $\rho$-$\mathrm{TV}$ indistinguishable if for any
distribution $\mu$ and two independent instances $I,I^{\prime}\sim\mu$ it
holds that

$\mathop{\bf
E\/}_{I,I^{\prime}\sim\mu}[d_{\mathrm{TV}}(A(I),A(I^{\prime}))]\leq\rho\,.$

A learning rule $A$ is $\rho$-fixed prior $\mathrm{TV}$ indistinguishable if
for any distribution $\mu$, there exists some prior $\mathcal{P}_{\mu}$ such
that for $I\sim\mu$ it holds that

$\mathop{\bf
E\/}_{I\sim\mu}[d_{\mathrm{TV}}(A(I),\mathcal{P}_{\mu})]\leq\rho\,.$

######  Definition 25 (Pseudo-Global Stability).

Let $\mathcal{R}$ be a distribution over random strings. A learning rule $A$
is said to be $(\eta,\nu)$-pseudo-globally stable if for any distribution
$\mu$ there exists an element $o_{r}\in\mathcal{O}$ for every
$r\in\mathrm{supp}(\mathcal{R})$ (depending on $\mu$) such that

$\mathop{\bf Pr\/}_{r\sim\mathcal{R}}\left[\mathop{\bf
Pr\/}_{I\sim\mu}[A(I,r)=o_{r}]\geq\eta\right]\geq\nu\,.$

Our general equivalence result follows.

######  Proposition 2 (TV Indistinguishability $\equiv$ Replicability).

Let $\mathcal{I}$ be an input space and $\mathcal{O}$ be an output space.

  * •

If a learning rule $A$ is $\rho$-replicable, then it is also
$\rho$-$\mathrm{TV}$ indistinguishable.

  * •

Consider a prior distribution $\mathcal{P}$ over $\mathcal{O}$. Consider a
learning rule $A$ that is $\rho$-$\mathrm{TV}$ indistinguishable and
absolutely continuous with respect to $\mathcal{P}$. Then, there exists a
learning rule $A^{\prime}$ that is equivalent to $A$ and $A^{\prime}$ is
$2\rho/(1+\rho)$-replicable.

We remark that one can adapt the proofs of Theorem 1 and Theorem 2 by setting
$\mathcal{I}=(\mathcal{X}\times\\{0,1\\})^{n}$, $\mu=\mathcal{D}^{n}$ and
$\mathcal{O}=\\{0,1\\}^{\mathcal{X}}$. Moreover, when $\mathcal{I}$ is
countable, the design of the reference probability measure works in a similar
way. Hence, we get the following corollary.

######  Corollary 4.

Let $\mathcal{I}$ be a countable domain and let $A$ be a learning rule that is
$\rho$-$\mathrm{TV}$ indistinguishable. Then, there exists a
$\frac{2\rho}{1+\rho}$-replicable learning rule $A^{\prime}$ that is
equivalent to $A.$

##  Appendix D TV Indistinguishability and Differential Privacy

###  D.1 DP Preliminaries

We introduce some standard tools from the DP literature. We start with the
Stable Histograms algorithm [KKMN09, BNS16b]. Let $\mathcal{X}$ be some domain
and let $S\in\mathcal{X}^{n}$ be a (multi)set of its elements. We denote by
$\text{freq}_{S}(x)=\frac{1}{n}\cdot|\\{i\in[n]:x_{i}=x\\}|,$ i.e., the
fraction of times that $x$ appears in $S.$ The following result holds. It
essentially allows us to privately publish a short list of elements that
appear with high frequency in a dataset.

######  Lemma 6 (Stable Histograms [KKMN09, BNS16b]).

Let $\mathcal{X}$ be some domain. For

$n\geq O\left(\frac{\log(1/(\eta\beta\delta))}{\eta\varepsilon}\right)$

there exists an $(\varepsilon,\delta)$-differentially private algorithm
StableHist which, with probability at least $1-\beta,$ on input
$S=(x_{1},\ldots,x_{n})\in\mathcal{X}^{n}$, outputs a list
$L\subseteq\mathcal{X}$ and a sequence of estimates $a\in[0,1]^{|L|}$ such
that

  * •

Every $x$ with $\mathrm{freq}_{S}(x)\geq\eta$ appears in $L$.

  * •

For every $x\in L,$ the estimate $a_{x}$ satisfies
$|a_{x}-\mathrm{freq}_{S}(x)|\leq\eta.$

We also recall the agnostic private learner for finite classes that was
proposed in [KLN+11] and is based on the Exponential Mechanism of [MT07].

######  Lemma 7 (Generic Private Learner [KLN+11]).

Let $\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$. There is an
$(\varepsilon,0)$-differentially private algorithm GenPrivLearner which given

$n=O\left(\log(|\mathcal{H}|/\beta)\cdot\max\left\\{\frac{1}{\varepsilon\alpha},\frac{1}{\alpha^{2}}\right\\}\right)$

samples from $\mathcal{D}$, outputs a hypothesis $h$ such that

$\mathop{\bf
Pr\/}\left[\mathrm{err}_{\mathcal{D}}(h)\leq\min_{h^{\prime}\in\mathcal{H}}\mathrm{err}_{\mathcal{D}}(h^{\prime})+\alpha\right]\geq
1-\beta\,.$

Finally, we state a result relating weak learners and privacy.

######  Theorem 10 (Weakly Accurate Private Learning $\implies$ Finite
Littlestone Dimension [ALMM19]).

Let $\mathcal{X}$ be some domain and $H\subseteq\\{0,1\\}^{\mathcal{X}}$ be a
hypothesis class with Littlestone dimension $d\in\mathbb{N}\cup\\{\infty\\}$
and let $A$ be a weakly accurate learning algorithm (i.e.,
$(\alpha,\beta)$-accurate with $\alpha=1/2-\gamma,\beta=1/2-\gamma$) for $H$
with sample complexity $n$ that satisfies $(\varepsilon,\delta)$-differential
privacy with $(\varepsilon,\delta)=(0.1,1/(n^{2}\log(n)))$. Then,
$n\geq\Omega(\log^{\star}(d))$.

In particular any class that is privately weakly-learnable has a finite
Littlestone dimension.

We remark that this theorem appears in [ALMM19] with accuracy constant $0.1.$
However, it is known from [DRV10] that a DP algorithm with error $1/2-\gamma$
can be boosted to one with arbitrarily small error with negligible loss in the
privacy guarantees.

The following result that appears in [BLM20] shows that if $\mathcal{H}$ has
finite Littlestone dimension, then there exists a $\rho$-globally stable
learner for this class.

######  Theorem 11 (Finite Littlestone Dimension $\implies$ Global Stability
[BLM20]).

Let $\mathcal{X}$ be some domain and
$\mathcal{H}\subseteq\left\\{0,1\right\\}^{\mathcal{X}}$ be a hypothesis class
with Littlestone dimension $d<\infty.$ Let $\alpha>0$ be the accuracy
parameter and define
$n=2^{2^{d+2}+1}4^{d+1}\cdot\left\lceil\frac{2^{d+2}}{\alpha}\right\rceil$.
Then, there exists a randomized algorithm
$A:(\mathcal{X}\times\\{0,1\\})^{n}\times\mathcal{R}\rightarrow\\{0,1\\}^{X}$
such that for any realizable distribution $\mathcal{D}$ there exists a
hypothesis $f_{\mathcal{D}}$ for which

$\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n},r\sim\mathcal{R}}[A(S,r)=f_{\mathcal{D}}]\geq\frac{1}{(d+1)2^{2^{d}+1}},\quad\mathop{\bf
Pr\/}_{(x,y)\sim\mathcal{D}}[f_{\mathcal{D}}(x)\neq y]\leq\alpha\,,$

where $\mathcal{R}$ is the source of internal randomness of $A.$

We also include a result from [GKM21, BGH+23] which states that replicability
implies differential privacy under general input domains131313In fact, this
result holds for general statistical tasks. The parameters stated in [BGH+23]
are slightly looser, but using our boosting results we can generalize them and
use the ones that appear in the statement..

######  Theorem 12 (Replicability $\implies$ Differential Privacy [GKM21,
BGH+23]).

Let $\mathcal{H}\subseteq\\{0,1\\}^{\mathcal{X}}$, where $\mathcal{X}$ is some
input domain. If $\mathcal{H}$ is learnable by an $n$-sample
$(\alpha,\beta)$-accurate $\rho$-replicable learner $A$, for
$\alpha\in(0,1/2),\rho\in(0,1),\beta\in\left(0,\frac{2\rho}{\rho+1}-2\sqrt{\frac{2\rho}{\rho+1}}+1\right)$,
then, for any
$(\alpha^{\prime},\beta^{\prime},\varepsilon,\delta)\in(0,1)^{4}$ it is
learnable by an $(\alpha+\alpha^{\prime},\beta^{\prime})$-accurate
$(\varepsilon,\delta)$-differentially private learner. Moreover, its sample
complexity is

$n\cdot\textnormal{poly}(1/\alpha^{\prime},1/\varepsilon,\log(1/\delta),\log(1/\beta^{\prime}))\,.$

###  D.2 The Proof of Theorem 3

In this section we show that Global Stability (cf. Definition 19) implies TV
indistinguishability in the context of PAC learning. In particular, we show
that given black-box access to a $\rho$-globally stable learner $A$ whose
stable output is $\alpha$-accurate, e.g., the one described in
LABEL:thm:finite_littlestoneimplies_global_stability, we can transform it to a
$\rho$-TV indistinguishable learner which is
$(\alpha+\alpha^{\prime},\beta)$-accurate, with a multiplicative
$\textnormal{poly}(1/\rho,1/\alpha^{\prime},\log(1/\beta)$ blow-up in its
sample complexity. We remark that this transformation is not restricted to
countable domains $\mathcal{X}$. As an intermediate result, we show that
global stability implies replicability.

######  Lemma 8 (Global Stability $\implies$ Replicability).

Let $A$ be an $n$-sample $\rho$-globally stable learner whose stable
hypothesis is $\alpha$-accurate. Then, for every
$\rho^{\prime},\alpha^{\prime},\beta\in(0,1)^{3}$, there exists a learner
$A^{\prime}$ (Algorithm 3) that is $\rho^{\prime}$-replicable and
$(\alpha+\alpha^{\prime},\beta)$-accurate. Moreover, $A^{\prime}$ needs

$\widetilde{O}\left(\frac{\log(1/\beta)}{\rho^{\prime 2}\rho^{3}}\right)$

oracle calls to $A$ and uses

$\widetilde{O}\left(\frac{\log(1/\beta)}{\rho^{2}\rho^{\prime
3}}\cdot\left(n+\frac{1}{\alpha^{\prime 2}}\right)\right)$

samples.

###### Proof.

We first argue about the accuracy and the confidence of the algorithm. Let
$h_{A}$ be the hypothesis such that $\mathop{\bf
Pr\/}_{S\sim\mathcal{D}^{n}}[A(S)=h]\geq 1-\rho$. The replicable heavy hitters
algorithm (Algorithm 1) guarantees that, with probability at least
$1-\beta/2$, $h_{A}$ will be contained in the output list $L$ (Lemma 5). We
call this event $E_{0}$ and we condition on it. In the next step, we call the
replicable agnostic learner on $L$ (Algorithm 2). Since there is a hypothesis
whose error rate is at most $\alpha$, we know that the output of the agnostic
learner will have error rate at most $\alpha+\alpha^{\prime}$, with
probability at least $1-\beta/2$ (Lemma 7). Let us call this event $E_{1}$.