# Stability is Stable: Connections between Replicability, Privacy, and
Adaptive Generalization

Mark Bun Department of Computer Science, Boston University. Email:
<EMAIL_ADDRESS>Supported by NSF awards CCF-1947889 and CNS-2046425, a Sloan
Research Fellowship, and Cooperative Agreement CB20ADR0160001 with the Census
Bureau. Marco Gaboardi Department of Computer Science, Boston University.
Email<EMAIL_ADDRESS>Supported by NSF awards CNS 2040249 and Cooperative
Agreement CB20ADR0160001 with the Census Bureau. Max Hopkins Department of
Computer Science and Engineering, UCSD, CA 92092. Email:
<EMAIL_ADDRESS>Supported by NSF Award DGE-1650112. Russell Impagliazzo
Department of Computer Science and Engineering, UCSD, CA 92092. Email:
<EMAIL_ADDRESS>Supported by NSF Award AF: Medium 2212136 Rex Lei
Department of Computer Science and Engineering, UCSD, CA 92092. Email:
<EMAIL_ADDRESS>Supported by NSF Award AF: Medium 2212136 Toniann Pitassi
Columbia University, University of Toronto and IAS. Email:
<EMAIL_ADDRESS>Supported by NSF Award AF: Medium 2212136. Satchit
Sivakumar Department of Computer Science, Boston University. Email:
<EMAIL_ADDRESS>Supported by NSF award CNS-2046425 and Cooperative Agreement
CB20ADR0160001 with the Census Bureau. Jessica Sorrell University of
Pennsylvania. Email<EMAIL_ADDRESS>Supported in part by the Simons
Foundation Collaboration on the Theory of Algorithmic Fairness.

###### Abstract

The notion of replicable algorithms was introduced in [48] to describe
randomized algorithms that are stable under the resampling of their inputs.
More precisely, a replicable algorithm gives the same output with high
probability when its randomness is fixed and it is run on a new i.i.d. sample
drawn from the same distribution. Using replicable algorithms for data
analysis can facilitate the verification of published results by ensuring that
the results of an analysis will be the same with high probability, even when
that analysis is performed on a new data set.

In this work, we establish new connections and separations between
replicability and standard notions of algorithmic stability. In particular, we
give sample-efficient algorithmic reductions between perfect generalization,
approximate differential privacy, and replicability for a broad class of
statistical problems. Conversely, we show any such equivalence must break down
computationally: there exist statistical problems that are easy under
differential privacy, but that cannot be solved replicably without breaking
public-key cryptography. Furthermore, these results are tight: our reductions
are statistically optimal, and we show that any computational separation
between DP and replicability must imply the existence of one-way functions.

Our statistical reductions give a new algorithmic framework for translating
between notions of stability, which we instantiate to answer several open
questions in replicability and privacy. This includes giving sample-efficient
replicable algorithms for various PAC learning, distribution estimation, and
distribution testing problems, algorithmic amplification of $\delta$ in
approximate DP, conversions from item-level to user-level privacy, and the
existence of private agnostic-to-realizable learning reductions under
structured distributions.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Main Results
      1. 1.1.1 Equivalences
      2. 1.1.2 Separating Stability: Computational Barriers and the Complexity of Correlated Sampling
      3. 1.1.3 Separating Stability: Statistical Barriers
    2. 1.2 Overview of Proofs of Equivalences
    3. 1.3 Further Discussion of Related Work
    4. 1.4 Open Problems
  2. 2 Preliminaries
    1. 2.1 Notions of Distributional Closeness
    2. 2.2 Differential Privacy
    3. 2.3 Replicability
    4. 2.4 PAC-Learning
    5. 2.5 Correlated Sampling
    6. 2.6 Terminology: “Reproducibility” and “Replicability”
  3. 3 Equating Stability: Differential Privacy, Perfect Generalization, and Replicability
    1. 3.1 Replicability implies Approximate-DP
    2. 3.2 Approximate-DP Implies One-Way Perfect Generalization
      1. 3.2.1 Preliminaries about Perfect Generalization
      2. 3.2.2 Preliminaries about Max Information
      3. 3.2.3 Approximate Differential Privacy to Bounded Max Information
      4. 3.2.4 Bounded Max Information to One-Way Perfect Generalization
    3. 3.3 Perfect Generalization Implies Replicability
    4. 3.4 Replicability Implies Perfect Generalization
  4. 4 Separating Stability: Computational Barriers
    1. 4.1 Cryptographic Hardness of Replicability
      1. 4.1.1 DP Algorithm for $\Pi_{\textit{RandEnc}}$
      2. 4.1.2 Cryptographic Adversary from Replicable Algorithm for $\Pi_{\textit{RandEnc}}$
      3. 4.1.3 Instantiating $\Pi_{\textit{RandEnc}}$ with the Goldwasser-Micali Cryptosystem
    2. 4.2 Correlated Sampling via One-Way Function Inverters
      1. 4.2.1 Relevant Definitions
      2. 4.2.2 Algorithm Overview
      3. 4.2.3 Algorithm Description and Pseudocode
      4. 4.2.4 Analysis – Structure and Simplifying Assumptions
      5. 4.2.5 Analysis – Distributional Accuracy.
      6. 4.2.6 Analysis — Correlated Sampling.
      7. 4.2.7 Analysis — Runtime
      8. 4.2.8 Analysis – Removing Assumption of Ideal Conditions
  5. 5 Separating Stability: Statistical Barriers
    1. 5.1 Quadratic Separation: One-way Marginals
      1. 5.1.1 Sketch of our approach
      2. 5.1.2 Formal argument
    2. 5.2 Quadratic separation: Agnostic Learning
      1. 5.2.1 Sign-One-Way Marginals
      2. 5.2.2 Solving Sign-One-Way Marginals using Agnostic Learning
      3. 5.2.3 Lower Bound for Sign-One-Way Marginals
    3. 5.3 Closing the Gap: Realizable Learning
      1. 5.3.1 Algorithm
      2. 5.3.2 Analysis
  6. 6 Applications
    1. 6.1 Item-level to User-level Privacy Transformation
    2. 6.2 Parameter Amplification for Differential Privacy and Perfect Generalization
    3. 6.3 A Realizable-to-Agnostic Reduction for Structured Distributions
      1. 6.3.1 List Heavy-Hitters
      2. 6.3.2 Replicable Realizable-to-Agnostic Reduction
      3. 6.3.3 Private Realizable-to-Agnostic Reduction
    4. 6.4 Replicable Algorithms from Reduction
      1. 6.4.1 PAC Learning
      2. 6.4.2 Distribution Estimation Problems
      3. 6.4.3 Gaussian Identity Testing
  7. A Estimating OPT
  8. B Learning Finite Littlestone Classes
  9. C Additional Properties of Replicability
    1. C.1 Randomness Management
    2. C.2 Replicability across Two Close Distributions
  10. D Glossary

##  1 Introduction

_Replicability_ is the principle that the findings of an empirical study
should remain the same when it is repeated on new data. Despite being a pillar
of the scientific method, replicability is extremely difficult to ensure in
today’s complex data generation and analysis processes. Questionable research
practices including misapplication of statistics, selective reporting of only
the findings that appear most statistically significant, and the formulation
of research hypotheses after the results are already known have been
identified as causes of an ongoing “crisis of replicability” across the
empirical sciences. Toward formulating solutions in the context of machine
learning and algorithmic data analysis, Impagliazzo, Lei, Pitassi, and Sorrell
[48] recently put forth a new definition of replicability for statistical
learning algorithms.111[48] stated this definition under the name
“reproducibility.” See Section 2.6 for a discussion of why we refer to it as
“replicability” instead.

######  Definition 1.1.

A randomized algorithm $A:\mathcal{X}^{n}\to\mathcal{Y}$ is $\rho$-replicable
if for every distribution $D$ over $\mathcal{X}$, we have

$\mathbf{Pr}[A(S_{1};r)=A(S_{2};r)]\geq 1-\rho,$

where $S_{1},S_{2}\in\mathcal{X}^{n}$ are independent sequences of i.i.d.
samples from $D$, and $r$ represents the coin tosses of the algorithm $A$.

That is, an algorithm (capturing an end-to-end data analysis process) is
replicable if with high probability over the choice of two independent samples
from the same distribution, it produces exactly the same output. If one
research team shares both their replicable analysis process ($A$) and the
random choices made along the way ($r$), then another research team can
independently verify their conclusions by performing the same analysis on a
fresh dataset.

Replicability is an extremely strong _stability_ constraint to place on an
algorithm. Informally, an algorithm is stable if its output is insensitive to
small changes to its input. Nevertheless, replicability is achievable for many
fundamental data analysis tasks, including statistical query learning, heavy
hitter identification, approximate median finding, and large-margin halfspace
learning [48, 42].

Replicability is not the first definition of algorithmic stability aimed at
ensuring the utility and safety of modern data analysis. Others have played
central roles in relatively mature areas such as differential privacy and
adaptive data analysis. Some of the aforementioned replicable algorithms were,
in fact, motivated or inspired by differentially private counterparts. Is
there a systematic explanation for this? _What can we learn about the
capabilities and limitations of replicable algorithms by relating
replicability to other notions of algorithmic stability?_

Let us briefly recall the types of algorithmic stability that arise in these
other areas:

##### Differential privacy.

A randomized algorithm is differentially private [35] if changing a single
input record results in a small change in the distribution of the algorithm’s
output. When each input record corresponds to one individual’s datum,
differential privacy guarantees that nothing specific to any individual can be
learned from the output of the algorithm. (See Section 2.4.) Differential
privacy comes with a rich algorithmic toolkit and understanding of the
feasibility of fundamental statistical tasks in query estimation,
classification, regression, distribution estimation, hypothesis testing, and
more.

##### Generalization in adaptive data analysis.

Generalization is the ability of a learning algorithm to reflect properties of
a population, rather than just properties of a specific sample drawn from that
population. Techniques for provably ensuring generalization form a hallmark of
theoretical machine learning. However, generalization is particularly
difficult to guarantee in settings where multiple analyses are performed
adaptively on the same sample. Traditional notions of generalization do not
hold up to downstream misinterpretation of results. For example, a classifier
that encodes detailed information about its training sample in its lower order
bits may generalize well, but can be used to construct a different classifier
that behaves very differently on the sample than it does on the population.
Interactive processes such as exploratory data analysis or feature selection
followed by classification/regression can ruin the independence between the
training sample and the method used to analyze it, invalidating standard
generalization arguments.

Adaptivity in data analysis has been identified as one contributing factor to
the replication crisis, and imposing stability conditions on learning
algorithms offers solutions to this part of the problem. A variety of such
stability conditions have been studied [32, 33, 23, 69, 31, 13, 67, 20, 58,
72], each offering distinct advantages in terms of the breadth of their
applicability and the quantitative parameters achievable. Two specific notions
play a central role in this work. The first is _perfect generalization_ [31,
13], which ensures that whatever can be inferred from the output of a learning
algorithm when run on a sample $S$ could have been learned just from the
underlying population itself:

######  Definition 1.2.

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

$e^{-\varepsilon}(\mathbf{Pr}_{Sim_{D}}[\mathcal{O}]-\delta)\leq\mathbf{Pr}[A(S)\in\mathcal{O}]\leq
e^{\varepsilon}\mathbf{Pr}_{Sim_{D}}[\mathcal{O}]+\delta.$ (1)

The second is _max-information_ [32] which constrains the amount of
information revealed to an analyst about the training sample:

######  Definition 1.3.

An algorithm $A:\mathcal{X}^{n}\to\mathcal{Y}$ has $(\varepsilon,\delta)$-max-
information with respect to product distributions if for every set of outcomes
$\mathcal{O}\subseteq(\mathcal{Y}\times\mathcal{X}^{n})$ we have

$\mathbf{Pr}[(A(S),S)\in\mathcal{O}]\leq
e^{\varepsilon}\mathbf{Pr}[(A(S),S^{\prime})\in\mathcal{O}]+\delta,$

where $S$ and $S^{\prime}$ are independent samples of size $n$ drawn i.i.d.
from an arbitrary distribution $D$ over $\mathcal{X}$.

As with differential privacy, both perfect generalization and max-information
are robust to post-processing.

Each stability definition described above is tailored to model a distinct
desideratum. At first glance, they may all appear technically incomparable.
For instance, differential privacy is stricter than the other definitions in
that it holds in the worst case over all input datasets without any
assumptions on the data-generating procedure. On the other hand, it is weaker
in that it only requires insensitivity to changing one input record, rather
than to resampling the entire input dataset as in max-information, perfect
generalization, or replicability. Meanwhile, differential privacy, max-
information, and perfect generalization quantify the sensitivity of the
algorithm’s output in a weaker way than replicability; the former three
notions only require that the distributions on outputs are similar, whereas
replicability demands that precisely the same output realization is obtained
with high probability.

Nevertheless, the (surprising!) technical connections between these
definitions have enabled substantial progress on the fundamental questions in
their respective areas. For example, it was exactly the adaptive
generalization guarantees of differential privacy that kickstarted the
framework of adaptive data analysis from [33]; the definition of max-
information was subsequently introduced [32] to unify existing analyses based
on differential privacy and description length bounds. As another
illustration, variants of replicability were introduced in [17, 41, 42] for
purely technical reasons, as it was observed that such algorithms could be
immediately used to construct differentially private ones. This connection was
essential in proving the characterization of private PAC learnability in terms
of the Littlestone dimension from online learning [3, 17]. In fact, this
characterization shows, that, in principle a private PAC learner using $n$
samples can be converted to a replicable PAC learner using a number of samples
that is an exponential tower of height $n$, but it is non-constructive and
does not suggest what such a learner looks like in general.

###  1.1 Our Main Results

####  1.1.1 Equivalences

Our main result is a complete characterization of the relationships between
these quantities. We prove that all four central stability notions —
replicability, differential privacy, perfect generalization, and bounded max-
information w.r.t. product distributions — are equivalent to one another via
constructive conversions that incur at most a near-quadratic overhead in
sample complexity.

Our equivalences apply to an abstract and broad class of _statistical tasks_
that capture learning from i.i.d. samples from a population. An instance of
such a task is obtained by considering a distribution $D$ from a pre-specified
family of distributions. Given i.i.d. samples from $D$, the goal of a learning
algorithm is to produce an outcome that is “good” for $D$ with high
probability. This formulation of a statistical task captures problems such as
PAC learning, where a sample from $D$ is a pair
$(x,f(x))\in\mathcal{X}\times\\{0,1\\}$ where $x$ is drawn from an arbitrary
marginal distribution over $\mathcal{X}$, and $f$ is an arbitrary function
from a fixed concept class $H$. A “good” outcome for such a distribution $D$
is a hypothesis $h:\mathcal{X}\to\\{0,1\\}$ that well-approximates $f$ on $D$.
Many other objectives such as regression, distribution parameter estimation,
distribution learning, hypothesis testing, and confidence interval
construction can be naturally framed as statistical tasks. (See Section 6.4
for other examples.)

Figure 1 illustrates the known relationships between the various stability
notions that hold with respect to any statistical task.

$(0.1)$-replicability$(\varepsilon,\delta)$-differential
privacypt$(\varepsilon,\delta)$-max-information w.r.t. product
distributionspt$(\delta,\varepsilon,\delta)$-one-way perfect
generalization$n\mapsto n\cdot\frac{\log(1/\delta)}{\varepsilon}$, Thm. 3.1
[42]pt$n\mapsto n^{2}$Cor. 3.13[66]Lem. 3.14$n\mapsto n$Thm. 3.17$n\mapsto
n\cdot\frac{\operatorname{poly}\log(1/\varepsilon,1/\delta)}{\varepsilon^{2}}$Thm.
3.19 Figure 1: The solid arrow from $A$ to $B$ means that every algorithm
satisfying $A$ also satisfies $B$. A dashed arrow means that for every
statistical task, a solution satisfying $A$ can be computationally efficiently
transformed into a solution satisfying $B$ with the stated blowup in sample
complexity. The thin dotted arrow means an explicit transformation exists, but
is not always computationally efficient, and assumes the outcome space is
finite.
This figure suppresses constant factors everywhere and polynomial factors in
$\delta$, assumes $\varepsilon$ is below a sufficiently small constant, and
assumes that $\delta$ is a sufficiently small inverse polynomial in $n$.

From these equivalences we obtain the following consequences, resolving
several open questions.

##### Sample-efficient replicable algorithms.

Any differentially private algorithm solving a statistical task (with a finite
outcome space) can be converted into a replicable algorithm solving the same
task with a near-quadratic blowup in its sample complexity. Thus, the wealth
of research on private algorithm design can be brought to bear on designing
replicable algorithms. We illustrate this algorithmic paradigm by describing
new replicable algorithms for some PAC learning, distribution parameter
estimation, and distribution testing problems in Section 6.4.

##### Equivalence between perfect generalization and differential privacy.

For simplicity, the relationships summarized in Figure 1 are stated in terms
of a one-way variant of perfect generalization, where only the inequality on
the right of (1) is required to hold. But the original two-way definition
turns out to be statistically equivalent for tasks with a finite outcome
space. This is because a one-way perfectly generalizing algorithm can be
converted to a replicable algorithm using Theorem 3.17, and Theorem 3.19
actually yields the stronger conversion back to a two-way perfectly
generalizing algorithm (See Theorem 6.3). Thus, an
$(\varepsilon,\delta)$-differentially private algorithm (with a finite outcome
space) can be converted to a perfectly generalizing one solving the same
statistical task with a near quadratic blow-up in sample complexity. This
resolves an open question of [31]. Their work also gave a conversion from
perfectly generalizing algorithms to differentially private ones with no
sample complexity overhead, and while their transformation preserves accuracy
for (agnostic) PAC learning, it is not clear how to analyze it for general
statistical tasks. Our conversion from perfect generalization to replicability
and then to differential privacy holds for all statistical tasks with a finite
outcome space.

##### Converting item-level to user-level privacy.

Consider a “user-level” learning scenario in which $n$ individuals each hold
$m$ training examples drawn i.i.d. from the same distribution. When is
$(\varepsilon,\delta)$-differentially private learning possible if we wish to
guarantee privacy with respect to changing _all_ of any individual’s samples
at once? Ghazi, Kumar, and Manurangsi [42] showed that this is possible when
$n\geq O(\log(1/\delta)/\varepsilon)$ and the task admits a replicable
learner. For the special case of PAC learning a concept class $H$, they argued
that this implies a user-level private learning algorithm whenever $H$ is
privately PAC learnable with respect to changing a single _sample_. They posed
the open problem of extending this result beyond PAC learning, e.g., to
private regression [49, 44]. Our conversion from any differentially private
algorithm to a replicable one implies that such a transformation is possible
for _any_ statistical task with a finite outcome space (Section 6.1).
Moreover, one can always take each indvidual’s number of samples $m$ to be
nearly quadratic in the sample complexity of the original item-level private
learner.

##### Amplifying differential privacy parameters.

While almost all $(\varepsilon,\delta)$-differentially private algorithms
enjoy a mild $\propto\log(1/\delta)$ dependence in their sample complexity on
the parameter $\delta$, it was not known how to achieve this universally, say
by amplifying large values of $\delta$ to asymptotically smaller ones. [17]
showed that for private PAC learning, such amplification is possible in
principle, but posed the open question of giving an explicit amplification
algorithm. By converting an $(\varepsilon,\delta)$-differentially private
algorithm with weak parameters to a replicable one, and then back to a
differentially private one with strong parameters, we resolve this question
for the general class of statistical tasks with a finite outcome space, and
with a much milder sample complexity blowup (Section 6.2).

##### Agnostic-to-realizable reductions for distribution-family learning.

[46] introduced a simple and flexible framework for converting realizable PAC
learners to agnostic learners without relying on uniform convergence
arguments. The framework applies to diverse settings such as robust learning,
fair learning, partial learning, and (as observed in this work) replicable
learning, with differential privacy providing a notable exception.222We note
the technique we introduce to adapt [46] to the replicable setting has no
clear translation to the private setting. While an agnostic-to-realizable
reduction for private PAC learning is known [24, 1], it relies on uniform
convergence and is only known to hold in the distribution-free PAC model. By
converting a realizable private learner to a realizable replicable learner,
then to an agnostic replicable learner, and back to an agnostic private
learner, we obtain a reduction that works in the absence of uniform
convergence (Section 6.3). In particular, this reduction applies to the
_distribution-family_ learning model, where one is promised that the marginal
distribution on unlabeled examples comes from a pre-specified family of
distributions.

####  1.1.2 Separating Stability: Computational Barriers and the Complexity of
Correlated Sampling

All of the transformations appearing in Figure 1 preserve computational
efficiency, with the lone exception of the transformation from perfectly
generalizing algorithms to replicable ones. This transformation makes use of
the technique of _correlated sampling_ from the distribution of outputs of a
perfectly generalizing algorithm $A$ when run on a fixed sample $S$
(elaborated on more in Sections 1.2 and 2.5). This step can be explicitly
implemented via rejection sampling from the output space of $A$, with the
rejection threshold determined by the probability mass function of $A(S)$, but
in general it is not computationally efficient.

We show that under cryptographic assumptions, this is inherent (Section 4).
Specifically, we show that under standard assumptions in public-key
cryptography, there exists a statistical task that admits an efficient
differentially private algorithm, but does not have any efficient replicable
algorithm. The task is defined in terms of a public-key encryption scheme with
the following rerandomizability property: Given a ciphertext
$\mathsf{Enc}(\mathbf{pk},b)$, there is an efficient algorithm producing a
uniformly random encryption of $b$. Fixing such a rerandomizable PKE, the
statistical task is as follows. Given a dataset consisting of random
encryptions of the form $\mathsf{Enc}(\mathbf{pk},b)$ where $\mathbf{pk}$ is a
fixed public key and $b\in\\{0,1\\}$ is a fixed bit, output any encryption of
$b$.

One can solve this problem differentially privately, essentially by choosing a
random ciphertext from the input dataset and rerandomizing it. On the other
hand, there is no efficient replicable algorithm for this task. If there were,
then one could use the public key to produce many encryptions of $0$ and $1$
and run the replicable algorithm on the results to produce canonical
ciphertexts $c_{0}$ and $c_{1}$, respectively. Then, given an unknown
ciphertext, one could repeatedly rerandomize it, run the replicable algorithm
on the results, and compare the answer to $c_{0}$ and to $c_{1}$ to identify
the underlying plaintext.

We also show that cryptographic assumptions are necessary even to separate
replicability from perfect generalization. Recalling again that the bottleneck
in computationally equating the two notions is in implementing correlated
sampling, we show in Section 4.2 that if one-way functions do not exist, then
correlated sampling is always tractable. In addition to addressing a natural
question about the complexity of correlated sampling, this shows that function
inversion enables an efficient transformation from perfectly generalizing
algorithms into replicable ones. (See Section 2.5 for more discussion.)

####  1.1.3 Separating Stability: Statistical Barriers

Our equivalences show that the sample complexities of perfectly generalizing
and replicable learning are essentially equivalent. Moreover: (1) An
approximate-DP algorithm can be converted to a perfectly
generalizing/replicable algorithm with near-quadratic blowup; and (2) A
perfectly generalizing/replicable algorithm can be converted to an
approximate-DP one using roughly the same number of samples. We prove that
both of these conversions are optimal by showing:

  1. 1.

Quadratic separations between differential privacy and perfect
generalization/replicability. We first consider the problem of estimating the
parameters of a product of $d$ Bernoulli distributions. By simply taking the
empirical mean of an input dataset, this problem can be solved using $O(\log
d)$ without any stability constraints. However, with differential privacy, it
is known that $\tilde{\Theta}(\sqrt{d})$ samples are necessary and sufficient.
By adapting the “fingerprinting” method underlying these privacy lower bounds
[29, 39, 28] to perfect generalization, we prove that any perfectly
generalizing or replicable algorithm for this problem requires
$\tilde{\Omega}(d)$ samples (Section 5.1).

By reducing from a variant of this one-way marginals problem, we also show a
general lower bound for replicable agnostic learning. Namely, we show that
every concept class $H$ requires $\tilde{\Omega}(VC(H)^{2})$ samples. For
concept classes of maximal VC dimension $VC(H)=\log|H|$, this too gives a
quadratic separation between replicable learning and both private and
unconstrained learning (Section 5.2).

  2. 2.

No separation between differential privacy and perfect
generalization/replicability. Complementing our lower bounds, we also show
that every finite class $H$ can be replicably PAC learned (in the realizable
setting) to error $\alpha$ with sample complexity $\tilde{O}_{H}(1/\alpha)$
(Section 5.3). Up to logarithmic factors, this matches the learning rate
achievable for both unconstrained and differentially private learning. Our
learner works by selecting a random threshold $v$, and selecting a random
concept from $H$ whose error with respect to the sample is at most $v$. A more
involved random thresholding strategy also yields an agnostic learner with
sample complexity $\tilde{O}_{H}(1/\alpha^{2})$.

###  1.2 Overview of Proofs of Equivalences

##### Perfect generalization is equivalent to replicability.

Recall that an algorithm is replicable if it is likely to produce exactly the
same output when run on two independent samples from any given population.
Replicability appears to be a dramatic strengthening of perfect
generalization, which only requires the distributions of $A(S)$ and
$A(S^{\prime})$ to be statistically close. Nevertheless, we prove that
perfectly generalizing algorithms can always be converted to replicable ones
whenever the output space $\mathcal{Y}$ is finite (Theorem 3.17). This can be
done via a primitive called _correlated sampling_ (See Section 2.5). A
correlated sampling algorithm for a class of distributions
$\mathcal{P}=\\{P\\}$ is a procedure $CS(P,r)$ such that 1) $CS(P,r)$ produces
a sample distributed according to $P$ when provided a uniformly random input
$r$, and 2) Whenever $P,Q\in\mathcal{P}$ satisfy
$d_{\mathrm{T}V}(P,Q)\leq\eta$, we have $\mathbf{Pr}[CS(P,r)=CS(Q,r)]\geq
1-O(\eta)$. That is, applying correlated sampling to two similar distributions
results in the same output with high probability – exactly what is needed for
replicability. We actually prove a stronger theorem, showing that the larger
class of one-way perfectly generalizing algorithms (where only the right-hand
inequality in 1 holds) are replicable via correlated sampling.

Conversely, we show how to convert replicable algorithms to perfectly
generalizing ones (Theorem 3.19). While a $\rho$-replicable algorithm is
automatically also a $(\beta=O(\rho),\varepsilon=0,\delta=O(\rho))$-perfectly
generalizing one, these parameters are too weak for applications where one
wants to take $\beta,\delta$ to be inverse polynomial in the dataset size $n$
(e.g., to prove the lower bounds in Section 5). To obtain a perfectly
generalizing algorithm with stronger parameters, we repeatedly run the
replicable algorithm using $k=O(\log(1/\delta))$ different sequences of coin
tosses $r_{1},\dots,r_{k}$, and using $\tilde{O}(1/\varepsilon^{2})$
independent samples for each sequence of coin tosses. Using the exponential
mechanism from differential privacy [60], we select an outcome $y_{i}$ that
appears approximately the most frequently amongst these repetitions in a
manner that ensures $(\beta=\delta,\varepsilon,\delta)$-perfect
generalization. This strategy allows us to obtain inverse polynomial
$\beta,\delta$ parameters with only a logarithmic multiplicative overhead in
the number of samples.

Bounded max-information implies perfect generalization. In Lemma 3.14, we show
that bounded max-information implies one-way perfect generalization with
similar parameters. Namely, if an algorithm $A$ has
$(\varepsilon,\delta)$-max-information with respect to product distributions,
then it is also $(\sqrt{\delta},2\varepsilon,\sqrt{\delta})$-one-way perfectly
generalizing. The idea is to take the simulator distribution $Sim_{D}$ to be
the distribution of $A(S^{\prime})$, where the randomness is taken over both
the coin tosses of $A$ _and_ the randomness of a sample $S^{\prime}\sim D$. A
similar argument is implicit in [13, Proof of Lemma 4.5]. Then by combining
Theorems 3.17 and 3.19, it follows that bounded max-information also implies
perfect generalization for finite outcome spaces (Theorem 6.3).

##### Replicability implies differential privacy.

In Theorem 3.1 we show that replicability implies differential privacy. Given
a replicable algorithm, one can run it $k=O(\log(1/\delta)/\varepsilon)$ times
using the same sequence of coin tosses, but on independent samples, producing
outcomes $y_{1},\dots,y_{k}$. Replicability ensures that most of these
outcomes are the same with high probability, and so this common outcome can be
selected in a standard differentially private way. This argument appears in
the differential privacy literature as a conversion from “globally stable” and
“pseudo-globally stable” learners to private ones [17, 41, 42]. Our
presentation of Theorem 3.1 includes an additional amplification step that
avoids union bounding over correctness, making the conversion suitable for a
broader range of parameters.

Differential privacy implies bounded max-information. The final conversion in
Figure 1 is from differentially private algorithms to algorithms with bounded
max-information. This argument is implicit in [66] and we show how it follows
from their work here (Corollaries 3.12 and 3.13).

###  1.3 Further Discussion of Related Work

Several elements of our approach were inspired by Ghazi, Kumar, and
Manurangsi’s study of the relationship between user-level and item-level
differentially private learning [42]. They introduced a notion of “pseudo-
global stability” that is essentially the same as replicability, and showed
that it implies differential privacy. Correlated sampling also played a
crucial role in their work by allowing individuals to use shared randomness to
reach consensus on a learned hypothesis. In fact, it provided a key step in
their conversion from “list globally stable” algorithms [41] (learning
algorithms that output a short list of hypotheses, one of which is almost
guaranteed to be canonical for the given distribution) to pseudo-globally
stable ones.

Stability in learning has a long history as a tool for ensuring
generalization. Early work [68, 40, 11, 71] showed that the stability of a
learning algorithm with respect to a specific loss function could ensure
strong generalization guarantees with respect to that loss. A more recent
literature has focused on stability notions that are not tied to a specific
loss, and which ideally are robust under post-processing and adaptive
composition. This includes understanding the generalization guarantees of
differential privacy [32, 33, 23, 66, 65, 76, 50] and other constraints on the
information-theoretic relationship between the input and output of a learning
algorithm [69, 20, 75, 67, 58, 72]. A related line of work [31, 13, 64]
considers more “semantic” notions of stability, defining it in terms of the
difficulty of inferring properties specific to the sample rather than of the
underlying distribution. Perfect generalization, one of the main definitions
we study in this work, was introduced by [31] and is a special case of
_typical stability_ that was introduced in independent work of Bassily and
Freund [13].

Independent of this work, [52] study similar relationships between notions of
stability. They focus on the PAC-learning setting, where they show a
statistical equivalence between differential privacy, replicability, and a
notion called “TV-indistinguishability” which can be thought of as a special
case of perfect generalization with $\varepsilon=0$. To clarify the
differences between our work and [52], first recall how we obtain
replicability from differential privacy:

  * •

First, we exploit existing connections between privacy and bounded max-
information from [66] to obtain an algorithm with bounded max-information from
a differentially private one.

  * •

We prove that bounded max-information implies perfect generalization.

  * •

We then show that we can obtain a replicable algorithm from a perfectly
generalizing one by applying correlated sampling to its distribution over
outputs. The relevant output distribution is induced by fixing an input sample
of the perfectly generalizing algorithm and redrawing its internal randomness.

Recall that the correlated sampling procedure may not be efficient, and that
we assume the output domain of the differentially private algorithm is finite.

The work of [52] follows a different approach. First, they start from a
differentially private PAC learner, rather than a differentially private
algorithm for a general statistical task, and factor through TV-
indistinguishability and Littlestone dimension. More specifically:

  * •

They first observe a similar equivalence of TV-indistinguishability and
replicability for general statistical tasks.

  * •

They then show that a private PAC learner implies the existence of a TV-
indistinguishable learner, leveraging results from [3] showing that private
PAC learning implies finite Littlestone dimension, and results from [42, 41]
showing that finite Littestone dimension implies list global-stability.

Our approach gives us a constructive procedure for converting a private
algorithm for a general statistical task into a replicable algorithm, so long
as the private algorithm has finite range. Our transformations induce a modest
sample complexity increase, resulting in a replicable algorithm with sample
complexity $n^{2}$, given a private learner with sample complexity $n$. By
contrast, the results of [52], while non-constructive, apply to countably
infinite domains (and therefore to some uncountably infinite ranges). However,
their results go through Littlestone dimension, which may be an exponential
tower in $n$, and so they obtain sample complexity bounds which are an
exponential tower in $n$ as well.

###  1.4 Open Problems

We highlight several directions and open problems for future work.

  1. 1.

Is a transformation from (one-way) perfectly generalizing algorithms to
replicable algorithms possible for infinite output spaces in general? While
correlated sampling introduces no sample complexity overhead in terms of the
output space, it is only known to be possible when the output space is finite
or the class of distributions to be sampled from is structured. (E.g., the
distributions in the class all have uniformly bounded Radon-Nikodym derivative
with respect to some fixed base measure).333Formally, such a case would fall
into a restricted notion of correlated sampling over a subset of
distributions, similar to the multiple coupling of [4]. In independent work,
[52] make progress towards this goal by giving a transformation from TV-
indistinguishability to replicability when there are only countably many
options for the TV-indistinguishable algorithm $\\{A(S)\\}_{S\in X^{n}}$. It
follows from Lemma 3.8 that $(\beta,\varepsilon,\delta)$-one-way perfect
generalization implies $(4\varepsilon+2\delta+2\beta)$-TV
indistinguishability, and so the result of [52] gives the following corollary.

######  Corollary 1.4.

Fix $n\in\mathbb{N}$, $\beta,\varepsilon,\delta\in(0,1]$. Let $\mathcal{X}$ be
a countable domain and $A:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ be a
$(\beta,\varepsilon,\delta)$-one-way perfectly generalizing algorithm for a
statistical task. Then there exists an algorithm
$A^{\prime}:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ that is
$\left(\frac{2\rho}{1+\rho}\right)$-replicable for
$\rho=4\varepsilon+2\delta+2\beta$, and for all $S\in\mathcal{X}^{n}$,
$A(S)=A^{\prime}(S)$.

Whether a transformation exists for general measure spaces remains open.444We
note that in the PAC-setting one can resolve this issue via factoring through
Littlestone Dimension and [48]’s heavy-hitters, but this results in tower
sample complexity. In Section 6.3.1 we discuss the _list heavy-hitters_
problem that may be a candidate for separating perfect generalization from
replicability over infinite output spaces.

  2. 2.

What are the minimal cryptographic assumptions under which a computational
separation between replicability and differential privacy exists? Our results
in Section 4 show that one-way functions are necessary, while public-key
assumptions are sufficient.

  3. 3.

[48, Lemma A.7] showed that replicable algorithms compose adaptively. That is,
a sequence of $k$ adaptively chosen $\rho$-replicable algorithms yields a
transcript that is $O(k\rho)$-replicable. One way to interpret this result is
as follows: Given a sequence of $k$ analyses that are each $(0.01)$-replicable
using a sample of size $n$, one can amplify their individual replicability
parameters to $O(1/k)$ at the expense of increasing their sample complexity to
$O(k^{2}n)$. This yields a $(0.01)$-replicable algorithm for performing all
$k$ analyses at a sample cost of $O(k^{2}n)$.

Our conversions between replicability and differential privacy yield a
different tradeoff, at least for simulating non-adaptive composition. Given
$k$ analyses that are each $(0.01)$-replicable using a sample of size $n$, one
can convert them to $\tilde{O}(1/\sqrt{k})$-differentially private algorithms
each using a sample of size $\tilde{O}(\sqrt{k}n)$. “Advanced” composition of
differential privacy [38] yields an $(0.01,\delta)$-differentially private
algorithm using $\tilde{O}(\sqrt{k}n)$ samples, which can then be turned back
into a $(0.01)$-replicable algorithm using $\tilde{O}(kn^{2})$ samples.

What is the optimal sample cost for conducting, or at least statistically
simulating, the (adaptive) composition of $k$ replicable algorithms? Is it
possible to do so at a cost of $O(kn)$ samples?

  4. 4.

In Section 5.3, we give a direct replicable algorithm for the task of
realizable PAC learning of finite classes with sample cost inverse linear in
the accuracy parameter $\alpha$. (As opposed to inverse quadratic, which is
what applying the reduction from replicability to approximate DP gives – see
Theorem 6.13 and the following discussion.) Are there other natural problems
for which there are (perhaps more dramatic) separations between what’s
achievable via directly constructing a replicable algorithm for a task, and
what’s achievable using our reduction to approximate DP? For example, can
discrete distributions over $[k]$ be replicably estimated using $O(k)$ samples
(as opposed to quadratic in $k$, which is what is obtained through our
reduction)? Can the mean of a $d$-variate Gaussian with unknown covariance be
estimated directly using $O(d)$ samples (as opposed to quadratic in $d$, which
is what is obtained through our reduction)? Even more ambitiously, is it
possible to characterize the types of problems for which our reduction from
replicability to approximate DP gives tight bounds?

  5. 5.

To what extent is replicability preserved under distributional shift? In
Appendix C, we give a simple argument showing that a $\rho$-replicable
algorithm is $\rho(1-\delta)^{2m}$-replicable across two close distributions.
Are there tighter replicability and non-replicability bounds for specific
families of distributions, problems, and algorithms under distributional
shifts?

##  2 Preliminaries

We start by formally defining a statistical task.

######  Definition 2.1.

A _statistical task_ with data domain $\mathcal{X}$ and output space
$\mathcal{Y}$ is a set of pairs $\mathcal{T}=\\{(D,G_{D})\\}$, where $D$ is a
distribution over $\mathcal{X}$ and $G_{D}\subseteq\mathcal{Y}$ is a “good”
set of outputs for distribution $D$. A randomized algorithm $\mathcal{A}$
solves statistical task $\mathcal{T}$ using $m$ samples and with failure
probability $\beta$ if for every $(D,G_{D})\in\mathcal{T},$

$\mathbf{Pr}_{S\sim D^{m},\mathcal{A}}[\mathcal{A}(S)\in G_{D}]\geq 1-\beta.$

###  2.1 Notions of Distributional Closeness

We recall the definition of total variation distance, that will be crucial in
this work.

######  Definition 2.2 (Total Variation Distance).

Let $P$ and $Q$ be probability distributions over some domain $S$. Then

$d_{\mathrm{T}V}(P,Q):=\sup_{E\subseteq
S}|\mathbf{Pr}_{P}[E]-\mathbf{Pr}_{Q}[E]|.$

We also define the notion of $(\varepsilon,\delta)$-indistinguishability, the
notion of closeness that is used in differential privacy.

######  Definition 2.3 ($(\varepsilon,\delta)$-indistinguishability).

Let $P$ and $Q$ be probability distributions over some domain $\mathcal{Y}$.
Then, we say that $P$ is $(\epsilon,\delta)$-indistinguishable from $Q$
(denoted as $P\approx_{\varepsilon,\delta}Q$) if for all
$O\subseteq\mathcal{Y}$,

$e^{-\epsilon}[\mathbf{Pr}_{P}[O]-\delta]\leq\mathbf{Pr}_{Q}[O]\leq
e^{\epsilon}\mathbf{Pr}_{P}[O]+\delta.$

We will frequently talk about random variables being
$(\varepsilon,\delta)$-indistinguishable, which means that their distributions
are $(\varepsilon,\delta)$-indistinguishable.

###  2.2 Differential Privacy

We say that two datasets $S,S^{\prime}\in\mathcal{X}^{n}$ are neighboring if
they differ for the data of one individual, i.e., their Hamming distance is
one. Differential privacy is formulated as a notion of indistinguishability
between the results of an algorithm when run on neighboring datasets.

######  Definition 2.4 (Differential Privacy [35]).

A randomized algorithm $\mathcal{A}:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ is
said to be $(\varepsilon,\delta)$-differentially private if for every pair of
neighboring datasets $S,S^{\prime}\in\mathcal{X}^{n}$, we have that for all
subsets $O\subseteq\mathcal{Y}$,

$\mathbf{Pr}[\mathcal{A}(S)\in O]\leq
e^{\varepsilon}\cdot\mathbf{Pr}[\mathcal{A}(S^{\prime})\in O]+\delta.$

That is, we have
$\mathcal{A}(S)\approx_{\varepsilon,\delta}\mathcal{A}(S^{\prime})$ for all
neighboring $S,S^{\prime}$.

One important property of differential privacy is that it is closed under
post-processing by arbitrary functions.

######  Lemma 2.5 (Post-Processing [35]).

If $\mathcal{A}:\mathcal{X}^{n}\rightarrow\mathcal{Y}$ is
$(\varepsilon,\delta)$-differentially private, and
$\mathcal{B}:\mathcal{Y}\rightarrow\mathcal{Z}$ is any randomized function,
then the algorithm $\mathcal{B}\circ\mathcal{A}$ is
$(\varepsilon,\delta)$-differentially private.

Differential privacy can be achieved by adding some carefully chosen noise to
a function and calibrating the noise to the sensitivity of the function: a
measure of how different can the results of the function be when run on
adjacent datasets.

######  Definition 2.6 ($\ell_{1}$-Sensitivity).

Let $f:\mathcal{X}^{n}\rightarrow\mathbb{R}^{d}$ be a function. Its
$\ell_{1}$-sensitivity is

$\Delta_{f}=\max_{\begin{subarray}{c}S,S^{\prime}\in\mathcal{X}^{n}\\\
S,S^{\prime}\text{neighbors}\end{subarray}}\|f(S)-f(S^{\prime})\|_{1}.$

There are many techniques that can be used to design differentially private
algorithms. One important technique that we will use in some of our
applications is the exponential mechanism.

######  Lemma 2.7 (Exponential Mechanism [60]).

Let $L$ be a set of outputs and $g:L\times\mathcal{X}^{n}\to\mathbb{R}$ be a
function that measures the quality of each output on a dataset. Assume that
for every $m\in L$, the function $g(m,.)$ has $\ell_{1}$-sensitivity at most
$\Delta$. Then, for all $\varepsilon>0$, there exists an $(\varepsilon,0)$-DP
mechanism that, on input $S\in\mathcal{X}^{n}$, outputs an element $m\in L$
such that, for all $a>0$, we have

$\mathbf{Pr}\left[\max_{i\in[L]}g(i,S)-g(m,S)\geq
2\Delta\frac{\ln|L|+a}{\varepsilon}\right]\leq e^{-a}.$

Standard $(\varepsilon,\delta)$-differential privacy automatically protects
the privacy of groups of individuals.

######  Lemma 2.8 (Group Privacy [35]).

Let $k\in\mathbb{N}^{+}$ and let $\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$
be an $(\varepsilon,\delta)$-DP algorithm. Then for all datasets
$S,S^{\prime}\in\mathcal{X}^{m}$ such that $\|S-S^{\prime}\|_{0}\leq k$,

$\mathcal{A}(S)\approx_{k\varepsilon,\delta\frac{e^{k\varepsilon}-1}{e^{\varepsilon}-1}}\mathcal{A}(S^{\prime}).$

Another property of differential privacy that we will use in many of our
algorithms is privacy amplification by subsampling. This says that we can have
a stronger privacy protection when we run a differentially private algorithm
on a subsample of a dataset.

######  Lemma 2.9 (Secrecy of the sample, [54, 7]).

Let $A:\mathcal{X}^{n}\to\mathcal{Y}$ be an
$(\varepsilon,\delta)$-differentially private algorithm. Consider the
algorithm $A^{\prime}:\mathcal{X}^{m}\to\mathcal{Y}$ that, given a dataset of
size $m$, randomly samples $n$ items without replacement and runs $A$ on the
resulting subsample. Then $A^{\prime}$ is
$(\varepsilon^{\prime},\delta^{\prime})$-differentially private for

$\varepsilon^{\prime}=\frac{n}{m}(e^{\varepsilon}-1),\qquad\delta^{\prime}=\frac{n}{m}\cdot\delta.$

###  2.3 Replicability

Replicability is a strong stability property for randomized algorithms,
requiring that the algorithm produce the exact same output with high
probability when invoked on two i.i.d. samples from the same distribution, so
long as the internal randomness is held fixed. We recall the definition of
replicability given in [48].

######  Definition 2.10 ([48]).

Let $D$ be a distribution over domain $\mathcal{X}$. Let $\mathcal{A}$ be a
randomized algorithm that takes as input samples from $D$. We say that
$\mathcal{A}$ is $\rho$-reproducible if

$\mathbf{Pr}_{S,S^{\prime},r}[\mathcal{A}(S;r)=\mathcal{A}(S^{\prime};r)]\geq
1-\rho,$

where $S,S^{\prime}$ are sets of samples drawn i.i.d. from $D$ and $r$
represents the internal randomness of $\mathcal{A}$.

We will sometimes use the alternative $2$-parameter definition of
replicability defined in [48]. Here we assume that the auxiliary inputs
described in their original definition are empty.555See Section 2.5 for an
explanation of our renaming of this definition to “replicable.”

######  Definition 2.11 ([48]).

Let $A(S;r)$ be an algorithm operating on a sample set $S\in\mathcal{X}^{n}$
and internal coins $r$. We say that coin tosses $r$ are $\eta$-good for $A$ on
distribution $D$ if there exists a “canonical output” $z_{r}$ such that
$\mathbf{Pr}_{S\sim D^{n}}[A(S;r)=z_{r}]\geq 1-\eta$. We say that $A$ is
$(\eta,\nu)$-replicable if, for every distribution $D$, with probability at
least $1-\nu$, the coin tosses $r$ are $\eta$-good on distribution $D$.

[48] observed that the two parameter and the original single parameter
definition (Definition 1.1) are essentially equivalent:

######  Claim 2.12 ([48]).

For every $0\leq\rho\leq v\leq 1$,

  1. 1.

Every $\rho$-replicable algorithm is also $(\rho/v,v)$-replicable.

  2. 2.

Every $(\rho,\nu)$-replicable algorithm is also $\rho+2\nu$-replicable.

It was proved in [48] that we can amplify the replicability parameter at an
inverse quadratic cost in the desired replicability parameter. We state a
version of this theorem with slightly different constants.

######  Lemma 2.13 (Amplification of Replicability, Theorem A.3, [48]).

Let $0<\eta,\nu,\beta<\frac{1}{2}$ and $m>0$. Let $\mathcal{A}$ be an
$(\eta,\nu)$-replicable algorithm for distribution $D$ with sample complexity
$m$ and failure probability $\beta$. If $\rho>0$, and $\nu+\rho<0.25$, there
exists a $\rho$-replicable algorithm $\mathcal{A}^{\prime}$ for $D$ with
sample complexity $m^{\prime}=\tilde{O}(m(\log
1/\beta)^{3}/\rho^{2}(1/2-\eta)^{2})$ and failure probability at most
$4(\beta+\rho)$.

###  2.4 PAC-Learning

We start by defining PAC Learning, which is a canonical definition of
supervised learning proposed by Valiant [73] and Vapnik and Chervonenkis [74].
We first consider the realizable setting.

######  Definition 2.14 (Realizable PAC learning, [73, 74]).

A learning problem is defined by a hypothesis class $H$. For any distribution
$D$ over the input space $\mathcal{X}$, consider $m$ independent draws
$x_{1},x_{2},\cdots x_{m}$ from distribution $P$. A labeled sample of size $m$
is the set $\\{(x_{1},f(x_{1})),(x_{2},f(x_{2})),\cdots,(x_{m},f(x_{m}))\\}$
where $f\in H$. We say an algorithm $A$ is an $(\alpha,\beta)$-accurate PAC
learner for the hypothesis class $H$ if for all functions $f\in H$ and for all
distributions $D$ over the input space, $A$ on being given a labeled sample of
size $m$ drawn from $D$ and labeled by $f$, outputs a hypothesis $h$ such that
with probability greater than or equal to $1-\beta$ over the randomness of the
sample and the algorithm,

$\mathbf{Pr}_{x\in D}[h(x)\neq f(x)]\leq\alpha.$

We also consider a variant called agnostic PAC learning, where the labels of
the input dataset can be noisy.

######  Definition 2.15 (Agnostic PAC learning, [45, 74]).

A learning problem is defined by a hypothesis class $H$. We say an algorithm
$\mathcal{A}$ is an $(\alpha,\beta)$-accurate PAC learner for the hypothesis
class $H$ if for all distributions $D$ over input, output pairs, $\mathcal{A}$
on being given a sample of size $m$ drawn i.i.d. from $D$ outputs a hypothesis
$h$ such that with probability greater than or equal to $1-\beta$ over the
randomness of the sample and the algorithm,

${\mathtt{err}}_{D}(h)\leq\inf_{f\in H}{\mathtt{err}}_{D}(f)+\alpha.$

where ${\mathtt{err}}_{D}(h)=\mathbf{Pr}_{(x,y)\in D}[h(x)\neq y]$. In this
context, we will sometimes refer to PAC-learning as the realizable setting.

We will need uniform convergence for several of our results.

######  Theorem 2.16 (Uniform Convergence, e.g., [12]).

Let $H$ be a binary class of functions with domain $\mathcal{X}$. Let its VC
dimension be $d$. Then, for any distribution $D$ over $\mathcal{X}$, for all
$m>0$,

$\mathbf{Pr}_{x_{1},\dots,x_{m}\sim D}\left[\sup_{h_{z}\in
H}\left|\frac{1}{m}\sum_{i=1}^{m}\mathbbm{1}[h_{z}(x_{i})=1]-\mathbf{Pr}_{x\sim
D}[h_{z}(x)=1]\right|\geq\gamma\right]\leq 4(2m)^{d}e^{-\gamma^{2}m/8}.$

###  2.5 Correlated Sampling

In the correlated sampling problem, two (or more) players are given
probability distributions ${\cal P},{\cal Q}$ over the same finite set, and
with access to shared randomness. The players (without communicating) want to
sample from their respective distributions, while minimizing the probability
that their outputs disagree.

More formally, let $Y=\\{0,1\\}$, and for a set $\Omega$, $2^{\Omega}$ denotes
the set of all functions from $\Omega$ to $Y$, and $\Delta_{\Omega}$ denotes
the set of all sampleable distributions on $\Omega$. For two distributions
${\cal P}$, ${\cal Q}$ over $\Omega$, let $d_{TV}({\cal P},{\cal Q})$ denote
the total variational distance between ${\cal P}$ and ${\cal Q}$.

######  Definition 2.17.

(Correlated Sampling) A correlated sampling strategy for a finite set $\Omega$
with error $\varepsilon:[0,1]\to[0,1]$ is an algorithm
$CS:\Delta_{\Omega}\times{\cal R^{\prime}}$ and a distribution ${\cal
R^{\prime}}$ on random strings such that:

  * •

(Marginal Correctness) For all ${\cal P}\in\Delta_{\Omega}$ and $w\in\Omega$,
$\mathbf{Pr}_{r^{\prime}\sim{\cal R^{\prime}}}[CS({\cal
P},r^{\prime})=w]={\cal P}(w)$.

  * •

(Error Guarantee) For all ${\cal P},{\cal Q}\in\Delta_{\Omega}$,
$\mathbf{Pr}_{r^{\prime}\sim{\cal R^{\prime}}}[CS({\cal P},r^{\prime})\neq
CS({\cal Q},r^{\prime})]\leq\varepsilon(d_{TV}({\cal P},{\cal Q}))$

Several independent papers [56, 47, 27] give correlated sampling strategies
over finite sets, with $\epsilon(\delta)=\frac{2\delta}{1+\delta}$. These
algorithms use consistent sampling strategies, which are also used in several
other contexts such as sketching algorithms, approximation algorithms, and
parallel repetition theorems. However, despite the many uses of correlated
sampling, some basic questions remain open. Notably, it is not known whether
or not correlated sampling is possible for infinite domains, or whether
correlated sampling can be made efficient. (All known algorithms run in
exponential-time in the worst-case.) For a nice discussion as well as new
results on the optimality of these constructions see [14]. In Section 3.3, we
give another application of correlated sampling, showing how any perfectly
generalizing algorithm can be transformed into a replicable one, via
correlated sampling. As noted in the introduction, this is the only
implication that does not preserve computational efficiency, due to the
inefficiency of the correlated sampling strategy.

In Section 4.1, we prove that this is inherent: under standard cryptographic
assumptions any such transformation is intractable, and therefore under the
same cryptographic assumption, correlated sampling is intractable. Moreover,
we show in Section 4.2 that some assumption is necessary: if one-way functions
do not exist (that is, all poly-time computable functions can be efficiently
inverted), we show that this implies a polynomial-time algorithm for
correlated sampling.

###  2.6 Terminology: “Reproducibility” and “Replicability”

[48] introduced a mathematical definition referring to a particular stability
notion of a randomized learning algorithm which they originally called
“reproducibility” (reproducible algorithms). In this paper, we use the term
“replicability” (replicable algorithms) to refer to the same mathematical
definition.

This terminology choice is more in line with the most current Association for
Computing Machinery (ACM) guidance regarding artifact review and badging [5],
version 1.1, updated on August 24, 2020. This update changed the ACM’s
definitons of the terms “reproducible” and “replicable” to be more agreeable
with the terminology currently used by the National Academies of Sciences,
Engineering and Medicine (see Chapter 3: Understanding Reproducibility and
Replicability, page 46, in [62]).

According to both the ACM’s and National Academies’ current definitions,
“reproducibility” refers to the ability of a second experimental group to
obtain similar results using the _same_ input data. Meanwhile, “replicability”
refers to the ability of a second experimental group to obtain similar results
using input data and methods that may be different than those used by the
original experimental group.

The mathematical definition introduced in [48] is a guarantee that, with high
probability, two executions of the same algorithm with the same randomness and
different sample sets will produce the same answer. Since this guarantee is
over different sample sets, the mathematical definition does not fit the “same
input data” condition in the above definitions of reproducibility. Instead,
the mathematical definition is a specific type of replicability — if the
second experimental group runs the same algorithm with the same random string
(but on a new sample), the two groups’ results are guaranteed to be identical
with high probability.

##  3 Equating Stability: Differential Privacy, Perfect Generalization, and
Replicability

###  3.1 Replicability implies Approximate-DP

In [42], the authors show a sample-efficient reduction from differentially
private PAC learning to replicable PAC learning. In this section, we show
their technique generalizes to arbitrary statistical problems.666The argument
remains similar to [42], but requires a few changes to avoid union bounding
over failure probability which can be costly in settings beyond PAC learning.

Recall the definition of a statistical task in Definition 2.1. We will show
that any statistical task with a “good” replicable learner can also be solved
privately, without substantial blowup in runtime or sample complexity.

######  Theorem 3.1 (Replicability $\to$ DP).

Let $\mathcal{T}$ be a statistical problem. For all $\beta>0$, if there is a
$0.01$-replicable algorithm solving $\mathcal{T}$ using $n_{R}$ samples and
with failure probability $\beta$, then for any $0<\varepsilon,\delta\leq 1$
there is an $(\varepsilon,\delta)$-DP algorithm for $\mathcal{T}$ using
$n_{DP}$ samples with failure probability
$O\left(\beta\log\frac{1}{\beta}\right)$, where

$\displaystyle n_{DP}(\epsilon,\delta,\beta)\leq n_{R}\cdot
O\left(\frac{\log\delta^{-1}\log\beta^{-1}}{\varepsilon}+\log^{2}\beta^{-1}\right)$

This conversion relies on the following private algorithm for selecting an
approximate mode.

######  Theorem 3.2 (DP Selection [51, 25, 10]).

There exists some $c>0$ such that for every $\varepsilon,\delta>0$ and
$m\in\mathbb{N}$, there is an ($\varepsilon,\delta$)-DP algorithm that on
input $S\in\mathcal{X}^{m}$, outputs with probability $1$ an element $x\in X$
that occurs in $S$ at most $\frac{c\log\delta^{-1}}{\varepsilon}$ fewer times
than the true mode of $S$. Moreover, the algorithm runs in
$\text{poly}(m,\log(|\mathcal{X}|))$ time.

The idea, as in [42], is to use replicablity to construct a sample over the
output space where some correct solution appears many times. In particular,
given a replicable algorithm $\mathcal{A}$ on $n$ samples, consider the
following simple procedure adapted from [42]: partition a larger data set, run
$\mathcal{A}$ on each part, and privately output a commonly repeated element.

Result: Privately ouputs solution to $(\mathcal{X},R)$

Input: Statistical Problem $(\mathcal{X},R)$. Distribution $D$ over
$\mathcal{X}$, Replicable algorithm $\mathcal{A}$ on $n$ samples

Parameters:

  * •

Privacy and Correctness $\beta,\varepsilon,\delta>0$

  * •

Seed Number $k_{1}=O(\log\beta^{-1})$

  * •

Partition Number
$k_{2}=O\left(\frac{\log\delta^{-1}}{\varepsilon}+\log\beta^{-1}\right)\cdot
k_{1}$

Algorithm:

1

  1. 1.

For every $j\in[k_{1}]$ and $i\in[\frac{k_{2}}{k_{1}}]$ sample
$S_{i,j}\sim{\cal X}^{n}$

  2. 2.

Sample $k_{1}$ random strings $\\{r_{j}\\}$.

  3. 3.

Let $y_{i,j}=\mathcal{A}(S_{i,j};r_{j})$.

  4. 4.

Run ($\varepsilon,\delta$)-DP Selection on $\\{y_{i,j}\\}$ and denote the
output by $y^{*}$.

return $y^{*}$

Algorithm 1 DP-to-Replicability Reduction

Recalling the two-parameter definition of replicability (2.11 and 2.12), since
our subroutine is $0.01$-replicable and $\beta$-correct, it is also
$(0.1,0.1)$-replicable and $\beta$ correct. Therefore, the proof of Theorem
3.1 is an immediate consequence of the following proposition.

######  Proposition 3.3.

For all sufficiently small $\beta,\varepsilon,\delta>0$, if $\mathcal{A}$ is
$(0.1,0.1)$-replicable and has failure probability $\beta$, then Algorithm 1
is $(\varepsilon,\delta)$-private and has failure probability $O(\beta\log
1/\beta)$.

###### Proof.

Privacy is essentially immediate from DP Selection. This follows because the
input to selection based on a neighboring input database $T^{\prime}$ differs
in at most one of the $\\{y_{i}\\}$ (as we’ve partitioned the sample
disjointly). Thus the reduction automatically inherits
$(\varepsilon,\delta)$-privacy from DP Selection. The main interest in the
reduction, then, is maintaining correctness which we argue next. The proof
breaks into two parts:

  1. 1.

With probability $1-\beta/2$, some $y^{*}\in\\{y_{i}\\}$ appears at least
$t_{1}\coloneqq
2c\left(\frac{\log\delta^{-1}}{\varepsilon}+\log\beta^{-1}\right)$ times.

  2. 2.

With probability $1-\beta\log 1/\beta$, any element appearing at least
$t_{2}\coloneqq
c\left(\frac{\log\delta^{-1}}{\varepsilon}+\log\beta^{-1}\right)$ times is
correct.

The result then follows from observing that by a union bound both conditions
hold with probability at least $1-O(\beta\log 1/\beta)$, and conditioned on
this fact DP-Selection always outputs an element that occurs at least
$t_{1}-c\frac{\log\delta^{-1}}{\varepsilon}\geq t_{2}$ times (which is then
guaranteed to be correct).

It remains to prove the claims. For the first, note that since $\mathcal{A}$
is $(0.1,0.1)$-replicable, there exists some $.1$-good random string
$r^{*}\in\\{r_{j}\\}$ with probability at least $1-\beta/4$. By a Chernoff
bound, the probability that the canonical element corresponding to $r^{*}$
appears fewer than $t_{1}$ times is at most $\beta/4$, which proves the claim
(for a large enough choice of $k_{2}$).

Finally, we argue any common element is correct. Since $\mathcal{A}$ is a
$\beta$-correct algorithm, in expectation, the number of incorrect outputs is
$\beta k_{2}$. Hence, by Markov’s inequality, the probability that there are
more than $b=O(\frac{k_{2}}{\log\beta^{-1}})$ incorrect outputs is at most
$\beta\log 1/\beta$. For small enough choice of constant in the correctness of
our replicable algorithm,777Note this choice can be taken universally with
respect to all parameters and the statistical problem itself. we can make
$b<t_{2}$, so no element appearing at least $t_{2}$ times can be incorrect as
desired.

∎

###  3.2 Approximate-DP Implies One-Way Perfect Generalization

####  3.2.1 Preliminaries about Perfect Generalization

Perfect generalization (Definition 1.2) is a notion of stability that captures
the idea (like differential privacy) that an algorithm $\mathcal{A}$ does not
depend on its input samples too much.

We also consider the following “two-sample” version of this definition. This
is frequently easier to work with for symmetry reasons.

######  Definition 3.4.

An algorithm $\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$ is said to be
$(\beta,\varepsilon,\delta)$-sample perfectly generalizing, if for every
distribution $D$ over $\mathcal{X}$, with probability at least $1-\beta$ over
the draw of two i.i.d. samples $S_{1},S_{2}\sim D^{m}$,
$\mathcal{A}(S_{1})\approx_{\varepsilon,\delta}\mathcal{A}(S_{2})$.

Cummings et al. [31] prove the following lemma relating perfect generalization
to sample perfect generalization.

######  Lemma 3.5 ([31]).

If algorithm $\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$ is
$(\beta,\varepsilon,\delta)$-perfectly generalizing, then it is also
$(\beta,2\varepsilon,3\delta)$-sample-perfectly generalizing.

We can also prove a partial converse to this result; this will be frequently
useful since it allows us to prove sample perfect generalization and invoke
this result to get perfect generalization.

######  Lemma 3.6.

Fix $\beta,\varepsilon,\delta\in(0,1]$. If algorithm
$\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$ is
$(\beta,\varepsilon,\delta)$-sample perfectly generalizing, then it is also
$(\sqrt{\beta},\varepsilon,\delta+\sqrt{\beta})$-perfectly generalizing.

###### Proof.

Since $\mathcal{A}$ is $(\beta,\varepsilon,\delta)$-sample PG, we have that
for any distribution $D$ over $\mathcal{X}$, with probability at least
$1-\beta$ over the draw of two i.i.d. datasets $S_{1},S_{2}\sim D^{m}$, we
have that $\mathcal{A}(S_{1})\approx_{\varepsilon,\delta}\mathcal{A}(S_{2})$.
This guarantees by the reverse Markov inequality that for $d=1-\sqrt{\beta}$,

$\displaystyle\mathbb{E}_{S_{1}}[\mathbf{Pr}_{S_{2}}(\mathcal{A}(S_{1})\approx_{\varepsilon,\delta}\mathcal{A}(S_{2}))]\geq
1-\beta\implies$
$\displaystyle\mathbf{Pr}_{S_{1}}[\mathbf{Pr}_{S_{2}}(\mathcal{A}(S_{1})\approx_{\varepsilon,\delta}\mathcal{A}(S_{2}))\geq
d]\geq\frac{1-\beta-d}{1-d}\implies$
$\displaystyle\mathbf{Pr}_{S_{1}}[\mathbf{Pr}_{S_{2}}(\mathcal{A}(S_{1})\approx_{\varepsilon,\delta}\mathcal{A}(S_{2}))\geq
1-\sqrt{\beta}]\geq 1-\sqrt{\beta}.$

Now, set $Sim_{D}$ to be the distribution of $\mathcal{A}(S_{2})$ where the
randomness of the distribution is taken over both the randomness of the
algorithm and the dataset.

For any fixed dataset $S_{1}$, let $G_{S_{1}}$ be the set of datasets $S_{2}$
such that $\mathcal{A}(S_{1})\approx_{\varepsilon,\delta}\mathcal{A}(S_{2})$.

Then, we get that with probability at least $1-\sqrt{\beta}$ over the draw of
$S_{1}$, for any $O\subseteq Y$,

$\displaystyle\mathbf{Pr}_{Sim_{D}}[O]$
$\displaystyle=\mathbf{Pr}_{S_{2},\mathcal{A}}[\mathcal{A}(S_{2})\in O]$
$\displaystyle=\mathbf{Pr}_{S_{2},\mathcal{A}}[\mathcal{A}(S_{2})\in O\mid
S_{2}\in G_{S_{1}}]\mathbf{Pr}[S_{2}\in
G_{S_{1}}]+\mathbf{Pr}_{S_{2},\mathcal{A}}[\mathcal{A}(S_{2})\in O\mid
S_{2}\not\in G_{S_{1}}]\mathbf{Pr}[S_{2}\not\in G_{S_{1}}]$
$\displaystyle\leq\mathbf{Pr}_{S_{2},\mathcal{A}}[\mathcal{A}(S_{2})\in O\mid
S_{2}\in G_{S_{1}}]+\sqrt{\beta}$ $\displaystyle\leq
e^{\varepsilon}\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S_{1})\in
O]+\delta+\sqrt{\beta}.$

Similarly, we can also argue that

$\displaystyle\mathbf{Pr}_{Sim_{D}}[O]$
$\displaystyle=\mathbf{Pr}_{S_{2},\mathcal{A}}[\mathcal{A}(S_{2})\in O]$
$\displaystyle=\mathbf{Pr}_{S_{2},\mathcal{A}}[\mathcal{A}(S_{2})\in O\mid
S_{2}\in G_{S_{1}}]\mathbf{Pr}[S_{2}\in
G_{S_{1}}]+\mathbf{Pr}_{S_{2},\mathcal{A}}[\mathcal{A}(S_{2})\in O\mid
S_{2}\not\in G_{S_{1}}]\mathbf{Pr}[S_{2}\not\in G_{S_{1}}]$
$\displaystyle=\geq\mathbf{Pr}_{S_{2},\mathcal{A}}[\mathcal{A}(S_{2})]\in
O\mid S_{2}\in G_{S_{1}})(1-\sqrt{\beta})$ $\displaystyle\geq
e^{-\varepsilon}\left(\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S_{1})\in
O]-\delta\right)(1-\sqrt{\beta})$ $\displaystyle\geq
e^{-\varepsilon}\left(\mathbf{Pr}_{\mathcal{A}}(\mathcal{A}(S_{1})\in
O]-\delta-\sqrt{\beta}\right).$

Hence, with probability at least $1-\sqrt{\beta}$ over the draw of $S_{1}$,

$Sim_{D}\approx_{\varepsilon,\delta}\mathcal{A}(S_{1}).$

∎

We also define a notion of “one-sided” perfect generalization which only
requires the probability of events under $A(S)$ not to increase too much
relative to their probability under the simulator distribution $Sim_{D}$. This
new definition will be crucial to show the equivalence between replicability
and perfect generalization, as well as for some of our applications.

######  Definition 3.7 (One-way perfect generalization).

An algorithm $\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$ is said to be
$(\beta,\varepsilon,\delta)$-one-way perfectly generalizing if for every
distribution $D$ over $\mathcal{X}$, there exists a distribution $Sim_{D}$
such that with probability at least $1-\beta$ over the draw of an i.i.d.
sample $S\sim D^{m}$, for every output set $O\subseteq\mathcal{Y}$ we have
that

$\mathbf{Pr}[\mathcal{A}(S)\in O]\leq
e^{\varepsilon}\mathbf{Pr}_{Sim_{D}}[O]+\delta.$

Next, we prove a simple lemma relating the parameters achievable with perfect
generalization.

######  Lemma 3.8.

Fix $m\in\mathbb{N}$, $\beta,\varepsilon,\delta\in(0,1]$. Let
$\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$ be a
$(\beta,\varepsilon,\delta)$-one-way perfectly generalizing algorithm. Then,
$\mathcal{A}$ is also $(\beta,0,2\varepsilon+\delta)$-perfectly generalizing.

###### Proof.

By the definition of one-way perfect generalization, we have that for all
distributions $D$ over $\mathcal{X}$, there exists a distribution $Sim_{D}$,
such that with probability $1-\beta$ over the draw of $S$, for all
$O\subseteq\mathcal{Y}$,

$\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in O]\leq
e^{\varepsilon}\mathbf{Pr}_{Sim_{D}}[O]+\delta.$

Using the fact that for $\varepsilon\leq 1$, $e^{\varepsilon}\leq
1+2\varepsilon$, we get that

$\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
O]\leq\mathbf{Pr}_{Sim_{D}}[O](1+2\varepsilon)+\delta,$

which gives us that

$\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
O]\leq\mathbf{Pr}_{Sim_{D}}[O]+2\varepsilon+\delta.$

Now, since this works for any set $O$, consider applying it to $O^{c}$. Then,
we get that

$\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
O^{c}]\leq\mathbf{Pr}_{Sim_{D}}[O^{c}]+2\varepsilon+\delta,$

which implies (by writing $\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
O^{c}]=1-\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in O]$ and likewise for
$Sim_{D}$ and doing some algebraic manipulation) that

$\mathbf{Pr}_{Sim_{D}}[O]\leq\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
O]+2\varepsilon+\delta.$

Hence, the lemma is proved. ∎

[31] also proved a strong relationship between $(\varepsilon,0)$-differential
privacy and perfect generalization. Specifically, they proved the following.

######  Theorem 3.9 ([31]).

If algorithm $\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$ is
$(\varepsilon,0)$-differentially private, then for all $\beta>0$, it is
$(\beta,\varepsilon\sqrt{2m\ln(2|\mathcal{Y}|/\beta)},0)$-perfectly
generalizing.

They left establishing similar relationships between
$(\varepsilon,\delta)$-differential privacy and perfect generalization as an
open question. We resolve this question for finite outcome spaces. Our
argument is indirect and involves showing that any approximate differentially
private algorithm is one-way perfectly generalizing. We will later use this to
prove that any approximate differentially private algorithm can be compiled
into another algorithm that is perfectly generalizing (under the original
definition). We do this through the tool of max information, that we discuss
next.

####  3.2.2 Preliminaries about Max Information

The notion of max information was formulated in work on the connection between
differential privacy and adaptive data analysis. It quantitatively captures
the degree of correlation between two random variables, by comparing the joint
distribution of the random variables to the product measure. Intuitively, if
the joint distribution and the product measure are “close”, then the random
variables are not too correlated with each other.

######  Definition 3.10 (Based on [32]).

The $\beta$-approximate max information between two correlated random
variables $X$ and $Z$, denoted $I^{\beta}_{\infty}(X,Z)$, is defined as the
minimum (infimum) value $k$ such that for all output sets $O$, we have that

$\displaystyle\mathbf{Pr}_{(a,b)\sim(X,Z)}[(a,b)\in O]\leq
2^{k}\mathbf{Pr}_{(a,b)\sim X\otimes Z}[(a,b)\in O]+\beta$ (2)

where $X\otimes Z$ represents the product measure of the $2$ random variables.

In this paper, we will be concerned about the degree of correlation between a
randomly sampled dataset, and the output of an algorithm run on that dataset.
Intuitively, replicability requires that an algorithm’s output does not depend
too much on the specific input sample it gets, so the max information between
these two random variables will be a useful quantity to analyze.

####  3.2.3 Approximate Differential Privacy to Bounded Max Information

Connections between max information and differential privacy have been
previously studied. Rogers, Roth, Smith and Thakkar [66] give a bound on the
max information between an approximate DP algorithms’ outputs and its inputs
(Theorem 3.1 in their paper). In fact, they prove the following general
statement that can be seen by examining their proof of Theorem 3.1.

######  Lemma 3.11 ([66]).

Fix $m\in\mathbb{N}$, $\varepsilon\in(0,1/2]$ and
$\delta\in[0,\varepsilon/15)$. Let $\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$
be an $(\varepsilon,\delta)$-DP algorithm. Then, for any distribution $D$ over
$\mathcal{X}$, if $S\sim D^{m}$, for all $t>0$,
$I^{\beta}_{\infty}(S;\mathcal{A}(S))\leq m\nu+6t\varepsilon\sqrt{m}$, where
$\beta=e^{-t^{2}/2}+cm\sqrt{\frac{\delta}{\varepsilon}}$, and
$\nu=C(\varepsilon^{2}+\sqrt{\frac{\delta}{\varepsilon}})$ for some
sufficiently large constants $c,C$.

We instantiate this lemma with parameters that are suitable for our
application.

######  Corollary 3.12.

Fix $m\in\mathbb{N}$, sufficiently small $\rho\in(0,1)$. Let
$\varepsilon=\frac{\rho}{\sqrt{8m\log(1/\rho)}}$,
$\delta\leq\frac{\varepsilon\rho^{6}}{m^{2}}$. Let
$\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$ be an $(\varepsilon,\delta)$-DP
algorithm. Then, for any distribution $D$ over $\mathcal{X}$, if $S\sim
D^{m}$, $I^{\rho^{3}}_{\infty}(S;\mathcal{A}(S))\leq O(\rho)$.

###### Proof.

Substituting the value of $\varepsilon$, $\delta$, and setting
$t=\sqrt{8\log(1/\rho)}$ in the expression for $\beta$ in Lemma 3.11, we get

$\beta=e^{-4\log(1/\rho)}+cm\sqrt{\frac{\rho^{6}}{m^{2}}}=O(\rho^{3}).$

Substituting in the expression for $\nu$ in Lemma 3.11 gives

$\nu=C\left(\varepsilon^{2}+\sqrt{\frac{\delta}{\varepsilon}}\right)\leq
C\left(\frac{\rho^{2}}{m}+\frac{\rho^{3}}{m}\right)=O\left(\frac{\rho^{2}}{m}\right).$

Substituting the values of $\nu,t$, and $\varepsilon$ in the upper bound for
max information gives

$I^{\rho^{3}}_{\infty}(S;\mathcal{A}(S))\leq
m\nu+6t\varepsilon\sqrt{m}=\rho^{2}+6\rho=O(\rho).$

∎

In general, one can convert an $(\varepsilon,\delta)$-differentially private
algorithm with $\varepsilon=O(1)$ and $\delta=1/\operatorname{poly}(n)$ into a
bounded max-information algorithm by first amplifying the privacy parameters:

######  Corollary 3.13.

There are constants $c,C>0$ such that the following holds. Let $\gamma>0$.
Suppose $\mathcal{A}:\mathcal{X}^{n}\to\mathcal{Y}$ is an
$(\varepsilon,\delta)$-differentially private algorithm solving a statistical
task up to some failure probability $\beta$ such that $\varepsilon\in(0,1)$
and
$\delta\leq\min\\{\gamma^{2}/c^{2},\rho^{2}/C^{2}\\}\rho^{4}/64\varepsilon^{3}(2C\rho+\sqrt{72\log(2/\gamma)})^{2}n^{4}$.
Then there is an algorithm
$\mathcal{A}^{\prime}:\mathcal{X}^{m}\to\mathcal{Y}$ solving the same
statistical task with the same failure probability $\beta$, such that

$m=4\varepsilon^{2}n^{2}\cdot\left(\frac{2C}{\rho}+\frac{\sqrt{72\log(2/\gamma)})}{\rho^{2}}\right),$

and for every distribution $D$ over $\mathcal{X}$, if $S\sim D^{m}$ we have
$I_{\infty}^{\gamma}(S;\mathcal{A}(S))\leq\rho$. Moreover, the conversion from
$\mathcal{A}$ to $\mathcal{A}^{\prime}$ preserves computational efficiency.

###### Proof.

The algorithm $\mathcal{A}^{\prime}$ simply samples $n$ items without
replacement from $S$ and runs $\mathcal{A}$ on the result. This perfectly
preserves correctness with respect to any statistical task. By Lemma 2.9, we
have that $\mathcal{A}^{\prime}$ is
$(\varepsilon^{\prime},\delta^{\prime})$-differentially private for

$\varepsilon^{\prime}=\frac{2n}{m}\leq\frac{1}{\sqrt{m}}\min\left\\{\sqrt{\frac{\rho}{2C}},\frac{\rho}{\sqrt{72\log(2/\gamma)}}\right\\},\qquad\delta^{\prime}=\frac{n}{m}\cdot\delta.$

Note that these parameters ensure that

$\frac{\delta^{\prime}}{\varepsilon^{\prime}}=\frac{\delta}{e^{\varepsilon}-1}\leq\frac{\delta}{\varepsilon}\leq\min\left\\{\frac{\gamma^{2}}{4c^{2}m^{2}},\frac{\rho^{2}}{4C^{2}m^{2}}\right\\}.$

Now set $t=\sqrt{2\log(2/\gamma)}$ in the statement of Lemma 3.11, which
ensures that

$e^{-t^{2}/2}+cm\sqrt{\frac{\delta^{\prime}}{\varepsilon^{\prime}}}\leq\frac{\gamma}{2}+cm\sqrt{\frac{\gamma^{2}}{4c^{2}m^{2}}}\leq\gamma.$

Then the lemma implies that

$\displaystyle I_{\infty}^{\gamma}(S;\mathcal{A}(S))$ $\displaystyle\leq
Cm\left((\varepsilon^{\prime})^{2}+\sqrt{\frac{\delta^{\prime}}{\varepsilon^{\prime}}}\right)+6t\varepsilon^{\prime}\sqrt{m}$
$\displaystyle\leq
Cm\left(\frac{\rho}{2Cm}+\frac{\rho}{2Cm}\right)+6\sqrt{2\log(2/\gamma)}\cdot\frac{\rho}{\sqrt{72\log(2/\gamma)}}$
$\displaystyle\leq\rho.$

∎

####  3.2.4 Bounded Max Information to One-Way Perfect Generalization

Next, we prove a key lemma relating bounded max-information to one-way perfect
generalization. The approach we follow is similar to that used to derive
relationships between pointwise $(\varepsilon,\delta)$-indistinguishability
and $(\varepsilon,\delta)$-indistinguishability in Lemma 3.3 of [55].

######  Lemma 3.14.

Fix $m\in\mathbb{N}$, $k>0$, $\beta\in(0,1)$ and
$\hat{\beta}=\sqrt{\frac{\beta}{1-2^{-k}}}$. Let
$\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$ be an algorithm. Then, for every
distribution $D$ over $\mathcal{X}$ and $S\sim D^{n}$, if
$I^{\beta}_{\infty}(S;\mathcal{A}(S))\leq k$, then $\mathcal{A}$ is
$(\hat{\beta},2k,\hat{\beta})$-one-way perfectly generalizing.

###### Proof.

The canonical distribution $Sim_{D}$ we will consider is the distribution of
$\mathcal{A}(S^{\prime})$, where the randomness is over both $S^{\prime}\sim
D^{m}$, and the internal randomness of $\mathcal{A}$.

We start by defining a set of ‘bad’ outputs for each fixed dataset $S$, i.e.
outputs on which the probability mass of $\mathcal{A}(S)$ is substantially
larger than that of the canonical distribution $Sim_{D}$. Formally, for each
dataset $S$, let

$B_{S}=\\{y\in\mathcal{Y}:\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)=y]\geq
2^{2k}\mathbf{Pr}_{S^{\prime}\sim
D^{m},\mathcal{A}}[\mathcal{A}(S^{\prime})=y]\\}.$

Next, we define a set of ordered pairs consisting of datasets and their
corresponding ‘bad’ outputs. Formally, let

$\Theta=\\{(S,y):S\in\mathtt{supp}(D^{m}),y\in B_{S}\\}.$

Our goal will be to prove that with high probability over a draw of a dataset
$S$, $\mathcal{A}(S)$ lands in the bad set $B_{S}$ with small probability.
This can then be used to establish one-way perfect generalization.

With this in mind, consider the expression
$\mathbb{E}_{S}[\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
B_{S}]]=\mathbb{E}_{S}[\mathbf{Pr}_{\mathcal{A}}[(S,\mathcal{A}(S))\in\Theta]]$.
By the law of total probability, this is equal to $\mathbf{Pr}_{S\sim
D^{m},\mathcal{A}}[(S,\mathcal{A}(S))\in\Theta]$. Using the definition of max-
information, we get that

$\displaystyle\mathbf{Pr}_{S\sim
D^{m},\mathcal{A}}[(S,\mathcal{A}(S))\in\Theta]\leq
2^{k}\mathbf{Pr}_{S,S^{\prime}\sim
D^{m},\mathcal{A}}[(S,\mathcal{A}(S^{\prime}))\in\Theta]+\beta.$ (3)

Now, analyzing the term $\mathbf{Pr}_{S,S^{\prime}\sim
D^{m},\mathcal{A}}[(S,\mathcal{A}(S^{\prime}))\in\Theta]$, we get

$\displaystyle\mathbf{Pr}_{S,S^{\prime}\sim
D^{m},\mathcal{A}}[(S,\mathcal{A}(S^{\prime}))\in\Theta]$
$\displaystyle=\sum_{T\in\mathtt{supp}(D^{m})}\mathbf{Pr}[S=T]\mathbf{Pr}_{S^{\prime}\sim
D^{m},\mathcal{A}}[\mathcal{A}(S^{\prime})\in B_{T}]$
$\displaystyle\leq\sum_{T\in\mathtt{supp}(D^{m})}\mathbf{Pr}[S=T]2^{-2k}\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
B_{T}]$
$\displaystyle=2^{-2k}\sum_{T\in\mathtt{supp}(D^{m})}\mathbf{Pr}[S=T]\mathbf{Pr}_{\mathcal{A},S\sim
D^{m}}[A(S)\in B_{S}\mid S=T]$ $\displaystyle=2^{-2k}\mathbf{Pr}_{S\sim
D^{m},\mathcal{A}}[(S,\mathcal{A}(S))\in\Theta],$

where the first inequality is by the definition of $B_{T}$ and the last
equality is by the law of total probability. Substituting the above in (3), we
get that

$\displaystyle\mathbf{Pr}_{S\sim
D^{m},\mathcal{A}}[(S,\mathcal{A}(S))\in\Theta]\leq 2^{-k}\mathbf{Pr}_{S\sim
D^{m},\mathcal{A}}[(S,\mathcal{A}(S)\in\Theta]+\beta.$

Rearranging, this gives us that

$\displaystyle\mathbb{E}_{S}[\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
B_{S}]]=\mathbf{Pr}_{S\sim
D^{m},\mathcal{A}}[(S,\mathcal{A}(S))\in\Theta]\leq\frac{\beta}{1-2^{-k}}=\hat{\beta}^{2}.$
(4)

Finally, by Markov’s inequality and the above equation, we can write the
following.

$\displaystyle\mathbf{Pr}_{S}[\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
B_{S}]>\hat{\beta}]\leq\frac{\mathbb{E}_{S}[\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
B_{S}]]}{\hat{\beta}}\leq\hat{\beta}.$ (5)

This implies that with probability $1-\hat{\beta}$ over $S\sim D^{m}$,
$\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\not\in B_{S}]>1-\hat{\beta}$.
Finally, we can write with probability $1-\hat{\beta}$ over $S\sim D^{m}$, for
every $O\subseteq\mathcal{Y}$,

$\displaystyle\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in O]$
$\displaystyle=\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
O\mid\mathcal{A}(S)\in B_{S}]\mathbf{Pr}[\mathcal{A}(S)\in B_{S}]$
$\displaystyle+\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
O,\mathcal{A}(S)\not\in B_{S}]$ $\displaystyle\leq
1\cdot\hat{\beta}+\mathbf{Pr}_{\mathcal{A}}[\mathcal{A}(S)\in
O,\mathcal{A}(S)\not\in B_{S}]$
$\displaystyle\leq\hat{\beta}+2^{2k}\mathbf{Pr}_{S^{\prime}\sim
D^{m},\mathcal{A}}[\mathcal{A}(S^{\prime})\in O,\mathcal{A}(S^{\prime})\not\in
B_{S^{\prime}}]$
$\displaystyle\leq\hat{\beta}+2^{2k}\mathbf{Pr}_{S^{\prime}\sim
D^{m},\mathcal{A}}[\mathcal{A}(S^{\prime})\in O].$

This completes the proof. ∎

We note that the above proof sets the failure probability due to data sampling
and that due to bad coins of the algorithm to be the same. Other tradeoffs
between these can be obtained by using Markov’s inequality with different
parameters in Equation 5. We chose them to be equal to each other for
simplicity of presentation and because that is the setting of interest in our
applications.

Observe that combining Lemma 3.11 and Lemma 3.14 above gives the following
connection between differential privacy and one-way perfect generalization.

######  Corollary 3.15.

Fix $m\in\mathbb{N}$, $\varepsilon\in(0,1/2]$ and
$\delta\in[0,\varepsilon/15)$. Let $\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$
be an $(\varepsilon,\delta)$-DP algorithm. Then, for sufficiently large
constants $c,C$, for all $t>0$, $\mathcal{A}$ is
$(\delta^{\prime},\varepsilon^{\prime},\delta^{\prime})$-one-way perfectly
generalizing, where
$\varepsilon^{\prime}=Cm(\varepsilon^{2}+\sqrt{\frac{\delta}{\varepsilon}})+6t\varepsilon\sqrt{m}$,
and $\delta^{\prime}=\frac{\beta}{1-2^{-O(\varepsilon^{\prime})}}$, where
$\beta=e^{-t^{2}/2}+cm\sqrt{\frac{\delta}{\varepsilon}}$.

As an example of the kind of result this can give, we show what we’d get if we
instantiated it with our parameters of interest (as in Corollary 3.12).

######  Corollary 3.16.

Fix $m\in\mathbb{N}$, sufficiently small $\rho\in(0,1]$. Let
$\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$ be an $(\varepsilon,\delta)$-DP
algorithm, where $\varepsilon=\frac{\rho}{\sqrt{8m\log(1/\rho)}}$,
$\delta\leq\frac{\varepsilon\rho^{6}}{m^{2}}$. Then, $\mathcal{A}$ is
$(O(\rho),O(\rho),O(\rho))$-one-way perfectly generalizing.

###### Proof.

From Corollary 3.12, we get that $I^{\rho^{3}}_{\infty}(S;\mathcal{A}(S))\leq
O(\rho)$. Substituting $k=\rho$ and $\beta=\rho^{3}$ in Lemma 3.14, we get
that $\hat{\beta}=\sqrt{\frac{c\rho^{3}}{1-2^{-O(\rho)}}}\leq
O(\sqrt{\rho^{2}})=O(\rho)$ (where the first inequality is since
$\frac{1}{1-2^{-O(\rho)}}=\frac{2^{O(\rho)}}{2^{O(\rho)}-1}\leq\frac{2}{2^{O(\rho)}-1}\leq\frac{C}{\rho}$
for some constant $C$, since $2^{c\rho}=e^{c\rho\ln 2}$ and $e^{x}\geq 1+x$
for all real $x$). This gives us from Lemma 3.14 that $\mathcal{A}$ is
$(O(\rho),O(\rho),O(\rho))$-one-way perfectly generalizing. ∎

###  3.3 Perfect Generalization Implies Replicability

In this section will show that the class of one-way perfectly generalizing
algorithms, which includes the special case of (two-way) perfectly
generalizing algorithms, can be transformed to replicable algorithms.

Let $CS(Q,\mathcal{Y},r^{\prime})$ represent a correlated sampling procedure
over domain $\mathcal{Y}$ sampling from a distribution $Q$ over $\mathcal{Y}$
with public randomness $r^{\prime}$. (See Section 2.5 for background on
correlated sampling). We now describe our transformation.

1 Input: dataset $S=(s_{1},\ldots,s_{n})$, description of one-way perfectly
generalizing algorithm $\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$

Output: $i\in\mathcal{U}$

1: Let $Q_{S}$ represent the distribution of $\mathcal{A}(S)$.

2: Output $CS(Q_{S},\mathcal{Y},r^{\prime})$ where $r^{\prime}$ is the random
string drawn in the correlated sampling algorithm.

Algorithm 2 Transformation from one-way perfectly generalizing algorithm to
replicable algorithm

The key idea is that correlated sampling converts total variation distance
into collision probability, which is the notion that is used in the definition
of replicability.

We now use this to prove the main theorem of this section.

######  Theorem 3.17.

Fix $m\in\mathbb{N}$ and $\beta,\varepsilon,\delta\in(0,1)$. Let
$A:\mathcal{X}^{m}\to\mathcal{Y}$ be a $(\beta,\varepsilon,\delta)$-one-way
perfectly generalizing algorithm with finite output space. Then, for any
distribution $D$ over $\mathcal{X}$, if $S\sim D^{m}$, Algorithm 2 when run on
dataset $S$ and with access to $\cal{A}$ is
$4(\beta+2\varepsilon+\delta)$-replicable.

###### Proof.

By Lemma 3.8, we have that $\mathcal{A}$ is also
$(\beta,0,2\varepsilon+\delta)$-perfectly generalizing. For any distribution
$D$ over $\mathcal{X}$, let $Sim_{D}$ be the canonical distribution witnessing
the perfect generalization property. Then, by the definition of
$(0,2\varepsilon+\delta)$-indistinguishability, we have that with probability
at least $1-\beta$ over a draw of a random dataset $S\sim D^{m}$,

$d_{TV}(\mathcal{A}(S),Sim_{D})\leq 2\varepsilon+\delta.$

From the guarantee of correlated sampling, we have that

$\mathbf{Pr}_{r^{\prime}\sim R}[CS(Q_{S},\mathcal{Y},r^{\prime})\neq
CS(Sim_{D},\mathcal{Y},r^{\prime})]\leq 2d_{TV}(Q_{S},Sim_{D}).$

Using the bound on TV distance from perfect generalization, we get that with
probability at least $1-2\beta$ over the draw of two datasets $S_{1},S_{2}\sim
D^{m}$, we have that

$\mathbf{Pr}_{r^{\prime}\sim R}[CS(Q_{S_{1}},\mathcal{Y},r^{\prime})\neq
CS(Sim_{D},\mathcal{Y},r^{\prime})]\leq 2(2\varepsilon+\delta)$

and

$\mathbf{Pr}_{r^{\prime}\sim R}[CS(Q_{S_{2}},\mathcal{Y},r^{\prime})\neq
CS(Sim_{D},\mathcal{Y},r^{\prime})]\leq 2(2\varepsilon+\delta).$

Consider the event $CS(Q_{S_{1}},\mathcal{Y},r^{\prime})\neq
CS(Q_{S_{2}},\mathcal{Y},r^{\prime})$. It is clear that this implies that
either $CS(Q_{S_{1}},\mathcal{Y},r^{\prime})\neq
CS(Sim_{D},\mathcal{Y},r^{\prime})$ or
$CS(Q_{S_{2}},\mathcal{Y},r^{\prime})\neq CS(Sim_{D},\mathcal{Y},r^{\prime})$.
Hence, we can write that with probability $1-2\beta$ over draws of $S_{1}$ and
$S_{2}$,

$\mathbf{Pr}_{r^{\prime}\sim R}[CS(Q_{S_{1}},\mathcal{Y},r^{\prime})\neq
CS(Q_{S_{2}},\mathcal{Y},r^{\prime})]\leq 4(2\varepsilon+\delta).$

Taking the expectation with respect to the draws of $S_{1}$ and $S_{2}$ gives
us

$\mathbf{Pr}_{r^{\prime}\sim R,S_{1},S_{2}\sim
D^{m}}[CS(Q_{S_{1}},\mathcal{Y},r^{\prime})\neq
CS(Q_{S_{2}},\mathcal{Y},r^{\prime})]\leq 4(2\varepsilon+\delta+\beta)$

which proves the result. ∎

Combining the above result and Corollary 3.16, we get a transformation from
approximate differentially private algorithms to replicable algorithms.

######  Corollary 3.18.

Fix $m\in\mathbb{N}$, sufficiently small $\rho\in(0,1)$. Let
$\varepsilon=\frac{\rho}{\sqrt{8m\log(1/\rho)}}$,
$\delta\leq\frac{\varepsilon\rho^{6}}{m^{2}}$. Let
$\mathcal{A}:\mathcal{X}^{m}\to\mathcal{Y}$ be an $(\varepsilon,\delta)$-DP
algorithm with finite output space. Fix a distribution $D$ over $\mathcal{X}$,
and let $S\sim D^{m}$. Then, Algorithm 2 run with inputs $S$ and algorithm
$\mathcal{A}$ is $O(\rho)$-replicable. Additionally, on any fixed dataset, the
output distribution of Algorithm 2 is the same as that of $\mathcal{A}$.

###### Proof.

From Corollary 3.16, we have that Algorithm $\mathcal{A}$ is
$(O(\rho),O(\rho),O(\rho))$-one-way perfectly generalizing. Then, applying
Theorem 3.17 proves that the transformation in Algorithm 2 gives a
$O(\rho)$-replicable algorithm. Correlated sampling does not change the
marginal distribution of the algorithm applied to a dataset and hence the
second part of the corollary is proved. ∎

###  3.4 Replicability Implies Perfect Generalization

In this section, we show how to convert a replicable algorithm to a perfectly
generalizing algorithm at a poly-logarithmic cost in $1/\delta$ (where
$\delta$ is the additive perfect generalization parameter).

It’s straightforward to show that $(\delta,\delta)$-replicability can be used
to obtain $(O(\delta),0,O(\delta))$-perfect generalization by translating from
collision probability to total variation distance. However, since we typically
want $\delta$ to be very small (often inverse polynomial in the number of
samples $m)$, obtaining such small parameters starting from, say,
$0.1$-replicability comes at a significant cost. This is because amplifying
$0.1$-replicability to $(\delta,\delta)$-replicability incurs a multiplicative
sample complexity overhead of $O(1/\delta^{2})$, which is tight by known lower
bounds for replicability [48, Theorem 7.1], and prohibitively large for many
applications. For example, our lower bounds showing tasks where replicability
has quadratically higher sample cost than differential privacy (see Section 5)
follow from proving such lower bounds on perfectly generalizing algorithms
with $\delta$ polynomially small in the dataset size, and then applying our
conversion from replicability to perfect generalization. If such a conversion
required $1/\delta^{2}$ samples, then this would not give us any non-trivial
lower bounds on the sample cost associated with replicably solving these
problems.

However, this idea still leaves hope, because it achieves $\varepsilon=0$.
Hence, by settling for larger $\varepsilon$, we hope to avoid this problem.

Our approach is inspired by a natural attempt to amplify weak replicability
parameters into strong parameters. Suppose we wish to turn a
$(0.01,0.01)$-replicable algorithm $A$ into a $(0.01,\delta)$-replicable one.
We know that with probability at least $0.99$ over the choice of the
randomness $r$ for $A$, there is a canonical output $z$ such that $A(S;r)=z$
with high probability over the sample $S$. Consider running $A$ using
$k=O(\log(1/\delta))$ independent sequences of coin tosses,
$r_{1},\dots,r_{k}$, then with probability $1-\delta$, at least one of these
sequences will have such a canonical output. Moreover, when such a canonical
output exists, we can identify it by running $A(\cdot;r_{j})$ on many
independent _samples_ $S$ and choosing the plurality outcome if it appears
enough times. Unfortunately, there is an obstacle here to directly designing a
replicable algorithm. The problem is that there may be many good sequences of
coin tosses, each with their own canonical outputs, and it is unclear how to
replicably identify a single one.

By relaxing our goal to achieving perfect generalization instead of
replicability, we can instead use the exponential mechanism to _sample_ from
the set of plurality outcomes. We define the score of the plurality output
$c_{j}$ for coin $r_{j}$ to be the number of datasets $S$ on which
$A(S;r_{j})=c_{j}$, and sample such a $c_{j}$ with probability proportional to
exponential in its score. We are able to show that the resulting algorithm is
$(\delta,\varepsilon,\delta)$-perfectly generalizing with $\varepsilon>0$, but
there are several technical nuances that make our analysis not quite
straightforward from the standard guarantees of the exponential mechanism. For
instance, we need to deal with the fact that the sets of plurality outputs
could differ when our algorithm is run on two i.i.d. datasets drawn from the
same distribution. Another interesting feature of this proof is that unlike
standard uses of the exponential mechanism to obtain differential privacy or
perfect generalization, we need to invoke the accuracy of the exponential
mechanism in our proof of perfect generalization.

1 Input: Sample access to distribution $D$, description of
$(0.01,0.01)$-replicable algorithm
$\mathcal{A}:\mathcal{X}^{*}\to\mathcal{Y}$, sample complexity parameter $m$,
perfect generalization parameters $\varepsilon,\delta,\beta$

Output: $y\in\mathcal{Y}$

1: Let $k=O(\log(1/\delta))$, and
$t=O\left(\frac{\log^{4}(1/\beta)\log(1/\varepsilon)}{\varepsilon^{2}}\right)$.

2: Draw uniformly random coins $r_{1},r_{2},\dots,r_{k}$ for algorithm
$\mathcal{A}$.

3: Draw $k$ sets $\mathbf{S_{i}}$, each of $t$ samples $S_{i,j}\sim D^{m}$.

4: for all $j\in[k]$ do

5: for all $i\in[t]$ do

6: Run $\mathcal{A}$ with coins $r_{j}$ and sample $S_{i,j}$ to get output
$z_{i,j}$.

7: end for

8: Let $c_{j}=\arg\max_{z\in\mathcal{Y}}\sum_{i=1}^{t}\mathbbm{1}[z_{i,j}=z]$,
and let
$\operatorname{score}\left((j,c_{j}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)=\sum_{i=1}^{t}\mathbbm{1}[z_{i,j}=c_{j}]$.

9: end for

10: Let $C=\\{(1,c_{1}),\dots,(k,c_{k})\\}$. Run the exponential mechanism on
the set $C$ with the score function $\operatorname{score}(.,.)$, sensitivity
parameter $4\sqrt{t\log(8kt/\beta)}$, and privacy parameter $\varepsilon$ to
get value $(j^{*},c_{j^{*}})$.

11: return output $c_{j^{*}}$ of the previous step.

Algorithm 3 Transformation from replicable algorithm $\mathcal{A}$ to
perfectly generalizing algorithm $\mathcal{A}^{\prime}$

We prove that the above algorithm is sample perfectly generalizing. Note that
this can be converted to a perfectly generalizing algorithm with
asymptotically the same parameters (for both perfect generalization and
accuracy) by setting the $\delta$ parameter to be $\delta^{2}$ instead and
invoking Lemma 3.6.

######  Theorem 3.19.

Fix sufficiently small $\delta,\gamma>0$ and $0<\varepsilon\leq 1$. Every
$(0.01,0.01)$-replicable algorithm $\mathcal{A}$ with $m$ samples that
succeeds on a statistical task with probability at least $1-\gamma^{2}$ can be
converted to a $(2\delta,\varepsilon,2\delta)$-sample perfectly generalizing
algorithm $\mathcal{A}^{\prime}$ taking
$O\left(\frac{m\log(1/\varepsilon)}{\varepsilon^{2}}\operatorname{poly}\log(1/\delta)\right)$
samples, that succeeds on the statistical task with probability at least
$1-O(\delta)-\gamma\log(1/\delta)$.

###### Proof.

Fix a distribution $D$ over the input set $\mathcal{X}$. Our proof is
constructive; the corresponding algorithm is given in Algorithm 3
($\mathcal{A}^{\prime}$), and we feed it with the following inputs: a
description of algorithm $\mathcal{A}$, sample complexity parameters $m$, and
perfect generalization parameters $(\delta,\varepsilon,\delta)$. (We also give
it sample access to distribution $D$). We will start by proving sample perfect
generalization of Algorithm 3.

######  Claim 3.20.

Algorithm $\mathcal{A}^{\prime}$ (represented in Algorithm 3) with the input
parameters specified in the previous paragraph is
$(2\delta,\varepsilon,2\delta)$-sample perfectly generalizing.

###### Proof.

Consider two samples $S$ and $S^{\prime}$ drawn independently from $D^{mkt}$.
We consider Algorithm 3 run on both of these samples and argue that their
output distributions are close in the sense required by sample perfect
generalization.

##### Step 1: At least one coin sequence is good w.h.p.

We say that a choice of the random coin tosses of Algorithm $\mathcal{A}$ is
“good” if it has a $0.99$-canonical output and call it “bad” otherwise. Then
by the two parameter definition of replicability, a random coin sequence is
“bad” with probability at most $0.01$. Hence, the probability that all $k$
coins sequences drawn in Step 2 of Algorithm 3 are bad is at most
$(0.01)^{k}\leq\delta^{2}$ for $k=O(\log(1/\delta))$. Let $E_{coin}$ represent
the event that there is at least one good coin. We will now condition on
$E_{coin}$ occurring; fix any set of coins $r_{1},\dots,r_{k}$ that has non-
zero probability of occurring under this conditioning. We will first consider
$\mathcal{A}$ run on the two independent datasets $S$ and $S^{\prime}$ with
the same random coins fixed above.

##### Step 2: Empirical output frequencies are close on two independent
datasets.

We define stage $j$ of Algorithm 3 as the process involved in generating
$c_{j}$ (i.e., one iteration of the outer loop in Step 4). We now use uniform
convergence to argue that with high probability over the samples, the
empirical frequencies of the outputs of all stages, i.e. all values of
$Score\left((j,c_{j}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)$,
are close to their expectation.

Start by defining $H$ to be the function class consisting of point functions,
i.e., functions of the form $h_{\ell}(x)=1$ if $x={\ell}$, and $h_{\ell}(x)=0$
otherwise, for every $\ell\in\mathcal{Y}$. It is easy to prove that the VC
dimension of $H$ is equal to $1$. Let $Q_{j}$ be the distribution of the
output of the replicable algorithm $\mathcal{A}$ when run with coin $r_{j}$ on
a random sample.

Then, using uniform convergence (Theorem 2.16), we get for every fixed $j$ and
for every $\gamma>0$, that

$\mathbf{Pr}_{z_{1,j},\dots,z_{t,j}\sim Q_{j}}\left[\sup_{h_{\ell}\in
H}\left|\frac{1}{t}\sum_{i=1}^{t}\mathbbm{1}[h_{\ell}(z_{i,j})=1]-\mathbf{Pr}_{z\sim
Q_{j}}[h_{\ell}(z)=1]\right|\geq\gamma\right]\leq 8te^{-\gamma^{2}t/8}.$

Observe that
$\frac{1}{t}\sum_{i=1}^{t}\mathbbm{1}[h_{\ell}(z_{i,j})=1]=\frac{1}{t}\sum_{i=1}^{t}\mathbbm{1}[z_{i,j}=\ell]$.
Similarly, $\mathbf{Pr}_{z\sim Q}[h_{\ell}(z)=1]=\mathbf{Pr}_{z\sim
Q_{j}}[z=\ell]$. Hence, we get that

$\mathbf{Pr}_{z_{1,j},\dots,z_{t,j}\sim
Q_{j}}\left[\sup_{\ell\in\mathcal{Y}}\left|\frac{1}{t}\sum_{i=1}^{t}\mathbbm{1}[z_{i,j}=\ell]-\mathbf{Pr}_{z\sim
Q_{j}}[z=\ell]\right|\geq\gamma\right]\leq 8te^{-\gamma^{2}t/8}.$

Setting $\gamma=2\sqrt{\frac{\log(8kt/\delta)}{t}}$, we get that

$\mathbf{Pr}_{z_{1,j},\dots,z_{t,j}\sim
Q_{j}}\left[\sup_{\ell\in\mathcal{Y}}\left|\sum_{i=1}^{t}\mathbbm{1}[z_{i,j}=\ell]-t\mathbf{Pr}_{z\sim
Q_{j}}[z=\ell]\right|\geq
2\sqrt{t\log(8kt/\delta)}\right]\leq\frac{\delta^{2}}{2k}.$

Using a union bound over all $k$ stages of the algorithm, this guarantees us
that the empirical frequencies (and in particular, the values
$\operatorname{score}\left((j,c_{j}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)$
are all within $2\sqrt{t\log(8kt/\delta)}$ of their expectations with
probability at least $1-\delta^{2}/2$.

Note that since we conditioned on a fixed random coin sequence, all the
randomness in $z_{i,j}$ comes from the data sample. Hence, if we consider
another sample
$S^{\prime}=(\mathbf{S}^{\prime}_{1},\mathbf{S}^{\prime}_{2},\dots,\mathbf{S}^{\prime}_{k})$
drawn i.i.d .from $D^{mkt}$, we have that with probability at least
$1-\delta^{2}$ over the draws of $S$ and $S^{\prime}$ that for all $j\in[k]$
and all $\ell\in\mathcal{Y}$ that
$\operatorname{score}\left((j,\ell),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)$
and
$\operatorname{score}\left((j,\ell),(\mathbf{S}^{\prime}_{1},\mathbf{S}^{\prime}_{2},\dots,\mathbf{S}^{\prime}_{k})\right)$
are both within $2\sqrt{t\log(8kt/\delta)}$ of their expectations, and are
hence within $4\sqrt{t\log(8kt/\delta)}$ of each other. We call this event
$E_{sample}$, and fix any sample pairs $(S,S^{\prime})$ that occur with non-
zero probability conditioned on this event. This allows us to argue that with
probability at least $1-\delta^{2}$, for all $j\in[k]$,

$\displaystyle|\operatorname{score}\left((j,c_{j}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)-\operatorname{score}\left((j,c^{\prime}_{j}),(\mathbf{S}^{\prime}_{1},\mathbf{S}^{\prime}_{2},\dots,\mathbf{S}^{\prime}_{k})\right)|\leq
4\sqrt{t\log(8kt/\delta)}.$ (6)

This follows directly from the above argument if $c_{j}=c^{\prime}_{j}$, but
if they are not equal, it also holds since otherwise either $c_{j}$ or
$c^{\prime}_{j}$ would not be a plurality output in stage $j$ of the
corresponding runs (since there would be an output that occurs more times in
stage $j$). This is because uniform convergence guarantees us that if $c_{j}$
occurs $a$ times in stage $j$ when the algorithm is run on dataset $S$, then
$c_{j}$ occurs atleast $a-4\sqrt{t\log(8kt/\delta)}$ times in stage $j$ when
the algorithm is run on dataset $S^{\prime}$. Hence, if $c^{\prime}_{j}$
occurs less than $a-4\sqrt{t\log(8kt/\delta)}$ in stage $j$, then we’d get
that $c_{j}$ would be the plurality output of stage $j$ in the run on dataset
$S^{\prime}$ and not $c^{\prime}_{j}$, which is a contradiction. This shows
that
$\operatorname{score}\left((j,c_{j}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)-\operatorname{score}\left((j,c^{\prime}_{j}),(\mathbf{S}^{\prime}_{1},\mathbf{S}^{\prime}_{2},\dots,\mathbf{S}^{\prime}_{k})\right)\leq
4\sqrt{t\log(8kt/\delta)}$; the other direction can be proved similarly.

##### Step 3: Arguing that there is at least one canonical output $c_{j}$ with
high score.

Conditioned on $E_{coin}$, we know that the run of Algorithm 3 on $S$ has at
least one coin sequence with a $0.99$-canonical output $z$. Suppose $r_{j}$ is
such a coin sequence. From the settings of $k$ and $t$, we get that
$2\sqrt{t\log(8kt/\delta)}\leq 0.09t$. Hence, conditioned further on
$E_{sample}$, we know that this canonical output $z$ is equal to the plurality
output $c_{j}$ in stage $j$, and that
$\operatorname{score}\left((j,c_{j}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)$
is at least $0.9t$. Hence, there exists an candidate $(j,c_{j})$ with score at
least $0.9t$.

##### Step 4: Arguing that probable outputs $(j^{*},c_{j^{*}})$ are in both
output sets $C$ and $C^{\prime}$.

By the accuracy guarantee of the exponential mechanism (Lemma 2.7), we have
that

$\mathbf{Pr}\left[\max_{j\in[k]}\operatorname{score}\left((j,c_{j}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)-\operatorname{score}\left((j^{*},c_{j^{*}}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)\geq
2\Delta\frac{\ln k+k}{\varepsilon}\right]\leq e^{-k}=\delta,$

where $\Delta=4\sqrt{t\log(8kt/\delta)}$. Hence, for the settings of $t$ and
$k$, we get that $2\Delta\frac{\ln
k+k}{\varepsilon}=O(\frac{k\sqrt{t\log(8kt/\delta)}}{\varepsilon})=o(t)$.
Hence, we have that

$\mathbf{Pr}\left[\operatorname{score}\left((j^{*},c_{j^{*}}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)\geq
0.9t-2\Delta\frac{\ln k+k}{\varepsilon}\right]\leq e^{-k}=\delta,$

which implies that for sufficiently small $\delta$,

$\mathbf{Pr}\left[\operatorname{score}\left((j^{*},c_{j^{*}}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)\geq
0.8t\right]\leq e^{-k}=\delta.$

Let’s consider any such $c_{j^{*}}$. By the conditioning on $E_{sample}$, we
have that $c_{j^{*}}$ occurs more than $0.8t-4\sqrt{t\log(kt/\delta)}>0.5t$
times in the output set of stage $j^{*}$ when Algorithm 3 is run on the sample
$S^{\prime}$. Hence, $c^{\prime}_{j^{*}}$ is also equal to $c_{j^{*}}$.

##### Step 5: Proving that
$\mathcal{A}^{\prime}(S,r)\approx_{\varepsilon,\delta}\mathcal{A}^{\prime}(S^{\prime},r)$
w.h.p.

We exploit the fact that two random variables $C$ and $D$ are
$(\varepsilon,\delta)$-indistinguishable if w.p. $\geq 1-\delta$ over a draw
$o$ from the distribution of $C$, we have
$e^{-\varepsilon}\mathbf{Pr}[D=o]\leq\mathbf{Pr}[C=o]\leq
e^{\varepsilon}\mathbf{Pr}[D=o]$, and vice versa for a draw from the
distribution of $D$ [55, Lemma 3.3, Part 1].

We proved in Step $4$ that fixing any coins and sample pairs that have non-
zero probability of occurring conditioned on $E_{coin}$ and $E_{sample}$, with
probability at least $1-\delta$ from a draw of $A^{\prime}(S,r)$ (where the
randomness is only that of the exponential mechanism), the output
$(j^{*},c_{j^{*}})$ occurs in both the sets $C$ and $C^{\prime}$. For all such
outputs, our idea is to use the differential privacy analysis of the
exponential mechanism.

A technical obstacle we need to surmount is that the output sets $C$ and
$C^{\prime}$ might be different, and so the normalizing factors used in the
exponential mechanism will vary accordingly. We deal with this by invoking
Inequality 6, which points out that even though the output sets are different,
the scores
$\operatorname{score}\left((j,c_{j}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)$
and
$\operatorname{score}\left((j,c^{\prime}_{j}),(\mathbf{S}^{\prime}_{1},\mathbf{S}^{\prime}_{2},\dots,\mathbf{S}^{\prime}_{k})\right)$
can differ by at most the sensitivity specified in Step 10 where the
exponential mechanism is invoked.

Hence, exactly mimicking the differential privacy analysis of the exponential
mechanism (see e.g., [37], Theorem 3.10) conditioned on $E_{coin}$ and
$E_{sample}$, with probability at least $1-\delta$ from a draw
$(j^{*},c^{\prime}_{j^{*}})$ of $\mathcal{A}^{\prime}(S,r)$, we get that

$e^{-\varepsilon}\mathbf{Pr}[\mathcal{A}^{\prime}(S,r)=(j^{*},c_{j^{*}})]\leq\mathbf{Pr}[\mathcal{A}^{\prime}(S^{\prime},r)=(j^{*},c^{\prime}_{j^{*}})]\leq
e^{\varepsilon}\mathbf{Pr}(\mathcal{A}^{\prime}(S,r)=(j^{*},c_{j^{*}})]$

and, moreover, $c^{\prime}_{j^{*}}=c_{j^{*}}$. By symmetry (since $S$ and
$S^{\prime}$ are both independent samples from the distribution with the same
properties), conditioned on $E_{coin}$ and $E_{sample}$, we get that with
probability at least $1-\delta$ from a draw $(j^{*},c_{j^{*}})$ of
$\mathcal{A}^{\prime}(S^{\prime},r)$,

$e^{-\varepsilon}\mathbf{Pr}[\mathcal{A}^{\prime}(S,r)=(j^{*},c_{j^{*}})]\leq\mathbf{Pr}[\mathcal{A}^{\prime}(S^{\prime},r)=(j^{*},c_{j^{*}})]\leq
e^{\varepsilon}\mathbf{Pr}[\mathcal{A}^{\prime}(S,r)=(j^{*},c_{j^{*}})].$

Hence, we have proved that conditioned on any fixed coins and sample pairs
with non-zero probability of occurring conditioned on $E_{coin}$ and
$E_{sample}$, we have
$\mathcal{A}^{\prime}(S,r)\approx_{\varepsilon,\delta}\mathcal{A}^{\prime}(S^{\prime},r)$.
Now, using the law of total probability, we get that

$\displaystyle\mathbf{Pr}_{r_{1},\dots,r_{k}}\left[\mathbf{Pr}_{S,S^{\prime}\sim
D^{mkt}}\Big{[}\mathcal{A}^{\prime}(S;r_{1},\dots,r_{k})\approx_{\varepsilon,\delta}\mathcal{A}^{\prime}(S^{\prime};r_{1},\dots,r_{k})\Big{]}\geq
1-\delta^{2}\right]\geq 1-\delta^{2}.$ (7)

##### Step 6: Switch quantifiers to get sample perfect generalization:

Now, we switch the quantifiers in equation 7.

$\displaystyle\mathbf{Pr}_{S,S^{\prime}\sim
D^{mkt},r_{1},\dots,r_{k}}\Big{[}\mathcal{A}^{\prime}(S;r_{1},\dots,r_{k})\approx_{\varepsilon,\delta}\mathcal{A}^{\prime}(S^{\prime};r_{1},\dots,r_{k})\Big{]}\geq
1-2\delta^{2}$ $\displaystyle\implies$
$\displaystyle\mathbb{E}_{S,S^{\prime}\sim
D^{mkt}}\left[\mathbf{Pr}_{r_{1},\dots,r_{k}}\Big{[}\mathcal{A}^{\prime}(S;r_{1},\dots,r_{k})\approx_{\varepsilon,\delta}\mathcal{A}^{\prime}(S^{\prime};r_{1},\dots,r_{k})\Big{]}\right]\geq
1-2\delta^{2}$ $\displaystyle\implies$
$\displaystyle\mathbf{Pr}_{S,S^{\prime}\sim
D^{mkt}}\left[\mathbf{Pr}_{r_{1},\dots,r_{k}}\Big{[}\mathcal{A}^{\prime}(S;r_{1},\dots,r_{k})\approx_{\varepsilon,\delta}\mathcal{A}^{\prime}(S^{\prime};r_{1},\dots,r_{k})\Big{]}\geq
d\right]\geq\frac{1-2\delta^{2}-d}{1-d}.$

Here, the last inequality holds by the reverse Markov inequality. Setting
$d=1-\delta$, we get that

$\displaystyle\mathbf{Pr}_{S,S^{\prime}\sim
D^{mkt}}\left[\mathbf{Pr}_{r_{1},\dots,r_{k}}\Big{[}\mathcal{A}^{\prime}(S;r_{1},\dots,r_{k})\approx_{\varepsilon,\delta}\mathcal{A}^{\prime}(S^{\prime};r_{1},\dots,r_{k})\Big{]}\geq
1-\delta\right]\geq 1-2\delta.$

Now, using the fact that if $X\approx_{\varepsilon,\delta}Y$ and
$M\approx_{\varepsilon,\delta}N$, then $\alpha
X+(1-\alpha)M\approx_{\varepsilon,\delta}\alpha Y+(1-\alpha)N$ for every
$\alpha\in[0,1]$ (i.e., $(\varepsilon,\delta)$-indistinguishability is
preserved under convex combinations), we get that

$\mathbf{Pr}_{S,S^{\prime}\sim
D^{mkt}}\left[\mathcal{A}^{\prime}(S)\approx_{\varepsilon,2\delta}\mathcal{A}^{\prime}(S^{\prime})\right]\geq
1-2\delta.$

This proves that $\mathcal{A}^{\prime}$ with the specified inputs is
$(2\delta,\varepsilon,2\delta)$-sample perfectly generalizing, as required.
Next, we deal with accuracy. ∎

######  Claim 3.21.

If Algorithm $\mathcal{A}$ succeeds at a statistical task with probability at
least $1-\gamma^{2}$, Algorithm $\mathcal{A}^{\prime}$ succeeds at the same
statistical task with probability at least $1-O(\delta)-\gamma\log(1/\delta)$.

###### Proof.

Recall the definition of success for a statistical task. The statistical task
is defined by a set of distribution, set pairs. For every distribution $D$,
there is an associated good set of outputs $O_{D}$. An algorithm succeeds at
this task with probability at least $1-\gamma$ if it outputs a member of this
good set with at least that probability (taken over random samples from $D$
and any internal coins of the algorithm).

If $\mathcal{A}$ succeeds at the task with probability at least
$1-\gamma^{2}$, by using reverse Markov’s inequality as in Step 6 of the
previous proof, we have that

$\displaystyle\mathbf{Pr}_{r}\left[\mathbf{Pr}_{S\sim
D^{m}}\Big{[}\mathcal{A}(S;r)\in O_{D}\Big{]}\geq 1-\gamma\right]\geq
1-\gamma$ (8)

We say a coin sequence $r_{j}$ is “accurate” if the inner inequality under the
probability is satisfied. Recall that we call a coin sequence $r_{j}$ “good”
if it has a $0.99$-canonical output. By the analysis in Step $1$ of the
previous proof, we have that with probability at least $1-\delta^{2}$, there
is a good coin sequence among the runs $r_{1},\dots,r_{k}$. Now, the
probability that all $k$ coin sequences are “accurate” is equal to
$(1-\gamma)^{\log(1/\delta)}\geq 1-\gamma\log(1/\delta)$. (This follows from
Bernoulli’s inequality $(1+a)^{k}\geq 1+ak$ for all $a\geq-1$ and non-negative
integers $k$.) Hence, by a union bound, the probability that the set of runs
$r_{1},\dots,r_{k}$ both contains a good coin sequence and that all the coin
sequences in the set are accurate is at least
$1-\gamma\log(1/\delta)-\delta^{2}$. Call this event $E_{coin-acc}$ and
condition on it. Additionally, condition on $E_{sample}$ as defined in Step
$2$ of the previous proof. Then, by the analysis in Step 4 of the previous
proof, we have that

$\mathbf{Pr}\left[\operatorname{score}\left((j^{*},c_{j^{*}}),(\mathbf{S}_{1},\mathbf{S}_{2},\dots,\mathbf{S}_{k})\right)\geq
0.8t\right]\leq e^{-k}=\delta,$

which implies that the exponential mechanism outputs a plurality output that
occurs at least $0.8t$ times in its stage with probability at least
$1-\delta$. Since we have conditioned on $E_{sample}$, we have that empirical
frequencies are close to their expected values, and hence the exponential
mechanism outputs the canonical output of a coin sequence that is at least
$0.25$-good with probability at least $1-\delta$. Using the law of total
probability to remove the conditioning on $E_{sample}$, we get that the
exponential mechanism outputs the canonical output of a coin sequence that is
at least $0.25$-good with probability at least $1-\delta-\delta^{2}$ (since
event $E_{sample}$ happens with probability at least $1-\delta^{2}$). Note
that since all the drawn coin sequences are accurate, we get that the
canonical output for every such sequence is in the good set $O_{D}$
(otherwise, the inequality inside the outer probability in equation 8 would
not be satisfied). Hence, conditioned on $E_{coin-acc}$, we have that
$\mathcal{A}^{\prime}$ outputs an element of the good set with probability at
least $1-\delta-\delta^{2}$. Using the law of total probability, we then get
that $\mathcal{A}^{\prime}$ outputs an element of the good set with
probability at least
$1-\delta-2\delta^{2}-\gamma\log(1/\delta)=1-O(\delta)-\gamma\log(1/\delta)$.
∎

Hence, combining the two claims on perfect generalization and accuracy, we
complete the proof of the theorem. ∎

##  4 Separating Stability: Computational Barriers

In this section, we show that standard cryptographic assumptions imply there
cannot exist computationally efficient transformations from differentially
private algorithms to replicable ones. Moreover, such cryptographic
assumptions are necessary: if one-way functions do not exist, there exists an
efficient algorithm for correlated sampling (and therefore for converting DP
to replicability as well via Corollary 3.18).

In Section 4.1, we define $\Pi_{\textit{RandEnc}}$, a statistical promise
problem. Given a public key $\mathbf{pk}$ and a dataset of ciphertexts
encrypting the same bit $b$ under $\mathbf{pk}$, a solution to
$\Pi_{\textit{RandEnc}}$ is any encryption of $b$ under $\mathbf{pk}$. In
Section 4.1.1, we give a simple algorithm $\mathtt{DPRandEnc}$ solving
$\Pi_{\textit{RandEnc}}$. $\mathtt{DPRandEnc}$ is
$(\varepsilon,\delta)$-differentially private and runs in polynomial time. In
Section 4.1.2, we show that the existence of an efficient replicable algorithm
for $\Pi_{\textit{RandEnc}}$ would violate the security guarantee of the
encryption scheme. Thus, assuming randomizable encryption schemes exist, there
is no efficient transformation from DP algorithms to replicable algorithms for
$\Pi_{\textit{RandEnc}}$. $\Pi_{\textit{RandEnc}}$ can be instantiated with
any PKE satisfying the requirements of Definition 4.2, but to demonstrate that
these requirements are not unreasonable, in Section 4.1.3 we show that they
are satisfied by the Goldwasser-Micali public-key encryption scheme [43].
Therefore the hardness of quadratic residuosity is sufficient to show hardness
for the transformation from differential privacy to replicability.

In Section 4.2, we give an algorithm for correlated sampling that is efficient
so long as no one-way functions exist. This algorithm can in turn be used in
Algorithm 2, to implement the correlated sampling step of the transformation
from a one-way perfectly generalizing algorithm to a replicable one, giving an
efficient transformation.

###  4.1 Cryptographic Hardness of Replicability

We define a promise problem $\Pi_{\textit{RandEnc}}$ (Definition 4.3) for a
public-key encryption scheme. $\Pi_{\textit{RandEnc}}$ is parameterized by a
public-key $\mathbf{pk}$ for a public-key encryption scheme $\mathcal{E}$ with
message space $\\{0,1\\}$ and ciphertext space $\mathcal{C}$. An instance of
$\Pi_{\textit{RandEnc}}$ consists of a sample of $m$ elements $c_{i}$, drawn
i.i.d. from an unknown distribution $D$ over $\mathcal{C}$. Promised that
either

  1. 1.

$D$ is supported entirely on encryptions of $0$ under $\mathbf{pk}$ or

  2. 2.

$D$ is supported entirely on encryptions of $1$ under $\mathbf{pk}$,

Problem $\Pi_{\textit{RandEnc}}$ asks the algorithm to output an encryption of
$0$ under $\mathbf{pk}$ in the first case and an encryption of $1$ under
$\mathbf{pk}$ in the second case.

We show that if the public-key encryption scheme supports a strong form of
rerandomization, Problem $\Pi_{\textit{RandEnc}}$ can be efficiently solved
with a differentially private algorithm. At the same time,
$\Pi_{\textit{RandEnc}}$ cannot be efficiently solved using a replicable
algorithm, assuming the security of the underlying encryption scheme. Thus, in
this setting, there cannot be an efficient black-box reduction from DP
algorithms to replicable algorithms.

For our construction, we use a standard definition for public-key encryption.

######  Definition 4.1 (Public-Key Encryption Scheme).

Let $\lambda\in\mathbb{N}$ be a security parameter and
$\mathcal{E}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ be a tuple of
algorithms running in time $\operatorname{poly}(\lambda)$, with
$\mathsf{KeyGen}:1^{*}\rightarrow\mathcal{K}_{p}\times\mathcal{K}_{s}$,
$\mathsf{Enc}:\mathcal{K}_{p}\times\\{0,1\\}\rightarrow\mathcal{C}$, and
$\mathsf{Dec}:\mathcal{K}_{s}\times\mathcal{C}\rightarrow\\{0,1\\}\cup\bot$.
We say $\mathcal{E}$ is a _public-key encryption scheme_ if it has the
following properties.

  * •

Correctness: Let $(\mathbf{sk},\mathbf{pk})\leftarrow\mathsf{KeyGen}(\lambda)$
and $c\leftarrow\mathsf{Enc}(\mathbf{pk},b)$ for $b\in\\{0,1\\}$. Then
$\mathsf{Dec}(\mathbf{sk},c)=b$.

  * •

Security: There exists a negligible function $\varepsilon(\lambda)$, such that
for all adversaries $\mathcal{A}$ running in time
$\operatorname{poly}(\lambda)$, letting
$(\mathbf{sk},\mathbf{pk})\leftarrow\mathsf{KeyGen}(\lambda)$ we have

$\left|\mathbf{Pr}[\mathcal{A}(\mathbf{pk},c)=1\mid
c\leftarrow\mathsf{Enc}(\mathbf{pk},1)]-\mathbf{Pr}[\mathcal{A}(\mathbf{pk},c)=1\mid
c\leftarrow\mathsf{Enc}(\mathbf{pk},0)]\right|<\varepsilon(\lambda).$

We also require that a public-key encryption scheme allows for efficient,
publicly computable ciphertext verification and rerandomization procedures.

######  Definition 4.2 (Randomizeable Encryption Scheme).

Let $\mathcal{E}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ be a public-key
encryption scheme. We call $\mathcal{E}$ a _randomizeable encryption scheme_
if it supports the following additional procedures.

  * •

(Perfect) Verification of Ciphertexts: There exists a deterministic polytime
algorithm $\mathcal{V}$ such that, for an honestly generated key pair
$(\mathbf{sk},\mathbf{pk})\leftarrow\mathsf{KeyGen}(\lambda)$ and value $c$,

    * –

If $\mathsf{Dec}(\mathbf{sk},c)\in\\{0,1\\}$, then
$\mathcal{V}(\mathbf{pk},c)=1$

    * –

If $\mathsf{Dec}(\mathbf{sk},c)=\bot$, then $\mathcal{V}(\mathbf{pk},c)=0$

  * •

(Perfect) Randomization of Ciphertexts: There exists a randomized polytime
algorithm $\mathsf{Rerandomize}$ such that, for all honestly generated key
pairs $(\mathbf{sk},\mathbf{pk})\leftarrow\mathsf{KeyGen}(\lambda)$, and all
ciphertexts $c_{1},c_{2}$ such that
$\mathsf{Dec}(\mathbf{sk},c_{1})=\mathsf{Dec}(\mathbf{sk},c_{2})$,

    * –

$d_{TV}(\mathsf{Rerandomize}(\mathbf{pk},c_{1}),\mathsf{Rerandomize}(\mathbf{pk},c_{2}))=0$

    * –

$\mathsf{Dec}(\mathbf{sk},\mathsf{Rerandomize}(\mathbf{pk},c))=\mathsf{Dec}(\mathbf{sk},c)$

Consider the following search problem $\Pi_{\textit{RandEnc}}$. Given a public
key $\mathbf{pk}$ for an encryption scheme $\mathcal{E}$, and an i.i.d. sample
of $m$ elements from a distribution $D$ supported on encryptions under
$\mathbf{pk}$ of a fixed bit $b\in\\{0,1\\}$, output an encryption of $b$
under $\mathbf{pk}$.

######  Definition 4.3 (Ciphertext Identification Problem).

An instance of $\Pi_{\textit{RandEnc}}$ is defined as follows. Let
$\mathcal{E}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ be a randomizeable
encryption scheme (Definition 4.2). Let $\lambda,m\in\mathbb{N}$, and let $D$
be a distribution over the ciphertext space $\mathcal{C}$ of $\mathcal{E}$.
Given public key $\mathbf{pk}$, honestly generated as
$(\mathbf{pk},\mathbf{sk})\leftarrow\mathsf{KeyGen}(\lambda)$, and a sample
$S\sim D^{m}$ drawn i.i.d. from $D$, output an element
$c^{*}\in\mathcal{C}\cup\bot$ such that

  1. 1.

If $\mathsf{Dec}(\mathbf{sk},c)=1$ for all $c\in\mathtt{supp}(D)$,
$\mathsf{Dec}(\mathbf{sk},c^{*})=1$

  2. 2.

If $\mathsf{Dec}(\mathbf{sk},c)=0$ for all $c\in\mathtt{supp}(D)$,
$\mathsf{Dec}(\mathbf{sk},c^{*})=0$

####  4.1.1 DP Algorithm for $\Pi_{\textit{RandEnc}}$

In this subsection, we present a differentially private algorithm
$\mathtt{DPRandEnc}$ for $\Pi_{\textit{RandEnc}}$. Our algorithm removes from
the dataset $S$ all $c_{i}$ for which verification fails, i.e.,
$\mathcal{V}(\mathbf{pk},c_{i})=0$. It then pads the remaining elements with
$k$ encryptions of 0 under $\mathbf{pk}$ and $k$ encryptions of 1 under
$\mathbf{pk}$. An element $c_{i}$ from the new dataset is then chosen
uniformly at random, and the algorithm outputs
$\mathsf{Rerandomize}(\mathbf{pk},c_{i})$.

Padding the dataset with additional ciphertexts, balanced between encryptions
of 0 and 1, guarantees privacy by ensuring that exchanging any element of $S$
for another will not significantly change the probability that the ciphertext
chosen for rerandomization encrypts a particular bit. If the distribution $D$
is supported on one of the two promised distributions, $\mathtt{DPRandEnc}$
will be correct unless it chooses to rerandomize an inserted ciphertext which
encrypts the incorrect bit. So long as the input sample is of size $m$ much
larger than $k$, this will happen only with small probability.

Result: Outputs a ciphertext $c\in\mathcal{C}$

Input: Sample $S$ of $m$ elements drawn i.i.d. from $D$

Parameters:

  * •

Privacy $\varepsilon$, failure probability $\beta$, padding length
$k=\frac{1}{\varepsilon}$

  * •

Sample Complexity $m=m(\varepsilon,\beta)\in
O\left(\frac{1}{\varepsilon\beta}\right)$

Algorithm:

  1. 1.

For $i\in[m]$, remove $c_{i}$ from $S$ if $\mathcal{V}(\mathbf{pk},c_{i})=0$

  2. 2.

Add $k$ ciphertexts $\mathsf{Enc}(\mathbf{pk},0)$ to the dataset

  3. 3.

Add $k$ ciphertexts $\mathsf{Enc}(\mathbf{pk},1)$ to the dataset

  4. 4.

Choose $c$ uniformly at random from the new dataset

return $\mathsf{Rerandomize}(\mathbf{pk},c)$

Algorithm 4 $\mathtt{DPRandEnc}$

######  Lemma 4.4.

Let $\varepsilon,\beta\in(0,1/2)$. Then for $m\in\Omega(1/(\varepsilon\beta))$
and $k=1/\varepsilon$, $\Pi_{\textit{RandEnc}}$ (Algorithm 4) runs in time
$\operatorname{poly}(\lambda,1/\varepsilon,1/\beta)$, is $\varepsilon$-DP, and
correct except with probability at most $\beta$.

###### Proof.

We begin by showing $\mathtt{DPRandEnc}$ is $\varepsilon$-DP. Note that the
last step of $\mathtt{DPRandEnc}$ calls $\mathsf{Rerandomize}$ on a ciphertext
$c$ that is guaranteed to be a valid encryption of a bit $b\in\\{0,1\\}$,
since all inputs failing verification are removed from $S$ before $c$ is
drawn, and only valid ciphertexts under $\mathbf{pk}$ are added to the input
dataset.

We will bound how much the probability that $c$ encrypts a fixed bit $b$ can
differ across neighboring data sets. Let $c$ be a random variable denoting the
ciphertext chosen for rerandomization. For all $b\in\\{0,1\\}$ and neighboring
datasets $S,S^{\prime}$, let $S_{b}$, $S_{\neg b}$, and $S_{\bot}$ denote the
subsets of $S$ such that $\mathsf{Dec}(\mathbf{sk},c)=b$,
$\mathsf{Dec}(\mathbf{sk},c)=\neg b$, and $\mathsf{Dec}(\mathbf{sk},c)=\bot$
respectively, and let $S^{\prime}_{b}$, $S^{\prime}_{\neg b}$, and
$S^{\prime}_{\bot}$ be defined analogously. Then

$\displaystyle\frac{\mathbf{Pr}[\mathsf{Dec}(\mathbf{sk},c)=b\mid
S]}{\mathbf{Pr}[\mathsf{Dec}(\mathbf{sk},c)=b\mid S^{\prime}]}$
$\displaystyle=\frac{|S_{b}|+k}{m-|S_{\bot}|+2k}\cdot\frac{m-|S^{\prime}_{\bot}|+2k}{|S^{\prime}_{b}|+k}$
$\displaystyle=\frac{|S_{b}|+k}{|S_{b}|+|S_{\neg
b}|+2k}\cdot\frac{|S^{\prime}_{b}|+|S^{\prime}_{\neg
b}|+2k}{|S^{\prime}_{b}|+k}$
$\displaystyle\leq\frac{|S_{b}|+k}{|S_{b}|+|S_{\neg
b}|+2k}\cdot\frac{|S_{b}|+|S_{\neg b}|+2k}{|S_{b}|-1+k}$
$\displaystyle=\frac{|S_{b}|+k}{|S_{b}|-1+k}$
$\displaystyle\leq\frac{k+1}{k},$

where the first inequality follows from $S,S^{\prime}$ neighboring, and the
fact that for $a>b$, $\frac{a}{b-1}>\frac{a+1}{b}$, so assuming $|S_{b}|\geq
1$ and $|S^{\prime}_{b}|=|S_{b}|-1$ maximizes the rightmost fraction. Because
the output distribution of $\mathsf{Rerandomize}(\mathbf{pk},c)$ is the same
for all ciphertexts encrypting the same bit under $\mathbf{pk}$, it follows
that for all subsets $T\subseteq\mathcal{C}$,

$\displaystyle\mathbf{Pr}[\mathtt{DPRandEnc}(S)\in T]$
$\displaystyle=\mathbf{Pr}[\mathsf{Rerandomize}(\mathbf{pk},c)\in
T\mid\mathsf{Dec}(\mathbf{sk},c)=1]\cdot\mathbf{Pr}[\mathsf{Dec}(\mathbf{sk},c)=1\mid
S]$
$\displaystyle\quad\quad\quad+\mathbf{Pr}[\mathsf{Rerandomize}(\mathbf{pk},c)\in
T\mid\mathsf{Dec}(\mathbf{sk},c)=0]\cdot\mathbf{Pr}[\mathsf{Dec}(\mathbf{sk},c)=0\mid
S].$

Using $p_{b}$ to denote $\mathbf{Pr}[\mathsf{Rerandomize}(\mathbf{pk},c)\in
T\mid\mathsf{Dec}(\mathbf{sk},c)=b]$, for $b\in\\{0,1\\}$, we then have that

$\displaystyle\mathbf{Pr}[\mathtt{DPRandEnc}(S)\in T]$
$\displaystyle=p_{1}\cdot\mathbf{Pr}[\mathsf{Dec}(\mathbf{sk},c)=1\mid
S]+p_{0}\cdot\mathbf{Pr}[\mathsf{Dec}(\mathbf{sk},c)=0\mid S]$
$\displaystyle\leq\frac{k+1}{k}\left(p_{1}\cdot\mathbf{Pr}[\mathsf{Dec}(\mathbf{sk},c)=1\mid
S^{\prime}]+p_{0}\cdot\mathbf{Pr}[\mathsf{Dec}(\mathbf{sk},c)=0\mid
S^{\prime}]\right)$
$\displaystyle=\frac{k+1}{k}\cdot\mathbf{Pr}[\mathtt{DPRandEnc}(S^{\prime})\in
T]$ $\displaystyle\leq
e^{\varepsilon}\cdot\mathbf{Pr}[\mathtt{DPRandEnc}(S^{\prime})\in T]$

where the final inequality follows from taking $k=1/\varepsilon$ and observing
$1+x\leq e^{x}$.

It remains to argue correctness of $\mathtt{DPRandEnc}$ when the sample $S$ is
drawn from one of the promised distributions. In this case, the input sample
$S$ consists of $m$ valid encryptions of the same bit $b$ under $\mathbf{pk}$.
Because $\mathsf{Rerandomize}(\mathbf{pk},c)$ is plaintext-preserving, the
probability that $\Pi_{\textit{RandEnc}}$ is incorrect given $S$, i.e.,
outputs a ciphertext encrypting $\neg b$, is exactly the probability that one
of the inserted ciphertexts encrypting $\neg b$ is chosen for rerandomization.
This happens with probability $\frac{k}{m+2k}$, so taking
$m>k/\beta=1/(\varepsilon\beta)$ ensures $\Pi_{\textit{RandEnc}}$ is correct
except with probability $\beta$. ∎

####  4.1.2 Cryptographic Adversary from Replicable Algorithm for
$\Pi_{\textit{RandEnc}}$

In this subsection, we show that if there exists a replicable polytime
algorithm, $\mathcal{B}$, for $\Pi_{\textit{RandEnc}}$, instantiated with a
randomizable encryption scheme $\mathcal{E}$, then there exists an adversary
breaking the security guarantee of $\mathcal{E}$. To break security, the
adversary must be able to distinguish whether a ciphertext $c$ encrypts a 1 or
a 0 with probability noticeably better than a coin flip.

The high level idea is as follows. The adversary can first use the ciphertext
rerandomization procedure to generate a dataset of ciphertexts encrypting the
same bit as $c$. It can then generate a dataset of ciphertexts encrypting 0 by
encrypting 0 under the public key and rerandomizing the resulting ciphertext.
The adversary will then invoke $\mathcal{B}$ on both datasets, fixing the same
randomness for both invocations. If the outputs of both invocations are equal,
the adversary will guess that $c$ encrypts a 0, and guess $c$ encrypts 1
otherwise.

Because rerandomization is perfect and $\mathcal{B}$ is a replicable algorithm
for $\Pi_{\textit{RandEnc}}$, if $c$ encrypts a 0, $\mathcal{B}$ will with
high probability produce the same output ciphertext for both invocations. If
$c$ encrypts a 1, $\mathcal{B}$ will can only output the same ciphertext for
both invocations if one of the two invocations is incorrect, and so with good
probability, the two outputs will differ. This implies the adversary will have