good distinguishing probability, breaking the security of the underlying
cryptosystem.

Result: Outputs a bit $b^{\prime}$

Input: public key $\mathbf{pk}$, ciphertext $c$

Algorithm:

  1. 1.

Draw a random string $r$

  2. 2.

$c_{0}\leftarrow\mathsf{Enc}(\mathbf{pk},0)$

  3. 3.

Generate a set $S_{0}$ of $m$ ciphertexts by running
$\mathsf{Rerandomize}(\mathbf{pk},c_{0})$ $m$ times

  4. 4.

$c_{0}\leftarrow\mathcal{B}(\mathbf{pk},S_{0};r)$

  5. 5.

Generate a sample $S$ of $m$ ciphertexts by running
$\mathsf{Rerandomize}(\mathbf{pk},c)$ $m$ times

  6. 6.

$c\leftarrow\mathcal{B}(\mathbf{pk},S;r)$

  7. 7.

if $c_{0}=c$, then $b^{\prime}=0$, otherwise $b^{\prime}=1$

return $b^{\prime}$

Algorithm 5 Adversary $\mathcal{A}$

######  Lemma 4.5.

Let $\mathcal{E}$ be a randomizeable encryption scheme, let
$\Pi_{\textit{RandEnc}}^{\mathcal{E}}$ denote the instantiation of
$\Pi_{\textit{RandEnc}}$ with $\mathcal{E}$. Let $\mathcal{B}$ be a
$\rho$-replicable algorithm for $\Pi_{\textit{RandEnc}}^{\mathcal{E}}$ with
failure probability $\beta$, running in time
$\operatorname{poly}(\lambda,\rho,\beta)$, and with sample complexity
$m\in\operatorname{poly}(\lambda,\rho,\beta)$. Then there exists an adversary
$\mathcal{A}$ running in time $\operatorname{poly}(\lambda,\rho,\beta)$ such
that

$\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)]\geq 1-2\beta-\rho.$

###### Proof.

The adversary $\mathcal{A}(\mathbf{pk},c)$ outputs 1 whenever $c_{0}\neq c$.
The distribution from which $S_{0}$ is drawn is supported entirely on
encryptions of $0$ and, conditioned on
$c\leftarrow\mathsf{Enc}(\mathbf{pk},1)$, the distribution from which $S$ is
drawn is supported entirely on encryptions of $1$. Then $c_{0}\neq c$ except
when one of the two calls to $\mathcal{B}$ is incorrect, which happens with
probability at most $2\beta$. Conditioned on
$c\leftarrow\mathsf{Enc}(\mathbf{pk},0)$, $S_{0}$ and $S$ comprise i.i.d.
samples from the same distribution over encryptions of 0. In this case,
$c_{0}\neq c$ if either call to $\mathcal{B}$ fails to be replicable, which
happens with probability at most $\rho$. Therefore

$\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)]\geq 1-2\beta-\rho.$

∎

In particular, taking $\beta,\rho$ to be constant in Lemma 4.5 gives an
adversary breaking the security of $\mathcal{E}$, yielding the following
theorem as a corollary.

######  Theorem 4.6.

Let $\mathcal{E}$ be a randomizeable encryption scheme, and let
$\Pi_{\textit{RandEnc}}^{\mathcal{E}}$ denote the instantiation of
$\Pi_{\textit{RandEnc}}$ with $\mathcal{E}$. Then there does not exist a
$\rho$-replicable algorithm for $\Pi_{\textit{RandEnc}}^{\mathcal{E}}$ with
failure probability $\beta$, running in time $\operatorname{poly}(1/\lambda)$,
for $\rho<1/4$ and $\beta<1/8$.

###### Proof.

If there exists a $\rho$-replicable algorithm $\mathcal{B}$ for
$\Pi_{\textit{RandEnc}}^{\mathcal{E}}$ with failure probability $\beta<1/8$
and replicability parameter $\rho<1/4$ running in time
$\operatorname{poly}(\lambda)$, then by Lemma 4.5, there exists an adversary
$\mathcal{A}$ running in time $\operatorname{poly}(\lambda)$ such that

$\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)]\geq 1/2>\mathrm{negl}(\lambda),$

and therefore $\mathcal{A}$ breaks the security of $\mathcal{E}$. ∎

####  4.1.3 Instantiating $\Pi_{\textit{RandEnc}}$ with the Goldwasser-Micali
Cryptosystem

Here we recall the high-level structure of the Goldwasser-Micali public-key
cryptosystem, introduced in [43]. The security of the cryptosystem relies on
the hardness of deciding quadratic residuosity for integers modulo a semiprime
$N$. Informally, encryptions of $0$ are quadratic residues modulo $N$, while
encryptions of $1$ are non-residues. Because multiplying an integer $c$ by a
quadratic residue modulo $N$ preserves quadratic residuosity of $c$,
Goldwasser-Micali ciphertexts can be efficiently rerandomized with only a
public key. The rerandomization procedure will pick a quadratic residue
$r^{2}$ uniformly at random, and output its product with the given ciphertext
modulo $N$.

######  Definition 4.7 (Goldwasser-Micali Cryptosystem ([43])).

The Goldwasser-Micali cryptosystem is defined over a plaintext message space
$\mathcal{M}=\\{0,1\\}$ and ciphertext space $\mathcal{C}=\mathbb{Z}^{*}_{N}$,
for $N$ a semiprime. The cryptosystem comprises the following routines.

  * •

$\mathsf{KeyGen}(\lambda)$: Sample $p,q$ distinct primes of bit-length
$O(\lambda)$ and let $N=pq$. Choose $x$ to be a quadratic non-residue modulo
$N$ with Jacobi symbol $\left(\frac{x}{p}\right)=\left(\frac{x}{q}\right)=-1$.
Let $\mathbf{sk}=(p,q)$, $\mathbf{pk}=(N,x)$, and output
$(\mathbf{sk},\mathbf{pk})$.

  * •

$\mathsf{Enc}(\mathbf{pk},b)$: To encrypt a bit $b\in\\{0,1\\}$, sample
$u\leftarrow_{\mathcal{U}}\mathbb{Z}^{*}_{N}$ and output $u^{2}x^{b}\mod N$.

  * •

$\mathsf{Dec}(\mathbf{sk},c)$: To decrypt a ciphertext $c$, output $\bot$ if
$\gcd(c,N)\neq 1$, $1$ if $c$ is not a quadratic residue modulo $N$ and 0
otherwise.

We now show that the Goldwasser-Micali cryptosystem satisfies the strong
rerandomization property described above. We define the verification procedure
$\mathcal{V}(\mathbf{pk},c)$ to output 1 if $\gcd(c,N)=1$ and 0 otherwise. We
define $\mathsf{Rerandomize}(\mathbf{pk},c)$ to be the procedure that samples
$r$ uniformly at random from $\mathbb{Z}_{N}^{*}$ and outputs
$(\mathbf{pk},r^{2}c\mod N)$.

######  Lemma 4.8.

The Goldwasser-Micali cryptosystem is a rerandomizeable encryption scheme
(definition 4.2), for the rerandomization procedure described above.

###### Proof.

Because $\mathsf{Dec}(\mathbf{sk},c)=\bot$ if and only if $\gcd(c,N)\neq 1$,
and $\mathcal{V}(\mathbf{pk},c)=0$ if and only if $\gcd(c,N)\neq 1$,
$\mathcal{V}$ satisfies the requirement of definition 4.2. The rerandomization
procedure multiplies a ciphertext $c$ by a random quadratic residue modulo
$N$, and therefore preserves quadratic residuosity of $c$. This in turn
preserves the plaintext message encrypted by $c$, and so
$\mathsf{Rerandomize}$ satisfies
$\mathsf{Dec}(\mathbf{sk},\mathsf{Rerandomize}(\mathbf{pk},c))=\mathsf{Dec}(\mathbf{sk},c)$.

To show that for all $c,c^{\prime}$ such that
$\mathsf{Dec}(\mathbf{sk},c)=\mathsf{Dec}(\mathbf{sk},c^{\prime})$,
$d_{TV}(\mathsf{Rerandomize}(\mathbf{pk},c),\mathsf{Rerandomize}(\mathbf{pk},c^{\prime}))=0$,
let $b\in\\{0,1\\}$, $c=u^{2}x^{b}\mod N$ and $c^{\prime}=v^{2}x^{b}\mod N$ be
honest encryptions of $b$ under $\mathbf{pk}=(N,x)$. It follows that

$\displaystyle\mathbf{Pr}[\mathsf{Rerandomize}(\mathbf{pk},c)=a]$
$\displaystyle=\mathbf{Pr}[\mathsf{Rerandomize}(\mathbf{pk},u^{2}x^{b}\mod
N)=a]$ $\displaystyle=\mathbf{Pr}[r^{2}u^{2}x^{b}=a\mod N]$
$\displaystyle=\mathbf{Pr}[r^{2}=u^{-2}x^{-b}a\mod N]$
$\displaystyle=\mathbf{Pr}[(u^{-1}vr)^{2}=u^{-2}x^{-b}a\mod N]$
$\displaystyle=\mathbf{Pr}[r^{2}v^{2}x^{b}=a\mod N]$
$\displaystyle=\mathbf{Pr}[\mathsf{Rerandomize}(\mathbf{pk},c^{\prime})=a],$

where the fourth equality follows from $r$ being chosen uniformly at random
from $\mathbb{Z}^{*}_{N}$. ∎

###  4.2 Correlated Sampling via One-Way Function Inverters

As we saw in Section 3.3, correlated sampling gives a generic way for
converting a perfectly generalizing algorithm into a replicable one. In this
section, we show that the existence of efficient one-way function inverters
implies the ability to efficiently perform correlated sampling on arbitrary
distributions over $\\{0,1\\}^{n}$. Specifically, we show that if there are no
non-uniform one-way functions, then there is polynomial time implicit
correlated sampling.

######  Theorem 4.9.

Assuming uniform one-way function inverters exist (Definition 4.11), Algorithm
$\mathtt{CorrSamp}$ is an $(m,n,\nu)$-implicit correlated sampling algorithm
that runs in time polynomial in $m$, $n$, and $1/\nu$.

###### Proof.

The distributional accuracy property is shown in the proof of Lemma 4.14. The
correlated sampling property is shown in the proof of Lemma 4.16. The runtime
of $\mathtt{CorrSamp}$ is shown in the proof of Lemma 4.17. ∎

####  4.2.1 Relevant Definitions

We model samplable distributions by considering the distribution induced by
giving random inputs to circuits. Furthermore, we allow for a distributional
error parameter $\nu$, giving some slack in the correctness of a correlated
sampler.

######  Definition 4.10 (Implicit Correlated Sampling Algorithm).

Let $m,n\in\mathbb{Z}^{+}$, and let $C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$
denote a circuit. Let distributional error parameter $\nu>0$.
$\mathcal{B}(C,\nu;r)$ is an _$(m,n,\nu)$ -implicit correlated sampling
algorithm_ if the following conditions hold:

  1. 1.

Inputs/Outputs: $\mathcal{B}$ takes as input a circuit
$C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$, a distributional error parameter
$\nu$, and a random string $r$. $\mathcal{B}$ outputs a string in
$\\{0,1\\}^{n}$.

  2. 2.

$\nu$-distributional accuracy: For all circuits
$C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$, the distributions $D_{C}$ and
$D_{\mathcal{B}(C,\nu)}$ satisfy
$d_{\mathrm{T}V}(D_{C},D_{\mathcal{B}(C,\nu)})\leq O(\nu)$.

Here, $D_{C}$ denotes the distribution over $\\{0,1\\}^{n}$ induced by
querying $C(r)$ on uniformly random inputs $r$, i.e., probability density
function $p_{D_{C}}(x)=\mathbf{Pr}_{r\sim U^{m}}[C(r)=x]$. Similarly,
$D_{\mathcal{B}(C,\nu)}$ denotes the distribution over $\\{0,1\\}^{n}$ induced
by querying $\mathcal{B}(C,\nu;r)$ with uniformly random strings $r$.

  3. 3.

Correlated sampling: For all pairs of circuits
$C_{1},C_{2}:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$,
$\mathbf{Pr}_{r}[\mathcal{B}(C_{1},\nu;r)\neq\mathcal{B}(C_{2},\nu;r)]\in
O(d_{\mathrm{T}V}(D_{C_{1}},D_{C_{2}})+\nu)$.

We assume we can invert any one-way function on almost all inputs.
Specifically, we assume that there is no non-uniform one-way function family,
so that there is a uniform way of inverting any circuit computing a function
via a polynomial-time inverter.

######  Definition 4.11 (Uniform One-Way Function Inverters).

Let $\nu^{\prime}>0$. $\mathcal{I}_{\nu^{\prime}}(C,y)$ is a _uniform one-way
function inverter with error $\nu^{\prime}$_ if, for any circuit
$C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$,
$\mathbf{Pr}_{r^{\prime}\sim\\{0,1\\}^{m}}[C(\mathcal{I}_{\nu^{\prime}}(C,C(r^{\prime})))=C(r^{\prime})]\geq
1-\nu^{\prime}$, and $\mathcal{I}$ runs in randomized polynomial time in $m$,
$n$, and $1/\nu^{\prime}$.

In this argument, we will choose $\nu^{\prime}$ to be inverse polynomially
small in $m,n,$ and $1/\nu$. In addition, we assume that $C(r)$ can be
efficiently computed.888Note that if there is no such efficient circuit $C$
that produces a sample from a distribution $D_{C}$ (on a uniformly random
input), then $D_{C}$ is hard to sample from, and designing an efficient
correlated sampling algorithm whose marginal distribution is $D_{C}$ (when
given circuit $C$) is hopeless. Thus, we can check if and when the inverter
succeeds. For notational convenience, we say that the inverter $\mathcal{I}$
returns “$\perp$” if it does not succeed.

Our correlated sampler randomly samples from pairwise-independent hash
families in its subroutines.

######  Definition 4.12 (Pairwise-Independent Hash Family).

A family of Boolean functions
$\mathcal{H}=\\{H|H:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}\\}$ is _pairwise-
independent_ if, for all $r_{1}\neq r_{2}\in\\{0,1\\}^{m}$ and
$x_{1},x_{2}\in\\{0,1\\}^{n}$,
$\mathbf{Pr}_{H\in\mathcal{H}}[H(r_{1})=x_{1}\land H(r_{2})=x_{2}]=2^{-2n}$.

####  4.2.2 Algorithm Overview

A correlated sampling algorithm $\mathcal{B}$ accomplishes two goals. First,
$\mathcal{B}(C,\nu;r)$ needs to accurately sample from the distribution
$D_{C}$. Second, $\mathcal{B}$ must convert a random string $r$ into the same
output when run on distributionally close circuits $C_{1}$ and $C_{2}$, with
high probability. In other words, $\mathcal{B}$ must choose a consistent way
to map random strings $r$ to elements in the support of $D_{C}$.

For intuition, consider a restricted case of correlated sampling problems in
which the distributions $D_{C}$ induced by random inputs to circuits
$C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$ are promised to be uniformly
supported on $2^{\ell}$ elements $x\in\\{0,1\\}^{n}$ for some fixed $\ell$.
Let $k$ be a small slack parameter, and consider the following sampler:

  1. 1.

Draw a random hash function $H:\\{0,1\\}^{n}\to\\{0,1\\}^{\ell+k}$

  2. 2.

Draw a random string $u\in\\{0,1\\}^{\ell+k}$

  3. 3.

Run the inverter on $u$: $r=\mathcal{I}_{\nu^{\prime}}(C\circ H,u)$

  4. 4.

If $r=\bot$ (i.e. $u$ is not in the support of $C\circ H$), repeat. Else
return $y^{*}=C(r)$

ptRandomness $\\{0,1\\}^{m}$ptStep 3.$r=\mathcal{I}_{\nu^{\prime}}(C\circ
H,u)$pt$\mathtt{supp}(D_{C})$$\\{0,1\\}^{n}$ptStep 4.$y^{*}=C(r)$ptHash range
$\\{0,1\\}^{\ell+k}$ptStep 2.$u\sim\mathcal{U}(\\{0,1\\}^{\ell+k})$ptStep
1.Draw $H$$C$$H$$\mathcal{I}_{\nu^{\prime}}(C\circ H,\cdot)$ Figure 2: High-
level structure of correlated sampler for uniform $D_{C}$

The high level idea is that $k$ can be chosen large enough such that
$\mathtt{supp}(D_{C})$ has few collisions with good probability (for random
$H$), but small enough s.t. $2^{k}$ (and therefore the runtime) remains
polynomial in the relevant parameters. Assuming no collisions occur, it is
easy to see this process is a correlated sampler since each element in the
support of $D_{C}$ is sampled uniformly at random, and moreover applied to
distinct circuits $C_{1}$ and $C_{2}$, $y^{*}$ only differs if the sampler
hits a hash value $u$ that contains an element in the symmetric difference
$\mathtt{supp}(C_{1})\Delta\mathtt{supp}(C_{2})$. Since there are no
collisions, this occurs exactly with probability $d_{TV}(D_{C_{1}},D_{C_{2}})$
as desired.

Moving to the general case, our algorithm $\mathtt{CorrSamp}$ applies this
idea as follows. $\mathtt{CorrSamp}$ divides the distribution $D_{C}$ into
“levels” $\ell$, such that each level contains elements in the support with
probability density near $2^{-\ell}$ (specifically, those in the range
$(2^{-\ell-1},2^{-\ell}]$). We now pick a level uniformly at random, and hope
to apply the above process. Intuitively, the main challenge is that given the
output $y^{*}$, we need to ensure $y^{*}$ actually belongs at level $\ell$.
This is done through the introduction of a second hash function
$H_{2}:\\{0,1\\}^{m}\to\\{0,1\\}^{m-\ell+k}$. In particular, fixing $u$ and
$y^{*}$ as in the simplified variant, we wish to estimate
$|C^{-1}(y^{*})|=|(H\circ C)^{-1}(u)|$ (assuming no collisions). To do this,
we call the inverter on the concatenated function
$F_{C,l,H,H_{2}}(r)\stackrel{{\scriptstyle{\mathrm{\scriptstyle
def}}}}{{=}}H(C(r))\mathbin{\|}H_{2}(r)$999 We use ‘$\mathbin{\|}$’ to denote
concatenation of strings. on many pairs of the form $(u||v)$, where
$v\in\\{0,1\\}^{m-\ell+k}$ is chosen uniformly at random. Since we have fixed
$u$, the inverter can only succeed on this call when $v=H_{2}(r)$ for some
$r\in(C\circ H)^{-1}(u)$. Since $v$ is chosen uniformly at random, the success
probability of the inverter is then directly proportional to the density of
$y^{*}$, allowing us to determine whether or not $y^{*}$ is in level $\ell$
with high probability.101010Of course this only holds assuming few collisions.
To handle the general case, we actually draw a new $H_{2}$ with every choice
$v$ to ensure this holds across all rounds. We can then return $y^{*}$ if it
is in the chosen level, and repeat the process from the beginning if not.
Because we have chosen $u$ uniformly at random from $\\{0,1\\}^{\ell+k}$, for
any $x$ it holds that $x=H^{-1}(u)$ with probability $2^{-\ell-k}$ (assuming
no collisions). Then this approach allows us to sample uniformly from level
$\ell$, where every $x$ in level $\ell$ is output with probability
proportional to $2^{-\ell}$. Note that since the true density may be a
constant factor away from $2^{-\ell}$, this is not yet quite enough to achieve
our true target distributional accuracy—we will address this detail in the
next section.

pt$\ell=0\mid x:p_{D}(x)\in(1/2,1]$pt$\ell=1\mid
x:p_{D}(x)\in(1/4,1/2]$pt$\vdots$pt$\ell=m-1\mid
x:p_{D}(x)\in[2^{-m},2^{-m+1}]$pt$\mathtt{supp}(D_{C})$$\\{0,1\\}^{n}$ptStep
1.Pick $\ell$ptStep 2.Pick $H_{1}$pt$H_{1}$ range $\\{0,1\\}^{\ell+k}$ptStep
3.$u\sim\mathcal{U}(\\{0,1\\}^{\ell+k})$pt$H_{2}$ range
$\\{0,1\\}^{m-\ell+k}$ptStep 5.Sample many
$v^{(i)}\sim\mathcal{U}(\\{0,1\\}^{m-\ell+k})$ptRandomness
$\\{0,1\\}^{m}$ptStep 6.Estimate $p_{D}(y^{*})$by inverting $F$ onall
$(u,v^{(i)})$ pairsptStep 7.If $p_{D}(y^{*})$ in chosen $\ell$return $y^{*}$,
o/w go to Step 1.ptStep 4.Pick
$H_{2}$$H_{1}$$H_{2}$$C$$\mathcal{I}_{\nu^{\prime}}(F,\cdot,\cdot)$ Figure 3:
High-level structure of correlated sampler for general $D_{C}$

####  4.2.3 Algorithm Description and Pseudocode

We now give pseudocode for the $\mathtt{CorrSamp}$ algorithm and its
subroutines, in addition to a more detailed description. The main algorithm
$\mathtt{CorrSamp}$ takes as input a circuit $C$ and an error parameter $\nu$.
As described in Section 4.2.2, at each iteration of the main loop,
$\mathtt{CorrSamp}$ picks a level $\ell$ uniformly at random, and then tries
to sample an element that has probability roughly $2^{-\ell}$ under $D_{C}$.
In addition to drawing a hash function $H_{1}$ with range
$\\{0,1\\}^{\ell+k}$, and an element $u$ from that range, it will also sample
a random threshold parameter $\beta\in(1,2]$, and invoke the subroutine
$\mathtt{ElemFind}_{C,\nu,\ell,\beta}(H_{1},u)$ with these parameters and
inputs. We will properly motivate this new parameter $\beta$ shortly, but
looking ahead, it will help us avoid the distributional accuracy issues
present in Section 4.2.2.

In the pseudocode for $\mathtt{CorrSamp}$ (Algorithm 6), $k$ is chosen to be
large enough that we will be able to avoid problematic collisions for all hash
functions with high probability, but small enough to ensure polynomial
runtime. The value $T_{1}$ is chosen to be large enough that
$\mathtt{CorrSamp}$ returns $x\neq\bot$ with high probability, but also small
enough such that we can guarantee certain simplifying assumptions will hold
with high probability across all rounds of $\mathtt{CorrSamp}$.

$k\leftarrow\Theta(\log(m)+\log(1/\nu))$

$T_{1}\leftarrow\Theta(mk2^{k}\log(1/\nu))$

5 for $t=1$ to $t=T_{1}$ do

6 $\beta\leftarrow_{r}[1,2]$

7 $\ell\leftarrow_{r}\\{0,1,\dots,m\\}$

8 $H_{1}\leftarrow_{r}$ pairwise independent hash function from $n$ bits to
$\ell+k$ bits

9 $u\leftarrow_{r}\\{0,1\\}^{\ell+k}$

10 $x\leftarrow\mathtt{ElemFind}_{C,\nu,\ell,\beta}(H_{1},u;r)$

if $x\neq\bot$ then

return $x$

end if

end for

return $\perp$

2 Input: Circuit $C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$, distributional
error parameter $\nu$, and random string $r$

Output: An element $x\in\\{0,1\\}^{n}$

Algorithm 6 $\mathtt{CorrSamp}(C,\nu;r)$

4 Input: Circuit $C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$, distributional
error parameter $\nu$, and random string $r$

Output: An element $x\in\\{0,1\\}^{n}$

The subroutine $\mathtt{ElemFind}_{C,\nu,\ell,\beta}(H_{1},u;r)$ follows the
approach described in Section 4.2.2, estimating the probability of
$y^{*}=H_{1}^{-1}(u)$ under $D_{C}$ by drawing many pairs $(H_{2},v)$ of hash
functions with elements from their range, and invoking the subroutine
$\mathtt{HashCheck}_{C,\nu,\ell,H_{1},u}(H_{2},v)$ to invert
$H(C(r))||H_{2}(r)$ on each $(u,v)$. This procedure approximates the density
of random strings $r$ mapped to $y^{*}$ by $C$. If $y^{*}$ is in or nearly in
level $\ell$, then $\mathtt{ElemFind}$ will obtain an estimate
$\widehat{q}(y^{*})$ that is close to $p_{D}(y^{*})2^{\ell-k}$. It will then
return $y^{*}$ only if $\frac{\beta}{2}2^{-k}<\widehat{q}(y^{*})\leq\beta
2^{-k}$, i.e. roughly when $\beta 2^{-\ell-1}<p_{D}(y^{*})\leq\beta
2^{-\ell}$.

We now reach the core reason for choosing our threshold $\beta$ randomly. As
in Section 4.2.2, if we did fix $\beta$, then any $y^{*}$ at level $\ell$ will
be sampled whenever $y^{*}\in H_{1}^{-1}(u)$, which happens with probability
proportional to $2^{-\ell}$. Since this occurs for any $p_{D}(y^{*})\in[\beta
2^{-\ell-1},\beta 2^{-\ell}]$, this is not a good enough estimate. The key is
to observe that choosing $\beta$ randomly allows us to avoid this kind of
uniform sampling over any particular level. Instead we sample from “fuzzy”
levels, where the choice of $\beta$ shifts the boundaries while maintaining
that the fuzzy levels partition $[0,1]$. In slightly more detail, observe that
for any $y^{*}$ there is some $j$ such that $p_{D}(y^{*})=\alpha
2^{-j-1}+(1-\alpha)2^{-j}$ for $\alpha\in[0,1]$. This means we want $y^{*}$ to
belong to ‘level’ $(j+1)$ with probability $\alpha$, and to level $j$ with
probability $(1-\alpha)$. We will show in Lemma 4.14 that choosing $\beta$
uniformly at random exactly achieves this.

In the pseudocode for $\mathtt{ElemFind}$ (Algorithm 7), $k$ is chosen to
balance the same constraints we have described for $\mathtt{CorrSamp}$. The
value for $T_{2}$, the number of hash function and element pairs $(H_{2},v)$
used to estimate the probability $p_{D}(y^{*})$, is large enough to ensure a
good empirical estimate for $y^{*}$, but small enough to ensure
$\mathtt{ElemFind}$ still runs in time polynomial in $m,n,$ and $1/\nu$.

$k\leftarrow\Theta(\log(m)+\log(1/\nu))$

7 $T_{2}\leftarrow\Theta(\nu^{-2}\log(1/\nu)T_{1}^{-1}\log(T_{1}^{-1}))$

8 for $i=1$ to $i=T_{2}$ do

9 $H^{i}_{2}\leftarrow_{r}$ pairwise independent hash function from $m$ bits
to $m-\ell+k$ bits

10 $v^{i}\leftarrow_{r}\\{0,1\\}^{m-\ell+k}$

Run $\mathtt{HashCheck}_{C,\nu,\ell,H_{1},u}(H_{2}^{i},v^{i};r)$

11 end for

12 Let $\widehat{q}_{x}$ denote the fraction of times $x$ was returned by
$\mathtt{HashCheck}$

13 if $\exists$ unique $x$ s.t. $x\neq\perp$ and
$\widehat{q}_{x}\in((\beta/2)2^{-k},\beta 2^{-k}]$ then

return $x$

else

return $\perp$

end if

2 (Explicit) Input: Hash function
$H_{1}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\ell+k}$, string
$u\in\\{0,1\\}^{\ell+k}$, random string $r$

3 (Implicit) Input: Circuit $C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$,
distributional error parameter $\nu$, integer $\ell\in\\{0,1,\dots,m\\}$,
interval rescaling parameter $\beta$

Output: String $x\in\\{0,1\\}^{n}$ and probability
$q_{x}\in((\beta/2)2^{-k},\beta 2^{-k}]$.

Algorithm 7 $\mathtt{ElemFind}_{C,\nu,\ell,\beta}(H_{1},u;r)$

5 (Explicit) Input: Hash function
$H_{1}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\ell+k}$, string
$u\in\\{0,1\\}^{\ell+k}$, random string $r$

6 (Implicit) Input: Circuit $C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$,
distributional error parameter $\nu$, integer $\ell\in\\{0,1,\dots,m\\}$,
interval rescaling parameter $\beta$

Output: String $x\in\\{0,1\\}^{n}$ and probability
$q_{x}\in((\beta/2)2^{-k},\beta 2^{-k}]$.

7

8 Define circuit
$F_{C,\ell,H_{1},H_{2}}(r^{\prime})=H_{1}(C(r^{\prime}))\mathbin{\|}H_{2}(r^{\prime})$

$\nu^{\prime}\leftarrow$ inverse polynomial quantity in $m,n,1/\nu$.

9
$r^{\prime}\leftarrow\mathcal{I}_{\nu^{\prime}}(F_{C,\ell,H_{1},H_{2}},(u\mathbin{\|}v);r)$

if $r^{\prime}=\perp$ then

return $\perp$

else

return $C(r^{\prime})$

end if

2 (Explicit) Input: Hash function (circuit)
$H_{2}:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{m-\ell+k}$, string
$v\in\\{0,1\\}^{m-\ell+k}$, and random string $r$

3 (Implicit) Input: Circuit $C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$,
distributional error parameter $\nu$, integer $\ell\in\\{0,1,\dots,m\\}$, hash
function $H_{1}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\ell+k}$ and string
$u\in\\{0,1\\}^{\ell+k}$

Output: String $x\in\\{0,1\\}^{n}$

Algorithm 8 $\mathtt{HashCheck}_{C,\nu,\ell,H_{1},u}(H_{2},v;r)$

5 (Explicit) Input: Hash function (circuit)
$H_{2}:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{m-\ell+k}$, string
$v\in\\{0,1\\}^{m-\ell+k}$, and random string $r$

6 (Implicit) Input: Circuit $C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$,
distributional error parameter $\nu$, integer $\ell\in\\{0,1,\dots,m\\}$, hash
function $H_{1}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{\ell+k}$ and string
$u\in\\{0,1\\}^{\ell+k}$

Output: String $x\in\\{0,1\\}^{n}$

####  4.2.4 Analysis – Structure and Simplifying Assumptions

In this section, we analyze the $\mathtt{CorrSamp}$ algorithm. Before
proceeding with the analysis, we first introduce several simplifying
assumptions below we will use throughout. In Section 4.2.5, we analyze the
distributional accuracy of $\mathtt{CorrSamp}$, showing that its distribution
over outputs is close to the target distribution. In Section 4.2.6, we analyze
the success probability of $\mathtt{CorrSamp}$ as a correlated sampler,
showing that for two circuits $C_{1}$ and $C_{2}$,
$\mathtt{CorrSamp}(C_{1},\nu;r)=\mathtt{CorrSamp}(C_{2},\nu;r)$ except with
probability proportional to $d_{\mathrm{T}V}(D_{C_{1}},D_{C_{2}})$. In Section
4.2.7, we show that $\mathtt{CorrSamp}$ runs in time polynomial in the $m$,
$n$, and $1/\nu$. Finally, in Section 4.2.8 we show that our simplifying
assumptions hold for the entire execution of $\mathtt{CorrSamp}$, except with
high probability. Thus, all statements about the behavior of
$\mathtt{CorrSamp}$ under the ideal conditions will still hold without these
assumptions, except with probability $O(\nu)$.

######  Definition 4.13 (Ideal Conditions).

We collectively refer to the following as the _ideal conditions_.

  * •

The inverter $\mathcal{I}_{\nu^{\prime}}$ never fails: for all $x$ and $r$ on
which $\mathtt{CorrSamp}$ invokes $\mathcal{I}_{\nu^{\prime}}(x;r)$,
$\mathcal{I}_{\nu^{\prime}}(x;r)\neq\bot$.

  * •

For every $\ell$, there is at most one $y^{*}\in H_{1}^{-1}(u)$ s.t.

$p_{D}(y^{*})\in[2^{-\ell-4},2^{-\ell+4}]$

  * •

$\mathtt{ElemFind}$ always returns $y^{*}$ or ‘$\bot$’. Furthermore, for
$y^{*}$ returned by $\mathtt{ElemFind}$, we have the stronger condition that
$p_{D}(y^{*})\in[2^{-\ell-2},2^{-\ell+2}].$

  * •

The empirical estimate of $\widehat{q}(y^{*})$ is good:

$\hat{q}(y^{*})\in\left(1\pm O\left(\nu\right)\right)p_{D}(y^{*})2^{\ell-k}$

####  4.2.5 Analysis – Distributional Accuracy.

In this section, we analyze the distributional accuracy of
$\mathtt{CorrSamp}$. Denote by $D_{\mathtt{CorrSamp}}$ the distribution over
outputs of $\mathtt{CorrSamp}(C,\nu)$. We show that
$d_{\mathrm{T}V}(D_{\mathtt{CorrSamp}},D_{C})\leq O(\nu)$, assuming the ideal
conditions of Definition 4.13.

######  Lemma 4.14 (Distributional Accuracy of $\mathtt{CorrSamp}$).

For all circuits $C:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$, the distributions
$D_{C}$ and $D_{\mathtt{CorrSamp}}$ satisfy
$d_{\mathrm{T}V}(D_{C},D_{\mathtt{CorrSamp}})\leq O(\nu)$, assuming the ideal
conditions of Definition 4.13 hold for all rounds of $\mathtt{CorrSamp}$.
Here, $D_{C}$ and $D_{\mathtt{CorrSamp}}$ denote the distributions over
$\\{0,1\\}^{n}$ induced by querying $C(r)$ and $\mathtt{CorrSamp}(C,\nu;r)$
respectively with uniformly random strings $r$.

We first prove the following useful lemma, bounding the probability that any
$x\in\mathtt{supp}(D_{C})$ is returned in a single round.

######  Lemma 4.15.

Fix an $x\in\mathtt{supp}(D_{C})$. Then
$\mathbf{Pr}_{H_{1},u,\ell,\beta}[\mathtt{ElemFind}_{C,\nu,\ell,\beta}(H_{1},u)=x]\in\frac{p_{D}(x)(1+O(\nu))}{(m+1)2^{k}}$.

###### Proof.

For any $\ell$, we have that
$\mathbf{Pr}_{H_{1},u}[x=H_{1}^{-1}(u)]=2^{-\ell-k}$. Conditioned on $x$ being
selected by $H_{1}$ and $u$, by construction,
$\mathtt{ElemFind}_{C,\nu,\ell,\beta}$ returns $x$ whenever
$\widehat{q}(x)\in(\frac{\beta}{2}2^{-k},\beta 2^{-k}]$. Rewriting
$p_{D}(x)=\gamma 2^{-j}$ for $\gamma\in[1/2,1]$, we observe that $x$ will only
ever have non-zero probability of being returned by
$\mathtt{ElemFind}_{C,\nu,\ell,\beta}(H_{1},u)$ when $j-1\leq\ell\leq j+2$,
from the assumptions of Definition 4.13. Since we have $\widehat{q}(x)\in(1\pm
O(\nu))p_{D}(x)2^{\ell-k}$ for any $\ell$ in this range, it follows that for
these $\ell$,

$\displaystyle\mathbf{Pr}_{\beta}\left[\widehat{q}(x)\in(\tfrac{\beta}{2}2^{-k},\beta
2^{-k}]\right]$
$\displaystyle\in\mathbf{Pr}_{\beta}[\tfrac{\beta}{2}<p_{D}(x)2^{\ell}(1\pm
O(\nu))\leq\beta]$
$\displaystyle\in\mathbf{Pr}_{\beta}[\tfrac{\beta}{2}<p_{D}(x)2^{\ell}\leq\beta]\pm
O(\nu)p(x)2^{\ell}.$

Recalling that $\ell$ is chosen uniformly at random from $\\{0,\dots,m\\}$, we
can then write the probability that $\mathtt{ElemFind}$ returns $x$ as

$\displaystyle\mathbf{Pr}_{H_{1},u,\ell,\beta}[\mathtt{ElemFind}_{C,\nu,\ell,\beta}(H_{1},u)=x]$
$\displaystyle\in\sum_{\ell\in[j-1,j+2]}\frac{\mathbf{Pr}_{\beta}[\tfrac{\beta}{2}<p_{D}(x)2^{\ell}\leq\beta]\pm
O(\nu)p_{D}(x)2^{\ell}}{(m+1)2^{\ell+k}}$
$\displaystyle\in\left(\sum_{\ell\in[j-1,j+2]}\frac{\mathbf{Pr}_{\beta}[\tfrac{\beta}{2}<p_{D}(x)2^{\ell}\leq\beta]}{(m+1)2^{\ell+k}}\right)\pm\frac{O(\nu)p_{D}(x)}{(m+1)2^{k}}.$

Observing that
$\mathbf{Pr}_{\beta}[\tfrac{\beta}{2}<p_{D}(x)2^{\ell}\leq\beta]=0$ except for
$\ell\in\\{j,j+1\\}$, we can simplify the series:

$\displaystyle\sum_{\ell\in[j-1,j+2]}\frac{\mathbf{Pr}_{\beta}[\tfrac{\beta}{2}<p_{D}(x)2^{\ell}\leq\beta]}{(m+1)2^{\ell+k}}$
$\displaystyle=\sum_{\ell\in[j,j+1]}\frac{\mathbf{Pr}_{\beta}[\tfrac{\beta}{2}<p_{D}(x)2^{\ell}\leq\beta]}{(m+1)2^{\ell+k}}$
$\displaystyle=\frac{\mathbf{Pr}_{\beta}[\tfrac{\beta}{2}<p_{D}(x)2^{j}\leq\beta]}{(m+1)2^{j+k}}+\frac{\mathbf{Pr}_{\beta}[\tfrac{\beta}{2}<p_{D}(x)2^{j+1}\leq\beta]}{(m+1)2^{j+k+1}}$
$\displaystyle=\frac{\mathbf{Pr}_{\beta}[\tfrac{\beta}{2}<\gamma\leq\beta]}{(m+1)2^{j+k}}+\frac{\mathbf{Pr}_{\beta}[\tfrac{\beta}{2}<2\gamma\leq\beta]}{(m+1)2^{j+k+1}}$
$\displaystyle=\frac{\mathbf{Pr}_{\beta}[\beta<2\gamma]}{(m+1)2^{j+k}}+\frac{\mathbf{Pr}_{\beta}[\beta\geq
2\gamma]}{(m+1)2^{j+k+1}}$
$\displaystyle=\frac{2\gamma-1}{(m+1)2^{j+k}}+\frac{2-2\gamma}{(m+1)2^{j+k+1}}$
$\displaystyle=\frac{2\gamma-1+1-\gamma}{(m+1)2^{j+k}}$
$\displaystyle=\frac{p_{D}(x)}{(m+1)2^{k}}.$

Plugging back into the probability that $\mathtt{ElemFind}$ returns $x$, we
have

$\displaystyle\mathbf{Pr}_{H_{1},u,\ell,\beta}[\mathtt{ElemFind}_{C,\nu,\ell,\beta}(H_{1},u)=x]$
$\displaystyle\in\frac{p_{D}(x)(1+O(\nu))}{(m+1)2^{k}}.$

∎

Finally, we can show that the output distribution of $\mathtt{CorrSamp}$ and
that of circuit $C$ are $O(\nu)$-close in variation distance.

###### Proof.

Proof of Lemma 4.14:

From Lemma 4.15, we have that in each round, $x$ is returned by
$\mathtt{ElemFind}$ with probability $\frac{p_{D}(x)(1\pm
O(\nu))}{(m+1)2^{k}}$.

Summing over all $x$, the probability that $\mathtt{CorrSamp}$ terminates in
any individual round is in the range $\frac{1\pm O(\nu)}{(m+1)2^{k}}$. So,
conditioned on a round of $\mathtt{CorrSamp}$ returning, the algorithm returns
$x$ with probability in $(1\pm O(\nu))p_{D}(x)$. Finally, $\mathtt{CorrSamp}$
does not return by the final $T_{1}$’th round with probability at most
$O(\nu)$, by the choice of $T_{1}$. Altogether, this implies
$d_{\mathrm{T}V}(D_{C},D_{\mathtt{CorrSamp}})\in O(\nu)$ as desired. ∎

####  4.2.6 Analysis — Correlated Sampling.

Next, we show that $\mathtt{CorrSamp}$ satisfies the correlated sampling
requirement of Definition 4.10. To simplify notation in this subsection, we
will denote the probability of an element $x$ under $D_{C_{1}}$ and
$D_{C_{2}}$ by $p_{1}(x)$ and $p_{2}(x)$ respectively.

######  Lemma 4.16 (Correlated Sampling of $\mathtt{CorrSamp}$).

For all pairs of circuits $C_{1},C_{2}:\\{0,1\\}^{m}\rightarrow\\{0,1\\}^{n}$,
assuming the ideal conditions hold for all rounds of
$\mathtt{CorrSamp}(C_{1},\nu;r)$ and $\mathtt{CorrSamp}(C_{2},\nu;r)$,

$\mathbf{Pr}_{r}[\mathtt{CorrSamp}(C_{1},\nu;r)\neq\mathtt{CorrSamp}(C_{2},\nu;r)]\leq
O(d_{\mathrm{T}V}(D_{C_{1}},D_{C_{2}})+\nu).$

###### Proof.

Let $E_{0}$ denote the event that
$\mathtt{CorrSamp}(C_{1},\nu;r)\neq\mathtt{CorrSamp}(C_{2},\nu;r)$, and for
simplicity of notation, shorten $\mathtt{ElemFind}$ to $\mathtt{EF}$, and
write $\mathtt{EF}^{(i)}_{C_{j}}$ to denote the output of $\mathtt{ElemFind}$
in the $i$th round. We start by making some simplifying assumptions. First,
observe that since the probability $\mathtt{CorrSamp}$ returns $\bot$ is
always at most $O(\nu)$, we can condition on the fact that both
$\mathtt{CorrSamp}(C_{2},\nu;r)\neq\bot$ and
$\mathtt{CorrSamp}(C_{1},\nu;r)\neq\bot$ without loss of generality. Second,
we can assume by symmetry that $\mathtt{CorrSamp}(C_{1},\nu;r)$ does not
return before $\mathtt{CorrSamp}(C_{2},\nu;r)$ (else relabel $C_{1}$ as
$C_{2}$).

With this in mind, let $E_{i}$ denote the event that
$\mathtt{CorrSamp}(C_{2},\nu;r)$ returns in round $i$. The event $E_{0}$ can
then be bounded by

$\mathbf{Pr}[E_{0}]\leq\sum\limits_{i}\mathbf{Pr}[E_{i}]\mathbf{Pr}_{\beta,\ell}[\mathtt{EF}^{(i)}_{C_{1}}\neq\mathtt{EF}^{(i)}_{C_{2}}\mid
E_{i}].$

To bound the probability of this inner event, observe that under our
assumptions, this occurs exactly when $x=\mathtt{EF}^{(i)}_{C_{2}}$, but for
the empirical estimate computed by $\mathtt{EF}^{(i)}_{C_{1}}$,
$\widehat{q}_{1}(x)\not\in[\frac{\beta}{2}2^{-k},\beta 2^{-k}]$. We will show
conditioned on any value of $x$ and $\ell$, this occurs with probability at
most:

$\mathbf{Pr}_{\beta}[\mathtt{EF}^{(i)}_{C_{1}}\neq x\mid
E_{i},\mathtt{EF}^{(i)}_{C_{2}}=x,\ell]\leq
O(2^{\ell}|p_{2}(x)-p_{1}(x)|+\nu).$ (9)

In this case, we can bound $E_{0}$ by conditioning further on $x$ and $\ell$
as:

$\displaystyle\mathbf{Pr}_{r}[E_{0}]$
$\displaystyle\leq\sum\limits_{i\in[T_{1}]}\mathbf{Pr}_{\beta,\ell}[E_{i}]\mathbf{Pr}_{\beta,\ell}[\mathtt{EF}^{(i)}_{C_{1}}\neq\mathtt{EF}^{(i)}_{C_{2}}\mid
E_{i}]$
$\displaystyle\leq\sum\limits_{i\in[T_{1}]}\mathbf{Pr}_{\beta,\ell}[E_{i}]\sum_{x\neq\bot}\mathbf{Pr}_{\beta,\ell}[\mathtt{EF}^{(i)}_{C_{1}}\neq\mathtt{EF}^{(i)}_{C_{2}}\mid
E_{i},\mathtt{EF}^{(i)}_{C_{2}}=x]\mathbf{Pr}_{\beta,\ell}[\mathtt{EF}^{(i)}_{C_{2}}=x|E_{i}]$
$\displaystyle\leq
O(\nu)+\sum\limits_{i\in[T_{1}]}\mathbf{Pr}_{\beta,\ell}[E_{i}]\sum_{x\neq\bot}\mathbf{Pr}_{\beta,\ell}[\mathtt{EF}^{(i)}_{C_{1}}\neq\mathtt{EF}^{(i)}_{C_{2}}\mid
E_{i},\mathtt{EF}^{(i)}_{C_{2}}=x]p_{2}(x)$ $\displaystyle\leq
O(\nu)+\sum\limits_{i\in[T_{1}]}\mathbf{Pr}_{\beta,\ell}[E_{i}]\sum_{x\neq\bot}p_{2}(x)\sum\limits_{\ell}\mathbf{Pr}[\ell\mid
E_{i},\mathtt{EF}^{(i)}_{C_{2}}=x]\mathbf{Pr}_{\beta}[\mathtt{EF}^{(i)}_{C_{1}}\neq\mathtt{EF}^{(i)}_{C_{2}}\mid
E_{i},\mathtt{EF}^{(i)}_{C_{2}}=x,\ell]$ $\displaystyle\leq
O(\nu)+\sum\limits_{i\in[T_{1}]}\mathbf{Pr}_{\beta,\ell}[E_{i}]\sum_{x\neq\bot}p_{2}(x)\sum\limits_{\ell}\mathbf{Pr}[\ell\mid
E_{i},\mathtt{EF}^{(i)}_{C_{2}}=x]O(2^{\ell}|p_{2}(x)-p_{1}(x)|).$

Under the ideal conditions, the posterior of $\ell$ is $0$ unless
$p_{2}(x)\in[2^{-\ell-2},2^{-\ell+2}]$, so altogether:

$\displaystyle\mathbf{Pr}_{r}[E_{0}]$ $\displaystyle\leq
O(\nu)+\sum\limits_{i\in[T_{1}]}\mathbf{Pr}_{\beta,\ell}[E_{i}]\sum_{x\neq\bot}p_{2}(x)\sum\limits_{\ell}\mathbf{Pr}[\ell\mid
E_{i},\mathtt{EF}^{(i)}_{C_{2}}=x]O\left(\frac{1}{p_{2}(x)}|p_{2}(x)-p_{1}(x)|\right)$
$\displaystyle\leq
O(\nu)+\sum\limits_{i\in[T_{1}]}\mathbf{Pr}_{\beta,\ell}[E_{i}]\sum_{x\neq\bot}O(|p_{2}(x)-p_{1}(x)|)$
$\displaystyle\leq O(d_{TV}(D_{C_{1}},D_{C_{2}})+\nu)$

as desired.

It is therefore left to prove Equation 9, which we analyze the probability by
splitting into two cases based on $p_{1}(x)$:

  1. 1.

$p_{2}(x)/4\leq p_{1}(x)\leq 4p_{2}(x)$

  2. 2.

$p_{1}(x)<p_{2}(x)/4$ or $p_{1}(x)>4p_{2}(x)$

##### Case 1:

In this case, because we are assuming the ideal conditions of Definition 4.13
and have conditioned on
$\mathtt{ElemFind}_{C_{2},\nu,\ell,\beta}(H_{1},u;r)=x$ for some $x$ in this
round, it must be the case that for this $x$ we have:

  * •

$p_{2}(x)\in[2^{-\ell-2},2^{-\ell+2}]$

  * •

$p_{1}(x)\in[2^{-\ell-4},2^{-\ell+4}]$ (from our assumption that
$p_{2}(x)/4\leq p_{1}(x)\leq 4p_{2}(x)$)

  * •

$\widehat{q}_{2}(x)\in(1\pm O(\nu))p_{2}(x)2^{\ell-k}$

  * •

$\widehat{q}_{1}(x)\in(1\pm O(\nu))p_{1}(x)2^{\ell-k}$.

From the uniqueness of $x$ satisfying $x=H_{1}^{-1}(u)$ and
$p_{1}(x)\in[2^{\ell-4},2^{-\ell+4}]$, we can assume that
$\mathtt{ElemFind}_{C_{1},\nu,\ell,\beta}(H_{1},u;r)$ outputs either $x$ or
$\bot$ in this round. Therefore, we can bound the probability
$\mathtt{ElemFind}_{C_{1},\nu,\ell,\beta}(H_{1},u;r)\neq\mathtt{ElemFind}_{C_{2},\nu,\ell,\beta}(H_{1},u;r)$
by the probability that $\mathtt{ElemFind}_{C_{1},\nu,\ell,\beta}(H_{1},u;r)$
outputs $\bot$ conditioned on
$\mathtt{ElemFind}_{C_{2},\nu,\ell,\beta}(H_{1},u;r)$ returning $x$. This
occurs whenever $\beta$ is chosen so that either

$(1+O(\nu))p_{1}(x)2^{\ell-k}<\frac{\beta 2^{-k}}{2}\leq
p_{2}(x)2^{\ell-k}(1+O(\nu))$

or

$p_{2}(x)2^{\ell-k}(1-O(\nu))\leq\beta 2^{-k}<p_{1}(x)2^{\ell-k}(1+O(\nu)).$

Observing that these cases are mutually exclusive and the first interval is
the largest, we consider only that worst case and rearrange to obtain the
condition

$\displaystyle\beta$ $\displaystyle\leq
2^{\ell+1}|p_{2}(x)-p_{1}(x)|+O(\nu)(p_{2}(x)+p_{1}(x))2^{\ell}$
$\displaystyle\leq 2^{\ell+1}|p_{2}(x)-p_{1}(x)|+O(\nu),$

where the last inequality follows from our previously stated bounds
$p_{1},p_{2}\in[2^{-\ell-4},2^{-\ell+4}]$.

Since $\beta$ is chosen uniformly at random from the interval $[1,2]$, it
follows that $\beta$ satisfies the condition above with probability no greater
than $2^{\ell+1}|p_{2}(x)-p_{1}(x)|+O(\nu)$. Conditioning on
$\mathtt{ElemFind}_{C_{2},\nu,\ell,\beta}(H_{1},u;r)=x$ and
$p_{2}(x)\in[2^{-\ell-4},2^{-\ell+4}]$, we have

$\displaystyle\mathbf{Pr}_{\beta}[\mathtt{ElemFind}_{C_{1},\nu,\ell\,\beta}(H_{1},u;r)=\bot]$
$\displaystyle\leq\mathbf{Pr}_{\beta}[\beta\leq
2^{\ell+1}|p_{2}(x_{2})-p_{1}(x_{2})|+O(\nu)]$ $\displaystyle\leq
2^{\ell+1}|p_{2}(x)-p_{1}(x)|+O(\nu).$

##### Case 2:

In this case, we have either $p_{1}(x)<p_{2}(x)/4$ or $p_{1}(x)>4p_{2}(x)$,
and so $p_{2}(x)\in O(|p_{2}(x)-p_{1}(x)|)$. Conditioning on
$\mathtt{ElemFind}_{C_{2},\nu,\ell,\beta}(H_{1},u;r)=x$ in this round also
gives us that $p_{2}(x)=\Theta(2^{-\ell})$, so

$\displaystyle\mathbf{Pr}_{\beta}[\mathtt{ElemFind}_{C_{1},\nu,\ell,\beta}(H_{1},u;r)\neq
x\mid\mathtt{ElemFind}_{C_{2},\nu,\ell,\beta}(H_{1},u;r)=x]$
$\displaystyle\leq 1$ $\displaystyle\leq O(2^{\ell}p_{2}(x_{2}))$
$\displaystyle\leq O(2^{\ell}|p_{2}(x_{2})-p_{1}(x_{2})|).$

Then for any value of $p_{1}(x)$ (either in Case 1 or Case 2) we have that

$\mathbf{Pr}_{\beta}[\mathtt{ElemFind}_{C_{1},\nu,\ell,\beta}(H_{1},u;r)\neq
x\mid\mathtt{ElemFind}_{C_{2},\nu,\ell,\beta}(H_{1},u;r)=x]\in
O(2^{\ell}|p_{2}(x)-p_{1}(x)|+\nu)$

as desired. ∎

####  4.2.7 Analysis — Runtime

######  Lemma 4.17 (Runtime of $\mathtt{CorrSamp}$).

Assuming inverter $\mathcal{I}$ runs in time polynomial in $m$, $n$, and
$1/\nu$, algorithm $\mathtt{CorrSamp}$ also runs in time polynomial in $m$,
$n$, and $1/\nu$.

###### Proof.

Algorithm $\mathtt{CorrSamp}$ runs for at most $O(mk2^{k}\log(1/\nu))$ rounds.
Parameter $k$ is chosen in $\Theta(\log(m)+\log(1/\nu))$, so $2^{k}\in
O(\operatorname{poly}(m,1/\nu))$. Randomly sampling a pairwise-independent
hash function from $n$ bits to $\ell+k$ bits can be done in
$\operatorname{poly}(m,n,1/\nu)$ time.

Each round of $\mathtt{CorrSamp}$ contains a call to $\mathtt{ElemFind}$. In
$\mathtt{ElemFind}$, there are $O(\operatorname{poly}(m,1/\nu))$ rounds in
which a hash function from $m$ bits to $m-\ell+k$ bits is randomly sampled
($O(\operatorname{poly}(m,1/\nu))$ time). Furthermore, each round contains a
call to $\mathtt{HashCheck}$, which runs in time
$\operatorname{poly}(m,n,1/\nu)$ by the assumption that inverter
$\mathcal{I}_{\nu^{\prime}}$ does as well.

Multiplying these nesting terms together, $\mathtt{CorrSamp}$ runs in time
polynomial in $m$, $n$, and $\nu$.

Note that the randomness management, which ensures that the same bits of the
random string $r$ are always used across multiple executions of
$\mathtt{CorrSamp}$, can also be done in time polynomial in $m$, $n$, and
$1/\nu$. Each algorithm and subroutine has a finite number of randomness
calls, and each call can be made using $\operatorname{poly}(m,n,1/\nu)$ random
bits. Thus, $r$ can efficiently be canonically proportioned for all uses of
randomness in the algorithm. For more details, see Appendix C.1.

Parameter $\beta$ is chosen uniformly randomly in $[1,2]$ in each loop of
$\mathtt{CorrSamp}$. Only polynomial in $m$, $n$, and $1/\nu$ bits of
precision are needed to choose $\beta$ so that the errors introduced by not
using uniformly random values are altogether small relative to distributional
error parameter $\nu$. ∎

####  4.2.8 Analysis – Removing Assumption of Ideal Conditions

######  Proposition 4.18.

The ideal conditions of Definition 4.13 hold across all steps of
$\mathtt{CorrSamp}$ with probability at least $1-O(\nu)$.

We break the proof into its four constituent part.

######  Lemma 4.19 (Inverter Never Fails).

Let $\mathcal{S}$ denote the set of strings $(x;r)$ on which
$\mathtt{CorrSamp}$ invokes $\mathcal{I}_{\nu^{\prime}}(x;r)$. The probability
the inverter fails on $\mathcal{S}$ is negligible:

$\mathbf{Pr}[\exists(x;r)\in\mathcal{S}:\mathcal{I}_{\nu^{\prime}}(x;r)=\bot]\leq
O(\nu),$

as long as $\nu^{\prime}=\operatorname{poly}(\nu^{-1},m,n)$ is sufficiently
small.

###### Proof.

Recall our inverter has the following guarantee

$\mathbf{Pr}_{r^{\prime}\sim\\{0,1\\}^{m}}[C(\mathcal{I}_{\nu^{\prime}}(C,C(r^{\prime}));r)=C(r^{\prime})]\geq
1-\nu^{\prime},$

where $r$ stands for the internal randomness of $\mathcal{I}$ and
$\nu^{\prime}$ can be taken to be polynomially small in $m,n$ and $\nu$. It
will be enough to take the failure rate $\nu^{\prime}\leq
O(\frac{\nu^{2}}{T_{1}T_{2}})=\operatorname{poly}(\nu^{-1},m,n)$. We will
bound the probability such an inverter fails on a random input $(u||v)$.

First, observe that by Markov’s inequality, most choices of internal
randomness $r$ for the inverter random work for almost all
$r^{\prime}\in\\{0,1\\}^{m}$:

$\mathbf{Pr}_{r}\left[\mathbf{Pr}_{r^{\prime}}\left[\mathcal{I}_{\nu^{\prime}}(C,C(r^{\prime}));r)\neq
C(r^{\prime})\right]\geq O\left(\frac{\nu}{T_{1}T_{2}}\right)\right]\leq
O(\nu).$

Assume then this event does not occur. Our algorithm only fails if the random
choice of $(u||v)$ is hashed to by a string for which
$\mathcal{I}_{\nu^{\prime}}(C,C(r^{\prime}));r)\neq C(r^{\prime})$. In the
worst case, these bad strings each correspond to unique
$(u||v)\in\\{0,1\\}^{m+2k}$, in which case we have a total of
$\frac{\nu}{T_{1}T_{2}}2^{m}$ out of $2^{m+2k}$ bad inputs. Union bounding
over the $T_{1}T_{2}$ applications of the inverter in $\mathtt{CorrSamp}$
gives a total failure probability of $1-O(\nu)$ as desired. ∎

To prove the remaining conditions, it will be useful first to bound the number
of collisions experienced by our hash functions.

######  Claim 4.20 (Collision Avoidance).

With probability at least $1-O(\nu)$, for all choices of $H_{1}$, $u$, and
$\ell$ in $\mathtt{CorrSamp}$:

  1. 1.

$H_{1}$ has no relevant collisions:

$\forall p_{D}(x),p_{D}(x^{\prime})\in[2^{-\ell-4},2^{-\ell+4}]:H_{1}(x)\neq
H_{1}(x^{\prime}),$

  2. 2.

For all $x\in H_{1}^{-1}(u)$, the total number of collisions across choices of
$H_{2}$ is at most:

$\left|\\{H_{2},(r,r^{\prime})\in
C^{-1}(x):H_{2}(r)=H_{2}(r^{\prime})\\}\right|\leq\delta_{x}T_{2}|C^{-1}(x)|,$

where $\delta_{x}=O\left(2^{\ell}p_{D}(x)\cdot\frac{mk\log(1/\nu)}{\nu}\cdot
2^{-k}\right)$

###### Proof.

To prove the first condition, observe there are at most $2^{\ell+4}$ elements
$x\in\\{0,1\\}^{n}$ with measure in the range
$p_{D}(x)\in[2^{-\ell-4},2^{-\ell+4}]$. Since our hash function is pairwise-
independent, the probability a collision exists in this range is therefore
bounded by $\frac{2^{2\ell+8}}{2^{2\ell+2k}}=2^{4-2k}$. Union bounding over
the $T_{1}$ choices of $H_{1}$, $u$, and $\ell$, a collision still occurs with
probability at most $2^{-\Omega(k)}\leq O(\nu)$ as desired.

To prove the second condition, fix $x\in H_{1}^{-1}(u)$ and observe that by
pairwise independence, the expected number of total collisions across all
choices of $H_{2}$ is at most

$T_{2}\frac{|C^{-1}(x)|^{2}}{2^{2m-2\ell+2k}}.$

by linearity of expectation, so by Markov’s inequality the probability there
are more than

$T_{2}\frac{|C^{-1}(x)|^{2}}{2^{2m-2\ell+2k}}\cdot\frac{T_{1}2^{m}}{\nu}\leq
T_{2}|C^{-1}(x)|\cdot\frac{2^{\ell}p_{D}(x)mk\log(1/\nu)}{\nu 2^{k}}$

total collisions is at most $O(\nu)/(T_{1}2^{m})$, so union bounding over all
choices of $H_{1}$, $u$, and $x$ gives the desired result. ∎

######  Lemma 4.21 (Uniqueness of $y^{*}$).

With probability at least $1-O(\nu)$ over all choices of $H_{1}$ and $u$,
there is at most one element $y^{*}\in H_{1}^{-1}(u)$ satisfying

$p_{D}(y^{*})\in[2^{-\ell-4},2^{-\ell+4}].$

###### Proof.

This is immediate from the fact that $H_{1}$ has no collisions on
$[2^{-\ell-4},2^{-\ell+4}]$ with high probability. ∎

######  Lemma 4.22 (Correctness of $\hat{q}$).

With probability at least $1-O(\nu)$, every run of $\mathtt{ElemFind}$
accurately estimates $p_{D}(y^{*})$ in the following sense:

$\widehat{q}(y^{*})\in\left((1\pm O(\nu))p_{D}(x)2^{\ell-k}\right)$

###### Proof.

For intuition, first consider the setting where no collisions occur in any
$H_{2}$. In this case, observe that the density of the pre-image of $x$ mapped
into the range of $H_{2}$ is exactly $p_{D}(x)2^{\ell-k}$ by construction,
that is:

$\frac{|H_{2}(C^{-1}(y^{*}))|}{2^{m-\ell+k}}=p_{D}(x)2^{\ell-k}.$

As such $\hat{q}(y^{*})$ is distributed as a Binomial distribution
$Bin(p_{D}(y^{*})2^{\ell-k},T_{2})$, and Chernoff promises that

$\mathbf{Pr}_{v,H_{2}}[|\hat{q}(x)-p_{D}(x)2^{\ell-k}|\geq
O(\nu)p_{D}(y^{*})2^{\ell-k}]\leq
e^{-\Omega(\nu^{2}T_{2})}\leq\frac{O(\nu)}{T_{1}}$

by our choice of $T_{2}$. The desired result then follows from union bounding
over all choices of $H_{1}$ and $u$.

We now modify this analysis under the assumption that at most

$C_{col}\coloneqq O\left(\frac{2^{\ell}p_{D}(y^{*})mk\log(1/\nu)}{\nu
2^{k}}\right)\cdot|C^{-1}(y^{*})|T_{2}$

total collisions occur, which holds across all rounds except with probability
$O(\nu)$ (4.20). In this case, since $p_{D}(y^{*})\leq 2^{\ell+4}$, we have

$C_{col}\leq O(\nu)|C^{-1}(y^{*})|T_{2}$

for $k=\Theta(\log(m/\nu))$ sufficiently large, and therefore that the
expectation of our adjusted binomial trial is close enough to its ideal
expectation:

$\sum_{H_{2}}\frac{|H_{2}(C^{-1}(y^{*}))|}{2^{m-\ell+k}}\in
T_{2}\cdot\left[(1-O(\nu))p_{D}(y^{*})2^{\ell-k},p_{D}(y^{*})2^{\ell-k}\right],$

that the collisions have no asymptotic effect on the original Chernoff bound.
∎

######  Lemma 4.23 (Correctness of $\mathtt{ElemFind}$).

With probability at least $1-O(\nu)$, all calls to $\mathtt{ElemFind}$ return
$y^{*}$ or ‘$\bot$’. Furthermore, for $y^{*}$ returned by $\mathtt{ElemFind}$,
we have the stronger condition that
${p_{D}(y^{*})\in[2^{-\ell-2},2^{-\ell+2}]}$.

###### Proof.

For the first claim, it is enough to argue that any $x\in H_{1}^{-1}(u)$
distinct from $y^{*}$ satisfies:

$\hat{q}(x)\notin[(\beta/2)2^{-k},\beta 2^{-k}].$

Assuming $y^{*}$ is unique (Lemma 4.21), we have either that
$p_{D}(x)<2^{-\ell-4}$ or $p_{D}(x)>2^{-\ell+4}$. Consider the former. We will
show $\hat{q}(x)<2^{-k-1}\leq(\beta/2)2^{-k}$. Note that since collisions only
lower $\hat{q}$, they can be ignored in this setting. By construction, the
pre-image of $x$ consists of at most $2^{m-\ell-4}$ strings $r^{\prime}$ map
to $x$, so $|H_{2}(C^{-1}(x))|$ is at most a

$\frac{2^{m-\ell-4}}{2^{m-\ell+k}}=\frac{2^{-k}}{16}$

fraction of the range of $H_{2}$. A Chernoff and Union bound give that all
such $x$ have empirical estimates less than $(\beta/2)2^{-k}$ except with
probability $2^{m}e^{-\Omega(2^{-k}T_{2})}\leq O(\nu)$.

Finally, consider $x$ satisfying $p_{D}(x)\geq 2^{-\ell+4}$. In this case, we
will aim show $\hat{q}(x)>\frac{2}{2^{k}}\geq\beta 2^{-k}$, so it is
sufficient to consider the worst case when $p_{D}(x)=2^{-\ell+4}$. By 4.20, we
can assume there are at most

$C_{col}\leq\frac{1}{4}T_{2}|C^{-1}(x)|$

total collisions over the choices of $H_{2}$, thus as in Lemma 4.22, the
collision-corrected Chernoff bound still promises $\hat{q}(x)>\frac{2}{2^{k}}$
with probability at least
$e^{-\Omega(2^{-k}T_{2})}\leq\frac{O(\nu)}{2^{m}T_{1}}$. Union bounding over
all choices of $H_{1}$, $u$, and values of $x$ completes the proof of the
first claim.

To prove the second claim, we observe that Lemma 4.22 gives us
$\widehat{q}(y^{*})\in(1\pm O(\nu))p_{D}(y^{*})2^{\ell-k}$. Bounding $(1\pm
O(\nu))\in(1/2,2)$, we have

$p_{D}(y^{*})\in(\widehat{q}(y^{*})2^{k-\ell-1},\widehat{q}(y^{*})2^{k-\ell+1}).$

If $\mathtt{ElemFind}$ returned $y^{*}$, it must be the case that

$\widehat{q}(y^{*})\in(\tfrac{\beta}{2}2^{-k},\beta
2^{-k}]\in(2^{-k-1},2^{-k+1}],$

and so

$p_{D}(y^{*})\in[2^{-\ell-2},2^{-\ell+2}],$

conditioned on $\mathtt{ElemFind}$ returning $y^{*}$, as claimed.

∎

##  5 Separating Stability: Statistical Barriers

###  5.1 Quadratic Separation: One-way Marginals

We start by defining the one-way marginals problem over $d$ coordinates, which
corresponds to outputting a good estimate of the expectation of a product of
Rademacher distributions in $\ell_{\infty}$-distance.

######  Definition 5.1.

Consider a product of $d$ Rademacher distributions with expectations
$p=(p_{1},\dots,p_{d})$ respectively. A vector $v\in\mathbb{R}^{d}$ is said to
be an $\alpha$-accurate solution to the one-way marginals problem if
$\|v-p\|_{\infty}\leq\alpha$.

######  Definition 5.2.

Let $C$ be the class of products of $d$ Rademacher distributions. Fix any
distribution $D$ in $C$. We say that an algorithm $(\alpha,\beta)$-accurately
solves the one-way marginals problem over $d$ coordinates, if it observes
samples from the distribution $D$, and with probability at least $1-\beta$
(over the randomness of the samples and the algorithm), produces an
$\alpha$-accurate solution $v\in\mathbb{R}^{d}$.

In this section, we show that any $0.0001$-replicable, $(0.01,0.01)$-accurate
algorithm for the one-way marginals problem over $d$ coordinates requires at
least $\widetilde{Omega}(d)$ samples.

On the other hand, under the constraint of $(1,\frac{1}{n^{2}})$-differential
privacy, this problem can be solved using $\widetilde{O}(\sqrt{d})$ samples,
via the Gaussian mechanism. This gives a quadratic separation between
differential privacy and replicability, and proves that our reduction is
asymptotically tight (up to logarithmic factors) in some settings (since our
reduction would give a $\tilde{O}(d)$-sample replicable algorithm for this
task).

The main theorem we prove in this section is the following.

######  Theorem 5.3.

Fix sufficiently large $d>0$. For any $0.0001$-replicable algorithm
$\mathcal{A}$ that $(0.01,0.001)$-accurately solves the one-way marginals
problem over $d$ coordinates with $m$ samples,

$m=\tilde{\Omega}(d).$

####  5.1.1 Sketch of our approach

Our techniques for proving the lower bound for replicability draw inspiration
from those used to prove lower bounds in privacy. Specifically, tight lower
bounds for the one-way marginals problem over $d$ coordinates under the
constraint of differential privacy are obtained using the fingerprinting
method [39, 29, 28]. The fingerprinting method captures the idea that there is
a trade-off between accuracy and correlation with the input sample. It
quantifies the idea that if the algorithm obtains a sample of small size, and
is also very accurate, then it must be heavily correlated with one of its
input examples, which is prohibited by differential privacy. Since
replicability also prohibits such correlation (at least at a high level), one
might expect the same method to be useful toward this end.

More formally, given an algorithm $\mathcal{A}$ solving the one-way marginals
problem, the correlation of coordinate $j$ of the output with the input sample
$S$ can be measured by the quantity

$Z=\sum\limits_{j\in[d]}\mathcal{A}^{j}(S)\sum\limits_{i\in[m]}(S^{j}_{i}-p_{j}).$

Note that the quantity $(S^{j}_{i}-p_{j})$ represents the drift between an
input example coordinate and the expectation of the distribution it’s drawn
from. $\mathbb{E}[Z]$ is large when on average, for many $j$,
$\mathcal{A}^{j}(S)$ is on the same side of $0$ as the sample drift
$\sum_{i}(S^{j}_{i}-p_{j})$, implying that the algorithm’s outputs are on
average correlated with its input.

We now recall the formal statement of the fingerprinting lemma.

######  Lemma 5.4 (Fingerprinting Lemma, Lemma 3.6 in [28]).

Let $f$ be any function from $\\{-1,1\\}^{m}\to[-1,1]$. Suppose $r$ is sampled
from the uniform distribution over $[-1,1]$ and $q\in\\{-1,1\\}^{m}$ is a
vector of $m$ independent Rademacher RVs each with expectation $r$. Then, if
$\mu_{q}$ is the empirical average of $q$, we get that

$\mathbb{E}_{r,q}[f(q)\sum_{i}(q_{i}-r)+2|f(q)-\mu_{q}|]\geq\frac{1}{3}.$

The lower bound for differential privacy proceeds by arguing that
$\mathbb{E}[Z]=\mathbb{E}[\sum_{j}\mathcal{A}^{j}(S)\sum_{i}(S^{j}_{i}-p_{j})]$
is large (via an appropriate application of the fingerprinting lemma), and
hence, by an averaging argument, there exists an example $S_{i^{*}}\in S$
correlated with the output, i.e. some $i^{*}\in[m]$ such that

$\mathbb{E}[Z_{i^{*}}]=\mathbb{E}[\sum_{j\in[d]}\mathcal{A}^{j}(S)(S^{j}_{i^{*}}-p_{j})]$

is large. With this in hand, consider an independently drawn example
$g=(g^{1}_{i^{*}},\dots,g^{d}_{i^{*}})$, and the neighboring dataset
$S^{\prime}$ obtained by replacing $S_{i^{*}}$ in the original dataset with
$g$. Since $g$ is independent of $S_{i^{*}}$, $\mathcal{A}^{j}(S^{\prime})$ is
uncorrelated with $(S^{j}_{i^{*}}-p_{j})$, and hence the “1-neighboring”
quantity

$\mathbb{E}[Z_{i^{*}}^{\prime}]=\mathbb{E}[\sum_{j\in[d]}\mathcal{A}^{j}(S^{\prime})(S^{j}_{i^{*}}-p_{j})]$

should be small. On the other hand, differential privacy promises that
$Z_{i^{*}}$ is distributionally close to $Z^{\prime}_{i^{*}}$, and hence
$\mathbb{E}[Z^{\prime}_{i^{*}}]$ and $\mathbb{E}[Z_{i^{*}}]$ must be close.
Balancing these considerations gives a lower bound on the number of samples
needed for differential privacy.

For replicability, the idea is to obtain a stronger lower bound by avoiding
averaging. Specifically, for $Z$ defined as above, we can argue that
$\mathbb{E}[Z]$ is large (as we would for the differential privacy lower
bound). Then, we can consider a freshly sampled dataset $S^{\prime}$ (drawn
from a product distribution with the same expectation
$p=(p_{1},\dots,p_{d})$), and consider the quantity
$Z^{\prime}=\sum_{j}\mathcal{A}^{j}(S^{\prime})\sum_{i}(S^{j}_{i}-p_{j})$. We
can argue that $Z^{\prime}$ is a sum of uncorrelated random variables, and
hence that $\mathbb{E}[Z^{\prime}]$ is small. On the other hand, by
replicability, $Z$ and $Z^{\prime}$ are distributionally close, since they
correspond to post-processing of the algorithm applied to independent
datasets. Note that this does not follow from differential privacy, since
datasets $S$ and $S^{\prime}$ may differ in many entries. Now, following a
similar approach to the differential privacy lower bound, we’d get a stronger
lower bound for replicability (since we have eliminated the averaging
argument).

Unfortunately, this approach does not work directly for technical reasons.
Specifically, $\rho$-replicability tells us that $Z$ and $Z^{\prime}$ are
distributionally close, but their expectations can have absolute value
difference as large as $\rho dm$ (since $\mathcal{A}(S)$ and
$\mathcal{A}(S^{\prime})$ could differ completely with probability $\rho$).
Since we are interested in constant $\rho$, this turns out to be too large for
the lower bound technique to work.

We deal with this by instead applying the fingerprinting method to prove a
lower bound against $(\frac{1}{m^{3}},1,\frac{1}{m^{3}})-$perfectly
generalizing algorithms. We find this lower bound interesting in its own
right, as it gives the first sample complexity separation between approximate
differential privacy and perfect generalization. Perfect generalization
roughly asks that the algorithm’s output distributions be
$(1,\frac{1}{m^{3}})$-close on two independent datasets drawn from the product
distribution. This can be used to argue that $\mathbb{E}[|Z|]$ is within
$\frac{1}{m^{2}}$ of (a constant multiple of) $\mathbb{E}[|Z^{\prime}|]$,
which turns out to be sufficient for the lower bound technique to apply.

Finally, appealing to our generic method of converting replicable algorithms
to perfectly generalizing ones, this method extends to a tight lower bound on
replicability (up to the loss of logarithmic factors in the number of
coordinates $d$). It remains an interesting problem whether such a lower bound
can be shown directly, ideally in a manner that avoids the resulting
logarithmic loss.

####  5.1.2 Formal argument

We start by proving our new lower bound for perfectly generalizing algorithms.

######  Theorem 5.5.

Fix any $m>0$ and sufficiently large $d>0$. Let $\mathcal{A}$ be a
$(\frac{1}{m^{3}},1,\frac{1}{m^{3}})$-perfectly generalizing,
$(0.01,0.01)$-accurate algorithm for the 1-way marginals problem over $d$
attributes using $m$ samples. Then, $m=\Omega(d)$.

###### Proof.

Assume without loss of generality that $m=\Omega(\log d)$.111111We will show
under this condition that $m=\Omega(d)$. Any algorithm on $O(\log d)$ samples
implies one between $O(\log d)$ and $O(d)$, which would give a contradiction.
Let $p\sim[-1,1]^{d}$, and draw $S,S^{\prime}\sim D_{p}^{m}$ independently
where $D_{p}$ is a product of Rademachers with expectation
$p=(p_{1},\dots,p_{d})$. Define the random variables

$Z=\sum_{j\in[d]}\mathcal{A}^{j}(S)\sum_{i\in[m]}(S^{j}_{i}-p_{j}),\quad
Z^{\prime}=\sum_{j\in[d]}\mathcal{A}^{j}(S)\sum_{i\in[m]}(S^{\prime
j}_{i}-p_{j}).$

As discussed above, we will argue that $\mathbb{E}[Z]$ is large (by the
fingerprinting lemma):

$\mathbb{E}[|Z|]\geq\frac{d}{10},$ (10)

that $\mathbb{E}[|Z^{\prime}|]$ is small (since $S^{\prime}$ is independent of
$S)$:

$\mathbb{E}[|Z^{\prime}|]\leq 2\sqrt{dm},$ (11)

and finally that $\mathbb{E}[|Z|]$ and $\mathbb{E}[|Z^{\prime}|]$ are close
(by perfect generalization):

$\mathbb{E}[|Z|]\leq e^{2}\mathbb{E}[|Z^{\prime}|]+\frac{8d}{m^{2}}.$ (12)

Combining the inequalities we get

$\frac{d}{10}\leq\mathbb{E}[|Z|]\leq
e^{2}\mathbb{E}\Big{[}|Z^{\prime}|\Big{]}+\frac{8d}{m^{2}}\leq
2e^{2}\sqrt{dm}+\frac{8d}{m^{2}}$

which implies $m\geq\Omega(d)$ as desired.

It remains to show Inequalities (10), (11), (12). We start with the first.
Apply the fingerprinting lemma to the function corresponding to the $j^{th}$
coordinate of the output of $\mathcal{A}$, when run on the $j^{th}$ column of
the input $S$ with all other columns set to any fixed values. Then, we get
that

$\displaystyle\mathbb{E}_{p_{j}\sim[-1,1],S^{j}\sim
Rad(p_{j})^{m}}[\mathcal{A}^{j}(S;r)\sum_{i}(S^{j}_{i}-p_{j})+2|\mathcal{A}^{j}(S;r)-\mu_{j}|]\geq\frac{1}{3},$

where $\mu_{j}$ is the empirical average of the $j^{th}$ column of the
dataset. Since this is true for all fixed coins of the algorithm and fixed
values of the other columns, by the law of total expectation, it is also true
for random coin tosses and any distribution over the values of the other
columns, and we get that

$\displaystyle\mathbb{E}_{p,S\sim
D_{p}^{m},\mathcal{A}}[\sum_{j}\mathcal{A}^{j}(S)\sum_{i}(S^{j}_{i}-p_{j})+2|\mathcal{A}^{j}(S)-\mu_{j}|]$
$\displaystyle=\mathbb{E}[Z]+2\mathbb{E}[\sum_{j}|\mathcal{A}^{j}(S)-\mu_{j}|]\geq\frac{d}{3}$

where we have used that $S$ is drawn from a product distribution. It is
therefore enough to argue that
$\mathbb{E}[\sum_{j}|\mathcal{A}^{j}(S)-\mu_{j}|]$ is small.

Since $\mathcal{A}$ is $(0.01,0.01)$-accurate, we can say that with
probability at least $0.99$, for all $j\in[d]$,
$|\mathcal{A}^{j}(S)-p_{j}|\leq\frac{1}{100}$. Taking expectation, we get that
$\mathbb{E}[\sum_{j\in[d]}|\mathcal{A}^{j}(S)-p_{j}|]\leq\frac{3d}{100}$. By a
Chernoff bound, we can argue that since $m=\Omega(\log d)$,
$\max_{j}|p_{j}-\mu_{j}|\leq 0.01$ with probability at least $0.99$. By the
triangle inequality, this gives us that
$\mathbb{E}[\sum_{j\in[d]}|\mathcal{A}^{j}(S)-\mu_{j}|]\leq\frac{6d}{100}$.
Since this holds for a fixed product of Rademachers, it also holds when the
expectation of the Rademacher random variables are chosen at random which
proves Equation 10.

Next, we show Equation 11, that $\mathbb{E}[|Z^{\prime}|]$ is small. Towards
this end, first note that $Z^{\prime}$ is a sum of mean $0$ uncorrelated
random variables. To see this, consider random variables
$M=\mathcal{A}^{j}(S)(S^{\prime j}_{i}-p_{j})$ and $N=A^{j}(S)(S^{\prime
j}_{i^{\prime}}-p_{j})$ for indices $i\neq i^{\prime}$. We claim that
$\mathbb{E}[M]=\mathbb{E}[N]=0$. This is by the following sequence of
inequalities (we prove this for $M$, the same argument holds for $N$).

$\displaystyle\mathbb{E}[M]$
$\displaystyle=\mathbb{E}_{p}\mathbb{E}_{S,S^{\prime},\mathcal{A}}[M\mid p]$
$\displaystyle=\mathbb{E}_{p}\mathbb{E}_{S,S^{\prime},\mathcal{A}}[\mathcal{A}^{j}(S)(S^{\prime
j}_{i}-p_{j})\mid p]$
$\displaystyle=\mathbb{E}_{p}\Big{[}\mathbb{E}_{S,S^{\prime},\mathcal{A}}[\mathcal{A}^{j}(S)\mid
p]\text{ }\mathbb{E}_{S,S^{\prime},\mathcal{A}}[(S^{\prime j}_{i}-p_{j})\mid
p]\Big{]}=0,$

where the last equality follows because conditioned on the vector $p$, the
expectation of the Rademacher $S^{j}_{i}$ is exactly equal to $p_{j}$. Hence,
by linearity of expectation, we get that the expectation of $Z^{\prime}$ is
also $0$.

Next, we show that $M$ and $N$ are uncorrelated. First, conditioning on $p$ we
can write

$\displaystyle\mathbb{E}_{p,S,S^{\prime},\mathcal{A}}[MN]$
$\displaystyle=\mathbb{E}_{p}\mathbb{E}_{S,S^{\prime},\mathcal{A}}[MN\mid p]$
$\displaystyle=\mathbb{E}_{p}\Big{[}\mathbb{E}_{S,S^{\prime},\mathcal{A}}[\mathcal{A}^{j}(S)^{2}\mid
p]\text{ }\mathbb{E}_{S,S^{\prime},\mathcal{A}}[(S^{\prime
j}_{i}-p_{j})(S^{\prime j}_{i^{\prime}}-p_{j})\mid p]\Big{]}$

since $S$ and $S^{\prime}$ are independent after conditioning. Since this is
also the case for $(S^{\prime j}_{i}-p_{j})$ and $(S^{\prime
j}_{i^{\prime}}-p_{j})$ we have

$\mathbb{E}[(S^{\prime j}_{i}-p_{j})(S^{\prime j}_{i^{\prime}}-p_{j})\mid
p]=\mathbb{E}[(S^{\prime j}_{i}-p_{j})\mid p]\text{ }\mathbb{E}[(S^{\prime
j}_{i^{\prime}}-p_{j})\mid p]=0.$

Since we have already seen that $\mathbb{E}[M]\mathbb{E}[N]=0$ (since
$\mathbb{E}[M]=0$), this implies that $M$ and $N$ are uncorrelated as desired.

Now assuming without loss of generality that $\mathcal{A}$ outputs values
between $[-1,1]$ (rounding inputs to this range only improves the accuracy and
doesn’t affect perfect generalization, which is robust to post-processing), we
have that

$\displaystyle\mathbb{E}^{2}[|Z^{\prime}|]$
$\displaystyle=\mathbb{E}_{p,S,S^{\prime},\mathcal{A}}^{2}\Big{[}\Big{|}\sum_{j\in[d]}\mathcal{A}^{j}(S)\sum_{i}(S^{\prime
j}_{i}-p_{j})\Big{|}\Big{]}$ $\displaystyle(\text{$S$ and $S^{\prime}$ are
i.i.d})$
$\displaystyle\leq\mathbb{E}_{p,S,S^{\prime},\mathcal{A}}\Big{[}\Big{(}\sum_{j\in[d]}\mathcal{A}^{j}(S)\sum_{i}(S^{\prime
j}_{i}-p_{j})\Big{)}^{2}\Big{]}$ $\displaystyle(\text{Jensen's Inequality})$
$\displaystyle=Var(Z^{\prime}).$ $\displaystyle(\mathbb{E}[Z^{\prime}]=0)$

Since $Z^{\prime}$ is a sum of uncorrelated random variables and
$\mathcal{A}^{j}(S)^{2}\leq 1$, we then get

$\displaystyle Var(Z^{\prime})$
$\displaystyle=\sum_{j}\sum_{i}Var(\mathcal{A}^{j}(S)(S^{\prime
j}_{i}-p_{j}))$ $\displaystyle\leq\sum_{j}\sum_{i}\mathbb{E}[(S^{\prime
j}_{i}-p_{j})^{2}]$ $\displaystyle\leq 4dm$

as desired.

It is left to show Equation 12. Let $Z_{p}$ be the random variable $Z$
conditioned on fixed $p$ (and likewise for $Z^{\prime}$). Let
$Z_{p,S,S^{\prime}}$ be the random variable $Z$ conditioned on fixed $p$, $S$
and $S^{\prime}$ (and likewise for $Z^{\prime}$). If $A$ is perfectly
generalizing, then by Lemma 3.5 and Lemma 2.5, for all fixed $p$, with
probability at least $1-\frac{1}{m^{3}}$ over the draw of $S,S^{\prime}$, we
have that $Z_{p,S,S^{\prime}}$ and $Z^{\prime}_{p,S,S^{\prime}}$ are
distributionally close, as are $|Z_{p,S,S^{\prime}}|$ and
$|Z^{\prime}_{p,S,S^{\prime}}|$. For any fixed $p$, let $E$ be the event that
$|Z_{p,S,S^{\prime}}|\approx_{2,\frac{3}{m^{3}}}|Z^{\prime}_{p,S,S^{\prime}}|$,
where the randomness in $E$ comes from the randomness of sampling $S$ and
$S^{\prime}$. Then, by the guarantee of perfect generalization, we have that
for all fixed $p$, $E$ occurs with probability at least $1-\frac{1}{m^{3}}$
and for any fixed $p$ we can write:

$\displaystyle\mathbb{E}[|Z_{p}|]=\mathbb{E}_{S,A}[\Big{|}\sum_{j\in[d]}\mathcal{A}^{j}(S)\sum_{i}(S^{j}_{i}-p_{j})\Big{|}]$
$\displaystyle=\int_{0}^{2dm}\mathbf{Pr}[|Z_{p}|>z]dz$
$\displaystyle=\int_{0}^{2dm}\left[\mathbf{Pr}[|Z_{p}|>z\mid
E]\mathbf{Pr}[E]+\mathbf{Pr}[|Z_{p}|>z\mid\overline{E}]\mathbf{Pr}[\overline{E})\right]dz$
$\displaystyle\leq\int_{0}^{2dm}(e^{2}\mathbf{Pr}[|Z^{\prime}_{p}|>z\mid
E]+\frac{3}{m^{3}})\mathbf{Pr}[E]+\mathbf{Pr}[\overline{E}]dz$
$\displaystyle\leq\int_{0}^{2dm}e^{2}\mathbf{Pr}[|Z^{\prime}_{p}|>z\mid
E]\mathbf{Pr}[E]dz+\int_{0}^{2dm}\left[\frac{3}{m^{3}}+\mathbf{Pr}[\overline{E}]\right]dz$
$\displaystyle\leq\int_{0}^{2dm}e^{2}\mathbf{Pr}[|Z^{\prime}_{p}|>z]dz+\int_{0}^{2dm}\left[\frac{3}{m^{3}}+\frac{1}{m^{3}}\right]dz$
$\displaystyle=e^{2}\mathbb{E}_{S,S^{\prime},\mathcal{A}}[|Z^{\prime}_{p}|]+\frac{8d}{m^{2}},$

where the first inequality follows since $|Z_{p}|$ and $|Z^{\prime}_{p}|$ are
distributionally close conditioned on $E$, the second inequality is by the
fact that $\mathbf{Pr}(E)\leq 1$, and the third since $\overline{E}$
corresponds to the probability of failure in the definition of perfect
generalization.

Finally taking expectation with respect to $p$, we get that

$\mathbb{E}[|Z|]\leq e^{2}\mathbb{E}[|Z^{\prime}|]+\frac{8d}{m^{2}}$

as desired. ∎

Now, we are ready to prove the lower bound for replicable algorithms.

###### Proof of Theorem 5.3.

Let $m$ be larger than an absolute constant $K$, without loss of
generality.121212We will show under this condition that $m=\tilde{\Omega}(d)$.
Any algorithm taking fewer than $K$ samples implies one taking between $K$ and
$\tilde{O}(d)$ samples, which would give a contradiction. By Claim 2.12, we
have that $\mathcal{A}$ is $(0.01,0.01)$-replicable and
$(0.01,0.001)$-accurate when given $m$ samples. Consider any sufficiently
small $\gamma>0$, and sufficiently large constant $c>0$. Applying Theorem
2.13, we get that there is a $\frac{1}{c\log(1/\gamma)}$-replicable and
$(0.01,0.008+\frac{1}{\log(1/\gamma)})=(0.01,0.01)$-accurate algorithm
$\mathcal{A^{\prime}}$ for one-way marginals over $d$ coordinates, which takes
$O\left(m\log^{2}(1/\gamma)\right)$ samples.

Next, we give a way of replicably amplifying the failure probability to
$\gamma$. We run the algorithm $\mathcal{A^{\prime}}$ $k=20\log(1/\gamma)$
times on different samples, and take the coordinate-wise median of the
outputs. Observe that for each coordinate, if more than half the values in
that coordinate are within $0.01$ of the true bias, then the median is
correct. Consider the probability that more than half the output values in a
coordinate are not within $0.01$ of the true bias. By a Chernoff bound, we
have that the number of outputs which are within $0.01$ of the true
expectation in $l_{\infty}$ norm are more than $0.5k$ with probability at
least $1-\gamma^{2}$, which guarantees that we get a
$(0.01,\gamma^{2})$-accurate algorithm for one-way marginals. Using
composition of replicability, we have that the resulting algorithm is
$(0.01,0.01)$-replicable and takes $O\left(m\log^{3}(1/\gamma)\right)$
samples.

Consider any sufficiently small $\delta>0$. By Theorem 3.19, we have that
there is a $(2\delta,1,2\delta)$-PG algorithm with failure probability at most
$\delta+\gamma\log(1/\delta)$ when given
$m^{\prime}=O(m\log^{3}(1/\gamma)\text{polylog}(1/\delta))$ samples. Setting
$\gamma=\frac{0.005}{\log 1/\delta}$, we get that that for sufficiently small
$\delta>0$, there is a $(2\delta,1,2\delta)$-PG algorithm with failure
probability at most $\delta+0.005$ (i.e. $(0.01,\delta+0.005)$-accurate), when
given $m^{\prime}=O(m\cdot\text{polylog}(1/\delta))$ samples. Setting
$\delta=\frac{1}{2m^{\prime 3}}$ and simplifying, we get that
$m^{\prime}=Cm\cdot\text{polylog}(m)$ for some constant $C$. Then, since
$m^{\prime}>m$ is larger than $K$, we get that $\delta$ is smaller than
$\frac{1}{K}$ and setting $K$ sufficiently large gives us a
$(0.01,0.01)$-accurate algorithm with $m^{\prime}$ samples.

Now, using the lower bound for perfect generalization in Theorem 5.5, we get
that $m^{\prime}=\Omega(d)$, which gives us that $m=\tilde{\Omega}(d)$,
completing the proof. ∎

###  5.2 Quadratic separation: Agnostic Learning

In this section, we prove a lower bound for agnostic learning (See Section 2.4
for the definition of agnostic learning) under the constraint of
replicability.

######  Theorem 5.6.

Fix sufficiently large $d>0$ and a hypothesis class $H$ with VC dimension $d$.
Any $(0.01,0.001)$-accurate, $0.0001$-replicable agnostic learner
$\mathcal{A}$ for $H$ requires at least $\tilde{\Omega}(d^{2})$ examples.

The key idea is that we will reduce a variant of the one-way marginals problem
over $d$ coordinates to the problem of agnostically learning any hypothesis
class with VC dimension $d$ (with quadratically more samples). The variant we
consider loosely corresponds to predicting the signs of the biases of the
product distribution. We show that this is possible using an agnostic learner
as a subroutine. We start by defining this problem more precisely.

####  5.2.1 Sign-One-Way Marginals

######  Definition 5.7.

Consider a product of $d$ Rademacher distributions with expectations
$p=(p_{1},\dots,p_{d})$. A vector $v\in[-1,1]^{d}$ is said to be an
$\alpha$-accurate solution to the sign-one-way marginals problem for this
distribution if
$\frac{1}{d}\sum_{j=1}^{d}v_{j}p_{j}\geq\frac{1}{d}\sum_{j=1}^{d}|p_{j}|-\alpha$.

Observe that if every $p_{j}$ is either $-1$ or $1$, an accurate solution
requires the $v_{j}$’s to do a very good job of predicting the signs on
average. On the other hand, if the $p_{j}$ values are all $0$, then every
value of $v$ is a $0$-accurate solution. Thus, this definition of error scales
depending on how biased the expectation is to either $1$ or $-1$, penalizing
solutions more when they do a poor job of predicting heavily biased
coordinates. (Indeed, we’d expect biased coordinates to be easier to predict,
so it makes sense to penalize solutions more on these coordinates.) Now, we
are ready to define the accuracy of an algorithm for the sign-one-way
marginals problem.

######  Definition 5.8.

Let $C$ be the class of products of $d$ Rademacher random variables. We say
that an algorithm $\mathcal{A}:\\{\\{-1,1\\}^{d}\\}^{m}\to[-1,1]^{d}$
$(\alpha,\beta)$-accurately solves the sign-one-way marginals problem over
class $C$ if for all fixed distributions $D$ in $C$, with probability at least
$1-\beta$ over the randomness of the examples it obtains from $D$ and the
internal randomness of the algorithm, it outputs an $\alpha$-accurate vector
$v$ for $D$.

####  5.2.2 Solving Sign-One-Way Marginals using Agnostic Learning

Our reduction in Algorithm 9 shows how to use an agnostic learner
$\mathcal{A}_{ag}$ for any class $H$ of VC dimension $d$ to construct an
algorithm $\mathcal{A}$ for the sign-one-way marginals problem.

The main idea of the algorithm is as follows. Fix a distribution $D$ that is a
product of Rademachers and let its expectation be $p=(p_{1},\dots,p_{d})$.
Consider a shattered set $x_{1},\dots,x_{d}$ for hypothesis class $H$.
Consider a distribution $D^{\prime}$ corresponding to sampling a uniformly
random point $x_{j}$ from the shattered set and then sampling a label in
$(-1,1)$ from a Rademacher with expectation $p_{j}$. Note that given a sample
$S$ of $d$ independently drawn examples from $D$, we can create a dataset
$S_{ag}$ of size roughly $d^{2}$ that looks like an i.i.d. sample from
$D^{\prime}$, by sampling a uniformly random $x_{j}$ and labeling it with a
new unused entry from coordinate $j$ of $S$ (we won’t run out of entries with
high probability). Now, note that since the set $x_{1},\dots,x_{d}$ is
shattered by $H$, there is a hypothesis $h$ in $H$ that outputs
$\operatorname{sign}(p_{j})$ on input $x_{j}$ (such a hypothesis also achieves
lowest possible error on $D^{\prime}$ among hypotheses in $H$). If the
agnostic learner is accurate when given $d^{2}$ samples, then the function $f$
it outputs is a good approximation to $h$ and as a result $f(x_{j})$ is also
likely to be an accurate prediction of the sign of $p_{j}$. Hence, function
$f$ can be used to obtain an accurate solution to the sign-one-way marginals
problem.

1 Input: Sample access to a product distribution $D$ over $\\{-1,1\\}^{d}$,
agnostic learner $\mathcal{A}_{ag}$ for hypothesis class $H$ with VC dimension
$d$

Output: Estimated biases $(v_{1},\dots,v_{d}).$

1: Draw $\frac{d}{\log^{c}d}$ i.i.d. examples from $D$ for some $c>0$. Call
the corresponding sample $S_{inp}$.

2: Let $x_{1},\dots,x_{d}$ be a shattered set of points for $H$. Let $U_{d}$
be the uniform distribution over $x_{1},\dots,x_{d}$.

3: Draw $m=\frac{d^{2}}{100\log^{2c}d}$ examples $S_{j}$ from $U_{d}$. Call
the sample $S_{ag}$. If any element $x_{i}$ occurs more than
$\frac{d}{\log^{c}d}$ times, then output $(1,\dots,1)$, else move to the next
step.

4: For each example $S_{j}$, label it with a new entry from coordinate $j$ of
the input sample $S_{inp}$. Call the labeled sample $S_{ag,lab}$.

5: Run agnostic learner $\mathcal{A}_{ag}$ on the labeled sample $S_{ag,lab}$.
Let the output function be $f$.

6: return $(f(x_{1}),f(x_{2}),\dots,f(x_{d}))$.

Algorithm 9 Algorithm $\mathcal{A}$ for sign-one-way marginals

######  Theorem 5.9.

Fix sufficiently large $d>0$. Let $\mathcal{A}_{ag}$ be a
$(0.01,0.001)$-accurate, $0.0001$-replicable agnostic learner for a hypothesis
class $H$ with VC dimension $d$. Then algorithm $\mathcal{A}$ is a
$(0.02,0.002)$-accurate, $0.0003$-replicable algorithm for the sign-one-way
marginals problem over $d$ coordinates.

###### Proof.

Let $D$ be a Rademacher distribution with expectation $(p_{1},\dots,p_{d})$.
Define a distribution $D_{ideal}$ over
$\\{x_{1},\dots,x_{d}\\}\times\\{-1,1\\}$ as follows. First, uniformly draw
$s\in\\{x_{1},\dots,x_{d}\\}$. Then, if $s=x_{j}$, draw $y$ from a Rademacher
with expectation $p_{j}$. Let $D_{ideal}$ be the distribution of the random
variable $(s,y)$ obtained using this procedure.

First, we observe that by a Chernoff bound and union bound, the probability
that any element $x_{i}$ occurs more than $\frac{d}{\log^{c}d}$ times in
$S_{ag}$ (where $S_{ag}$ is sampled as described in Step 3) is exponentially
small in $d$ (hence less than $0.01$ for sufficiently large $d$). Call this
bad event $E$.

Next, consider the following method for sampling a dataset $S_{ideal}$ of
$\frac{d}{100\log^{2c}d}$ i.i.d. samples from $D_{ideal}$: first draw
$\ell=\frac{d}{100\log^{2c}d}$ i.i.d. examples $s_{i}\sim U_{d}$ and then for
each of them, if the value obtained is $x_{j}$, sample $y_{j}\sim Rad(p_{j})$.
Consider the event $E_{ideal}$ that the number of occurrences of any example
$x_{i}$ is larger than $\frac{d}{\log^{c}d}$. The probability of this event is
exactly equal to $\mathbf{Pr}[E]$. Notice that the distribution of
$S_{ag,lab}$ is identical to the distribution of $S_{ideal}$ conditioned on
event $\overline{E_{ideal}}$. For any distribution $D^{\prime}$ and event
$\overline{E}$, a simple calculation shows
$d_{\mathrm{T}V}(D^{\prime},D^{\prime}|_{\overline{E}})\leq\mathbf{Pr}[E]$.
Hence, we get that the total variation distance between the distribution of
$S_{ideal}$ conditioned on event $\overline{E_{ideal}}$ and the distribution
of $S_{ideal}$ is at most $0.0001$ for sufficiently large $d$.

Now, we know that with probability at least $0.999$ over the coins of the
algorithm and the sample, the agnostic learner produces an output that is
accurate with respect to its input sample. Now, by the data-processing
inequality for total variation distance, we have that
$d_{\mathrm{T}V}(\mathcal{A}_{ag}(S_{ideal}),\mathcal{A}_{ag}(S_{ag,lab}))\leq
0.0001$. Consider the distribution $D_{ideal}$ and the subset $O$ of
$0.01$-accurate functions w.r.t. the best function in the class $H$ (i.e. the
function that minimizes $\mathbf{Pr}_{(x,y)\in D_{ideal}}[h(x)\neq y]$) . By
the definition of total variation distance, we have that the probability that
learner $\mathcal{A}_{ag}$ produces outputs in this subset $O$ on seeing
$S_{ag,lab}$ is within $0.0001$ of the probability that $\mathcal{A}_{ag}$
produces outputs in this subset $O$ on seeing $S_{ideal}$. Since the latter
happens with probability at least $0.999$, we have that with probability at
least $0.9989$, the agnostic learner is $0.01$-accurate when fed the sample
$S_{ag,lab}$. This implies by the definition of the accuracy guarantee that
with probability at least $0.9989$ over the randomness of the learner
$\mathcal{A}_{ag}$ and sample $S_{ag,lab}$, that

$\displaystyle\mathbf{Pr}_{(x,y)\sim D_{ideal}}[f(x)\neq y]\leq\inf_{h\in
H}\mathbf{Pr}_{(x,y)\sim D_{ideal}}[h(x)\neq y]+0.01,$

where $f$ is the output function of the agnostic learner. For
$x\in\\{x_{1},\dots,x_{d}\\}$, let $p_{x}$ be $p_{j}$ if $x=x_{j}$. Observe
that the function that predicts $\operatorname{sign}(p_{x})$ achieves the
infimum on the right hand side of the above equation.

Now, using the fact that expectation of an indicator is the probability of the
indicated event, and that $\mathbbm{1}[a\neq b]=\frac{1-ab}{2}$ when $a$ and
$b$ are in $\\{-1,1\\}$, we get that with probability at least $0.9989$ over
the randomness of the learner $\mathcal{A}_{ag}$ and sample $S_{ag,lab}$,

$\displaystyle\mathbb{E}_{(x,y)\sim D_{ideal}}[\mathbbm{1}[f(x)\neq
y]]\leq\inf_{h\in H}\mathbb{E}_{(x,y)\sim D_{ideal}}[\mathbbm{1}[h(x)\neq
y]]+0.01$ $\displaystyle\implies$ $\displaystyle\mathbb{E}_{(x,y)\sim
D_{ideal}}\left[\frac{1-f(x)y}{2}\right]\leq\inf_{h\in H}\mathbb{E}_{(x,y)\sim
D_{ideal}}\left[\frac{1-h(x)y}{2}\right]+0.01$ $\displaystyle\implies$
$\displaystyle\mathbb{E}_{(x,y)\sim
D_{ideal}}\left[\frac{1-f(x)y}{2}\right]\leq\mathbb{E}_{(x,y)\sim
D_{ideal}}\left[\frac{1-\operatorname{sign}(p_{x})y}{2}\right]+0.01$
$\displaystyle\implies$ $\displaystyle\mathbb{E}_{(x,y)\sim
D_{ideal}}\left[f(x)y\right]\geq\mathbb{E}_{(x,y)\sim
D_{ideal}}\left[\operatorname{sign}(p_{x})y\right]-0.02.$

Now, Algorithm $\mathcal{A}$ calls the agnostic learner except with
probability $0.0001$. Unraveling the expectations, accounting for the fact
that $\mathcal{A}$ outputs $(1,1\dots,1)$ when it doesn’t call the agnostic
learner, and using the fact that the randomness of sample $S_{ag,lab}$ is from
the randomness of the algorithm $\mathcal{A}$ as well as the randomness of
$S_{inp}$, we get that with probability at least $0.998$ over the randomness
of the algorithm $\mathcal{A}$ and input sample, $S_{inp}$, that

$\displaystyle\frac{1}{d}\sum_{j=1}^{d}f(x_{j})p_{j}\geq\frac{1}{d}\sum_{j=1}^{d}\operatorname{sign}(p_{j})p_{j}-0.02,$

proving that $\mathcal{A}$ is a $(0.02,0.002)$-accurate algorithm for sign-
one-way marginals over $d$ coordinates.

Next, we prove that $\mathcal{A}$ inherits the replicability of the agnostic
learner $\mathcal{A}_{ag}$. Consider two sets of independent samples
$S_{inp,1}$ and $S_{inp,2}$. Consider any set of random coins $r$ drawn for
algorithm $\mathcal{A}$. Note that when the coins dictate that when some point
in the shattered set occurs too many times, the algorithm always outputs
$(1,\dots,1)$. Recall that this is event $E$, which we previously showed
occurs with probability at most $0.0001$. Hence, in this case
$\mathcal{A}(S_{inp,1};r)=\mathcal{A}(S_{inp,2};r)$ with probability $1$.
Hence, it is sufficient to consider coins such that every point in the
shattered set occurs fewer than $\frac{d}{\log^{2c}d}$ times in the sample
$S_{ag}$. Now, as argued previously, the total variation distance between the
distribution of $S_{ag,lab}$ (call it $D_{ag}$) and the same number of i.i.d.
samples from $D_{ideal}$ is at most $0.0001$ for sufficiently large $d$. Thus,
we have that the probability of any event changes by at most $0.0002$ under
samples $S_{ag,lab},S^{\prime}_{ag,lab}\sim D_{ideal}^{m}$ versus samples
$S_{ag,lab},S^{\prime}_{ag,lab}\sim D_{ag}^{m}$. This allows us to conclude
that

$\displaystyle\mathbf{Pr}_{S_{inp,1},S_{inp,2}\sim D^{m},r}$
$\displaystyle[\mathcal{A}(S_{inp,1};r)=\mathcal{A}(S_{inp,2};r)]$
$\displaystyle\geq\mathbf{Pr}_{S_{inp,1},S_{inp,2}\sim
D^{m},r}[\mathcal{A}(S_{inp,1};r)=\mathcal{A}(S_{inp,2};r)\mid\overline{E}]$
$\displaystyle\geq\mathbf{Pr}_{S_{ag,lab},S^{\prime}_{ag,lab}\sim
D_{ag},r_{ag}}[\mathcal{A}_{ag}(S_{ag,lab};r_{ag})=\mathcal{A}_{ag}(S^{\prime}_{ag,lab};r_{ag})]$
$\displaystyle\geq\mathbf{Pr}_{S_{ag,lab},S^{\prime}_{ag,lab}\sim
D_{ideal}^{m},r_{ag}}[\mathcal{A}(S_{ag,lab};r_{ag})=\mathcal{A}(S^{\prime}_{ag,lab};r_{ag})]-0.0002$
$\displaystyle\geq 0.9999-0.0002=0.9997.$

Hence, we have proved that $\mathcal{A}$ is $0.0005$-replicable. ∎

####  5.2.3 Lower Bound for Sign-One-Way Marginals

In this section, we show that accurately and replicably solving the sign-one-
way marginals problem over $d$ coordinates requires a number of samples that
is nearly linear in $d$. We will use a variant of the fingerprinting method
used to prove the lower bound for the one-way marginals problem for perfectly
generalizing algorithms, and then extend this to a lower bound for replicable
algorithms. This argument is similar to that used to prove the lower bound for
the one-way marginals problem (Theorem 5.5), except that the notion of
accuracy is different, and so we use a different version of the fingerprinting
lemma, given below.

######  Lemma 5.10 ([28], Lemma A.1 and A.2).

Let $f$ be a function from $\\{-1,1\\}^{m}\to\mathcal{R}$. Let $p$ be a
uniformly random variable between $-1$ and $1$, and $\vec{x}$ be a random
vector of length $m$, consisting of i.i.d. Rademacher random variables with
expectation $p$.

Then,

$\displaystyle\mathbb{E}_{p,\vec{x}}[f(\vec{x})\sum_{i=1}^{m}(x_{i}-p)]=\mathbb{E}_{p}[2pg(p)]$

where $g(p)=\mathbb{E}_{\vec{x}\sim p}[f(\vec{x})]$.

######  Theorem 5.11.

Fix any $m>0$, sufficiently large $d>0$. Let $\mathcal{A}$ be a
$(\frac{1}{m^{3}},1,\frac{1}{m^{3}})$-perfectly generalizing,
$(0.05,0.05)$-accurate algorithm for the sign-one-way marginals problem over
$d$ coordinates using $m$ samples that always outputs a vector in
$[-1,1]^{d}$. Then, $m=\Omega(d)$.

###### Proof.

Without loss of generality, let $m$ be larger than a constant $K$.131313We
will show under this condition that $m=\Omega(d)$. Any algorithm on $\leq K$
samples implies one taking between $K$ and $O(d)$ samples, which would give a
contradiction. Let $S$ be the input dataset to the algorithm $\mathcal{A}$.
Following the framework in Theorem 5.5, we will first argue the expected
correlation of our algorithm and its input is large:

$\sum_{j=1}^{d}\mathbb{E}_{p,\mathcal{A},S\sim
D_{p}^{m}}[\mathcal{A}^{j}(S)\sum_{i=1}^{m}(S^{j}_{i}-p_{j})]\geq 0.35d.$

To see this, observe that by the accuracy of the algorithm, for any fixed
distribution $D_{p}$ that is a product of Rademachers with expectation
$p=(p_{1},\dots,p_{d})$, we have that we have that with probability at least
$0.95$ over the randomness of the algorithm $\mathcal{A}$ and its input
sample,

$\displaystyle\frac{1}{d}\sum_{j=1}^{d}v_{j}p_{j}\geq\frac{1}{d}\sum_{j=1}^{d}\operatorname{sign}(p_{j})p_{j}-0.05,$

where $v$ is the vector output by the algorithm.

Now, taking expectation over the randomness of the algorithm $\mathcal{A}$ and
the input sample $S$, we get that

$\displaystyle\mathbb{E}_{\mathcal{A},S\sim
D_{p}^{m}}\left[\frac{1}{d}\sum_{j=1}^{d}\mathcal{A}^{j}(S)p_{j}\right]\geq
0.95\left[\frac{1}{d}\sum_{j=1}^{d}|p_{j}|-0.05\right]-0.05,$

which implies that

$\displaystyle\mathbb{E}_{\mathcal{A},S\sim
D_{p}^{m}}\left[\frac{1}{d}\sum_{j=1}^{d}\mathcal{A}^{j}(S)p_{j}\right]\geq\frac{1}{d}\sum_{j=1}^{d}|p_{j}|-0.15,$

Now, consider each coordinate of expectation vector $p$ drawn uniformly from
$[-1,1]$. Then, we have that conditioned on any fixed $p$, the above equation
holds. Hence, using the law of total expectation, we get that

$\displaystyle\mathbb{E}_{p,\mathcal{A},S\sim
D_{p}^{m}}\left[\sum_{j=1}^{d}\mathcal{A}^{j}(S)p_{j}\right]\geq\mathbb{E}_{p}\left[\sum_{j=1}^{d}|p_{j}|\right]-0.15d$
(13) $\displaystyle\implies$
$\displaystyle\sum_{j=1}^{d}\mathbb{E}_{p,\mathcal{A},S\sim
D_{p}^{m}}\left[\mathcal{A}^{j}(S)p_{j}\right]\geq\sum_{j=1}^{d}\mathbb{E}_{p_{j}\sim[-1,1]}\left[|p_{j}|\right]-0.15d=0.35d,$
(14)

where we have used the fact that
$\mathbb{E}_{p_{j}\sim[-1,1]}[|p_{j}|]=\frac{1}{2}$. Now, fix a coordinate
$j\in[d]$. For any fixed internal randomness $r$ of algorithm $\mathcal{A}$,
and for any values of columns of $S$ that are not the $j^{th}$ column, we get
from Lemma 5.10 applied to the function $f$ corresponding to the algorithm
$\mathcal{A}$ on the complete dataset $S$ with internal randomness $r$, that

$\mathbb{E}_{p_{j},S^{j}\sim
Rad(p_{j})^{m}}\left[\mathcal{A}^{j}(S;r)p_{j}\right]=\mathbb{E}_{p_{j},S^{j}\sim
Rad(p_{j})^{m}}[\mathcal{A}^{j}(S;r)\sum_{i=1}^{m}(S^{j}_{i}-p_{j})].$

Now, since this holds for any fixed values of internal randomness $r$ and for
any values of columns of $S$ that are not the $j^{th}$ column, it holds for
any distribution over the internal randomness $r$ and any distribution over
values of other columns of $S$. Hence, we get that

$\mathbb{E}_{p,\mathcal{A},S\sim
D_{p}^{m}}\left[\mathcal{A}^{j}(S)p_{j}\right]=\mathbb{E}_{p,\mathcal{A},S\sim
D_{p}^{m}}[\mathcal{A}^{j}(S)\sum_{i=1}^{m}(S^{j}_{i}-p_{j})],$

where we have used that $D_{p}$ is a product distribution. Now, summing over
all coordinates $j\in[d]$, we get that

$\displaystyle\sum_{j=1}^{d}\mathbb{E}_{p,\mathcal{A},S\sim
D_{p}^{m}}[\mathcal{A}^{j}(S)\sum_{i=1}^{m}(S^{j}_{i}-p_{j})]=\sum_{j=1}^{d}\mathbb{E}_{p,\mathcal{A},S\sim
D_{p}^{m}}\left[\mathcal{A}^{j}(S)p_{j}\right]\geq 0.35d,$ (15)

where we have used Equation 14.

Now, we can proceed exactly as in the proof of Theorem 5.5 (we repeat high-
level details for completeness; for more details, see that proof).

Let $S^{\prime}$ be another dataset drawn from the same distribution $D_{p}$.
Let $Z=\sum_{j\in[d]}\mathcal{A}^{j}(S)\sum_{i}(S^{j}_{i}-p_{j})$ and
$Z^{\prime}=\sum_{j\in[d]}\mathcal{A}^{j}(S^{\prime})\sum_{i}(S^{j}_{i}-p_{j})$.

First, note that $Z^{\prime}$ is a sum of uncorrelated random variables with
mean $0$ (see the proof of Theorem 5.5 for a proof of this).

We can then prove (as in the proof of Theorem 5.5) that

$\displaystyle\mathbb{E}[|Z^{\prime}|]=\mathbb{E}_{p,\mathcal{A},S,S^{\prime}\sim
D_{p}^{m}}\Big{[}\Big{|}\sum_{j\in[d]}\mathcal{A}^{j}(S^{\prime})\sum_{i}(S^{j}_{i}-p_{j})\Big{|}\Big{]}\leq
2\sqrt{dm},$

Then, we can invoke the perfect generalization guarantee to prove (as in the
proof of Theorem 5.5) that

$\displaystyle\mathbb{E}[|Z|]\leq
e^{2}\mathbb{E}[|Z^{\prime}|]+\frac{8d}{m^{2}},$

Hence, combining the inequality above with equation 15, we get that

$0.35d\leq\mathbb{E}[|Z|]\leq
e^{2}\mathbb{E}[|Z^{\prime}|]+\frac{8d}{m^{2}}\leq
2e^{2}\sqrt{dm}+\frac{8d}{m^{2}}.$

Simplifying, this gives that

$m=\Omega(d).$

∎

Now, we are ready to apply our conversion from replicability to perfect
generalization to prove a similar lower bound for replicable algorithms.

######  Theorem 5.12.

Fix sufficiently large $d>0$. For any $0.0005$-replicable algorithm
$\mathcal{A}$ that is $(0.02,0.002)$-accurate on the sign-one-way marginals
problem over $d$ coordinates with $m$ samples,

$m=\tilde{\Omega}(d).$

###### Proof.

Without loss of generality, let $m$ be larger than a constant $K$.141414We
will show under this condition that $m=\tilde{\Omega}(d)$. Any algorithm on
$\leq K$ samples implies one taking between $K$ and $\tilde{O}(d)$ samples,
which would give a contradiction. By Claim 2.12, we have that $\mathcal{A}$ is
$(0.01,0.05)$-replicable and $(0.02,0.002)$-accurate when given $m$ samples.
Consider any sufficiently small $\gamma>0$. Next, applying Theorem 2.13, we
get that for sufficiently large constant $c>1$, there is a
$\frac{1}{c\log(1/\gamma)}$-replicable and
$(0.01,0.008+\frac{4}{c\log(1/\gamma)})=(0.01,0.01)$-accurate algorithm
$\mathcal{A^{\prime}}$ for sign-one-way marginals over $d$ coordinates, which
takes $O\left(m\log^{2}(1/\gamma)\right)$ samples.

Next, we give a way of replicably amplifying the failure probability to
$\gamma$. We run the algorithm $\mathcal{A}$ for $k=20\log(1/\gamma)$ times on
different samples, and take the mean of the outputs. Using composition of
replicability, we have that the resulting algorithm is $0.0001$-replicable and
takes $O\left(m\log^{3}(1/\gamma)\right)$ samples. Now, we analyze the failure
probability of this algorithm. Let the output vectors of $\mathcal{A}$ on the
$k$ runs be $v^{1},\dots,v^{k}$. We are interested in the quantity
$\frac{1}{d}\sum_{j=1}^{d}\left[|p_{j}|-\frac{p_{j}}{k}\sum_{i=1}^{k}v^{i}_{j}\right]$.
First, we analyze the expectation of this quantity.

$\displaystyle\mathbb{E}\left[\frac{1}{d}\sum_{j=1}^{d}\left[|p_{j}|-\frac{p_{j}}{k}\sum_{i=1}^{k}v^{i}_{j}\right]\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{d}\sum_{j=1}^{d}p_{j}\left[\operatorname{sign}(p_{j})-\frac{1}{k}\sum_{i=1}^{k}v^{i}_{j}\right]\right]$
$\displaystyle=\mathbb{E}\left[\frac{1}{d}\sum_{j=1}^{d}\frac{1}{k}\sum_{i=1}^{k}p_{j}\left[\operatorname{sign}(p_{j})-v^{i}_{j}\right]\right]$
$\displaystyle=\frac{1}{k}\sum_{i=1}^{k}\mathbb{E}\left[\frac{1}{d}\sum_{j=1}^{d}p_{j}\left[\operatorname{sign}(p_{j})-v^{i}_{j}\right]\right]\leq
0.03$

where the last inequality is because the quantity inside the last expectation
is less than $0.02$ with probability at least $0.99$ (and because all the
$v^{i}$ are identically distributed). Next, observe that the quantity
$\frac{1}{k}\sum_{i=1}^{k}\left(\frac{1}{d}\sum_{j=1}^{d}p_{j}\left[\operatorname{sign}(p_{j})-v^{i}_{j}\right]\right)$
is a sum of $k$ independent random variables (since the $i^{th}$ term in the
sum only depends on random variable $v^{i}$) in the interval $[-2,2]$. Hence,
using Hoeffding’s inequality, we have that the probability that the sum is
larger than $0.05$ is less than $\gamma^{2}$.

Now, by Theorem 3.19, we have that there is a $(2\delta,1,2\delta)$-PG
algorithm with failure probability at most $\delta+\gamma\log(1/\delta)$ when
given $m^{\prime}=O(m\log^{3}(1/\gamma)\operatorname{poly}\log(1/\delta))$
samples (where failure in this case means outputting a solution that is not
$0.05$-accurate). Setting $\gamma=\frac{0.005}{\log(1/\delta)}$, we get that
that for sufficiently small $\delta>0$, there is a $(2\delta,1,2\delta)$-PG
algorithm with failure probability at most $\delta+0.005$ (i.e., one that is
$(0.05,\delta+0.005)$-accurate), when given
$m^{\prime}=O(m\cdot\operatorname{poly}\log(1/\delta))$ samples. Setting
$\delta=\frac{1}{2m^{\prime 3}}$ and simplifying, we get that
$m^{\prime}=C\cdot m\cdot\operatorname{poly}\log m$ for some constant $C$.
Hence, since $m^{\prime}>m$ is larger than $K$, we get that $\delta$ is
smaller than $\frac{1}{K}$ and setting $K$ to be sufficiently large, we get a
$(0.05,0.05)$-accurate algorithm with $m^{\prime}$ samples.

Now, using the lower bound for perfect generalization in Theorem 5.11, we get
that $m^{\prime}=\Omega(d)$, which gives us that $m=\tilde{\Omega}(d)$,
completing the proof. ∎

Now, we can use the reduction from sign-one-way marginals to agnostic learning
to obtain the sample complexity lower bound for agnostic learning.

###### Proof of Theorem 5.6.

If there were a $(0.01,0.001)$-accurate, $0.0001$-replicable agnostic learning
algorithm using fewer than $\frac{d^{2}}{100\log^{2c}d}$ (where $c$ is some
sufficiently large constant) samples, then by Theorem 5.9, there would be a
$(0.02,0.002)$-accurate, $0.0005$-replicable algorithm for the sign-one-way
marginals problem over $d$ coordinates taking only $\frac{d}{\log^{c}d}$
samples, which contradicts Theorem 5.12. ∎

We note that our agnostic learning lower bound as stated only holds only for
constant accuracy, and might not give the optimal dependence on the accuracy
parameter $\alpha$ for general $(\alpha,\beta)$-agnostic learning. We leave it
as an open problem to determine the right dependence on $\alpha$.

###  5.3 Closing the Gap: Realizable Learning

Now that we’ve seen natural settings in which our reduction is tight (and
therefore exhibited a quadratic statistical separation between privacy and
replicability), it is reasonable to ask whether there are any settings under
which the reduction is loose, or even where privacy and replicability might
have the same statistical cost. In this section, we’ll show this is indeed the
case for (certain regimes of) a closely related problem: realizable PAC-
learning. In particular, in this section we exhibit a replicable algorithm for
PAC-learning that gives a quadratically improved dependence on the accuracy
and confidence parameters over applying our reduction from privacy (see
Theorem 6.13).

######  Theorem 5.13 (Finite Classes are Replicably Learnable).

Any class $H$ is replicably Agnostic learnable with sample complexity:

$m(\rho,\alpha,\beta)\leq
O\left(\frac{\log^{2}|H|+\log\frac{1}{\rho\beta}}{\alpha^{2}\rho^{2}}\log^{3}\frac{1}{\rho}\right).$

In the realizable setting, the $\alpha$-dependence can be improved to linear:

$m(\rho,\alpha,\beta)\leq
O\left(\frac{\log^{2}|H|+\log\frac{1}{\rho\beta}}{\alpha\rho^{2}}\log^{3}\frac{1}{\rho}\right).$

Theorem 5.13 gives a quadratic improvement over the sample complexity via
reduction from private learning in both confidence and accuracy, and in
particular has the same asymptotic dependence as in private PAC-learning (and
hence avoids any statistical blowup in the setting where $\log|H|$ is thought
of as small). In fact, it’s worth noting the result is tight in these
parameters, as even standard PAC-learning requires the same dependencies.

####  5.3.1 Algorithm

At its core, the algorithm achieving Theorem 5.13 relies on a simple random
thresholding trick. In particular, the idea is roughly to estimate the risk of
each concept in the class $H$ by standard uniform convergence bounds, choose a
random error threshold $v\in[OPT,OPT+\alpha]$, and finally output a random
$f\in H$ with empirical error $err_{S}(f)=\frac{1}{|S|}\sum\limits_{(x,y)\in
S}\mathbf{1}[f(x)\neq y]$ at most $v$. Implementing this strategy requires a
bit more effort, and is achieved formally by the following algorithm.

1

Result: Replicably outputs hypothesis with error at most $OPT+\alpha$

Input: Finite Class $H$, Joint Distribution $D$ over $X\times\\{0,1\\}$
(Sample Access)

Parameters:

  * •

Replicability, Accuracy, Confidence $\rho,\alpha,\beta>0$

  * •

Sample Complexity $m=m(\rho,\alpha,\beta)\leq
O\left(\frac{\log^{2}|H|\log\frac{1}{\rho}+\rho^{2}\log\frac{1}{\beta}}{\alpha^{2}\rho^{4}}\right)$

  * •

Replicability bucket size $\tau\leq O(\frac{\alpha\rho}{\ln|H|})$

Algorithm:

2

  1. 1.

Draw a labeled sample $S\sim D^{m}$ and compute $err_{S}(f)$ for every $f\in
H$.

  2. 2.

Replicably output initialization $v_{\text{init}}\in[OPT,OPT+\alpha/2]$ (see
Algorithm 12)

  3. 3.

Select random threshold
$v\leftarrow_{r}\\{v_{\text{init}}+\frac{3}{2}\tau,v_{\text{init}}+\frac{5}{2}\tau,\ldots,v_{\text{init}}+\alpha/4-\tau/2\\}$

  4. 4.

Randomly order all $f\in H$

return Output the first hypothesis $f$ in the order s.t. $err_{S}(f)\leq v$.

Algorithm 10 (Intermediate) Replicable Learner for Finite Classes

We note that Step 2, estimating OPT, follows essentially the same argument as
the basic replicable statistical query algorithm of [48]. We give the argument
in Appendix A for completeness.

We note that while Algorithm $\mathtt{rFiniteLearner}$ is a replicable
agnostic PAC learner, it is not quite sufficient to prove Theorem 5.13 due to
its poor dependence on $\rho$. We’ll see in the next section how to obtain the
stated parameters by separately amplifying $\mathtt{rFiniteLearner}$ starting
from good constant replicability.

####  5.3.2 Analysis

We’ll start by proving the following weaker bound for our intermediate
learner.

######  Theorem 5.14 (Intermediate Learnability of Finite Classes).

Let $H$ be any finite concept class. Algorithm $\mathtt{rFiniteLearner}$ is a
(proper) agnostic replicable learning algorithm for $H$ with sample
complexity:

$m(\rho,\alpha,\beta)\leq
O\left(\frac{\log^{2}|H|\log(\frac{1}{\rho})+\rho^{2}\log\frac{1}{\beta}}{\alpha^{2}\rho^{4}}\right).$

In the realizable setting, the $(\alpha,\beta)$-dependence can be improved to:

$m(\rho,\alpha,\beta)\leq
O\left(\frac{\log^{2}|H|\log(\frac{1}{\rho})+\rho^{4}\log\frac{1}{\beta}}{\alpha\rho^{4}}\right).$

The main challenge in Theorem 5.14 is proving replicability. (Accuracy and
failure probability are essentially immediate from standard uniform
convergence arguments.) To this end, note that the randomness $r$ used by
$\mathtt{rFiniteLearner}$ is largely broken into three parts: estimating OPT,
choosing a random threshold, and ordering the concepts in $H$. We’ll focus
first on the latter two, where the choice of $v$ restricts $H$ to two subsets
$H_{1}$ and $H_{2}$ (those with empirical error at most $v$), depending on
input samples $S_{1}$ and $S_{2}$. We first appeal to the classical
observation of Broder [27] to argue that as long as the symmetric difference
of $H_{1}$ and $H_{2}$ are small, outputting the first concept from these sets
(according to the random ordering) is a replicable procedure.

######  Observation 5.15.

Let $O(H,r)$ be a random ordering of concept class $H$. Let $\emptyset\subset
H_{1},H_{2}\subseteq H$, and let $f_{1}$ and $f_{2}$ be the first elements of
$H_{1}$ and $H_{2}$ respectively according to $O(H,r)$. Then
$\mathbf{Pr}_{r}[f_{1}\neq f_{2}]=\frac{|H_{1}\Delta H_{2}|}{|H_{1}\cup
H_{2}|}$, where $\Delta$ denotes the symmetric difference.

The key to proving replicability is then to observe that most choices of $v$
induce small symmetric difference between the corresponding $H_{1}$ and
$H_{2}$. Namely, the idea is to observe that for any fixed joint distribution
$D$, intervals

$I_{0}=[OPT,OPT+\tau],\ldots,I_{\alpha/(2\tau)}=[OPT+\alpha/2-\tau,OPT+\alpha/2],$

and corresponding threshold positions $v_{i}=OPT+\frac{(2i+1)}{2}\tau$, the
sets

$H^{(i)}_{1}=\\{h\in H:err_{S_{1}}(h)\leq v_{i}\\},\quad H^{(i)}_{2}=\\{h\in
H:err_{S_{2}}(h)\leq v_{i}\\}$

are close for most choices of $v_{i}$, $S_{1}$, and $S_{2}$. To adjust for the
fact that we don’t know the value of OPT, we will in fact prove something
slightly more general that allows our starting point to range anywhere from
$OPT$ to $OPT+\alpha/2$.

######  Lemma 5.16.

Let $v_{\text{init}}\in[OPT,OPT+\alpha/2]$ and $\tau\leq
O\left(\frac{\alpha\rho^{2}}{\log|H|}\right)$ a parameter that divides
$\alpha/4$. Define the intervals

$I_{0}=[v_{\text{init}},v_{\text{init}}+\tau),\
I_{1}=[v_{\text{init}}+\tau,v_{\text{init}}+2\tau),\ \ldots\ ,\
I_{\frac{\alpha}{4\tau}}=\left[v_{\text{init}}+\frac{1}{4}\alpha-\tau,v_{\text{init}}+\frac{1}{4}\alpha\right]$

and corresponding thresholds $v_{i}=v_{\text{init}}+\frac{(2i+1)}{2}\tau$, and
let

$H^{(i)}_{1}=\\{h\in H:err_{S_{1}}(h)\leq v_{i}\\},\quad H^{(i)}_{2}=\\{h\in
H:err_{S_{2}}(h)\leq v_{i}\\}$

denote the hypotheses with empirical error at most $v_{i}$ across two
independent samples $S_{1}$ and $S_{2}$ of size
$O(\frac{\log\rho^{-1}}{\tau^{2}})$. Then with probability at least
$1-\rho/4$, a uniformly random choice of $i\in[\frac{\alpha}{4\tau}]$
satisfies:

$\frac{|H^{(i)}_{1}\Delta H^{(i)}_{2}|}{|H^{(i)}_{1}\cup
H^{(i)}_{2}|}\leq\rho/4.$

###### Proof.

For convenience of notation, let $|I_{i}|$ denote the number of hypotheses
whose true risk lies in interval $I_{i}$, and $|I_{[i]}|$ the number of
hypotheses in intervals up through $I_{i}$. We call a threshold $v_{i}$ “bad”
if any of the following conditions hold.

  1. 1.

The $i$th interval has too many elements:

$|I_{i}|>\frac{\rho}{30}|I_{[i-1]}|.$

  2. 2.

The number of elements beyond $I_{i}$ increases too quickly:

$\exists j\geq 1:|I_{i+j}|\geq e^{j}|I_{[i-1]}|.$

and “good” otherwise. We will argue the following two claims.

  1. 1.

If $v_{i}$ is a good threshold, then $H^{(i)}_{1}$ and $H^{(i)}_{2}$ are
probably close

$\underset{S_{1},S_{2}}{\mathbf{Pr}}\left[\frac{|H^{(i)}_{1}\Delta
H^{(i)}_{2}|}{|H^{(i)}_{1}\cup H^{(i)}_{2}|}\leq\frac{\rho}{4}\right]\geq
1-\frac{\rho}{8}.$

  2. 2.

At most a $\frac{\rho}{8}$ fraction of thresholds are bad.

Since we pick a threshold uniformly at random, it is good with probability at
least $1-\rho/8$ and a union bound gives the desired result.

It remains to prove the claims. For the first, observe that for any fixed
hypothesis $h$ with true risk $err_{D}(h)\in I_{i+j}$, the probability that
the empirical risk of $h$ is less than $v_{i}$ is at most

$\mathbf{Pr}[err_{S}(h)\leq v_{i}]\leq e^{-\Omega(j^{2}\tau^{2}|S|)}$ (16)

by a Chernoff bound. Let $x_{i}$ denote the variable which counts the number
of hypotheses with true risk beyond $I_{i}$ that cross the threshold $v_{i}$
empirically. If $v_{i}$ is “good,” we can bound $\mathbb{E}[x_{i}]$ by

$\mathbb{E}[x_{i}]\leq|I_{[i-1]}|\sum\limits_{j>0}e^{-\Omega(j^{2}\tau^{2}|S|-j)}\leq\frac{\rho^{2}}{2000}|I_{[i-1]}|$

for our choice of $|S|$. Markov’s inequality then promises

$\mathbf{Pr}\left[x_{i}\geq\frac{\rho}{30}|I_{[i-1]}|\right]\leq\frac{\rho}{64}.$

On the other hand, the probability any hypothesis in $I_{[i-1]}$ crosses
$v_{i}$ is at most $e^{-\Omega(\tau^{2}|S|)}$, so similarly the probability
that more than a $\frac{\rho}{30}$ fraction of such hypotheses cross $v_{i}$
is at most $\frac{\rho}{64}$. Finally, since $v_{i}$ is ‘good,’ $I_{i}$ itself
contributes at most $\frac{\rho}{30}|I_{[i-1]}|$ hypotheses that cross the
threshold in the worst case, so in total we have that with probability at
least $1-\frac{\rho}{32}$, at most $\frac{\rho}{10}|I_{[i-1]}|$ hypotheses
cross the threshold in either direction. Considered over two runs of the
algorithm, this implies that with probability at least $1-\frac{\rho}{16}$,
$|H^{(i)}_{1}\Delta H^{(i)}_{2}|$ cannot be too big

$|H^{(i)}_{1}\Delta H^{(i)}_{2}|\leq\frac{\rho}{5}|I_{[i-1]}|.$

Furthermore, since the probability that more than a $\frac{\rho}{30}$ fraction
of hypotheses in $I_{[i-1]}$ cross $v_{i}$ is at most $\frac{\rho}{64}$, we
also have that $|H^{(i)}_{1}\cup H^{(i)}_{2}|$ cannot be too small:

$|H^{(i)}_{1}\cup H^{(i)}_{2}|\geq\left(1-\frac{\rho}{15}\right)|I_{[i-1]}|$

with probability at least $1-\frac{\rho}{64}$. Thus altogether a union bound
gives

$\underset{S_{1},S_{2}}{\mathbf{Pr}}\left[\frac{|H^{(i)}_{1}\Delta
H^{(i)}_{2}|}{|H^{(i)}_{1}\cup H^{(i)}_{2}|}\leq\frac{\rho}{4}\right]\geq
1-\frac{\rho}{8}$

as desired.

Finally, we need to show that almost all thresholds are good. To see this,
first observe that since $v_{\text{init}}\geq OPT$, $|I_{[i]}|>0$ for all
$i\geq 0$. To count the number of bad thresholds, let $i_{1}\geq 1$ be the
position of the first bad threshold, and $t_{1}$ denote the largest index such
that $i_{1}+t_{1}$ fails a condition. Define $i_{j}$ and $t_{j}$ recursively
as the first bad threshold beyond $i_{j-1}+t_{j-1}$ and its corresponding
latest failure. Observe that by construction, any interval that does not lie
in any $[i_{j}.i_{j}+t_{j}]$ is good, so there are at most $\sum t_{j}$ bad
thresholds.

Let $\ell$ denote the final index of the above greedy process. By definition
of a bad interval, each $t_{j}$ multiplicatively increases the number of total
hypotheses from $I_{[i_{j}]}$ by at least
$\left(1+\frac{\rho}{30}\right)^{t_{j}}$. Since $|I_{0}|\geq 1$ and the total
number of hypotheses is $|H|$ by definition, we may therefore write:

$|H|\geq|I_{[i_{\ell}+t_{\ell}]}|\geq\left(1+\frac{\rho}{30}\right)^{\sum\limits_{j=1}^{\ell}t_{j}}$

and thus that the total number of bad intervals is at most

$\sum_{j=1}^{\ell}t_{j}\leq O\left(\frac{\log(|H|)}{\rho}\right).$

Since we have chosen $\tau$ such that the total number of intervals altogether
is at least $\Omega\left(\frac{\log(|H|)}{\rho^{2}}\right)$, the appropriate
choice of constant gives that at most a $\rho/8$ fraction are bad as desired.
∎

To complete the argument, it is enough to show we can find a good starting
point $v_{\text{init}}$.

######  Lemma 5.17.

There exists a $\rho$-replicable algorithm over
$O\left(\frac{\log(\frac{|H|}{\rho\beta})}{\rho^{2}\alpha^{2}}\right)$ samples
that outputs a good estimate of $OPT$ with high probability:

$\mathbf{Pr}_{r,S}\big{[}\mathcal{A}(S)\in[OPT,OPT+\alpha/2]\big{]}\geq
1-\beta$

Proving this Lemma largely follows from prior techniques but is a bit tedious,
so we leave the proof for Appendix A. With these tools in hand, we are finally
ready to prove Theorem 5.13.

###### Proof of Theorem 5.14.

We start by showing $\mathtt{rFiniteLearner}$ is $\rho$-replicable.
$\mathtt{rFiniteLearner}$ starts by running a replicable subroutine (with
parameters $\rho^{\prime}=\rho/2$ an $\beta^{\prime}=\beta/2$) to find an
estimate for OPT. Using new (independent) randomness, it then selects a
threshold $v_{i}$ and a random ordering over $H$, and outputs the first
hypothesis in $H^{(i)}=\\{h:R_{\text{emp}}(h,S)\leq v_{i}\\}$. By Lemma 5.16
and 5.15, this latter process is $\rho/2$-replicable. By composition of
replicability, the entire algorithm is therefore $\rho$-replicable as desired.

Correctness of $\mathtt{rFiniteLearner}$ follows from standard uniform
convergence type arguments. In particular, by our choice of $|S|$, any
hypothesis with empirical risk at most $OPT+\alpha/2$ has true risk less than
$OPT+\alpha$ with probability at least $1-\beta/2$. Furthermore, as long as
our estimation of $OPT$ is successful (which occurs with probability at least
$1-\beta/2$), we always output such a hypothesis. Thus altogether we output a
hypothesis with true error at most $OPT+\alpha$ with probability at least
$1-\beta$ as desired.

Finally, we need to argue that the dependence on $\alpha$ can be improved to
linear in the realizable setting. Note that in this case, we can simply set
$v_{\text{init}}$ to 0, and ignore the estimation of OPT. The improvement then
follows immediately from noting that when $OPT=0$, a standard Chernoff bound
improves Equation 16 to

$\mathbf{Pr}[err_{S}(h)\leq v_{i}]\leq
e^{-\Omega(\frac{j^{2}\tau|S|}{(i+j)})}\leq
e^{-\Omega(\frac{j^{2}\tau^{2}|S|}{\alpha})}.$

Similarly, only $O(\frac{\log\frac{|H|}{\beta}}{\alpha})$ examples are needed
to ensure hypotheses with $O(\alpha)$ empirical risk have $O(\alpha)$ true
risk with high probability, and the rest of the proof follows as in the
agnostic case. ∎

Finally, we amplify the above to prove Theorem 5.13.

###### Proof of Theorem 5.13.

Our amplification algorithm is a modification of the original technique
introduced in [48], designed to take advantage of the fact that the dependence
on $\beta$ (failure) and $\rho$ (replicability) are highly unbalanced in
learning tasks. Draw $k=O(\log(1/\rho))$ random strings $r_{1},\ldots,r_{k}$,
and consider the distributions $\\{D_{i}\\}_{i=1}^{k}$ generated by running
$\mathtt{rFiniteLearner}(r_{i},S)$ with parameters $\rho^{\prime}=.01$ and
$\beta^{\prime}=\beta\cdot\text{poly}(\rho)$ on a large enough sample $S$. The
idea is to argue that with good probability over the choice of random strings
$r$, at least one of these distributions has an $\Omega(1)$-heavy-hitter
(which is also a good hypothesis with extremely high probability). Roughly
speaking, we can then use the heavy hitters algorithm of [48] across these
distributions to $\rho/2$-replicably output a good hypothesis, and union bound
over all applications to argue correctness of the final output.

Let’s formalize this argument. First, observe since our setting of
$\mathtt{rFiniteLearner}$ is $.01$-replicable, at least $90\%$ of the random
strings have a ‘canonical element,’ i.e. one that appears across at least
$90\%$ of random samples. Call such strings good, and observe that any good
string $r_{i}$ corresponds to a distribution $\mathcal{D}_{i}$ with a
$.9$-heavy-hitter by construction. Over a random choice of $O(\log\rho^{-1})$
such strings, the former guarantee then promises at least one of these strings
is good with probability greater than $1-\rho/4$ and therefore that at least
one distribution in $\\{D_{i}\\}_{i=1}^{k}$ has a $.9$-heavy-hitter. With this
in mind, we now appeal to the heavy-hitter algorithm of [48], which draws
$O(\frac{\log\rho^{-1}}{\rho^{2}})$ samples from a distribution to replicably
output a list of all $\Omega(1)$-heavy-hitters.151515We note the technique
actually outputs a list of some weight close to $c$, but this is largely
irrelevant in our setting where $c$ (and the shift in $c$) are constant. To
make our entire process $\rho$-replicable, we will run the above process for
$\rho^{\prime}=O(\frac{\rho}{\log\rho^{-1}})$. To this end, we draw samples
$S_{1},\ldots,S_{t}$ for $t=O(\frac{\log^{3}\rho^{-1}}{\rho^{2}})$ and
generate $t$ corresponding samples from each $\\{D_{i}\\}_{i=1}^{k}$ (re-using
$S_{j}$ between distributions), which we use to run [48]’s heavy-hitters
algorithm. Union bounding over all applications, this process is
$\rho/4$-replicable, and with probability at least $1-\rho/4$ outputs a non-
empty list of hypotheses. Finally, we break in to one of two cases. If the
result list is indeed non-empty, simply output a random element of the list (a
fully replicable procedure). Otherwise, run $\mathtt{rFiniteLearner}$ on a
fresh random string and sample, and output the result.

Finally, we argue replicability and correctness of the above process. First,
note the output list is non-empty with probability at least $1-\rho/4$, and
two independent samples produce the same list (with fixed randomness) with
probability at least $1-\rho/2$ by replicability of the repeated heavy hitter
process discussed above. Therefore the entire process is $\rho$-replicable as
desired. For correctness, note that we have used at most
$\operatorname{poly}(\rho^{-1})$ instances of $\mathtt{rFiniteLearner}$.
Recall that we set the failure probability of $\mathtt{rFiniteLearner}$ to be
very small, with $\beta^{\prime}=\beta\cdot\text{poly}(\rho^{-1})$. Since each
individual application of $\mathtt{rFiniteLearner}$ fails with probability
less than $\beta^{\prime}$, union bounding over all applications of the
algorithm implies every output hypothesis is ‘good’ (within $\alpha$ of OPT)
with probability at least $1-\beta$. Since we only output hypotheses generated
by this process, the probability of outputting a bad hypothesis is then less
than $\beta$ as desired.

Altogether, the sample complexity of the above algorithm is given by the size
of samples

$t|S_{i}|=O\left(\frac{\log^{3}\rho^{-1}}{\rho^{2}}\cdot\frac{\log^{2}|H|+\log\frac{1}{\rho\beta}}{\alpha^{2}}\right),$

or

$O\left(\frac{\log^{3}\rho^{-1}}{\rho^{2}}\cdot\left(\frac{\log|H|+\log\frac{1}{\rho\beta}}{\alpha}+\log^{2}|H|\right)\right)$

in the realizable case.

∎

##  6 Applications

In this section we take advantage of our reductions between notions of
stability to resolve (or otherwise make progress on) several open problems in
the algorithmic stability literature.

###  6.1 Item-level to User-level Privacy Transformation

The original motivation of introducing the definition of pseudo-global
stability in [42] was to come up with PAC learning algorithms in the example-
rich, user-level privacy setting. In this setting, there are a number of users
with many samples (the regime we will be interested in is when there are a few
users who have enough samples to solve the problem for themselves). The
motivation behind this setting is to leverage the data of example-rich users
to obtain statistical insights without compromising their privacy. Such
statistical analyses could then be released and used widely, even by users who
didn’t have as much data.

The technique of [42] involves coming up with pseudo-globally stable
algorithms for PAC learning, and then having each user run a pseudo-globally
stable algorithm with the same coins. Then, you can privately identify a heavy
hitter among the outputs of the users (such a heavy hitter exists with high
probability because of the property of pseudo-global stability), and since
changing an entire user’s sample will affect only one output, this procedure
will be user-level differentially private. One open question raised in their
paper was whether their techniques could be extended beyond the PAC setting.

Our argument that pseudo-global stability and differential privacy are two
sides of the same coin answers this question in the affirmative, and has the
additional benefit of eliminating the need to cleverly design pseudo-globally
stable (replicable) algorithms. We showed previously that item-level
differentially private algorithms can be compiled into replicable algorithms
with only a quadratic overhead in sample complexity (See Sections 3.2 and
3.3). Hence, our results allow for a general transformation from item-level to
user-level privacy for statistical tasks in the example-rich setting; each
user applies correlated sampling to the same item-level differentially private
algorithm applied to their specific sample, and then a heavy hitter is
identified via differentially private selection.

######  Theorem 6.1.

There are universal constants $c,K>0$ such that the following holds. Let
$\mathcal{T}$ be a statistical task with a finite output space. Given a
$(0.1,\frac{c}{n^{3}})$-item level differentially private algorithm
$\mathcal{A}$ that solves $\mathcal{T}$ using $n$ samples and with failure
probability $\beta$, for every $1\geq\varepsilon,\delta>0$, there exists an
$(\varepsilon,\delta)$-user level differentially private algorithm
$\mathcal{A}_{u}$ that solves $\mathcal{T}$ with failure probability
$O(\beta\log\frac{1}{\beta})$, when given access to the data of $O(\frac{\log
1/\beta}{\varepsilon}\log\frac{\log 1/\beta}{\delta})$ users, each of whom
have at least $Kn^{2}\log(1/\beta)$ examples.

###### Proof.

Firstly, we can amplify the privacy parameters of $\mathcal{A}$ by
subsampling. By Lemma 2.9, the algorithm $\mathcal{A}^{\prime}$ that, given
$m=Kn^{2}$ samples, subsamples $n$ items without replacement and runs
$\mathcal{A}^{\prime}$ on the result is
$(1/\sqrt{Km},cK/m^{2})$-differentially private. Moreover, when run on inputs
consisting of i.i.d. samples from a distribution $D$, the output of
$\mathcal{A}^{\prime}$ is identically distributed to that of $\mathcal{A}$, so
$\mathcal{A}^{\prime}$ also solves $\mathcal{T}$ with $m$ examples and failure
probability $\beta$.

For a sufficiently large constant $K$ and sufficiently small constant $c$,
Corollary 3.18 then implies that $\mathcal{A}^{\prime}$ gives rise to a
$c$-replicable algorithm solving $\mathcal{T}$ with $m$ examples and failure
probability $\beta$.

Now, consider Algorithm 1 adapted to the user-level setting as follows (with
number of users as specified in the theorem): instead of partitioning a
centralized sample (as done in that algorithm), each of the users applies
algorithm $\mathcal{A}^{\prime}$ to their own set of $O(\log(1/\beta))$ i.i.d.
samples (with the same set of $O(\log(1/\beta))$ different coins—this can be
achieved through a common random string that they share). Then, the outputs
are sent to a central server, and
$(\varepsilon^{\prime}=\frac{\varepsilon}{C\log
1/\beta},\delta^{\prime}=\frac{\delta}{2\log 1/\beta})$-DP selection is then
applied to choose a heavy hitter (as discussed in Algorithm 1). Let’s call
this algorithm $\mathcal{A}_{u}$.

The accuracy guarantees proved for Algorithm 1 give us that the failure
probability of this Algorithm $\mathcal{A}_{u}$ is at most $O(\beta\log
1/\beta)$. Hence, we are left to argue privacy. Note that changing a single
user’s sample can change at most $C\log 1/\beta$ outputs to which the
$(\varepsilon^{\prime},\delta^{\prime})$-DP selection algorithm is applied to.
Hence, by group privacy (Lemma 2.8), we have that $\mathcal{A}_{u}$ is
$(\varepsilon^{\prime}\log
1/\beta,\delta^{\prime}\frac{e^{\varepsilon^{\prime}\log
1/\beta}-1}{e^{\varepsilon^{\prime}}-1})$-user level differentially private.
Substituting the value of $\varepsilon^{\prime}$ and $\delta^{\prime}$ then
gives an $(\varepsilon,\delta)$-user level private algorithm. This completes
the proof. ∎

###  6.2 Parameter Amplification for Differential Privacy and Perfect
Generalization

The equivalence between replicability and differential privacy gives us the
first generic amplification theorem for the $\delta$ parameter of approximate
differential privacy for general statistical tasks. Prior to our work, it was
known that the $\varepsilon$ parameter could be amplified algorithmically and
efficiently. That is, using random sampling (Lemma 2.9), one can improve an
$(\varepsilon_{0},\delta_{0})$-differentially private algorithm to a
$(p\varepsilon_{0},p\delta_{0})$-differentially private one with an $O(1/p)$
blowup in the sample complexity. However, this technique is unable to improve
the $\delta$ parameter of such an algorithm asymptotically as a function of
the number of samples $n$, e.g., from $\delta(n)=1/n^{10}$ to
$\delta^{\prime}(n)=\exp(-n^{0.99})$.

The recent characterization of private PAC learnability in terms of
Littlestone dimension [3, 17, 41] implies that such an amplification of
$\delta$ is (at least, in principle) possible for private PAC and agnostic
learning and for private query release. Given a target class $\mathcal{C}$ in
one of these settings, the existence of a
$(\varepsilon=0.1,\delta=O(1/n^{2}\log n))$-differentially private algorithm
using a finite number of samples $n$ implies that $\mathcal{C}$ has some
finite Littlestone dimension $d$. This in turn implies that, for every
$\varepsilon,\delta>0$, there is an $(\varepsilon,\delta)$-differentially
private agnostic PAC learning algorithm for $\mathcal{C}$ using
$\operatorname{poly}(d,1/\varepsilon,\log(1/\delta))$ samples and a private
query release algorithm for $\mathcal{C}$ using
$\operatorname{poly}(2^{2^{d}},1/\varepsilon,\log(1/\delta))$ samples.
Unfortunately, the first part of this argument is non-constructive, and in the
worst-case, leads to a final algorithm using a number of samples that is an
exponential tower in $\Omega(n)$! [17] posed the open question of whether such
amplification could be done algorithmically, even for the special case of
private PAC learning.

Our approach is to first convert a differentially private algorithm with weak
parameters to a replicable one. We may then use the fact that replicable
algorithms can be converted back to differentially private ones with excellent
privacy parameters. Altogether we obtain a constructive amplification theorem
that achieves only a modest blowup in sample complexity, and which applies to
general statistical tasks with finite output spaces.

######  Theorem 6.2.

There is a universal constant $c>0$ such that the following holds. Let
$\mathcal{T}$ be a statistical task with a finite output space. Suppose there
is an $(\varepsilon=0.1,\delta=c/n^{3})$-differentially private algorithm that
solves $\mathcal{T}$ using $n$ samples and with failure probability $\beta$.
Then for every $\varepsilon,\delta>0$, there exists an
$(\varepsilon,\delta)$-differentially private algorithm solving $\mathcal{T}$
using

$O\left(\frac{\log(1/\delta)\log(1/\beta)}{\varepsilon}+\log^{2}(1/\beta)\right)\cdot
n^{2}$

samples and with failure probability $O(\beta\log 1/\beta)$.

###### Proof.

Let $A$ be a $(0.1,c/n^{3})$-differentially private algorithm solving
$\mathcal{T}$ with $n$ samples and failure probability $O(1/\log(1/\beta))$.
By Lemma 2.9, the algorithm $A^{\prime}$ that, given $m=Kn^{2}$ samples,
subsamples $n$ items without replacement and runs $A$ on the result is
$(1/\sqrt{Km},cK/m^{2})$-differentially private. Moreover, when run on inputs
consisting of i.i.d. samples from a distribution $P$, the output of
$A^{\prime}$ is identically distributed to that of $A$, so $A^{\prime}$ also
solves $\mathcal{T}$ with $m$ samples and failure probability $\beta$.

For a sufficiently large constant $K$ and sufficiently small constant $c$,
Corollary 3.18 implies that $A^{\prime}$ gives rise to a $c$-replicable
algorithm solving $\mathcal{T}$ with $m$ samples and failure probability
$\beta$. Applying Theorem 3.1 thus results in an
$(\varepsilon,\delta)$-differentially private algorithm solving $\mathcal{T}$
with

$m\cdot
O\left(\frac{\log(1/\delta)\log(1/\beta)}{\varepsilon}+\log^{2}(1/\beta)\right)$

samples and failure probability $O(\beta\log 1/\beta)$. ∎

We can also show a similar amplification of the parameters for perfect
generalization, indeed, even from one-way perfect generalization to perfect
generalization itself.

######  Theorem 6.3.

There is a universal constant $c>0$ such that the following holds. Let
$\mathcal{T}$ be a statistical task with a finite output space. Suppose there
is an $(\beta^{\prime}=10^{-5},\varepsilon=10^{-5},\delta=10^{-5})$-one-way
perfectly generalizing algorithm that solves $\mathcal{T}$ using $n$ samples
and with failure probability $\beta$. Then for every $\varepsilon,\delta>0$,
there exists an $(\delta,\varepsilon,\delta)$\- perfectly generalizing
algorithm solving $\mathcal{T}$ using

$O\left(n\cdot\frac{\log(1/\varepsilon)\operatorname{poly}\log(1/\delta)}{\varepsilon^{2}}\right)$

samples and with failure probability $O(\delta)+\sqrt{\beta}\log(1/\delta)$.

###### Proof.

Let $A$ be a $(10^{-5},10^{-5},10^{-5})$-perfectly generalizing algorithm
solving $\mathcal{T}$ with $n$ samples and failure probability $\beta$. By
Lemma 3.17, there is a $(0.0001)$-replicable algorithm solving $\mathcal{T}$
with the same failure probability and the same number of samples. By Claim
2.12 and Theorem 3.19, there exists a
$(\delta^{2}/4,\varepsilon,\delta^{2}/4)$-sample perfectly generalizing
algorithm solving $\mathcal{T}$ using
$O(n\cdot\frac{\log(1/\varepsilon)\operatorname{poly}\log(1/\delta)}{\varepsilon^{2}})$
samples with failure probability $O(\delta)+\sqrt{\beta}\log(1/\delta)$. Lemma
3.6 converting sample perfect generalization to perfect generalization gives
the result. ∎

###  6.3 A Realizable-to-Agnostic Reduction for Structured Distributions

One of the main running examples throughout this work (and indeed a focal
point in [48, 42] as well) is the PAC-learning paradigm. Traditionally, PAC-
learning has two main settings, realizable learning (where the adversary must
choose a hypothesis in the class), and the agnostic setting (which allows an
arbitrary adversary). It is a well known fact in the study of traditional
statistical learning that realizable and agnostic learning are equivalent up
to polynomial blowup in sample complexity [74, 12, 45]. Furthermore, an analog
of this fact holds for most supervised paradigms (see e.g. [16, 18, 57, 9, 36,
59, 2]), including privacy [24, 1]. This was originally shown by Beimel,
Nissim, and Stemmer [24], who gave a sample-efficient agnostic-to-realizable
reduction for approximately differentially private PAC-learning. Their result
has since been used extensively (see e.g. [25, 21, 19, 1, 17]), and is often
used to justify focus on the realizable setting.

While certainly impactful, Beimel, Nissim, and Stemmer’s reduction (and later
improvements on the same [1, 17]) are complicated and limited in application.
Like the results that came before them (in the traditional setting), their
techniques rely heavily on uniform convergence, and therefore always incur a
cost in VC dimension of the class (or analogously in $\log|H|$ in many
settings we consider). Such bounds are typically only useful in the
distribution-free setting, where the adversary is free to choose arbitrary
(often strange, combinatorial) distributions over the data that don’t appear
in practice. Outside of such cases, it is typically possible to learn in many
fewer samples than VC dimension would predict (see e.g. [63]), so it is
reasonable to ask whether this efficiency can be generically maintained in the
agnostic setting. Towards this end, Hopkins, Kane, Lovett, and Mahajan [46]
recently gave a more generic reduction independent of VC dimension, but their
techniques do not adapt directly to the private setting, which was left as an
open problem in their work.

We resolve this problem (at least in finite domains) via reduction to and from
replicability: agnostic private learning requires only a small polynomial
blowup over the realizable case that is independent of class-size, even under
arbitrary distributional assumptions. With this in mind, we briefly introduce
the distribution-family variant of the PAC-model, which first appeared
(implicitly) in seminal work of Benedek and Itai [16] on learning under fixed
distributions. We highlight the differences from the standard model below.

######  Definition 6.4 (Distribution-Family Model [16]).

A learning problem is defined by a hypothesis class $H$ and family of
distributions $\boldsymbol{\mathscr{D}}$ over the instance space
$\mathcal{X}$. We say an algorithm $\mathcal{A}$ is an
$(\alpha,\beta)$-accurate Agnostic learner for the hypothesis class
$(H,\mathscr{D})$ if for all distributions $D$ over input, output pairs whose
marginal $\boldsymbol{D_{\mathcal{X}}\in\mathscr{D}}$, $\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]$. When the
adversary is additionally restricted to choosing $D$ s.t. $\inf_{f\in
H}{\mathtt{err}}_{D}(f)=0$, we call the problem realizable.

We give the first private agnostic-to-realizable reduction from the
distribution-family model, and in general the first reduction with no reliance
on uniform convergence or VC dimension.

######  Theorem 6.5.

Let $(H,\mathscr{D})$ be a hypothesis class that is
$(1,\frac{1}{poly(n)})$-privately $(\alpha,0.01)$-PAC learnable in
$n=n(\alpha)$ samples in the realizable setting. Then $(H,\mathscr{D})$ is
$(1,\frac{1}{poly(m)})$-privately $(\alpha,\beta)$-agnostically learnable in

$m(\alpha,\beta)\leq
O\left(\frac{n^{2}\alpha^{2}+\log^{3}(\Pi_{H}(cn^{2}))}{\alpha^{2}}\log\beta^{-1}\log\left(\frac{n\log\beta^{-1}}{\alpha}\right)\right)$

samples for some universal constant $c>0$.

In the statement of Theorem 6.5, $\Pi_{H}(n)$ denotes the growth function of
$(X,H)$. The growth function captures the maximum number of labelings
functions from $H$ can induce on samples of size $n$, and is at most
$n^{O(d)}$ for classes with VC dimension $d$. Moreover, since
$\Pi_{H}(cn^{2})\leq 2^{cn^{2}}$, this means agnostic learning experiences at
most a polynomial blowup over the realizable setting:

######  Corollary 6.6.

Let $(H,\mathscr{D})$ be a hypothesis class that is
$(1,\frac{1}{poly(n)})$-privately $(\alpha,0.01)$-PAC learnable in
$n=n(\alpha)$ samples in the realizable setting. Then $(H,\mathscr{D})$ is
$(1,\frac{1}{poly(m)})$-privately $(\alpha,\beta)$-agnostically learnable in

$m(\alpha,\beta)\leq\tilde{O}\left(\frac{n^{6}\log\beta^{-1}}{\alpha^{2}}\right)$

samples.

At a high level, the proof of this result is (comparatively) simple. Given a