For any set $b\in[n+1]^{m}$, we have that
$\mu^{\text{ins}}_{n,m}(b)=\mu_{n+1,m}(b)$

###### Proof of 6.

Same as that of 2. ∎

####  C.2.2 Lemmas for reflection coupling

We state and prove some results about reflection mapping and couplings.

######  Lemma 1.

Let $P$ and $Q$ be probability distributions over ${\mathbb{R}}^{d}$. Let
$\psi:{\mathbb{R}}^{d}\rightarrow{\mathbb{R}}^{d}$ be a bijection such that
$\phi_{P}(\psi(x))=\phi_{Q}(x)$, $\phi_{P}(\psi^{-1}(x))=\phi_{Q}(x)$ and
$\left|{\det\left(\frac{d\psi(x)}{dx}\right)}\right|=1$, where
$\frac{d\psi(x)}{dx}$ is the Jacobian of the multivariate map $\psi$. Let
$x\sim P$ be a sample from $P$. Let $y=x$ if
$\text{Unif}(0,1)\leq\frac{\phi_{Q}(x)}{\phi_{P}(x)}$, otherwise $y=\psi(x)$.
Then $(x,y)$ is a maximal coupling of $P$ and $Q$.

###### Proof.

We first show that $y$ is a sample from $Q$. Let $E$ be an event in the range
of $Q$. Let accept be the event when $u\sim\text{Unif}(0,1)$,
$u\leq\frac{\phi_{Q}(x)}{\phi_{P}(x)}$. We have,

$\displaystyle\mathbb{P}\left[{y\in E}\right]$
$\displaystyle=\mathbb{P}\left[{y\in
E,\text{accept}}\right]+\mathbb{P}\left[{y\in E,\text{reject}}\right]$
$\displaystyle=\mathbb{E}_{x,u}\left[\mathbb{1}\left\\{{x\in
E}\right\\}\mathbb{1}\left\\{{u\leq\frac{\phi_{Q}(x)}{\phi_{P}(x)}}\right\\}\right]+\mathbb{E}_{x,u}\left[\mathbb{1}\left\\{{\psi(x)\in
E}\right\\}\mathbb{1}\left\\{{u>\frac{\phi_{Q}(x)}{\phi_{P}(x)}}\right\\}\right]$
$\displaystyle=\mathbb{E}_{x}\left[\mathbb{1}\left\\{{x\in
E}\right\\}\mathbb{P}\left[{\left\\{{u\leq\frac{\phi_{Q}(x)}{\phi_{P}(x)}}\right\\}\Big{|}x}\right]\right]+\mathbb{E}_{x}\left[\mathbb{1}\left\\{{\psi(x)\in
E}\right\\}\mathbb{P}\left[{\left\\{{u>\frac{\phi_{Q}(x)}{\phi_{P}(x)}}\right\\}\Big{|}x}\right]\right]$
$\displaystyle=\int_{{\mathbb{R}}^{d}}\mathbb{1}\left\\{{x\in
E}\right\\}\min\left\\{{1,\frac{\phi_{Q}(x)}{\phi_{P}(x)}}\right\\}\phi_{P}(x)dx$
$\displaystyle+\int_{{\mathbb{R}}^{d}}\mathbb{1}\left\\{{\psi(x)\in
E}\right\\}\left({1-\min\left\\{{1,\frac{\phi_{Q}(x)}{\phi_{P}(x)}}\right\\}}\right)\phi_{P}(x)dx$
$\displaystyle=\int_{{\mathbb{R}}^{d}}\mathbb{1}\left\\{{x\in
E}\right\\}\min\left\\{{\phi_{P}(x),\phi_{Q}(x)}\right\\}dx+\int_{{\mathbb{R}}^{d}}\mathbb{1}\left\\{{\psi(x)\in
E}\right\\}\max\left\\{{0,\phi_{P}(x)-\phi_{Q}(x)}\right\\}dx$

For the second term, we now do change of variable - let $v=\phi(x)$ \- using
the given properties of $\psi$, we have
$\phi_{P}(x)=\phi_{P}(\psi^{-1}(v))=\phi_{Q}(v)$ and
$\phi_{Q}(x)=\phi_{P}(v)$. Furthermore
$dv=\left|{\det\left(\frac{d\psi(x)}{dx}\right)}\right|dx=dx$. Finally, we are
integrating over ${\mathbb{R}}^{d}$, and since $\phi$ is a bijection, it can
flip the limits of some of the coordinates, however, that is taken into
account with using the absolute value of the determinant of the Jacobian. The
second term therefore becomes $\int_{{\mathbb{R}}^{d}}\mathbb{1}\left\\{{v\in
E}\right\\}\max\left\\{{0,\phi_{Q}(v)-\phi_{P}(v)}\right\\}dv$. We now combine
the integrands of both the terms, and substitute $v=x$ as the variable in the
second term. This gives us,

$\displaystyle\mathbb{P}\left[{y\in E}\right]$
$\displaystyle=\int_{{\mathbb{R}}^{d}}\mathbb{1}\left\\{{x\in
E}\right\\}\left({\min\left\\{{\phi_{P}(x),\phi_{Q}(x)}\right\\}+\max\left\\{{0,\phi_{Q}(x)-\phi_{P}(x)}\right\\}}\right)dx$

Note that for a fixed $x$, if $\phi_{P}(x)\leq\phi_{Q}(x)$, the integrand
becomes $\mathbb{1}\left\\{{x\in
E}\right\\}\left({\phi_{P}(x)+\phi_{Q}(x)-\phi_{P}(x)}\right)=\mathbb{1}\left\\{{x\in
E}\right\\}Q(x)$. On the other hand, if $\phi_{P}(x)>\phi_{Q}(x)$, the
integrand becomes $\mathbb{1}\left\\{{x\in E}\right\\}\phi_{Q}(x)$. Hence, for
all cases, we get that,

$\mathbb{P}\left[{y\in
E}\right]=\int_{{\mathbb{R}}^{d}}\mathbb{1}\left\\{{x\in
E}\right\\}\phi_{Q}(x)dx=Q(E)$

We now show that it is a maximal coupling i.e. the probability of accept is
$1-\text{TV}(P,Q)$. We have,

$\displaystyle\mathbb{P}\left[{\text{accept}}\right]$
$\displaystyle=\mathbb{E}_{x,u}\left[\mathbb{1}\left\\{{u\leq\frac{\phi_{Q}(x)}{\phi_{P}(x)}}\right\\}\right]=\int_{{\mathbb{R}}^{d}}\min\left\\{{1,\frac{\phi_{Q}(x)}{\phi_{P}(x)}}\right\\}\phi_{P}(x)dx$
$\displaystyle=\int_{{\mathbb{R}}^{d}}\min\left\\{{\phi_{P}(x),\phi_{Q}(x)}\right\\}dx=1-\text{TV}(P,Q)\qed$

######  Lemma 2.

Let $P$ and $Q$ be two isotropic probability distributions over
${\mathbb{R}}^{d}$ with means $\mu_{P}$ and $\mu_{Q}$ such that for any
vectors $\mathrm{x},\mathrm{y}$, $\phi_{P}(\mathrm{x})=\phi_{Q}(\mathrm{y})$
if $\left\|{\mathrm{x}-\mu_{P}}\right\|=\left\|{\mathrm{y}-\mu_{Q}}\right\|$.
Given vector $\mathrm{u}$ in ${\mathbb{R}}^{d}$, the reflection of
$\mathrm{u}$ under $(Q,P)$,
$\mathrm{v}=\text{reflect}(\mathrm{u},\mu_{Q},\mu_{P})=\mu_{Q}+(\mu_{P}-\mathrm{u})$,
satisfies:

  1. 1.

Invertibility: $\mathrm{u}=\mathrm{u}_{Q}+(\mu_{P}-\mathrm{v})$

  2. 2.

$\phi_{Q}(\mathrm{v})=\phi_{P}(\mathrm{u})$ and
$\phi_{P}(\mathrm{v})=\phi_{Q}(\mathrm{u})$

  3. 3.

$\left|{\text{det}\left({\frac{d\
\text{reflect}(\mathrm{u},\mu_{Q},\mu_{P})}{d\mathrm{u}}}\right)}\right|=1$

###### Proof of Lemma 2.

The proofs follows immediately using the given assumptions. ∎

####  C.2.3 Coupling Markov chains

We setup some notation to describe the coupling that Algorithm 4 constructs.
The following discussion is for deletion of index $n$, but it can be verified
that the arguments naturally extend to the insertion case. We remind that
$\mu_{n,m}$ denotes the distribution of sampling $m$ elements uniformly
randomly from $[n]$, and mini-batches $b_{j}\sim\mu_{n,m}$. Furthermore, we
will use $\mathbf{b}_{j}=[b_{1},b_{2},\ldots,b_{j}]$ denote the set of indices
upto $j$. For dataset $S$ and mini-batch indices $b$, let the gradient
$\nabla\widehat{F}_{S}(\mathrm{w},\mathrm{z}_{b}):=\frac{1}{|b|}\sum_{j\in
b}\nabla f(\mathrm{w},\mathrm{z}_{j})$. Define
$\tilde{\mathrm{w}}_{j+1}:=\mathring{\mathrm{w}}_{j}-\eta\nabla
F_{S}(\mathring{\mathrm{w}}_{j},\mathrm{z}_{b_{j}})$,
$\bar{\mathrm{w}}_{j+1}:=\tilde{\mathrm{w}}_{j+1}-\eta\theta_{j}$ and
$\mathrm{w}_{j+1}:={\mathcal{P}}(\bar{\mathrm{w}}_{j+1})$. Note that
$\tilde{\mathrm{w}}_{j}$ is also function of $b_{j}$ but this dependency is
not highlighted for notational simplicity.

The iterates and the mini-batches
$[(\bar{\mathrm{w}}_{2},b_{1}),(\bar{\mathrm{w}}_{3},b_{2}),\ldots,(\bar{\mathrm{w}}_{T+1},b_{T})]$
produced by Algorithm 2 is a sample from a $T$-step first order Markov Chain
over an uncountable state space ${\mathbb{R}}^{d}\times[n]^{*}$. We remark
that $\bar{\mathrm{w}}_{1}$ is a constant initialization, and so isn’t
considered. Let $P$ be the joint distribution over the $T$ iterates $\times$
mini-batches. The joint density of $P$ can be factored as,

$\displaystyle\phi_{P}((\bar{\mathrm{w}}_{2},b_{1}),(\bar{\mathrm{w}}_{3},b_{2}),\ldots,(\bar{\mathrm{w}}_{T+1},b_{T}))=\phi_{P}(\bar{\mathrm{w}}_{2},b_{1})\phi_{P}(\bar{\mathrm{w}}_{3},b_{2}|\mathrm{w}_{2})\ldots\phi_{P}(\bar{\mathrm{w}}_{T+1},b_{T}|\mathrm{w}_{T},\mathrm{w}_{T-1})$

where
$\phi_{P}(\bar{\mathrm{w}}_{2},b_{1})=\bar{\phi}_{P}(\bar{\mathrm{w}}_{2}|b_{1})\mu_{n,m}(b_{1})$
and $\bar{\phi}_{P}(\bar{\mathrm{w}}_{2}|b_{1})$ is the density of
${\mathcal{N}}(\tilde{\mathrm{w}}_{2},\eta^{2}\sigma^{2}{\mathbb{I}})$.
Similarly, the conditionals
$\phi_{P}(\bar{\mathrm{w}}_{j},b_{j-1}|\mathrm{w}_{j-1},\mathrm{w}_{j-2})=\bar{\phi}_{P}(\bar{\mathrm{w}}_{j}|b_{j-1},\mathrm{w}_{j-1},\mathrm{w}_{j-2})\mu_{n,m}(b_{j-1})$.
Furthermore, let $\tilde{P}$ denote the marginal of
$[\bar{\mathrm{w}}_{2},\bar{\mathrm{w}}_{2},\ldots,\bar{\mathrm{w}}_{T+1}]$,
the joint density of which can be factored as,

$\displaystyle\tilde{\phi}_{\tilde{P}}(\bar{\mathrm{w}}_{2},\bar{\mathrm{w}}_{3},\ldots,\bar{\mathrm{w}}_{T+1})=\phi_{\tilde{P}}(\bar{\mathrm{w}}_{2})\phi_{\tilde{P}}(\bar{\mathrm{w}}_{3}|\mathrm{w}_{2})\ldots\phi_{\tilde{P}}(\bar{\mathrm{w}}_{T+1}|\mathrm{w}_{T},\mathrm{w}_{T-1})$

where
$\phi_{\tilde{P}}(\bar{\mathrm{w}}_{2})=\mathbb{E}_{b_{1}}\phi_{P}(\bar{\mathrm{w}}_{2},b_{1})$,
and the conditional
$\phi_{\tilde{P}}(\bar{\mathrm{w}}_{j}|\mathrm{w}_{j-1},\mathrm{w}_{j-2})=\mathbb{E}_{b_{j-1}}\bar{\phi}_{P}(\bar{\mathrm{w}}_{j},b_{j-1}|\mathrm{w}_{j-1},\mathrm{w}_{j-2})$.
Finally, given a fixed mini-batch sequence
$\mathbf{b}=\left\\{{b_{1},b_{2},\ldots,b_{T}}\right\\}$, let $P_{\mathbf{b}}$
denote the joint conditional distribution of
$\left\\{{\bar{\mathrm{w}}_{2},\bar{\mathrm{w}}_{3},\ldots,\bar{\mathrm{w}}_{T+1}}\right\\}$
given $\mathbf{b}$. In this case, $P_{\mathbf{b}}$ factorizes as:

$\displaystyle\phi_{P_{\mathbf{b}}}(\bar{\mathrm{w}}_{2},\bar{\mathrm{w}}_{3},\ldots,\bar{\mathrm{w}}_{T+1})=\phi_{P_{b_{1}}}(\bar{\mathrm{w}}_{2})\phi_{P_{b_{2}}}(\bar{\mathrm{w}}_{3}|\mathrm{w}_{2})\ldots\phi_{P_{b_{T}}}(\bar{\mathrm{w}}_{T+1}|\mathrm{w}_{T},\mathrm{w}_{T-1})$

where
$\phi_{P_{b_{1}}}(\bar{\mathrm{w}}_{2})=\bar{\phi}_{P}(\mathrm{w}_{2}|b_{1})$
and
$\phi_{P_{b_{j-1}}}(\bar{\mathrm{w}}_{j}|\mathrm{w}_{j-1},\mathrm{w}_{j-2})=\bar{\phi}_{P}(\bar{\mathrm{w}}_{j}|b_{j-1},\mathrm{w}_{j-1},\mathrm{w}_{j-2})$.
We similarly have a Markov Chain to generate the iterates for dataset
$S^{\prime}$ \- call this joint distribution over iterates and mini-batches as
$Q$, the marginals over iterates as $\tilde{Q}$ and for a given
$\mathbf{b}\sim\left\\{{\mu_{n-1,m}}\right\\}^{\otimes T}$, the conditionals
over the iterates as $Q_{\mathbf{b}}$.

Mini-
batches$b_{1}$$b_{2}$$b_{3}$$b_{T}$$\bar{\mathrm{w}}_{2}$$\bar{\mathrm{w}}_{1}$$\bar{\mathrm{w}}_{3}$$\bar{\mathrm{w}}_{4}$$\mathbf{\bar{w}}_{T+1}$Iterates……
Figure 2: Markov chain for _noisy-m-A-SGD_ Algorithm

We now describe how the unlearning Algorithm 4 constructs a coupling between
$P$ and $Q$ to generate $(\mathbf{\bar{w}}^{(1)},\mathbf{\bar{w}}^{(2)})$. We
first describe the coupling of mini-batch indices. Sample
$\mathbf{b}\sim(\mu^{m}_{n})^{\otimes T}$, let $\mathbf{b}^{(1)}=\mathbf{b}$.
We now look at all $b_{j}^{(1)}\in\mathbf{b}^{(1)}$: if $n\not\in
b_{j}^{(1)}$, then let $b_{j}^{(2)}=b_{j}^{(1)}$, otherwise for each such
$b_{j}^{(1)}$, we replace $n$ by randomly sampling an index from
$[n]\backslash b_{j}^{(1)}$, and call this $b_{j}^{(2)}$. We then define the
ordered set $\mathbf{b}^{(2)}=\left\\{{b_{j}^{(2)}}\right\\}_{j=1}^{T}$. From
5, this is a valid coupling of mini-batch indices. Sample
$\mathbf{\bar{w}}=[\bar{\mathrm{w}}_{2},\bar{\mathrm{w}}_{3},\ldots,\bar{\mathrm{w}}_{T+1}]\sim
P_{\mathbf{b}^{(1)}}$, which corresponds to training with Algorithm 2 on
dataset $S$. Set $\mathbf{\bar{w}}^{(1)}:=\mathbf{\bar{w}}$. To generate
$\mathbf{\bar{w}}^{(2)}$, we do rejection sampling steps at each iteration. At
the first step, we sample $u_{1}\sim\text{Unif}(0,1)$, and check if
$u_{1}\leq\frac{\phi_{Q_{\mathbf{b}^{(2)}}}(\bar{\mathrm{w}}_{2})}{\phi_{P_{\mathbf{b}^{(1)}}}(\bar{\mathrm{w}}_{2})}$.
If the step succeeds, then we proceed to the second iteration, wherein we
again do a step of rejection sampling with ratio of conditional densities and
so on. However, if anyone of the rejection sampling step fails, lets say the
$t^{\text{th}}$ step, then we do a _reflection_ of iterate
$\bar{\mathrm{w}}_{t+1}$ about the mid-point of the means of
$P_{\mathbf{b}^{(1)}}(\cdot|\mathrm{w}_{t},\mathrm{w}_{t-1})$ and
$Q_{\mathbf{b}^{(2)}}(\cdot|\mathrm{w}_{t},\mathrm{w}_{t-1})$ , which are
$\tilde{\mathrm{w}}^{(1)}_{t+1}=\mathrm{w}_{t}-\eta\nabla
F_{S}(\mathrm{w}_{t},\mathrm{z}_{b_{t}})$ and
$\tilde{\mathrm{w}}^{(2)}_{t+1}=\mathrm{w}_{t}-\eta\nabla
F_{S^{\prime}}(\mathrm{w}_{t},\mathrm{z}_{b_{t}^{\prime}})$ respectively. Set
$\bar{\mathrm{w}}^{(2)}_{t+1}=\text{reflect}(\bar{\mathrm{w}}_{t+1},\tilde{\mathrm{w}}^{(2)}_{t+1},\tilde{\mathrm{w}}^{(1)}_{t+1})$.
After the reflection, we continue training on dataset $S^{\prime}$ which
corresponds to continue sampling from the $(t+1)^{\text{th}}$ step of the
Markov chain for $Q_{\mathbf{b}^{(2)}}$ conditioned on the $t^{\text{th}}$
sample being $\bar{\mathrm{w}}^{(2)}_{t}$. This generates the random variables
$\mathbf{\bar{w}}^{(1)}$ and $\mathbf{\bar{w}}^{(2)}$.

We now show that this is indeed a coupling.

######  Lemma 3.

For any measurable set $E\subseteq{\mathbb{R}}^{dT}$,
$\mathbb{P}\left[{\mathbf{\bar{w}}^{(2)}\in E}\right]=\tilde{Q}(E)$

###### Proof of Lemma 3.

We will first show that $\mathbb{P}\left[{\mathbf{\bar{w}}^{(2)}\in
E|(\mathbf{b}^{(1)},\mathbf{b}^{(2)})}\right]=Q_{\mathbf{b}^{(2)}}(E)$. The
proof is based on induction on the length of the Markov chain $T$. Define
$\mathbf{\bar{w}}_{T}^{(2)}:=\left\\{{\bar{\mathrm{w}}_{2}^{(2)},\cdots,\bar{\mathrm{w}}_{T-1}^{(2)}}\right\\}$.
The key to the proof is the observation that the marginals
${P_{b_{1}^{(1)}}}(\cdot)$ and ${Q_{b_{1}^{(2)}}}(\cdot)$ are Gaussian
${\mathcal{N}}(\tilde{\mathrm{w}}_{2}^{(1)},\eta^{2}\sigma^{2}{\mathbb{I}})$
and
${\mathcal{N}}(\tilde{\mathrm{w}}_{2}^{(2)},\eta^{2}\sigma^{2}{\mathbb{I}})$
respectively, and the conditionals ${P_{b_{j}^{(1)}}}(\cdot|\mathrm{w}_{j})$
and ${Q_{b_{j}^{(2)}}(\cdot|\mathrm{w}_{j})}$ are also Gaussian
${\mathcal{N}}(\tilde{\mathrm{w}}_{j+1}^{(1)},\eta^{2}\sigma^{2}{\mathbb{I}})$
and
${\mathcal{N}}(\tilde{\mathrm{w}}_{j+1}^{(2)},\eta^{2}\sigma^{2}{\mathbb{I}})$.

For $T=1$, we only care about the marginals ${P_{b_{1}^{(1)}}}(\cdot)$ and
${Q_{b_{1}^{(2)}}}(\cdot)$, which as argued before, are normally distributed.
From Lemma 2, we have established that the reflection map satisfies the
conditions in Lemma 1. Combining these, we have that the base case $T=1$
follows from the reflection coupling result stated as Lemma 1.

We proceed to the induction step. There are two cases, depending on whether we
do a rejection sampling in the $T^{th}$ step or not: we call these "rej-
sample" and "no-rej-sample" respectively. If we do a rejection sampling, we
further have two cases (1a). accept: either all rejection samplings, including
the one in the $T^{\text{th}}$ step are accepts, (1b). reflect: all rejection
samplings, except the one in the $T^{\text{th}}$ step are accepts, and in the
$T^{\text{th}}$ step, we reflect. Finally, if we don’t do a rejection sampling
step, we have the third case (2). reject: some rejection sampling prior to $T$
results in reject; in this case, the $T^{\text{th}}$ sample
$\bar{\mathrm{w}}_{T+1}^{(2)}\sim
Q_{b_{T}^{(2)}}(\cdot|\mathrm{w}_{T}^{(2)},\mathrm{w}_{T-1}^{(2)})$. Cases (1)
and (2) partition the whole event space for $T$ draws, whereas cases (1a) and
cases (1b) partitions the space of the $T^{\text{th}}$ draw, conditioned on
the first event. Also note that case (1) vs (2) distinction is measurable
w.r.t. the natural filtration generated by the Markov chain upto $T-1$ draws.

Note that conditioned on the events "rej sample" as well as
$\mathbf{w}^{(2)}_{T-1}$, the last step is just a one-step reflection coupling
method. To elaborate, the conditionals
$Q_{b_{T}^{(2)}}(\cdot|\mathrm{w}_{T}^{(2)},\mathrm{w}_{T-1}^{(2)})$ and
$P_{b_{T}^{(2)}}(\cdot|\mathrm{w}_{T}^{(2)},\mathrm{w}_{T-1}^{(2)})$ used in
the $T^{\text{th}}$ rejection sampling are Gaussians, which along with the
reflection map satisfies properties of Lemma 1, as in the base case. Let
$E_{last}=\left\\{{y|\exists\mathbf{x}:(\mathbf{x},y)\in E}\right\\}$ be the
projection of $E$ on the last co-ordinate and
$E_{y}=\left\\{{\mathbf{x}|(\mathbf{x},y)\in E}\right\\}$. According to Lemma
2, the conditional distribution of $\mathrm{w}_{T+1}^{(2)}$ is
$Q_{b_{T}^{(2)}}(\cdot|\mathrm{w}_{T}^{(2)},\mathrm{w}_{T-1}^{(2)})$:

$\displaystyle\mathbb{P}\left[{\bar{\mathrm{w}}_{T+1}^{(2)}\in
E_{last}|\text{rej-
sample},{\mathbf{\bar{w}}_{T-1}^{(2)}},(\mathbf{b}^{(1)},\mathbf{b}^{(2)})}\right]$
$\displaystyle=\mathbb{P}\left[{\bar{\mathrm{w}}_{T+1}^{(2)}\in
E_{last},\text{accept}|\text{rej-
sample},{\mathbf{\bar{w}}_{T-1}^{(2)}},(\mathbf{b}^{(1)},\mathbf{b}^{(2)})}\right]$
$\displaystyle\qquad+\mathbb{P}\left[{\bar{\mathrm{w}}_{T+1}^{(2)}\in
E_{last},\text{reflect}|\text{rej-
sample},{\mathbf{\bar{w}}_{T-1}^{(2)}},(\mathbf{b}^{(1)},\mathbf{b}^{(2)})}\right]$
$\displaystyle=\Large\int_{{\mathbb{R}}^{d}}\mathbb{1}\left({\bar{\mathrm{w}}_{T+1}^{(2)}\in
E_{last}}\right)\phi_{Q_{b_{T}^{(2)}}}(\bar{\mathrm{w}}_{T+1}^{(2)}|\mathrm{w}_{T}^{(2)},\mathrm{w}_{T-1}^{(2)})d\bar{\mathrm{w}}_{T+1}^{(2)}$

For the "no-rej-sample" case, we have:

$\displaystyle\mathbb{P}\left[{\bar{\mathrm{w}}_{T+1}^{(2)}\in
E_{last}|\text{no-rej-
sample},{\mathbf{\bar{w}}_{T-1}^{(2)}},(\mathbf{b}^{(1)},\mathbf{b}^{(2)})}\right]=\underset{\bar{\mathrm{w}}_{T+1}^{(2)}}{\mathbb{E}}\left[\mathbb{1}\left({\bar{\mathrm{w}}_{T+1}^{(2)}\in
E_{last}}\right)\right]$
$\displaystyle=\Large\int_{{\mathbb{R}}^{d}}\mathbb{1}\left({\bar{\mathrm{w}}_{T+1}^{(2)}\in
E_{last}}\right)\phi_{Q_{b_{T}^{(2)}}}(\bar{\mathrm{w}}_{T+1}^{(2)}|\mathrm{w}_{T}^{(2)},\mathrm{w}_{T-1}^{(2)})d\bar{\mathrm{w}}_{T+1}^{(2)}$

We will now combine the two cases. Let $\phi^{(r)}(\cdot)$ and
$\phi^{(nr)}(\cdot)$ denote the densities of $\mathbf{\bar{w}}_{T-1}^{(2)}$
under the "rej-sample" and "no-rej-sample" events respectively.

$\displaystyle\mathbb{P}\left[{\mathbf{\bar{w}}^{(2)}\in
E|(\mathbf{b}^{(1)},\mathbf{b}^{(2)})}\right]$
$\displaystyle=\mathbb{P}\left[{\bar{\mathrm{w}}_{T+1}^{(2)}\in
E_{last}\,\Big{|}\,\text{rej-
sample},{\mathbf{\bar{w}}_{T-1}^{(2)}},(\mathbf{b}^{(1)},\mathbf{b}^{(2)})}\right]\mathbb{P}\left[{\mathbf{\bar{w}}_{T-1}^{(2)}\in
E_{\bar{\mathrm{w}}_{T+1}^{(2)}},\text{rej-sample}}\right]$
$\displaystyle+\mathbb{P}\left[{\bar{\mathrm{w}}_{T+1}^{(2)}\in
E_{last}\,\Big{|}\,\text{no-rej-
sample},{\mathbf{\bar{w}}_{T-1}^{(2)}},(\mathbf{b}^{(1)},\mathbf{b}^{(2)})}\right]\mathbb{P}\left[{\mathbf{\bar{w}}_{T-1}^{(2)}\in
E_{\bar{\mathrm{w}}_{T+1}^{(2)}},\text{no-rej-sample}}\right]$
$\displaystyle=\int_{{\mathbb{R}}^{dT}}\mathbb{1}\left\\{{\bar{\mathrm{w}}_{T+1}^{(2)}\in
E_{last}}\right\\}\mathbb{1}\left\\{{\mathbf{\bar{w}}_{T-1}^{(2)}\in
E_{\bar{\mathrm{w}}_{T+1}^{(2)}}}\right\\}$
$\displaystyle\cdot\left\\{{\mathbb{1}_{\text{rej-
sample}}\left\\{{\mathbf{\bar{w}}_{T-1}^{(2)}}\right\\}\phi^{(r)}(\mathbf{\bar{w}}_{T-1}^{(2)})+\mathbb{1}_{\text{no-
rej-
sample}}\left\\{{\mathbf{\bar{w}}_{T-1}^{(2)}}\right\\}\phi^{(nr)}(\mathbf{\bar{w}}_{T-1}^{(2)})}\right\\}\phi_{Q_{{b_{T}^{(2)}}}}(\bar{\mathrm{w}}_{T+1}^{(2)}|\mathrm{w}_{T}^{(2)},\mathrm{w}_{T-1}^{(2)})d\mathbf{\bar{w}}_{T}^{(2)}$
$\displaystyle=\int_{{\mathbb{R}}^{dT}}\mathbb{1}\left\\{{\mathbf{\bar{w}}^{(2)}\in
E}\right\\}\phi_{Q_{\mathbf{b}_{T-1}^{(2)}}}(\mathbf{\bar{w}}_{T-1}^{(2)})\phi_{Q_{{b^{(2)}_{T}}}}(\bar{\mathrm{w}}_{T+1}^{(2)}|\mathrm{w}_{T}^{(2)},\mathrm{w}_{T-1}^{(2)})d\mathbf{\bar{w}}_{T}^{(2)}$
$\displaystyle=\int_{{\mathbb{R}}^{dT}}\mathbb{1}\left\\{{\mathbf{\bar{w}}^{(2)}\in
E}\right\\}\phi_{Q_{\mathbf{b}^{(2)}}}(\mathbf{w}_{T}^{(2)})d\mathbf{\bar{w}}_{T}^{(2)}=Q_{\mathbf{b}^{(2)}}(E)$

where the third equality uses the induction hypothesis that
$\mathbf{\bar{w}}_{T-1}^{(2)}$, conditioned on $\mathbf{b}^{(1)}$ and
$\mathbf{b}^{(2)}$, is distributed as $Q_{\mathbf{b}_{T-1}^{(2)}}$. Finally,
we integrate with respect to the coupling generating
$(\mathbf{b}^{(1)},\mathbf{b}^{(2)})$; we get

$\displaystyle\mathbb{P}\left[{\mathbf{\bar{w}}^{(2)}\in E}\right]$
$\displaystyle=\sum_{(\mathbf{b}^{(1)},\mathbf{b}^{(2)})}\mathbb{P}\left[{\mathbf{\bar{w}}^{(2)}\in
E|(\mathbf{b}^{(1)},\mathbf{b}^{(2)})}\right]\mathbb{P}\left[{\mathbf{b}^{(1)},\mathbf{b}^{(2)}}\right]$
$\displaystyle=\sum_{(\mathbf{b}^{(1)},\mathbf{b}^{(2)})}Q_{\mathbf{b}^{(2)}}(E)\mathbb{P}\left[{\mathbf{b}^{(1)},\mathbf{b}^{(2)}}\right]=\sum_{\mathbf{b}^{(2)}}Q_{\mathbf{b}^{(2)}}(E)\mathbb{P}\left[{\mathbf{b}^{(2)}}\right]=\tilde{Q}(E)$

This completes the proof. ∎

We now show that not only the marginals over the iterates, but the entire
state maintained by the algorithm, which includes the mini-batching indices is
transported.

######  Lemma 4.

For any measurable event in
$\left({{\mathbb{R}}^{d}\times[n]^{m}}\right)^{\otimes T}$, we have

$\displaystyle\mathbb{P}\left[{(\mathbf{\bar{w}}^{(2)},\mathbf{b}^{(2)})\in
E}\right]=Q(E)$

###### Proof of Lemma 4.

We first decompose the event
$E\subseteq\left({{\mathbb{R}}^{d}\times[n]^{m}}\right)^{\otimes T}$ as two
events, $E=E_{1}\times E_{2}$ where $E_{1}\subseteq{\mathbb{R}}^{dT}$ and
$E_{2}\subseteq\left({[n]^{m}}\right)^{T}$. We have

$\displaystyle\mathbb{P}\left[{(\mathbf{\mathbf{\bar{w}}}^{(2)},\mathbf{b}^{(2)})\in
E}\right]$
$\displaystyle=\mathbb{E}_{\mathbf{b}^{(1)}}\mathbb{P}\left[{\mathbf{\mathbf{\bar{w}}}^{(2)}\in
E_{1}|\mathbf{b}^{(1)},\mathbf{b}^{(2)}}\right]\mathbb{P}\left[{\mathbf{b}^{(2)}\in
E_{2}}\right]$
$\displaystyle=\mathbb{E}_{\mathbf{b}^{(1)}}\tilde{Q}_{\mathbf{b}^{(2)}}(E_{1})\mu_{n,m}^{\text{del}\otimes
T}(E_{2})$
$\displaystyle=\mathbb{E}_{\mathbf{b}^{(1)}}\tilde{Q}_{\mathbf{b}^{(2)}}(E_{1})\mu_{n-1,m}^{\otimes
T}(E_{2})$
$\displaystyle=\tilde{Q}_{\mathbf{b}^{(2)}}(E_{1})\mu_{n-1,m}^{\otimes
T}(E_{2})=Q(E)$

where the second and third equality follows from Lemma 3 and 5, and the final
equality follows from the definition of event $E$ and probability distribution
$Q$. ∎

We now lower bound the probability of accepting at all rejection sampling
steps.

######  Lemma 5.

Let “accept" be the event in which all rejection sampling result in accepts so
there is no reflection or recompute. The probability of accept is lower
bounded as,

$\mathbb{P}\left[{\text{accept}}\right]\geq 1-\frac{\sqrt{T}\rho}{8}$

###### Proof of Lemma 5.

We evaluate the probability that all rejection sampling steps result in
accepts. We first do it conditioned on $\mathbf{b}^{(1)},\mathbf{b}^{(2)}$

$\displaystyle\mathbb{P}\left[{\text{accept}|\mathbf{b}^{(1)},\mathbf{b}^{(2)}}\right]$
$\displaystyle=\underset{\bar{\mathrm{w}}_{T}^{(1)},\bar{\mathrm{w}}_{T+1}^{(2)},\left\\{{u_{j}}\right\\}_{j=1}^{T}}{\mathbb{E}}\left[\prod_{j=1}^{T}\mathbb{1}_{\text{accept}}(u_{j})\right]$
$\displaystyle=\underset{\mathbf{\bar{w}}_{T}^{(1)},\mathbf{\bar{w}}_{T+1}^{(2)}}{\mathbb{E}}\left[\prod_{j=1}^{T}\mathbb{P}\left[{u_{j}\leq\frac{\phi_{Q_{b^{(2)}_{j}}}(\bar{\mathrm{w}}_{j+1}^{(1)}|\mathrm{w}_{j}^{(1)},\mathrm{w}_{j-1}^{(1)})}{\phi_{P_{b^{(1)}_{j}}}(\bar{\mathrm{w}}_{j+1}^{(1)}|\mathrm{w}_{j}^{(1)},\mathrm{w}_{j-1}^{(1)})}\Big{|}\mathbf{\bar{w}}_{T}^{(1)},\mathbf{\bar{w}}_{T}^{(2)}}\right]\right]$
$\displaystyle=\int_{{\mathbb{R}}^{dT}}\prod_{j=1}^{T}\min\left\\{{\phi_{P_{b^{(1)}_{j}}}(\bar{\mathrm{w}}_{j+1}^{(1)}|\mathrm{w}_{j}^{(1)})\mathrm{w}_{j-1}^{(1)}),\phi_{Q_{b^{(2)}_{j}}}(\bar{\mathrm{w}}_{j+1}^{(1)}|\mathrm{w}_{j}^{(1)}),\mathrm{w}_{j-1}^{(1)})}\right\\}d\mathbf{\bar{w}}^{(1)}_{T}$
$\displaystyle=\prod_{j=1}^{T}\left({\int_{{\mathbb{R}}^{d}}\min\left\\{{\phi_{P_{b^{(1)}_{j}}}(\bar{\mathrm{w}}_{j+1}^{(1)}|\mathrm{w}_{j}^{(1)}),\mathrm{w}_{j-1}^{(1)}),\phi_{Q_{b^{(2)}_{j}}}(\bar{\mathrm{w}}_{j+1}^{(1)}|\mathrm{w}_{j}^{(1)}),\mathrm{w}_{j-1}^{(1)})}\right\\}d\bar{\mathrm{w}}^{(1)}_{j+1}}\right)$

The term

$\displaystyle\int_{{\mathbb{R}}^{d}}\min\left\\{{\phi_{P_{b^{(1)}_{j}}}(\bar{\mathrm{w}}_{j+1}^{(1)}|\mathrm{w}_{j}^{(1)}),\mathrm{w}_{j-1}^{(1)}),\phi_{Q_{b^{(2)}_{j}}}(\bar{\mathrm{w}}_{j+1}^{(1)}|\mathrm{w}_{j}^{(1)}),\mathrm{w}_{j-1}^{(1)})}\right\\}d\bar{\mathrm{w}}^{(1)}_{j+1}$
$\displaystyle=1-\text{TV}_{\mathbf{\bar{w}}_{j}^{(1)},\mathbf{b}^{(1)},\mathbf{b}^{(2)}}(P_{b_{j}^{(1)}},Q_{b_{j}^{(2)}})$

where the notation $\text{TV}_{x}(\cdot,\cdot)$ denotes the conditional TV
between the arguments, conditioned on the subscript. Let
$\gamma_{j}=\frac{\Delta(b_{j}^{(1)},b_{j}^{(2)})}{2}$ i.e. the number of
elements differing in $b_{j}^{(1)}$ and $b_{j}^{(2)}$ . Note that if
$\gamma_{j}=0$, then $b_{j}^{(1)}=b_{j}^{(2)}$ and
$P_{b_{j}^{(1)}}=Q_{b_{j}^{(2)}}$, and hence
$\text{TV}_{\bar{\mathrm{w}}_{j-1}^{(1)},\mathbf{b}^{(1)},\mathbf{b}^{(2)}}(P_{b_{j}^{(1)}},Q_{b_{j}^{(2)}})=0$.
In the other case, $\gamma_{j}=1$, which corresponds to the case when the
deleted point was used in the $j^{\text{th}}$ mini-batch. In this case, the
means of $P_{b_{j}^{(1)}}$ are $Q_{b_{j}^{(2)}}$ at separated by at most
$\frac{2G\eta}{m}$ \- this follows as in the proof of Proposition 2. In
particular, fixing previous iterates and $\bar{\mathrm{w}}_{j-1}^{(1)}$ and
mini-batch indices $\mathbf{b}^{(1)},\mathbf{b}^{(2)}$, using the fact that
gradients are in norm bounded by $G$, $P_{b_{j}^{(1)}}$ and $Q_{b_{j}^{(2)}}$
are Gaussians with variance $\eta^{2}\sigma^{2}{\mathbb{I}}$ and means
separated by either $\frac{2G\eta\gamma_{j}}{m}$ or $0$, depending on
$\gamma_{j}$. Combining the two cases, and using TV between Gaussians formula
[13], we have
$1-\text{TV}_{\bar{\mathrm{w}}_{j-1}^{(1)},\mathbf{b}^{(1)},\mathbf{b}^{(2)}}(P_{b_{j}^{(1)}},Q_{b_{j}^{(2)}})\geq\left({1-\frac{G\eta}{\eta\sigma
m}}\right)^{\gamma_{j}}=\left({1-\frac{G}{\sigma m}}\right)^{\gamma_{j}}$. We
therefore get
$\int_{{\mathbb{R}}^{d}}\min\left\\{{\phi_{P_{b^{(1)}_{j}}}(\bar{\mathrm{w}}_{j+1}^{(1)}|\mathrm{w}_{j}^{(1)}),\mathrm{w}_{j-1}^{(1)}),\phi_{Q_{b^{(2)}_{j}}}(\bar{\mathrm{w}}_{j+1}^{(1)}|\mathrm{w}_{j}^{(1)}),\mathrm{w}_{j-1}^{(1)})}\right\\}d\bar{\mathrm{w}}^{(1)}_{j+1}\geq\left({1-\frac{G}{\sigma
m}}\right)^{\gamma_{j}}$. Plugging this in the conditional probability of
accept expression, we get

$\displaystyle\mathbb{P}\left[{\text{accept}|\mathbf{b}^{(1)},\mathbf{b}^{(2)}}\right]$
$\displaystyle\geq\prod_{j=1}^{T}\left({1-\frac{G}{\sigma
m}}\right)^{\gamma_{j}}=\left({1-\frac{G}{\sigma
m}}\right)^{\sum_{j=1}^{T}\gamma_{j}}\geq
1-\frac{G\sum_{j=1}^{T}\gamma_{j}}{\sigma m}$

We now integrate with respect to $\mathbf{b}^{(1)},\mathbf{b}^{(2)}$. Note
that $\sum_{j=1}^{T}\gamma_{j}$ is the number of mini-batches which contain
the deleted point. Since in each mini-batch, $m$ points are selected uniformly
randomly from $n$,
$\mathbb{E}_{\mathbf{b}^{(1)},\mathbf{b}^{(2)}}{\gamma_{j}}=\frac{m}{n}$,
which gives us
$\mathbb{E}_{\mathbf{b}^{(1)},\mathbf{b}^{(2)}}\sum_{j=1}^{T}\gamma_{j}=\frac{Tm}{n}$.
Hence,

$\displaystyle\mathbb{P}\left[{\text{accept}}\right]\geq
1-\frac{G\mathbb{E}_{\mathbf{b}^{(1)},\mathbf{b}^{(2)}}\sum_{j=1}^{T}\gamma_{j}}{\sigma
m}=1-\frac{GT}{\sigma n}=1-\frac{\sqrt{T}\rho}{8}$

where the last equality follows from plugging in
$\sigma=\frac{8\sqrt{T}G}{n\rho}$ as in Proposition 2. ∎

We are now ready to prove Proposition 4.

###### Proof of Proposition 4.

We need to show that upon deletion and insertion, the probability distribution
of the entire state maintained by the algorithm, which is all iterates as well
as mini-batches indices is transported - this, for one deletion, follows from
Lemma 4 (which is for unprojected iterates), together with the fact that
projection is a deterministic operation. Moreover, as before, the above
argument also holds for insertion and generalizes arbitrary edit requests.

We now proceed to bound the probability to recompute. This follows directly
combining Lemma 5, Proposition 2 and Remark 2. From Remark 2, upon $k$ edits,
the total variation distance is at most $k$ times total variation distance
upon 1 edit. Since the algorithm is $\rho$-TV stable (Proposition 2), and the
assumption that the number of samples are between $n/2$ and $2n$, the total
variation distance upon $k$ edits is at most $2k\rho$. Hence, using Lemma 5,
we have that the probability to recompute is probability of “reject" is at
most $\frac{k\rho\sqrt{T}}{4}$. ∎

##  Appendix D Runtime and space complexity

In this section, we discuss, in detail, the learning and unlearning runtime of
the algorithms, as well as their space complexity.

###  D.1 Learning runtime

In this work, we did not aim to carefully optimize the runtime for
training/learning algorithm, as long as the algorithm achieves the rate in
Theorem 2. However, we briefly discuss the runtime of each algorithm, and
highlight easy improvements, where possible. Algorithm 1 requires $mT$ = $\rho
n$ stochastic gradient computations. On the other hand, for Algorithm 2, if
$m\leq\sqrt{\frac{LD\rho n}{G\sqrt{d}}}$, it requires $mT=m\left({\frac{\rho
n}{md}}\right)=\frac{(\rho n)^{2}}{d}$ stochastic gradient computations -
setting larger $m$ only hurts the total runtime, without any advantage. Note
that total stochastic gradient descent computations of _noisy-m-SGD_ (i.e.
without acceleration, see Section E.1) is also $\frac{(\rho n)^{2}}{d}$;
however, the key advantage of acceleration is that it allows setting larger
mini-batch sizes: $T^{3}$ as opposed to $T$, which leads to smaller number of
iterations: $\sqrt{\frac{\rho n}{\sqrt{d}}}$ as opposed to $\frac{\rho
n}{\sqrt{d}}$ and hence a smaller probability of recompute. From [32], we know
that mini-batch SGD (with or without acceleration) is optimal for smooth
convex composite/ERM optimization in the low accuracy regime: when accuracy
$\alpha\gtrsim\frac{1}{\sqrt{n}}$. In this regime, an algorithm makes at least
$\Omega\left({\frac{1}{\alpha^{2}}}\right)$ calls to a stochastic gradient
oracle. It can be then verified that for our accuracy, our algorithms make the
optimal number of oracle calls.

For Algorithm 2, as discussed, faster algorithms lead to better unlearning
times. It is natural to ask what happens if we additionally introduce variance
reduction techniques on top of acceleration to yield even faster runtimes. In
particular, what if we use Katyusha [2], which has optimal runtime in terms of
stochastic gradient computations. We argue that even though it improves the
runtime of the learning algorithm, it does not yield improvement for
unlearning beyond what we have with acceleration. From Corollary 5.8 in [2],
setting largest allowed $m=\sqrt{n}$, we get that
$Tm=O\left({\frac{\sqrt{n}}{\sqrt{\epsilon}}}\right)$ – in our case,
$\epsilon=\frac{\sqrt{d}}{\rho n}$, which yields
$Tm=O\left({\sqrt{n}\sqrt{\frac{\rho n}{\sqrt{d}}}}\right)$ stochastic
gradient computations. Note that this is smaller than that of _noisy-m-A-SGD_
(unless $\rho$ is very small), however $T=\sqrt{\frac{\rho n}{\sqrt{d}}}$ –
same as that of _noisy-m-A-SGD_ , and hence yields no improvement in
unlearning time. However, note that using Katyusha would give us optimal
oracle complexity even in the _high_ accuracy regime.

###  D.2 Unlearning runtime

We now look at how much compute it takes for Algorithm 3 and 4 to handle the
edit requests. We first give a general result, which holds for any TV-stable
algorithm with the unlearning algorithm being the one which constructs a
coupling with acceptance probability at least $1-\rho$. We give in-expectation
bounds on the number of times verification fails or a full or partial
recompute is triggered.

######  Proposition 6.

For a coupling based unlearning algorithm with acceptance probability at least
$1-\rho$, for $k$ edit requests, the expected number of times recompute is
triggered is at most $4k\rho$.

###### Proof of Proposition 6.

We first setup some notation. In the general setup, for $k$ edit requests, let
$s$ be the number of times a recompute is triggered. Let
$\left\\{{Z_{1},Z_{2},\ldots,Z_{s}}\right\\}$ be a set of random variables,
where each $Z_{i}$ denotes how many edit requests the $i^{\text{th}}$
recompute can _handle_. To elaborate, $Z_{i}$ takes value $j$, if upon $j$
edit requests, a recompute is triggered. The $Z_{i}$’s comprises to the
randomness used in the algorithm like mini-batching indices or Gaussian noise,
as well as the randomness used for rejection sampling. It is important to note
that $Z_{i}^{\prime}s$ are not necessarily independent. In particular, in
Algorithm 4, we reuse the Gaussian noise upto the iteration in which rejection
sampling fails, and only use fresh/independent Gaussian noise in the later
steps. However, note that we have exact unlearning, and the output at each
step is $\rho$-TV stable (w.r.t. all the randomness used). Hence, since the
above description of the distribution of $Z_{i}$’s depend only on the TV
stability parameter, it follows that $Z_{i}^{\prime}s$ are (marginally)
identical.

We now use the fact that the unlearning algorithm constructs a coupling with
acceptance probability at least $1-\rho$ to describe the probability
distribution of $Z_{i}$. We have that upon one edit request, the probability
that a recompute is triggered is at most $\rho$. This means that $Z_{i}<2$
with probability $\leq\rho$. Using Remark 2, this generalizes as $Z_{i}<j$
with probability at most $(j-1)\rho$. Note that in our setup, we observe at
most $k$ requests, so $Z_{i}$ taking values larger than $k$ is not meaningful.
However if $k\rho<1$, it means that probability that $Z_{i}$ takes values
smaller than $k$ is less than $1$, and therefore there is a positive
probability of $Z_{i}$ being larger than $k$. To remedy this, we define
another random variable $X_{i}$’s which takes values in the set
$\left\\{{1,2,\ldots,k}\right\\}$. Furthermore, for any $i$,
$\mathbb{P}\left[{X_{i}=j}\right]=\mathbb{P}\left[{Z_{i}=j}\right]$ for $j\leq
k$, but
$\mathbb{P}\left[{Z_{i}=j}\right]=\sum_{l=k}^{\infty}\mathbb{P}\left[{X_{i}=l}\right]$.
By construction, this ensures that $1\leq Z_{i}\leq k$, when we observe at
most $k$ requests.

We want upper bounds on $s$ conditioned on the fact that $k$ requests are
addressed i.e. $X_{1}+X_{2}\ldots,X_{s}\geq k$. For this we write $s$ as
$s:=\min_{q}\left\\{{2k\geq X_{1}+X_{2}\ldots,X_{q}\geq k}\right\\}$. The
first inequality holds trivially since we ensured that $X_{i}\leq k$. It is
easy to see that $s$ is a stopping time with respect to the filtered
probability space of the stochastic process
$\left\\{{X_{i}}\right\\}_{i\in{\mathbb{N}}}$. Furthermore, since $X_{i}$’s
are identical, we can apply Wald’s equation to get,

$\displaystyle 2k\geq\mathbb{E}[X_{1}+X_{2}+\ldots
X_{s}]=\mathbb{E}[s]\mathbb{E}[X_{1}]=\mathbb{E}[s]\sum_{j=1}^{k}{\mathbb{P}}\left\\{{X_{i}\geq
j}\right\\}=\mathbb{E}[s]\sum_{j=1}^{\infty}{\mathbb{P}}\left\\{{Z_{i}\geq
j}\right\\}$
$\displaystyle\geq\mathbb{E}[s]\sum_{j=1}^{1+1/\rho}{\mathbb{P}}\left\\{{Z_{i}\geq
j}\right\\}=\mathbb{E}[s]\sum_{j=1}^{1+1/\rho}\left({1-{\mathbb{P}}\left\\{{Z_{i}<j}\right\\}}\right)\geq\mathbb{E}[s]\left({\frac{1}{\rho}-\sum_{j=1}^{1+1/\rho}(j-1)\rho}\right)$
$\displaystyle\geq\mathbb{E}[s]\left({\frac{1}{\rho}-\int_{j=0}^{1/\rho}j\rho
dj}\right)\geq\mathbb{E}[s]\left({\frac{1}{\rho}-\frac{1}{2\rho^{2}}\rho}\right)\geq\frac{\mathbb{E}[s]}{2\rho}$

This gives us that $\mathbb{E}[s]\leq 4k\rho$. ∎

Next, we look at the runtimes for Algorithm 3 and Algorithm 4 to handle one
deletion or insertion request. For this, we look at the runtime of
verification, i.e., deciding if recompute needs to be triggered or not. We
show how in the standard algorithmic model of computation (say, word RAM
model), using suitable data structures, this can be done efficiently.
Furthermore, as standard in convex optimization, we can use Nemirovski-Yudin’s
model of computation [24] which counts the number of accesses to the first-
order (gradient) information of the function, and a projection oracle. Let
$\mathfrak{G}$ denote the compute cost for one gradient access or projection
in the standard model of computation – we assume that both oracles require the
same compute. In the rest of the discussion, we provide runtime as a function
of the problem parameters ignoring all constants. Furthermore, since we
assumed that the number of samples at any point in the stream is between
$\frac{n}{2}$ and $2n$, we will just work with $n$ samples, and everything
would still be the same, up to constants.

##### Verification runtime of Algorithm 3.

For Algorithm 3, note that for deletion, for every iteration, we need to check
if the used mini-batch $b_{t}$ contained the requested point. A brute force
search takes $O(m)$ time, whereas if we sort when we save the mini-batch
indices $b_{t}$, we can do a binary search in
$O(\operatorname{log}\left(m\right))$ time; we can even do constant time
search by storing a dictionary/hash table, giving us an $O(T)$ total time. The
most efficient way however is to store a dictionary of sample to mini-batch
iterations that the sample was used in. For this, it takes $O(1)$ time lookup
for every edit request. For insertion, similarly, at every iteration, we first
sample from a Bernoulli with bias $m/n$ which takes constant time, giving us
$O(T)$ total time. However, equivalently, we just sample one Bernoulli with
bias $Tm/n$ and recompute based on its outcome. This gives us an $O(1)$ time
lookup for every edit request.

##### Verification runtime of Algorithm 4.

For Algorithm 4, we can similarly search in constant time whether the deleted
point was used in any iteration or not. For every iteration in which the
deleted point is in the mini-batch, we need to compute a gradient at a new
point, so as to replace the deleted point. Sampling a point uniformly from a
discrete universe takes linear time (in the size) in the worst case, but with
some pre-processing can be done in logarithmic/constant time. For example,
when saving the mini-batch indices $b_{t}$, if we save a sorted list of the
indices not sampled, using binary search, we can sample in
$O(\operatorname{log}\left(n-(m-1)\right))$ time. The more efficient way is,
if we save a probability table, then we can use Alias method to sample in
$O(1)$ time [30]. Hence for such iterations, we query _two_ gradients, and it
takes $O(d)$ compute to add/subtract this gradients. Since the total number of
iterations in which a deleted point was sampled in, in expectation, is
$\frac{Tm}{n}$, the expected total compute is $\frac{Tm(\mathfrak{G}+d)}{n}$.

We now consider the computational cost of rejection sampling. In Algorithm 4,
at every iteration we check if
Unif$\left({0,1}\right)\leq\frac{\phi_{{\mathcal{N}}(\mathrm{g}_{t}^{\prime},\sigma^{2}{\mathbb{I}})}(\xi_{t})}{\phi_{{\mathcal{N}}(\mathrm{g}_{t},\sigma^{2}{\mathbb{I}})}(\xi_{t})}$,
where $\phi_{{\mathcal{N}}(\mathrm{g}_{t},\sigma^{2}{\mathbb{I}})}(\cdot)$ and
$\phi_{{\mathcal{N}}(\mathrm{g}_{t}^{\prime},\sigma^{2}{\mathbb{I}})}(\cdot)$
are probability densities evaluated at the sampled point $\xi_{t}$. We thus
need to compute this ratio of probability densities – since these are Gaussian
densities, the ratio is just the following the expression:

$\displaystyle\frac{\phi_{{\mathcal{N}}(\mathrm{g}_{t}^{\prime},\sigma^{2}{\mathbb{I}})}(\xi_{t})}{\phi_{{\mathcal{N}}(\mathrm{g}_{t},\sigma^{2}{\mathbb{I}})}(\xi_{t})}=\frac{\frac{1}{(\sqrt{2\pi\sigma^{2}})^{d}}\operatorname{exp}\left(-\frac{\left\|{\mathrm{g}_{t}^{\prime}-\xi_{t}}\right\|^{2}}{2\sigma^{2}}\right)}{\frac{1}{(\sqrt{2\pi\sigma^{2}})^{d}}\operatorname{exp}\left(-\frac{\left\|{\mathrm{g}_{t}-\xi_{t}}\right\|^{2}}{2\sigma^{2}}\right)}=\operatorname{exp}\left(\frac{1}{2\sigma^{2}}\left({\left\|{\mathrm{g}_{t}-\xi_{t}}\right\|^{2}-\left\|{\mathrm{g}_{t}^{\prime}-\xi_{t}}\right\|^{2}}\right)\right).$

It takes $O(d)$ time to do the above computation. Moreover, we only need to
compute the ratio in iterations where the means differ – these correspond to
the iterations where the deleted point was sampled or the inserted point would
have been sampled. By a direct computation, the expected number of such
iterations is $\frac{Tm}{n}$. This gives us a computational cost of
$\frac{Tmd}{n}$ for rejection sampling, and hence the expected runtime of
verification is $\frac{Tm(\mathfrak{G}+d)}{n}$.

We now state bounds on runtime for both unlearning algorithms.

######  Claim 7.

The expected total unlearning runtime of Algorithm 3 for $k$ edit requests is
$O\left({\max\left\\{{k,\min\left\\{{\rho,1}\right\\}k\cdot\text{Training
time}}\right\\}}\right)$.

###### Proof of 7.

The total runtime of Algorithm 3 is the time for verification plus the runtime
for recomputation, whenever a recompute is triggered. The recomputation time
is just the training time, and in the model considered, excepted cost of one
recomputation takes $O\left({Tm\left({\mathfrak{G}+d}\right)}\right)$ time,
since at every iteration, $m$ gradients are computed and vectors added. As
discussed in Appendix D, the expected verification time for Algorithm 3 is
$O(1)$. From Proposition 3, the unlearning Algorithm 3 recomputes with
probability $O(\min\left\\{{\rho,1}\right\\})$ for one edit request.
Therefore, using Proposition 6 which bounds the number of recomputes, we have
that the expected total runtime is bounded as
$kO(1)+4k\min\left\\{{\rho,1}\right\\}\cdot
O\left({Tm\left({\mathfrak{G}+d}\right)}\right)\leq
O\left({\max\left({1,\min\left\\{{\rho,1}\right\\}Tm\left({\mathfrak{G}+d}\right)}\right)k}\right)$.
For a sufficiently large $\rho$, the unlearning time of Algorithm 3 is clearly
dominated by the training time. In particular, in the corresponding batch
Algorithm 1, we set $m=\frac{\rho n}{T}$, giving a total runtime of
$O\left({\max\left({1,\min\left\\{{\rho^{2},1}\right\\}n\left({\mathfrak{G}+d}\right)}\right)k}\right)$.
Hence for $\rho\gtrsim\frac{1}{\sqrt{n(\mathfrak{G}+d})}$, the total runtime
in expectation is at most $O(\min\left\\{{\rho,1}\right\\}\cdot
k\cdot\text{Training time})$. In the other case, the expected total runtime is
just $O(k)$. ∎

######  Claim 8.

The expected total unlearning runtime of Algorithm 4 for $k$ edit requests is
$O\left({\max\left\\{{k,\min\left\\{{\rho\sqrt{T},1}\right\\}\cdot
k\cdot\text{Training time}}\right\\}}\right)$.

###### Proof of 8.

As before, the total runtime of Algorithm 3 is the time for verification plus
the runtime for recomputation, whenever a recompute is triggered. As discussed
in Appendix D, the expected verification time for Algorithm 4 is
$O\left({\frac{Tm(\mathfrak{G}+d)}{n}}\right)$. The recomputation in this case
may be partial but it also includes a reflection. The reflection operation
with $d$ dimensional vectors takes $O(d)$ compute. Furthermore, we upper bound
the partial recomputation time by worst-case full recomputation time, giving a
recomputation time $O\left({Tm\left({\mathfrak{G}+d}\right)}\right)$. From
Lemma 5, we have that the unlearning coupling is not maximal but recomputes
with probability $\min\left\\{{\rho\sqrt{T},1}\right\\}$. Finally, by
Proposition 6 we have that the expected total runtime is bounded as
$kO\left({Tm\left({\mathfrak{G}+d}\right)}\right)+4k\min\left\\{{\rho\sqrt{T},1}\right\\}\cdot
O\left({\frac{Tm(\mathfrak{G}+d)}{n}}\right)\leq
O\left({\max\left({\min\left\\{{\rho\sqrt{T},1}\right\\},\frac{1}{n}}\right)kmT(\mathfrak{G}+d)}\right)$.
In contrast, for Algorithm 4, the runtime is at most
$O\left({\max\left({\min\left\\{{\rho\sqrt{T},1}\right\\},\frac{1}{n}}\right)kmT(\mathfrak{G}+d)}\right)$.
Our lower bounds will show that we need $\rho\gtrsim\frac{1}{n}$ to get any
non-trivial accuracy. Therefore the maximum is always obtained by
$\min\left\\{{\rho\sqrt{T},1}\right\\}$. Moreover, $k$ is a trivial lower
bound on runtime, since we need to observe all $k$ edit requests. Hence, we
get that the total runtime in expectation, is at most
$O\left({\max\left\\{{k,\min\left\\{{\rho\sqrt{T},1}\right\\}\cdot
k\cdot\text{Training time}}\right\\}}\right)$. ∎

###  D.3 Space complexity

In this work, the objective was not to optimize the memory used, but rather,
to study if the problem can be solved computationally efficiently, no matter
how much (reasonable) memory the algorithm uses. However, we discuss, in this
section, that the space complexities of the proposed algorithms, which we will
see, is arguably, reasonably small. We ignore the space used to store the
dataset. In both algorithms, we save a hash-table of iterations to samples -
since we do $T$ iterations with $m$ samples each, this takes space of $O(Tm)$
words. We also store all the iterates, which are $d$-dimensional vectors, so
this takes a space of $O(dT)$ words. Finally, we also store a dictionary of
iterations to models, which takes $O(T)$ space. The space complexity therefore
is $O(T(\max\left\\{{m,d}\right\\})$. Plugging in the values of $T$, we get
the following.

##### Algorithm 1:

Plugging $T\leq\frac{\rho n}{m}$ from Proposition 1, we get space complexity =
$O\left({\rho n\max\left\\{{1,\frac{d}{m}}\right\\}}\right)$. As remarked in
Section 5.1.1, we can improve the space complexity by not requiring to save
all the iterates and yet have the same unlearning runtime. In the proof of 7,
we upper bound the recomputation time by a _full_ re-computation time - this
means that the upper bound on unlearning runtime holds even if the algorithm
does full retraining everytime verification fails. The unlearning Algorithm 3
can thus be modified as follows: for deletion, instead of continue retraining
from iteration $t$ where the deleted point participates, we can just do _full_
retraining, with fresh randomness for all mini-batches. For insertion, note
that when if condition is met (line 6 in Algorithm 3), we use the iterate
$\mathrm{w}_{t}$ to compute the gradient on the inserted point (line 8 in
Algorithm 3); however, if we don’t save $\mathrm{w}_{t}$, we can just compute
it on the fly by doing a full retraining with the same old mini-batches. After
$\mathrm{w}_{t}$ is computed, we just continue as in Algorithm 3.

With the above modification, we only need to save a hash-table of used samples
to binary values which correspond to whether they were used or not, which
takes $O(Tm)$ words, and a $d$ dimensional model. Hence, the space complexity
of Algorithm 3 is $O(Tm+d)$ words.

##### Algorithm 2:

From Proposition 2, note that if $m\leq O(T^{3})$, $T=\frac{\rho n}{md}$, and
therefore, $dT=\frac{\rho n}{m}$. If we use the largest mini-batch size
$m=O(T^{3})$, then $T=\sqrt{\frac{\rho n}{\sqrt{d}}}$, and hence
$dT=d^{3/4}\sqrt{\rho n}$. Therefore, the space complexity is
$O(T\max\left\\{{m,d}\right\\})\leq O\left({\max\left\\{{\frac{(\rho
n)^{2}}{d},d^{3/4}\sqrt{\rho n}}\right\\}}\right)$ words.

##  Appendix E Other algorithms and batch unlearning

To demonstrate the generality of our framework, we give two more algorithms.
The first is _noisy-m-SGD_ which is the same as Algorithm 2 but without
acceleration, and the second is _quantized-m-SGD_ , based on randomized
quantization. We note that both algorithms have worse theoretical guarantees
than Algorithm 2, however the first establishes our claim that acceleration is
beneficial, whereas the second shows how a previous work of [17] for $k$-means
clustering, can, not only be seen as a special case of our framework, but also
extended to general convex risk minimization problems. Moreover, in the second
case, we consider a more general setup of _batch_ edit requests, and show that
our techniques are flexible enough to easily generalize to the batch variant.

###  E.1 _noisy-m-SGD_

Algorithm 5 _noisy-m-SGD_($\mathrm{w}_{t_{0}},t_{0}$)

0: Initial model $\mathrm{w}_{t_{0}}$, data points
$\left\\{{\mathrm{z}_{1},\ldots,\mathrm{z}_{n}}\right\\}$, $T,\eta,m$

1: $\mathrm{w}_{0}=0$

2: for $t=t_{0},t_{0}+1,\ldots,T$ do

3: Sample mini-batch $b_{t}$ of size $m$ uniformly randomly

4: $\mathrm{g}_{t}=\frac{1}{m}\sum_{j\in b_{t}}\nabla
f(\mathrm{w}_{t},\mathrm{z}_{j})$

5: Sample $\theta_{t}\sim{\mathcal{N}}(0,\sigma^{2}{\mathbb{I}}_{d})$

6:
$\mathrm{w}_{t+1}={\mathcal{P}}\left({\mathrm{w}_{t}-\eta\left({\mathrm{g}_{t}+\theta_{t}}\right)}\right)$

7: Save($b_{t},\theta_{t},\mathrm{w}_{t},\mathrm{g}_{t}$)

8: end for

8: $\widehat{\mathrm{w}}_{S}=\frac{1}{T}\sum_{t=1}^{T+1}\mathrm{w}_{t}$

######  Proposition 7.

Let $f(.,\mathrm{z})$ be an $L$-smooth $G$-Lipschitz convex function $\forall\
\mathrm{z}$. Algorithm 5, run with
$t_{0}=1,\eta=\min\left\\{{\frac{1}{2L},\frac{D}{\left({\frac{G}{\sqrt{m}}+\sigma}\right)\sqrt{T}}}\right\\}$,
$\sigma=\frac{8\sqrt{T}G}{n\rho}$, and $T\geq\frac{(\rho n)^{2}}{16m^{2}}$
outputs $\widehat{\mathrm{w}}_{S}$ which is $\min\left\\{{1,\rho}\right\\}$-TV
stable and satisfies
$\mathbb{E}{\widehat{F}_{S}(\widehat{\mathrm{w}}_{S})-\widehat{F}_{S}(\mathrm{w}^{*}_{S})}\lesssim\frac{GD\sqrt{d}}{\rho
n}$

###### Proof of Proposition 7.

The $TV$-stability guarantee of $\rho=\frac{8\sqrt{T}G}{n}$ follows exactly as
in the proof of Proposition 2. We now proceed to the accuracy guarantee, which
follows simply by guarantee of SGD on smooth convex functions. We have already
shown in Proposition 2 that the gradients are unbiased and its variance
bounded by $\frac{2G^{2}}{m}+\frac{2G^{2}}{m}+\sigma^{2}d$.

Therefore, using Theorem 4.1 in [3] with step-size $\eta\leq\frac{1}{2L}$, we
have

$\displaystyle\mathbb{E}{\widehat{F}(\widehat{\mathrm{w}})-\widehat{F}(\mathrm{w}^{*})}\leq
O\left({2\eta{\mathcal{V}}^{2}+\frac{D^{2}}{\eta
T}}\right)=O\left({2\eta\left({\frac{2G^{2}}{m}+\sigma^{2}d}\right)+\frac{D^{2}}{\eta
T}}\right)$

Let $\tilde{G}^{2}=\frac{2G^{2}}{m}+\sigma^{2}d$, balancing the trade-off in
$\eta$ gives us $\eta=\frac{D}{\tilde{G}\sqrt{T}}$. Therefore setting
$\eta=\min\left\\{{\frac{1}{2L},\frac{D}{\tilde{G}\sqrt{T}}}\right\\}$ gives
us

$\displaystyle\mathbb{E}{\widehat{F}(\widehat{\mathrm{w}})-\widehat{F}(\mathrm{w}^{*})}$
$\displaystyle\leq
O\left({\frac{LD^{2}}{T}+\frac{\tilde{G}D}{\sqrt{T}}}\right)\leq
O\left({\frac{LD^{2}}{T}+\frac{GD}{\sqrt{Tm}}+\frac{\sigma\sqrt{d}D}{\sqrt{T}}}\right)$
$\displaystyle\leq
O\left({\frac{LD^{2}}{T}+\frac{GD}{\sqrt{Tm}}+\frac{GD\sqrt{d}}{n\rho}}\right)$

Finally, the condition in the sub-sampling amplification
$\frac{8G^{2}}{m^{2}\sigma^{2}}\leq 1.256$ again becomes
$T\geq\frac{(n\rho)^{2}}{16m^{2}}$. ∎

We now show that Algorithm 5 achieves the same upper bound on excess empirical
risk as Algorithm 2.

######  Corollary 2.

Let $f(.,\mathrm{z})$ be an $L$-smooth $G$-Lipschitz convex function $\forall\
\mathrm{z}$. Algorithm 5, run with
$m\geq\min\left\\{{\frac{d}{16},\frac{1}{4}\left({\frac{(\rho
n)G\sqrt{d}}{LD}}\right)^{1/2}}\right\\}$,
$\eta=\min\left\\{{\frac{1}{2L},\frac{D}{\left({\frac{G}{\sqrt{m}}+\sigma}\right)\sqrt{T}}}\right\\}$,
$\sigma=\frac{8\sqrt{T}G}{n\rho}$, and $T=\max\left\\{{\frac{(\rho
n)^{2}}{md},\frac{LD\rho n}{G\sqrt{d}}}\right\\}$ outputs
$\widehat{\mathrm{w}}_{S}$ which is $\rho$-TV stable and satisfies
$\mathbb{E}{\widehat{F}_{S}(\widehat{\mathrm{w}}_{S})-\widehat{F}_{S}(\mathrm{w}^{*}_{S})}\lesssim\frac{GD\sqrt{d}}{\rho
n}$

###### Proof of Corollary 2.

We start with the result in Proposition 7. Note that as long as
$\frac{GD}{\sqrt{mT}}\gtrsim\frac{LD^{2}}{T}\iff m\lesssim\frac{TG^{2}}{LD}$,
the second term is larger than the first. We balance the two trade-offs in
$T$. Optimizing the trade-off between second and third term gives us
$\frac{GD}{\sqrt{mT}}=\frac{GD\sqrt{d}}{\rho n}\iff T=\frac{(\rho
n)^{2}}{md}$; and optimizing the second trade-off gives us
$\frac{\sqrt{d}}{\rho n}=\frac{LD^{2}}{T}\iff T=\frac{LD^{2}(\rho
n)}{\sqrt{d}}$. Hence setting $T=\max\left({\frac{(\rho
n)^{2}}{md},\frac{LD^{2}(\rho n)}{\sqrt{d}}}\right)$ yields an expected excess
empirical risk of $O\left({\frac{GD\sqrt{d}}{n\rho}}\right)$.

We now look at the condition $T\geq\frac{(n\rho)^{2}}{16m^{2}}$ given in
Proposition 7, with $T$ set as $T=\max\left({\frac{(\rho
n)^{2}}{md},\frac{LD^{2}(\rho n)}{\sqrt{d}}}\right)$. We therefore require
$\frac{(\rho n)^{2}}{md}\geq\frac{(\rho n)^{2}}{16m^{2}}\iff
m\geq\frac{d}{16}$, as well as $\frac{LD(\rho n)}{G\sqrt{d}}\geq\frac{(\rho
n)^{2}}{16m^{2}}\iff m\geq\frac{1}{4}\left({\frac{(\rho
n)G\sqrt{d}}{LD}}\right)^{1/2}$ \- this recovers the condition
$m\geq\min\left\\{{\frac{d}{16},\frac{1}{4}\left({\frac{(\rho
n)G\sqrt{d}}{LD}}\right)^{1/2}}\right\\}$ in the Proposition statement. Hence,
combining all the above arguments, we get that for any
$m\geq\min\left\\{{\frac{d}{16},\frac{1}{4}\left({\frac{(\rho
n)G\sqrt{d}}{LD}}\right)^{1/2}}\right\\}$ , setting
$T=\max\left\\{{\frac{(\rho n)^{2}}{md},\frac{LD(\rho
n)}{G\sqrt{d}}}\right\\}$, yields an expected excess empirical risk of
$O\left({\frac{GD\sqrt{d}}{n\rho}}\right)$. ∎

Algorithm 6 Unlearning for _noisy-m-SGD_

0: Delete point with index $j$ or insert $\mathrm{z}$ (with index $n+1$) for
_noisy-m-SGD_

1: for $t=1,2\ldots,T$ do

2: Load$\left({\theta_{t},\mathrm{w}_{t},b_{t},\mathrm{g}_{t})}\right)$

3: if deletion and $j\in b_{t}$ then

4: Sample $i\sim\text{Uniform}([n]\backslash b_{t})$

5: $\mathrm{g}_{t}^{\prime}=\mathrm{g}_{t}-\frac{1}{m}\left({\nabla
f(\mathrm{w}_{t},\mathrm{z}_{j})-\nabla
f(\mathrm{w}_{t},\mathrm{z}_{i})}\right)$

6:
Save($\mathrm{g}_{t}^{\prime},b_{t}\backslash\left\\{{j}\right\\}\cup\left\\{{i}\right\\}$)

7: else if insertion and Bernoulli$\left({\frac{m}{n+1}}\right)$ then

8: Sample $i\sim\text{Uniform}(b_{t})$

9: $\mathrm{g}_{t}^{\prime}=\mathrm{g}_{t}-\frac{1}{m}\left({\nabla
f(\mathrm{w}_{t},\mathrm{z}_{i})-\nabla f(\mathrm{w}_{t},\mathrm{z})}\right)$

10:
Save($\mathrm{g}_{t}^{\prime},b_{t}\backslash\left\\{{i}\right\\}\cup\left\\{{n+1}\right\\}$)

11: else

12: continue

13: end if

14: $\xi_{t}=\mathrm{g}_{t}+\theta_{t}$

15: if
Uniform$\left({0,1}\right)\geq\frac{\phi_{{\mathcal{N}}(\mathrm{g}_{t}^{\prime},\sigma^{2}{\mathbb{I}})}(\xi_{t})}{\phi_{{\mathcal{N}}(\mathrm{g}_{t},\sigma^{2}{\mathbb{I}})}(\xi_{t})}$
then

16:
$\xi^{\prime}_{t}=\text{reflect}(\xi_{t},\mathrm{g}_{t}^{\prime},\mathrm{g}_{t})$

17: $\mathrm{w}_{t+1}=\mathrm{w}_{t}-\eta\xi_{t}^{\prime}$

18: $\text{Save}(\xi^{\prime}_{t})$

19:  _noisy-m-SGD( $\mathrm{w}_{t+1},t+1$)_ // Continue retraining, on current
dataset

20: break

21: end if

22: end for

######  Remark 5.

The choice of $T$ in Proposition 2 yields that the largest mini-batch size
that can be set, without hurting runtime, is $m=\frac{\rho nG}{\sqrt{d}LD}$.
Furthermore, the condition
$m\geq\min\left\\{{\frac{d}{16},\frac{1}{4}\left({\frac{(\rho
n)G\sqrt{d}}{LD}}\right)^{1/2}}\right\\}$ becomes
$T\geq\left({\frac{\sqrt{d}LD}{4G}}\right)^{2}$.

We now state and prove the main theorem for this section.

######  Theorem 4.

Let $f(\cdot,\mathrm{z})$ be an $L$-smooth $G$-Lipschitz convex function
$\forall\ \mathrm{z}$. For any $\frac{1}{n}\leq\rho\leq 1$, using Algorithm 5
as the learning algorithm and Algorithm 6 as its unlearning algorithms, then
given a stream of edit requests,

  1. 1.

Satisfies exact unlearning at every point in the stream.

  2. 2.

At time $i$ in the stream of edit requests, outputs
$\widehat{\mathrm{w}}_{S^{i}}$, such that if
$\left({\frac{L^{1/2}D^{2}\sqrt{d}}{G(\rho
n)}}\right)^{2/3}\leq\frac{GD}{\sqrt{\rho n}}$, then its with excess empirical
risk bounded as,

$\displaystyle\mathbb{E}{\widehat{F}_{S}(\widehat{\mathrm{w}}_{S^{i}})-\widehat{F}_{S}(\mathrm{w}_{S^{i}}^{*})}\lesssim\left({\frac{L^{1/2}D^{2}\sqrt{d}}{G(\rho
n)}}\right)^{2/3}$

  3. 3.

For $k$ edit requests, the expected total unlearning runtime is
$O(\max\left\\{{\rho k\cdot\text{Training time},k}\right\\})$

###### Proof of Theorem 4.

We proceed as in the proof of Theorem 1. For any $0<\tilde{\rho}\leq 1$, from
Proposition 7, the output $\widehat{\mathrm{w}}_{S}$ is $\tilde{\rho}$-TV
stable, and the excess empirical risk using Algorithm 5 on a dataset $S$ on
$n$ points, is bounded as,

$\displaystyle\mathbb{E}\widehat{F}_{S}(\widehat{\mathrm{w}}_{S})-\widehat{F}_{S}(\mathrm{w}^{*}_{S})\leq
O\left({\frac{LD^{2}}{T}+\frac{GD}{\sqrt{Tm}}+\frac{GD\sqrt{d}}{n\tilde{\rho}}}\right)$

It can be easily verified that Proposition 4 and Proposition 4 still holds for
_noisy-m-SGD_ , which gives us that the algorithm satisfies exact unlearning
at every time in the stream, proving the first part of the claim, Moreover,
its recompute probability bounded by $O(\tilde{\rho}k\sqrt{T})$ and therefore
the unlearning runtime bounded by
$O(\max\left\\{{k,\tilde{\rho}k\sqrt{T}\cdot\text{Training time}}\right\\}$.
Substituting $\tilde{\rho}=\frac{\rho}{\sqrt{T}}$, and using the largest mini-
batch size $m=\left({\frac{G}{LD}}\right)^{2}T$, the upper bound on excess
empirical risk becomes $\frac{LD^{2}}{T}+\frac{GD\sqrt{d}\sqrt{T}}{n\rho}$.
Optimizing the trade-off, we have $\frac{LD^{2}}{T}=\frac{LD^{2}}{T}\iff
T=\left({\frac{LD(\rho n)}{G\sqrt{d}}}\right)^{2/3}$, and the excess empirical
risk bound upper bound is
$\frac{LD}{T}=\left({\frac{L^{1/2}D^{2}\sqrt{d}}{G(\rho n)}}\right)^{2/3}$.
Note that this also proves the third part of the claim. Furthermore, as in the
proof of Theorem 1, it can be verified that the condition
$T\geq\frac{(\tilde{\rho}n)^{2}}{16m^{2}}$ is equivalent to
$\left({\frac{L^{1/2}D^{2}\sqrt{d}}{G(\rho
n)}}\right)^{2/3}\leq\frac{1}{\sqrt{\rho n}}$, which just means that the
excess empirical risk of _noisy-m-SGD_ is at most that of _sub-sample-GD_.
Finally, the upper bound holds for any point in the stream using the
assumption that the number of samples are between $\frac{n}{2}$ and $2n$,
thereby establishing the second claim. ∎

###  E.2 _quantized-m-SGD_

The work of [17] considers unlearning in $k$-means clustering. The key
algorithmic technique is randomized quantization of vectors to a
$\tau$-lattice. The intuition is that if the vector is an average of $n$ data
points which are bounded in norm, then upon changing one data point, the
vectors $O\left({\frac{1}{n}}\right)$ close. Therefore, if the lattice is
sufficiently coarse, then it would ensure that both are mapped up the same
point in the lattice. However, if we consider deterministic quantization, then
there exists points such that for any $\epsilon>0$, shifting the point by
$\epsilon$ changes the quantized point. Therefore, we first shift the lattice
by a uniformly random phase, which ensures that such a situation occurs with a
small probability.

In their application of $k$-means clustering, this vector is a cluster
centroid, which is an average of the data points in the cluster. We apply this
idea to convex risk minimization problems, wherein we quantize average
gradients, which by the Lipshcitzness assumption are bounded in norm.

We now introduce the quantization operation formally. Given a vector
$\mathrm{x}$, let
$\theta\sim\text{Unif}\left[-\frac{1}{2},-\frac{1}{2}\right]^{d}$, consider
the quantization given by:

$\displaystyle
Q_{\theta}(\mathrm{x})=\tau\left({\theta+\arg\min_{j\in\mathrm{Z}^{d}}\left({\mathrm{x}-\tau(\theta+j)}\right)}\right)$

We now state a result about the quantization operation.

######  Lemma 6.

Let $B_{\delta}(\mathrm{u})$ denote the Euclidean call of radius $\delta$
centered at $\mathrm{u}$. The following holds for the quantization operation,

  1. 1.

For any $\mathrm{x}$, $\mathbb{E}{Q_{\theta}(\mathrm{x})}=\mathrm{x}$ and
$\mathbb{E}{\left\|{\mathrm{x}-\mathbb{E}{\mathrm{x}}}\right\|}^{2}\leq\tau^{2}d$

  2. 2.

For any vector $\mathrm{u}$, $\mathbb{P}\left[{\exists\mathrm{v}\in
B_{\delta}(\mathrm{u}):Q_{\theta}(\mathrm{u})\neq\mathrm{Q}_{\theta}(\mathrm{v})}\right]\leq\frac{2d\delta}{\tau}$

###### Proof of Lemma 6.

Note that for a given $\mathrm{x}$,
$\mathrm{Q}_{\theta}(\mathrm{x})\sim\text{Unif}\left[\mathrm{x}-\frac{\tau}{2},\mathrm{x}+\frac{\tau}{2}\right]^{d}$,
hence $\mathbb{E}{Q_{\theta}(\mathrm{w})}=\mathrm{w}$. Furthermore, since
$\mathrm{w}-\mathbb{E}{\mathrm{w}}\sim\text{Unif}\left[-\frac{\tau}{2},\frac{\tau}{2}\right]^{d}$,
we have
$\mathbb{E}{\left\|{\mathrm{w}-\mathbb{E}{\mathrm{w}}}\right\|}^{2}=d\mathbb{E}\left({\mathrm{w}_{1}-\mathbb{E}{\mathrm{w}_{1}}}\right)^{2}=\frac{d\tau^{2}}{12}$.
The second part of the claim is Lemma C.2 in [17]. ∎

To see why [17] is a special case of our framework, note that the total
variation distance between two random variables is at most the probability of
disagreement under _any_ coupling. [17] uses the same quantization randomness
(used for training) for verifying after the edit request - this corresponds to
a trivial coupling between the quantization randomness, hence the total
variation distance between the outputs is bounded by the upper bound on the
probability that the quantized points change (see Lemma 6). This establishes
that it is a TV stable method. Finally, as said before, using the same
quantization randomness corresponds to a trivial coupling, but can be shown to
be maximal since the probability distribution is uniform around the to-be-
quantized point. Therefore, we have that [17] uses a maximal coupling based
unlearning method.

##### Batch unlearning:

We consider a batch unlearning setup, wherein instead of observing an
insertion or deletion request, we observe a batch edit request with insertions
and deletions. We demonstrate that our general approach of coupling mini-batch
indices is flexible enough to handle this variant naturally. The batch
unlearning ideas and results extend to other algorithms: _noisy-m-A-SGD_ ,
_noisy-m-SGD_ and _subsample-GD_. We also note that the computational benefit
of batch unlearning as opposed to handling edits one by one is only a constant
factor, which at best is two.

We now discuss how we extend the randomized quantization idea to convex risk
minimization. In our learning algorithm _quantized-m-SGD_ , at each iteration,
we draw a mini-batch of $m$ samples, uniformly randomly from $n$ samples, use
it to compute the gradient on the previous iterate , quantize using a randomly
sampled phase, and update. Algorithm 8 implements the above procedure.

Algorithm 7 _quantized-m-SGD_

0: Initial model $\mathrm{w}_{1}$, data points
$\left\\{{\mathrm{z}_{1},\ldots,\mathrm{z}_{n}}\right\\}$,$T,\eta$

1: for $t=1,2\ldots,T$ do

2: Sample mini-batch $b_{t}$ of size $m$ uniformly randomly

3: Sample $\theta_{t}\sim\text{Unif}\left[-\frac{1}{2},\frac{1}{2}\right]^{d}$

4: $\mathrm{g}_{t}=\frac{1}{m}\sum_{j\in b_{t}}\nabla
f(\mathrm{w}_{t},\mathrm{z}_{j})$

5: $\mathrm{w}_{t+1}=\mathrm{w}_{t}-\eta
Q_{\theta_{t}}\left({\mathrm{g}_{t}}\right)$

6: Save($\theta_{t},\mathrm{w}_{t},b_{t},\mathrm{g}_{t}$)

7: end for

7: $\widehat{\mathrm{w}}_{S}=\frac{1}{T+1}\sum_{j=1}^{T+1}\mathrm{w}_{j}$

We first prove a lemma which bounds the total variation distance between
outputs generated by _quantized-m-SGD_ on arbitrarily differing datasets -
these can be thought of as arising after a batch edit request.

######  Lemma 7.

Let $S$ and $S^{\prime}$ be two datasets of $n$ and $n+k_{2}$ points
respectively, such that $S$ has $k_{1}$ points which differ from $S^{\prime}$
i.e. $\left|{S\backslash S^{\prime}}\right|=k_{1}$, therefore $S$ and
$S^{\prime}$ differ by $k_{1}+k_{2}$ points. Let
$\left\\{{\mathrm{w}_{j}}\right\\}_{j=1}^{T}$ and
$\left\\{{\mathrm{w}_{j}^{\prime}}\right\\}_{j=1}^{T}$ be iterates of
_quantized-m-SGD_ on datasets $S$ and $S^{\prime}$ respectively. The total
variation distance between distribution of average iterates
$\widehat{\mathrm{w}}_{S}$ and $\widehat{\mathrm{w}}_{S^{\prime}}$ is bounded
as,

$\displaystyle\text{TV}(\widehat{\mathrm{w}}_{S},\widehat{\mathrm{w}}_{S^{\prime}})\leq\frac{4GTd(k_{1}+k_{2})}{n\tau}$

###### Proof of Lemma 7.

Without loss of generality, we enumerate $S$ and $S^{\prime}$ into subsets as
follows: let $S_{1}$ and $S_{1}^{\prime}$ be the first $n-k_{1}$ elements of
$S$ and $S^{\prime}$ which are the same. Let $S_{2}$ and $S_{2}^{\prime}$ be
the next $k_{1}$ differing elements in $S$ and $S^{\prime}$ respectively.
Finally, let $S_{3}^{\prime}$ be the last $k_{2}$ elements of $S^{\prime}$.

We look at iteration $t$ of _quantized-m-SGD_ and fix the previous model
$\mathrm{w}_{t}=\mathrm{w}_{t}^{\prime}=\mathrm{w}$. We will now compute the
conditional total variation distance between $\mathrm{w}_{t+1}$ and
$\mathrm{w}_{t+1}^{\prime}$. Note that since the only randomness is in the
sub-sampling and quantization, we can compute the total variation distance
between sub-sampled quantized gradients on fixed $\mathrm{w}$ for both
datasets, and this will lower bound total variation distance between the
iterates $\mathrm{w}_{t+1}$ and $\mathrm{w}_{t+1}^{\prime}$ by data processing
inequality. Let $b^{(1)}$ and $b^{(2)}$ be a uniform sample of $m$ points from
datasets $S$ and $S^{\prime}$ respectively. For a fixed $\mathrm{w}$, let the
gradient on $S$ indexed by $b^{(1)}$ be denoted as
$\mathrm{g}_{b^{(1)}}^{S}(\mathrm{w})=\frac{1}{m}\sum_{j\in b^{(1)}}\nabla
f(\mathrm{w},\mathrm{z}_{j}^{S})$, and similarly for $S^{\prime}$. Let $P$ and
$Q$ denote the probability distribution of
$\mathrm{g}_{b^{(1)}}^{S}(\mathrm{w})$ and
$\mathrm{g}_{b^{(2)}}^{S^{\prime}}(\mathrm{w})$ respectively. We have the
following claim, which we will prove via mathematical induction on $k_{2}$:
for any measurable set $R$, for any $k_{2}$,
$\left|{P(R)-Q(R)}\right|\leq\frac{4Gdk_{1}}{n\tau}+\sum_{j=1}^{k_{2}}\frac{4Gd}{(n+j)\tau}$.

##### Base case 1: $\mathbf{k_{2}=0:}$

Firstly note that both $b^{(1)}\sim\text{Unif}([n],m)$ and
$b^{(2)}\sim\text{Unif}([n],m)$, and consider the trivial coupling
$b^{(1)}=b^{(2)}=b$, where $b\sim\text{Unif}([n],m)$, be a uniform sample of
$m$ points from $[n]$. We now use the fact that total variation distance is at
most the probability of disagreement for any coupling. This gives us that

$\displaystyle\text{TV}(Q_{\theta}(\mathrm{g}_{b^{(1)}}^{S}(\mathrm{w})),Q_{\theta}(\mathrm{g}_{b^{(2)}}^{S^{\prime}}(\mathrm{w}))\leq\mathbb{P}\left[{Q_{\theta}(\mathrm{g}_{b}^{S}(\mathrm{w}))\neq
Q_{\theta}(\mathrm{g}_{b}^{S^{\prime}}(\mathrm{w}))}\right]$

We will focus on upper bounding the right hand side. The proof follows by
using the quantization guarantee (Claim 6) combined amplification from
subsampling. Without loss of generality, assume that the first $k_{1}$ samples
in $S$ and $S^{\prime}$ are the ones that differ. Fix the random (uniform)
sample $b$ of indices - suppose for this fixed value of $b$, exactly $j$
differing data points are sampled. From $G$ Lipschitzness, and that we have
exactly $j$ differing data points,
$\left\|{\mathrm{g}_{b}^{S}(\mathrm{w})-\mathrm{g}_{b}^{S^{\prime}}(\mathrm{w})}\right\|\leq\frac{2Gj}{m}$.
Hence, applying Claim 6, we have that

$\mathbb{P}\left[{Q_{\theta}(\mathrm{g}_{b}^{S}(\mathrm{w}))\neq
Q_{\theta}(\mathrm{g}_{b}^{S^{\prime}}(\mathrm{w}))\Big{|}b\text{ producing
}j\text{ differing samples}}\right]\leq\frac{4Gdj}{\tau m}.$

We will now integrate with respect to the randomness in $b$ \- for this, we
need to calculate the probability that a sample of $b$ (uniform $m$ out of
$n$) produces exactly $j$ differing data points, call it $p(j)$. By direct
computation, we have that $p(j)=\frac{{k_{1}\choose j}{n-k_{1}\choose
m-j}}{{n\choose m}}$. Hence we have,

$\displaystyle\mathbb{P}\left[{Q_{\theta}(\mathrm{g}_{b}^{S}(\mathrm{w}))\neq
Q_{\theta}(\mathrm{g}_{b}^{S^{\prime}}(\mathrm{w}))}\right]$
$\displaystyle=\sum_{j=0}^{k_{1}}p(j)\mathbb{P}\left[{Q_{\theta}(\mathrm{g}_{b}^{S}(\mathrm{w}))\neq
Q_{\theta}(\mathrm{g}_{b}^{S^{\prime}}(\mathrm{w}))\Big{|}\ b\ \text{produces
}j\ \text{differing samples}}\right]$
$\displaystyle\leq\sum_{j=0}^{k_{1}}\frac{{{k_{1}}\choose j}{n-{k_{1}}\choose
m-j}}{{n\choose m}}\frac{4Gdj}{\tau m}=\frac{m{k_{1}}}{n}\frac{4Gd}{\tau
m}=\frac{4Gd{k_{1}}}{\tau n}$

where the second last equality is a consequence of Vandermonde’s identity, as
we show below. We need to show that $\sum_{j=0}^{k_{1}}\frac{{{k_{1}}\choose
j}{n-{k_{1}}\choose m-j}j}{{n\choose
m}}=\frac{m{k_{1}}}{n}\iff\sum_{j=0}^{k_{1}}{{k_{1}}\choose
j}{n-{k_{1}}\choose m-j}j=\frac{m{k_{1}}}{n}{n\choose m}={k_{1}}{n-1\choose
m-1}$. This holds because,

$\displaystyle\sum_{j=0}^{k_{1}}{{k_{1}}\choose j}{n-{k_{1}}\choose m-j}j$
$\displaystyle=\sum_{j=0}^{k_{1}}\frac{{k_{1}}}{j}{{k_{1}}-1\choose
j-1}{n-{k_{1}}\choose m-j}j={k_{1}}\sum_{j=0}^{k_{1}}{{k_{1}}-1\choose
j-1}{n-{k_{1}}\choose m-j}$
$\displaystyle={k_{1}}\sum_{j=0}^{{k_{1}}-1}{{k_{1}}-1\choose
j}{n-{k_{1}}\choose(m-1)-j}={k_{1}}{n-1\choose m-1}$

where in the second last equality, we re-indexed the sum which removes the
first element, but it was zero anyway, and the last equality follows from
Vandermonde’s identity.

##### Base case 2: $\mathbf{k_{2}=1:}$

In this case, $S^{\prime}$ has one more element that $S^{\prime}$ \- let this
point be denoted as $q$. In this case, the probability distribution using
$S^{\prime}$ has the form
$Q=\left({1-\frac{m}{n+1}}\right)Q_{1}+\frac{m}{n+1}Q_{2}$, where $Q_{1}$ is
the probability distribution conditioned on the event that $q$ is sub-sampled,
and $Q_{2}$ is the probability distribution conditioned on the complementary
event. For any measurable set $R$, we have,

$\displaystyle\left|{P(R)-Q(R)}\right|=\left|{\left({1-\frac{m}{n+1}}\right)Q_{1}(R)+\frac{m}{n+1}Q_{2}(R)-P(R)}\right|$

Note that $Q_{1},Q_{2}$ and $P$ are all probability distributions over $n$
elements. Furthermore, $P$ and $Q_{1}$ are probability distributions over
$k_{1}$ differing elements, therefore we can use base case $k_{2}=0$ to get
that $\left|{P(R)-Q_{1}(R)}\right|\leq\epsilon_{1}:=\frac{4Gdk_{1}}{n\tau}$.
We therefore get,

$\displaystyle\left|{P(R)-Q(R)}\right|$
$\displaystyle\leq\left|{\left({1-\frac{m}{n+1}}\right)Q_{1}(R)+\frac{m}{n+1}Q_{2}(R)-Q_{1}(R)+\epsilon_{1}}\right|$
$\displaystyle=\left|{\frac{m}{n+1}\left({Q_{2}(R)-Q_{1}(R)}\right)+\epsilon_{1}}\right|$

Finally note that $Q_{1}$ and $Q_{2}$ are probability distributions over $n$
such that upon sub-sampling $m$ elements, there is exactly one differing
element, therefore we get,
$\left|{Q_{2}(R)-Q_{1}(R)}\right|\leq\frac{4Gd}{m\tau}$. We therefore have
that

$\displaystyle\left|{P(R)-Q(R)}\right|$
$\displaystyle\leq\frac{m}{n+1}\frac{4Gd}{m\tau}+\frac{4Gdk_{1}}{n\tau}=\frac{4Gd}{(n+1)\tau}+\frac{4Gdk_{1}}{n\tau}$

##### Induction Hypothesis:

Suppose the following holds for $k_{2}\leq\tilde{k}$: for any measurable set
$R$,
$\left|{P(R)-Q(R)}\right|\leq\frac{4Gdk_{1}}{n\tau}+\sum_{j=1}^{\tilde{k}}\frac{4Gd}{(n+j)\tau}$.

##### Induction Step: $k_{2}=\tilde{k}+1$

Let the _last_ element of $S^{\prime}$ be $q$. As in the base case, we
decompose the distribution $Q$ into a mixture of two components based on
whether $q$ is sampled or not. We have
$Q=\left({1-\frac{m}{n+\tilde{k}+1}}\right)Q_{1}+\frac{m}{n+\tilde{k}+1}Q_{2}$.
Note that $Q_{1}$ is a probability distribution which does not use the last
element of $S^{\prime}$. Therefore we can use Induction hypothesis which gives
us that
$\left|{Q_{1}(R)-P(R)}\right|\leq\frac{4Gdk_{1}}{n\tau}+\sum_{j=1}^{\tilde{k}}\frac{4Gd}{(n+j)\tau}$.
We therefore get,

$\displaystyle\left|{P(R)-Q(R)}\right|$
$\displaystyle=\left|{P(R)-\left({1-\frac{m}{n+\tilde{k}+1}}\right)Q_{1}(R)-\frac{m}{n+\tilde{k}+1}Q_{2}(R)}\right|$
$\displaystyle\leq\left|{\frac{m}{n+\tilde{k}+1}\left({Q_{1}(R)-Q_{2}(R)}\right)+\frac{4Gdk_{1}}{n\tau}+\sum_{j=1}^{\tilde{k}}\frac{4Gd}{(n+j)\tau}}\right|$
$\displaystyle\leq\left|{\frac{m}{n+\tilde{k}+1}\frac{4Gd}{m\tau}+\frac{4Gdk_{1}}{n\tau}+\sum_{j=1}^{\tilde{k}}\frac{4Gd}{(n+j)\tau}}\right|$
$\displaystyle=\frac{4Gdk_{1}}{n\tau}+\sum_{j=1}^{\tilde{k}+1}\frac{4Gd}{(n+j)\tau}$

where in the last inequality, as in the base case, we used that fact that
distributions $Q_{1}$ and $Q_{2}$ differ because in one we subsample the last
element where as in the other we don’t, so from Claim 6, for two data sets of
size $m$ differing in one element, the failure probability is
$\frac{4Gd}{m\tau}$. This completes the induction argument. We bound the sum
simply as $\sum_{j=1}^{k_{2}}\frac{4Gd}{(n+j)\tau}\leq\frac{4Gdk_{2}}{n\tau}$,
which gives us that the whole term is bounded by
$\frac{4Gd(k_{1}+k_{2})}{n\tau}$.

The above, by an application of data processing inequality, shows that the
conditional TV distance between $\mathrm{w}_{t+1}$ and
$\mathrm{w}_{t+1}^{\prime}$ is at most $\frac{4Gd(k_{1}+k_{2})}{n\tau}$. Note
that the upper bound holds uniformly over all conditioning events. Moreover,
from the maximal coupling characterization of TV distance, we have that for
any coupling of $\mathrm{w}_{t+1}$ and $\mathrm{w}_{t+1}^{\prime}$, the
conditional probability of disagreement is at most
$\frac{4Gd(k_{1}+k_{2})}{n\tau}$. Consider the coupling which just
concatenates all these couplings, then an application of union bound over the
$T$ iterates, the joint probability of disagreement under this coupling is at
most $\frac{4Gd(k_{1}+k_{2})T}{n\tau}$ which gives us our upper bound on TV
distance between joint iterates. Finally, by data processing inequality, the
same upper bound holds for the average iterates which finishes the proof. ∎

We now establish the guarantees on the learning Algorithm 7. To handle batch
edit request, we extend the notion of exact unlearning with one edit request
to batch request: we term it exact batch unlearning. We similarly also extend
$\rho$-TV-stability to $(k_{1},k_{2},\rho)$-TV stability, which is $\rho$-TV
stability under arbitrary $k_{1}$ deletions and $k_{1}+k_{2}$ insertions, as
well as $k_{1}$ insertions and $k_{1}+k_{2}$ deletions.

######  Proposition 8.

Let $f(.,\mathrm{z})$ be an $L$-smooth $G$-Lipschitz convex function $\forall\
\mathrm{z}$. Algorithm 5, run with
$\eta=\min\left\\{{\frac{1}{2L},\frac{D}{\left({\frac{G}{\sqrt{m}}+\tau\sqrt{d}}\right)\sqrt{T}}}\right\\}$,
$\tau=\frac{4GdT}{\rho n}$, and $T=\max\left\\{{\frac{(\rho
n)}{d^{3/2}\sqrt{m}},\left({\frac{LD(\rho
n)}{Gd^{3/2}}}\right)^{2/3}}\right\\}$ outputs $\widehat{\mathrm{w}}_{S}$
which is $(k_{1},k_{2},(k_{1}+k_{2})\rho)$-TV stable and satisfies
$\mathbb{E}{\widehat{F}_{S}(\widehat{\mathrm{w}}_{S})-\widehat{F}_{S}(\mathrm{w}^{*}_{S})}\lesssim\left({\frac{\sqrt{L}GD^{2}d^{3/2}}{\rho
n}}\right)^{2/3}$.

###### Proof of Proposition 8.

The $(k_{1},k_{2},(k_{1}+k_{2})\rho)$-TV stability guarantee follows from
Lemma 7 by taking a supremeum over all datasets $S$ and $S^{\prime}$ of sizes
$n$ and $n+k_{2}$ (or $n-k_{2})$ to get that that TV stability is uniformly
upper bound by $\frac{4GTd(k_{1}+k_{2})}{n\tau}=(k_{1}+k_{2})\rho$, where the
equality follows upon setting $\tau=\frac{4GdT}{\rho n}$. For the excess
empirical risk bound, we use the guarantee on excess empirical risk of SGD on
smooth convex functions (for example, Theorem 4.1 from [3]), combined with the
fact in Lemma 6 that quantization produces unbiased estimates of the gradient
with bounded variance
${\mathcal{V}}^{2}\leq\frac{2G^{2}}{m}+\tau^{2}d=\frac{2G^{2}}{m}+\frac{16G^{2}d^{3}T^{2}}{(\rho
n)^{2}}$. Therefore, choosing step size $\eta\leq\frac{1}{2L}$, we get

$\displaystyle\mathbb{E}{\widehat{F}_{S}(\widehat{\mathrm{w}}_{S})-\widehat{F}_{S}(\mathrm{w}^{*}_{S})}\leq
O\left({2\eta{\mathcal{V}}^{2}+\frac{D^{2}}{\eta
T}}\right)=O\left({2\eta\left({\frac{2G^{2}}{m}+\frac{16G^{2}d^{3}T^{2}}{(\rho
n)^{2}}}\right)+\frac{D^{2}}{\eta T}}\right)$

Define $\tilde{G}^{2}=2\left({\frac{2G^{2}}{m}+\frac{16G^{2}d^{3}T^{2}}{(\rho
n)^{2}}}\right)$ and set
$\eta=\min\left\\{{\frac{1}{2L},\frac{D}{\tilde{G}\sqrt{T}}}\right\\}$, which
makes the upper bound

$\displaystyle\mathbb{E}{\widehat{F}_{S}(\widehat{\mathrm{w}}_{S})-\widehat{F}(\mathrm{w}^{*}_{S})}$
$\displaystyle\leq O\left({2\eta{\mathcal{V}}^{2}+\frac{D^{2}}{\eta
T}}\right)=O\left({\frac{LD^{2}}{T}+\frac{\tilde{G}D}{\sqrt{T}}}\right)$
$\displaystyle\leq
O\left({\frac{LD^{2}}{T}+\frac{GD}{\sqrt{Tm}}+\frac{GDd^{3/2}\sqrt{T}}{(\rho
n)}}\right)$

Balancing the trade-off between the las two terms gives us $T=\frac{(\rho
n)}{d^{3/2}\sqrt{m}}$. Similarly, balancing the trade-off between the first
and last term gives us $T=\left({\frac{LD(\rho n)}{Gd^{3/2}}}\right)^{2/3}$.
Hence setting $T=\max\left\\{{\frac{(\rho
n)}{d^{3/2}\sqrt{m}},\left({\frac{LD(\rho
n)}{Gd^{3/2}}}\right)^{2/3}}\right\\}$ gives us that the expected excess
empirical risk is bounded by $\left({\frac{\sqrt{L}GD^{2}d^{3/2}}{\rho
n}}\right)^{2/3}$ and completes the proof. ∎

######  Remark 6.

We see that the TV stability parameter above is $(k_{1}+k_{2})\rho$ as opposed
to $(k_{1}+2k_{2})\rho$ which is what we would obtain with $\rho$-TV stability
for one edit request and using the triangle inequality of TV distance (see
Remark 2).

######  Remark 7.

The largest mini-batch size, without hurting runtime, is
$m=\left({\frac{G}{LD}}\right)^{2}T=\left({\frac{G^{2}(\rho
n)}{(LD)^{2}d^{3/2}}}\right)^{2/3}$, which gives us $T=\left({\frac{LD(\rho
n)}{Gd^{3/2}}}\right)^{2/3}$.

We now proceed to unlearning. The unlearning algorithm (Algorithm 8) upon
observing an edit request comprising of both insertions and deletions, first
couples the mini-batch indices (described formally in the next paragraph), and
computes the gradient on the new mini-batch It then uses the _same_
quantization randomness as in training, and checks if the quantized point
changes. If it does, in any iteration, then it calls recompute. The use of the
same quantization randomness corresponds to a trivial coupling between the
quantization randomness. We explain the coupling procedure in detail below.

##### Batch coupling:

We setup some notation. Consider the training dataset $S$ and dataset realized
after the batch edit request $S^{\prime}$. Given a vector $\mathrm{w}$, let
$Q_{\theta_{1}}(\mathrm{g}_{b_{1}}^{S}(\mathrm{w}))$ denote the quantized
gradient vector where $\theta_{1}$ is the quantization randomness and $b_{1}$
is the mini-batching randomness on dataset $S^{\prime}$. Similarly,
$Q_{\theta_{2}}(\mathrm{g}_{b_{1}}^{S^{\prime}}(\mathrm{w}))$ denotes the
quantized vector with $\theta_{2}$ as the quantization randomness and $b_{2}$
as the mini-batching randomness on dataset $S^{\prime}$. We couple
$\theta_{1}$ and $\theta_{2}$ by considering the trivial coupling
$\theta_{1}=\theta_{2}$ i.e. the joint probability measure is defined only on
the diagonal of the product measure. To couple the mini-batch indices, we
consider two cases: if the training dataset $S$ has less more or more points
than $S^{\prime}$. For simplicity, Algorithm 8 is the pseudo-code
corresponding only to the first case.

In the first case, suppose $S$ has $n$ points and $S^{\prime}$ has $n+k_{2}$
points, realized after $k_{1}$ deletions and $k_{1}+k_{2}$ insertions. Without
loss of generality, order the two datasets as follows: the first $n-k_{1}$
points in $S$ and $S^{\prime}$ are the same, call these
$S_{1}=S_{1}^{\prime}$, next we have the last $k_{1}$ points of $S$, and
arbitrary $k_{1}$ points of $S^{\prime}$ \- call these $S_{2}$ and
$S^{\prime}_{2}$, and moreover let the mapping of indices from
$S_{2}\rightarrow S_{2}^{\prime}$ by denoted by $\iota$. Finally we have the
rest of $k_{2}$ points of $S^{\prime}$, call this $S_{3}^{\prime}$. In the
following discussion, and in Algorithm 8, when we consider elements of these
sets, we mean their indices. As before, let $\mu_{n,m}$ and $\mu_{n+k_{2},m}$
denote the probability measures correspondingly to sampling $m$ elements
uniformly from a discrete universe of size $n$ (i.e. $S$) and $n+k_{2}$ (i.e.
$S^{\prime}$) respectively. These sub-sampling measures are coupled in the
following way in Algorithm 8. We first sample $b^{(1)}\sim\mu_{n,m}$ (during
training). Let $b^{(1)}_{2}$ be the $m_{2}$ indices in $S_{2}$: replace these
by the corresponding indices in $S_{2}^{\prime}$ i.e. $\iota(b^{(1)}\cap
S_{2})$. Next, sample $b\sim\mu_{n+k_{2},m}$: let $b_{3}$ be the $m_{3}$
indices which are in $S_{3}^{\prime}$. We now resample
$b^{(2)}_{1}\sim\text{Unif}(b^{(1)},m_{3})$ \- these are indices used in
training, which are now to be replaced. Define
$b^{(2)}=\left({b^{(1)}\backslash\left\\{{b^{(1)}\cap
S_{2}}\right\\}\cup\left\\{{\iota(b^{(1)}\cap
S_{2})}\right\\}}\right)\backslash b^{(2)}_{1}\cup\left\\{{S_{3}^{\prime}\cap
b}\right\\}$. Let the distribution of $b^{(2)}$ produced in the above way be
denoted as $\mu^{\text{edit}}_{n,m}$. We now show that $(b^{(1)},b^{(2)})$ is
indeed a coupling of $\mu_{n,m}$ and $\mu_{n+k_{2},m}$.

######  Claim 9.

With the construction described above, we have that $b^{(1)}\sim\mu_{n,m}$ and
$b^{(2)}\sim\mu^{\text{edit}}_{n,m}=\mu_{n+k_{2},m}$.

###### Proof of 9.

$b^{(1)}\sim\mu_{n,m}$ follows trivially by construction. For the other part,
for any set $E$ of $m$ indices arising from the coupling construction, let
$E_{1}$ be the set of $m-m_{3}$ points from $S\cup S_{2}^{\prime}$ and $E_{2}$
be the set of $m_{3}$ points from $S_{3}^{\prime}$. Since these $m_{3}$ points
of $E_{2}$ need to be selected when sampling $b$, the probability of sampling
these points is $\frac{{n\choose m-m_{3}}}{{n+k_{2}\choose m}}$, where the
numerator denotes the number of ways to sample from $S^{\prime}\backslash
S_{3}^{\prime}$. For the points in $E_{1}$, these come from $b^{(1)}$ and
replacement using $S_{2}^{\prime}$ (which is a deterministic operation).
Hence, probability of $E_{1}$ is $\frac{{n-(m-m_{3})\choose m_{3}}}{{n\choose
m}}$, where the numerator denotes the number of ways to sample rest of
elements not in $E_{1}$ when sampling $b^{(1)}$. Finally, we need to consider
the re-sampling step i.e sampling $b^{(2)}_{1}$ \- note that the draw of
$E_{1}$ and $E_{2}$ fixes the set produced by this re-sampling, and thus its
probability is $\frac{1}{{m\choose m_{3}}}$. This gives us

$\displaystyle\mu^{\text{edit}}_{n,m}(E)$ $\displaystyle=\frac{{n\choose
m-m_{3}}}{{n+k_{2}\choose m}}\cdot\frac{{n-(m-m_{3})\choose m_{3}}}{{n\choose
m}}\cdot\frac{1}{{m\choose m_{3}}}$ $\displaystyle=\frac{1}{{n+k_{2}\choose
m}}\cdot\frac{n!(n-(m-m_{3}))!m!(n-m)!m_{3}!(m-m_{3})!}{(m-m_{3})!(n-(m-m_{3}))!m_{3}!(n-m)!n!m!}=\frac{1}{{n+k_{2}\choose
m}}=\mu_{n+k_{2},m}(E)$

∎

In the second case, $S$ has more samples than $S^{\prime}$ \- let number of
samples in $S$ be $n$, and in $S^{\prime}$ be $n-k_{2}$ and there $k_{1}$
samples in $S^{\prime}$ not in $S$. As before we order the sets as: let
$S_{1}=S_{1}^{\prime}$ be the $n-k_{2}-k_{1}$ samples which are the same in
both $S$ and $S^{\prime}$. Let $S_{2}$ be the next $k_{1}$ samples in $S$,
which correspond to $S_{2}^{\prime}$, the rest of $k_{1}$ samples in
$S^{\prime}$ \- the mapping from $S_{2}$ to $S_{2}^{\prime}$ being $\iota$.
Finally let $S_{3}$ be the rest of $k_{2}$ samples in $S$. We first sample
$b^{(1)}\sim\mu_{n,m}$ (during training). Let $b^{(1)}_{2}$ be the $m_{2}$
indices in $S_{2}$: replace these by the corresponding indices in
$S_{2}^{\prime}$ i.e. $\iota(b^{(1)}\cap S_{2})$. Let $b^{(1)}_{3}$ denote the
sub-sampled indices which are in the last $k_{2}$ indices of $S$, and let
$m_{3}=\left|{b^{(1)}_{3}}\right|$. We re-sample $m_{3}$ indices as
$b=\text{Unif}((S^{\prime}\backslash\iota(b^{(1)}\cap S_{2})\backslash
b^{(1)}),m_{3})$. Finally, define
$b^{(2)}=\left({b^{(1)}\backslash\left\\{{b^{(1)}\cap
S_{2}}\right\\}\cup\left\\{{\iota(b^{(1)}\cap
S_{2})}\right\\}}\right)\backslash b^{(1)}_{3}\cup b$. Let the distribution of
$b^{(2)}$ produced in the above way be denoted as $\mu^{\text{edit}}_{n,m}$.
We now show that $(b^{(1)},b^{(2)})$ is indeed a coupling of $\mu_{n,m}$ and
$\mu_{n-k_{2},m}$.

######  Claim 10.

With the construction described above, we have that $b^{(1)}\sim\mu_{n,m}$ and
$b^{(2)}\sim\mu^{\text{edit}}_{n,m}=\mu_{n-k_{2},m}$.

###### Proof of 10.

$b^{(1)}\sim\mu_{n,m}$ follows trivially by construction. For the other part,
let $E$ be a set of $m$ indices from $[n-k_{2}]$. Note that _any_ number of
points in $E$ can arise due to re-sampling (i.e. when sampling $b^{\prime}$),
hence we need to consider all such possibilities - let $m_{3}$ be the number
of indices in $E$ produced via re-sampling. Fixing one of ${m\choose m_{3}}$
combinations, the probability that it was re-sampled is
$\frac{1}{{n-k_{2}-(m-m_{3})\choose m_{3}}}$. From the rule of sum, the
probability that _any_ $m_{3}$ sized set was produced via re-sampling is
$\frac{{m\choose m_{3}}}{{n-k_{2}-(m-m_{3})\choose m_{3}}}$. For each such
set, it could arise from any of $m_{3}$ points from $k_{2}$, which gives us
${k_{2}\choose m_{3}}$ possibilities. The probability of choosing any such
set, when sampling $b^{(1)}$, is $\frac{{k_{2}\choose m_{3}}}{{n\choose m}}$.
We now combine these and apply the rule of sum on different choices of
$m_{3}$, from $0$ to $m$. We get,

$\displaystyle\mu^{\text{edit}}_{n,m}(E)$
$\displaystyle=\sum_{m_{3}=0}^{m}\frac{{m\choose
m_{3}}}{{n-k_{2}-(m-m_{3})\choose m_{3}}}\cdot\frac{{k_{2}\choose
m_{3}}}{{n\choose m}}$ $\displaystyle=\frac{1}{{n\choose
m}}\sum_{m_{3}=0}^{m}\frac{m!(n-k_{2}-m)!m_{3}!}{m_{3}!(m-m_{3})!(n-k_{2}-m+m_{3})!}{k_{2}\choose
m_{3}}$ $\displaystyle=\frac{1}{{n\choose
m}}\sum_{m_{3}=0}^{m}\frac{m!(n-k_{2}-m)!}{(n-k_{2})!}\cdot\frac{(n-k_{2})!}{(m-m_{3})!(n-K_{2}-(m-m_{3}))!}{k_{2}\choose
m_{3}}$ $\displaystyle=\frac{{n-k_{2}\choose m}}{{n\choose
m}}\sum_{m_{3}=0}^{m}{n-k_{2}\choose m-m_{3}}{k_{2}\choose
m_{3}}=\frac{{n-k_{2}\choose m}}{{n\choose m}}\cdot{n\choose
m}={n-k_{2}\choose m}=\mu_{n-k_{2},m}$

where the third last equality follows from Vandermonde’s identity. ∎

Algorithm 8 Batch unlearning for _quantized-m-SGD_

0: Edit request produces dataset $S^{\prime}$ of $n+k_{2}$ points, with
$k_{1}$ deletions and $k_{1}+k_{2}$ insertions; let $S_{1},S_{2}$ and
$S_{1}^{\prime},S_{2}^{\prime}$ and $S_{3}^{\prime}$ be partitions of $S$ and
$S^{\prime}$ respectively, as defined in “Batch coupling"

1: for $t=1,2\ldots,T$ do

2: Load($\theta_{t},\mathrm{w}_{t},b_{t},\mathrm{g}_{t}$)

3: $b\sim\text{Unif}(S^{\prime},m)$

4: $m_{3}=\left|{\left\\{{x\in S_{3}\cap b}\right\\}}\right|$

5: $b^{(2)}_{1}\sim\text{Unif}(b_{t},m_{3})$

6: $\mathrm{g}_{t}^{\prime}=\mathrm{g}_{t}-\frac{1}{m}\left({\sum\limits_{j\in
b_{t}\cap S_{2}}\nabla
f(\mathrm{w}_{t},\mathrm{z}_{j})+\sum\limits_{j\in\iota(b_{t}\cap
S_{2})}\nabla f(\mathrm{w}_{t},\mathrm{z}_{j})-\sum\limits_{j\in
b^{(2)}_{1}}\nabla f(\mathrm{w}_{t},\mathrm{z}_{j})+\sum\limits_{j\in
S_{3}\cap b}\nabla f(\mathrm{w}_{t},\mathrm{z}_{j})}\right)$

7: $b^{(2)}_{t}=\left({b_{t}\backslash\left\\{{b_{t}\cap
S_{2}}\right\\}\cup\left\\{{\iota(b_{t}\cap S_{2})}\right\\}}\right)\backslash
b^{(2)}_{1}\cup\left\\{{S_{3}^{\prime}\cap b}\right\\}$

8: Save($\mathrm{g}_{t}^{\prime},b^{(2)}_{t}$)

9: if $Q_{\theta_{t}}\left({\mathrm{g}_{t}}\right)\neq
Q_{\theta_{t}}\left({\mathrm{g}_{t}^{\prime}}\right)$ then

10:  _quantized-m-SGD_ // Recompute on current dataset

11: break

12: end if

13: end for

We now state the main result about unlearning.

######  Proposition 9.

(Algorithm 7, Algorithm 8) satisfies exact batch unlearning. Moreover, for $k$
batch edit requests, where the $i^{\text{th}}$ request comprises of
$k^{i}_{1}$ deletions and $k^{i}_{1}+k^{i}_{2}$ insertions, or $k^{i}_{1}$
insertions and $k^{i}_{1}+k^{i}_{2}$ deletions, Algorithm 8 recomputes with
probability at most $2\sum_{i=1}^{k}(k^{i}_{1}+k^{i}_{2})\rho$.

###### Proof of Proposition 9.

We consider one batch edit request of $k_{1}$ deletions and $k_{1}+k_{2}$
insertions (case 1) and $k_{1}$ insertions and $k_{1}+k_{2}$ deletions (case
2). We have that applications of Claims 9 and 9 give us that mini-batches are
transported, for cases 1 and 2 respectively. Moreover, since we consider a
trivial coupling of quantization randomness, we can consider it part of the
(randomized) algorithmic map. Therefore, as in the proof of Proposition 3,
transportation of mini-batches suffices to give us that Algorithm 8 satisfies
exact unlearning. Repeated application of the above generalizes it to
arbitrary $k$ edits. We now proceed to bound the probability of recompute
directly for a batch edit request. For a fixed model $\mathrm{w}$, and a fixed
iteration, we fix the mini-batches $(b^{(1)},b^{(2)})$ such that $b^{(1)}$ and
$b^{(2)}$ differ by $j$ indices. From Lemma 6, we have

$\displaystyle\mathbb{P}_{\theta,(b^{(1)},b^{(2)})}\left[Q_{\theta}(\mathrm{g}_{b^{(1)}}^{S}(\mathrm{w}))\neq
Q_{\theta}(\mathrm{g}_{b^{(2)}}^{S^{\prime}}(\mathrm{w}))|(b^{(1)},b^{(2)})\text{
such that }b^{(1)},b^{(2)}\text{ differ in }j\text{
indices}\right]\leq\frac{4Gdj}{m\tau}$

We now integrate over the conditioning event. To do this, we need to compute
the probability of the event that sampling $(b^{(1)},b^{(2)})$ generates $j$
differing indices - denote this as $p(j)$.

Since we have two case for coupling constructions, we consider each one by
one. We first look at the second case: from construction of the coupling, it
is easy to verify that $j$ differing indices can be produced when, for any
$i$, $b^{(1)}$ samples $i$ elements from the $k_{1}$ differing items and $j-i$
indices from the last $k_{2}$ indices, for any $i$ from $0$ to $j$. Hence, by
direct computation, we have

$\displaystyle p(j)=\sum_{i=0}^{j}\frac{{k_{1}\choose i}{k_{2}\choose
j-i}{n-(k_{1}+k_{2})\choose m-j}}{{n\choose m}}=\frac{{n-(k_{1}+k_{2})\choose
m-j}}{{n\choose m}}\sum_{i=0}^{j}{k_{1}\choose i}{k_{2}\choose
j-i}=\frac{{n-(k_{1}+k_{2})\choose m-j}{k_{1}+k_{2}\choose j}}{{n\choose m}}$

where the last equality follows from Vandermonde’s identity. Plugging this in
the following, we have,

$\displaystyle\mathbb{P}_{\theta,(b^{(1)},b^{(2)})}\left[Q_{\theta}(\mathrm{g}_{b^{(1)}}^{S}(\mathrm{w}))\neq
Q_{\theta}(\mathrm{g}_{b^{(2)}}^{S^{\prime}}(\mathrm{w}))\right]$
$\displaystyle=\sum_{j=0}^{k_{1}+k_{2}}p(j)\mathbb{P}_{\theta,(b^{(1)},b^{(2)})}\left[Q_{\theta}(\mathrm{g}_{b^{(1)}}^{S}(\mathrm{w}))\neq
Q_{\theta}(\mathrm{g}_{b_{2}}^{S^{\prime}}(\mathrm{w}))|b^{(1)},b^{(2)}\text{
differ in }j\text{ indices}\right]$
$\displaystyle\leq\sum_{j=0}^{k_{1}+k_{2}}\frac{{n-(k_{1}+k_{2})\choose
m-j}{k_{1}+k_{2}\choose j}}{{n\choose
m}}\frac{4Gdj}{m\tau}=\frac{m(k_{1}+k_{2})}{n}\frac{4Gd}{m\tau}$
$\displaystyle=\frac{4Gd(k_{1}+k_{2})}{n\tau}\leq\frac{k\rho}{T}$

where the second equality is a consequence of Vandermonde’s identity proved in
Lemma 7 (Base case $k_{2}=0$) and the last inequality follows by plugging in
$\tau=\frac{4GdT}{\rho n}$.

We now look at the first case (when $S$ is smaller than $S^{\prime}$), which
is slightly more involved. Let $i_{1}$ denote the number of indices in
$b^{(1)}\cap S_{1}$, and let $i_{2}$ be the number of indices in $b^{(2)}\cup
S_{3}^{\prime}$. Furthermore, since we resample $i_{2}$ indices from
$b^{(1)}$, let $i_{3}$ be the number of indices from $S_{1}$ which are re-
sampled. It can be verified that if $b^{(1)}$ and $b^{(2)}$ differ in $j$
indices, then we need to have $i_{1}+i_{3}=j$. This is because it can happen
that both $i^{(2)}$ is large, but upon re-sampling, it chooses elements from
$k_{1}$, which does not increase the number of different indices between
$b^{(1)}$ and $b^{(2)}$ Also, note that by construction $i_{3}\leq i_{2}\leq
j$. Hence the probability $p(j)$, by direct computation is,

$\displaystyle p(j)$
$\displaystyle=\sum_{i_{1},i_{2},i_{3}=0,i_{1}+i_{3}=j,i_{3}\leq i_{2}\leq
j}^{j}\frac{{k_{1}\choose i_{1}}{n-k_{1}\choose m-i_{1}}}{{n\choose
m}}\cdot\frac{{k_{2}\choose i_{2}}{n\choose m-i_{2}}}{{n+k_{2}\choose
m}}\cdot\frac{{i_{1}\choose i_{2}-i_{3}}}{{m\choose i_{2}}}$
$\displaystyle=\sum_{i_{1}=0}^{j}\sum_{i_{2}=j-i_{1}}^{j}\frac{{k_{1}\choose
i_{1}}{n-k_{1}\choose m-i_{1}}}{{n\choose m}}\cdot\frac{{k_{2}\choose
i_{2}}{n\choose m-i_{2}}}{{n+k_{2}\choose m}}\cdot\frac{{i_{1}\choose
i_{2}-(j-i_{1})}}{{m\choose i_{2}}}$

where in the second equality, we substituted $i_{3}=j-i_{1}$. We now claim
that $p(j)=\frac{{n-k_{1}\choose m-j}{k_{1}+k_{2}\choose j}}{{n+k_{2}\choose
m}}$, which we will argue via a double counting argument. Note that it
suffices to show that $\sum_{i_{1}=0}^{j}\sum_{i_{2}=j-i_{1}}^{j}{k_{1}\choose
i_{1}}{n-k_{1}\choose m-i_{1}}\cdot{k_{2}\choose i_{2}}{n\choose
m-i_{2}}\frac{{i_{1}\choose i_{2}-(j-i_{1})}}{{m\choose
i_{2}}}={n-k_{1}\choose m-j}{k_{1}+k_{2}\choose j}{n\choose m}$ . Consider set
$A$ of $n+k_{2}$ elements, composed of $A_{1}$ of $n-k_{1}$, $A_{2}$ of
$k_{1}$ and $A_{3}$ of $k_{2}$ elements, and a $B$ of $n$ elements, composed
of $B_{1}$ of $n-k_{1}$ and $B_{2}$ of $k_{1}$ elements. Note that the
expression ${n-k_{1}\choose m-j}{k_{1}+k_{2}\choose j}{n\choose m}$ is the
size of number of combinations of $2m$ elements, $m$ each from $A$ and $B$
such that the number of elements from $A_{2}\cup A_{3}$ is $j$. We will show
that the other expression also counts this set, via basic combinatorial rules.
For this, consider combinations of $m$ elements from $B$ $A_{3}$ and such that
we have $i_{2}$ elements from $A_{3}$ and the rest $m-i_{2}$ from $B$. Also,
consider combinations of $m$ elements from $A_{1}\cup A_{2}$ which consists of
$i_{1}$ elements from $A_{2}$ the rest from $A_{1}$. We now modify these as
follows, out of $m$ elements from $A$, select $i_{2}$ elements and replace
thse from elements from $A_{3}$ \- not that if it turns out that out of
$i_{2}$ selected, $j-i_{1}$ are from $A_{1}$, then the number of elements from
$A_{2}\cup A_{3}$ after replacement becomes exactly $j$. However, also note
that for each such combination arising, there are ${m\choose i_{2}}$
combinations of samples from $A_{1}$ and $A_{2}$, which give the same _final_
combination after replacement. Hence, we need to apply the rule of division,
so as not to repeatedly count the same combination. Finally, using the rule of
sum to consider all possible values of $i_{1}$ and $i_{2}$ retrieves the
expression $\sum_{i_{1}=0}^{j}\sum_{i_{2}=j-i_{1}}^{j}{k_{1}\choose
i_{1}}{n-k_{1}\choose m-i_{1}}\cdot{k_{2}\choose i_{2}}{n\choose
m-i_{2}}\frac{{i_{1}\choose i_{2}-(j-i_{1})}}{{m\choose
i_{2}}}={n-k_{1}\choose m-j}{k_{1}+k_{2}\choose j}{n\choose m}$ and completes
the argument.

We again plug in the above in the following expression to get,

$\displaystyle\mathbb{P}_{\theta,(b^{(1)},b^{(2)})}\left[Q_{\theta}(\mathrm{g}_{b^{(1)}}^{S}(\mathrm{w}))\neq
Q_{\theta}(\mathrm{g}_{b^{(2)}}^{S^{\prime}}(\mathrm{w}))\right]$
$\displaystyle=\sum_{j=0}^{k_{1}+k_{2}}p(j)\mathbb{P}_{\theta,(b^{(1)},b^{(2)})}\left[Q_{\theta}(\mathrm{g}_{b^{(1)}}^{S}(\mathrm{w}))\neq
Q_{\theta}(\mathrm{g}_{b_{2}}^{S^{\prime}}(\mathrm{w}))|b^{(1)},b^{(2)}\text{
differ in }j\text{ indices}\right]$
$\displaystyle\leq\sum_{j=0}^{k_{1}+k_{2}}\frac{{n-k_{1}\choose
m-j}{k_{1}+k_{2}\choose j}}{{n+k_{2}\choose
m}}\frac{4Gdj}{m\tau}=\frac{m(k_{1}+k_{2})}{n}\frac{4Gd}{m\tau}$
$\displaystyle=\frac{4Gd(k_{1}+k_{2})}{n\tau}$

where the second equality is again a consequence of Vandermonde’s identity as
in Lemma 7, and the last inequality follows by plugging in
$\tau=\frac{4GdT}{\rho n}$. Finally, we condition on the iterates till
iteration $t$, which gives us the conditional probability of the iterates
differing at iteration $t$ is at most $\frac{(k_{1}+k_{2})\rho}{T}$. Taking a
union bound over all $T$ iterations gives us that probability is at most
$(k_{1}+k_{2})\rho$. Finally, we extend it to $k$ edit request, by using the
fact, by assumption than the number of data points at any point in the stream
is between $\frac{n}{2}$ and $2n$. This, with the result for one edit request,
directly give us the probability to recompute is at most
$2\sum_{i=1}^{k}(k^{i}_{1}+k^{i}_{2})\rho$. ∎

We now state and prove the main result.

######  Theorem 5.

Let $f(\cdot,\mathrm{z})$ be an $L$-smooth $G$-Lipschitz convex function
$\forall\ \mathrm{z}$. For any $\frac{1}{n}\leq\rho<\infty$, using Algorithm 7
as the learning algorithm and Algorithm 8 as its unlearning algorithm, then
given a stream of batch edit requests,

  1. 1.

Satisfies exact batch unlearning at every point in the stream.

  2. 2.

At time $i$ in the stream of edit requests, outputs
$\widehat{\mathrm{w}}_{S^{i}}$, such that its excess empirical risk bounded
as,

$\displaystyle\mathbb{E}{\widehat{F}_{S}(\widehat{\mathrm{w}}_{S^{i}})-\widehat{F}_{S}(\mathrm{w}_{S^{i}}^{*})}\lesssim\left({\frac{\sqrt{L}GD^{2}d^{3/2}}{\rho
n}}\right)^{2/3}$

  3. 3.

For $k$ batch edit requests, where the $i^{\text{th}}$ request comprises of
$k^{i}_{1}$ deletions and $k^{i}_{1}+k^{i}_{2}$ insertions, or $k^{i}_{1}$
insertions and $k^{i}_{1}+k^{i}_{2}$ deletions, the expected total unlearning
runtime is
$O(\max\left\\{{\min\left\\{{\rho,1}\right\\}\sum_{i=1}^{k}(k_{1}^{1}+k_{2}^{i})\cdot\text{Training
time},k}\right\\})$

###### Proof of Theorem 5.

The first and the second claims follow from Proposition 9 and Proposition 8
respectively combined with the assumption that the number of samples at every
point in the stream is between $\frac{n}{2}$ and $2n$. Finally, as in the the
proof 8 for runtime _noisy-m-A-SGD_ , we can use the same data-structures
together with the fact the quantization operation takes $O(d)$ time, to get
that the claimed runtime. These together finish the proof of Theorem 5. ∎

##  Appendix F Lower bounds on excess empirical risk

Give a convex function $f(\cdot,\mathrm{z})$, we consider empirical risk
minimization on a dataset of $n$ points. We assume $f(\cdot,\mathrm{z})$ is
$1$-Lipschitz for all $\mathrm{z}$, and diam$({\mathcal{W}})\leq 1$. This is
only for simplification as the bounds scale naturally with these constants, as
discussed in [9]. We look at algorithms, which given two datasets $S$ and
$S^{\prime}$ of size $n$ differing by one point, _disagree_ only on a set of
measure at most an $\rho$.

We have from the optimal transport connection that this requirement is
equivalent to the total variation distance being at most $\rho$. We want to
understand then what is the lower bound on excess empirical risk:

$\displaystyle\underset{\Delta(S,S^{\prime})=1}{\sup}\mathbb{P}\left[{\mathcal{A}}(S^{\prime})\neq{\mathcal{A}}(S)\right]\leq\rho$
$\displaystyle\iff\underset{\Delta(S,S^{\prime})=1}{\sup}\text{TV}({\mathcal{A}}(S),{\mathcal{A}}(S^{\prime}))\leq\rho$
$\displaystyle\implies\mathbb{E}{\left[\text{excess empirical
risk}\right]}\geq\alpha(\rho,n,d)$

We focus on proving the implication. [9] gave lower bounds on accuracy for DP
algorithms by providing a reduction to computing mean of the dataset. We
present and give the proof of the reduction, adapted to our context, for
completeness. The reduction is that if we have a TV-stable algorithm for
empirical risk minimization for a particular $f$ with some accuracy, then we
have a TV-stable algorithm for mean computation problem with _certain_
accuracy. We will look at mean computation problem over datasets with norm of
the mean being $\Theta(M)$, for some given $M$. Let
$\mu(S)=\frac{1}{n}\sum_{j=1}^{n}\mathrm{z}_{i}$ denote the mean of dataset
$S=\left\\{{\mathrm{z}_{1},\mathrm{z}_{2},\cdots\mathrm{z}_{n}}\right\\}$.

Let the optimal accuracy of such a mean computation problem be denoted as
follows:

$\displaystyle\alpha_{\text{mean}}^{2}(n,\rho,d,M):=\min_{{\mathcal{A}}:\rho\text{-TV-
stable}}\max_{\begin{subarray}{c}S=\\{\mathrm{z}_{i}\\}_{i\in[n]}:\left\|{\mathrm{z}_{i}}\right\|\leq
1,\\\ M/2\leq\left\|{\mu(S)}\right\|\leq
2M\end{subarray}}{\mathbb{E}}_{\mathcal{A}}\left\|{{\mathcal{A}}(S)-\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|^{2}$

######  Proposition 10.

For any $\rho$-TV stable algorithm ${\mathcal{A}}$, there exists a
$1$-Lipschitz convex function $f$, a constraint set ${\mathcal{W}}$ with
diameter(${\mathcal{W}})\leq 1$ and a dataset $S$ of $n$ data point such that

$\widehat{F}_{S}({\mathcal{A}}(S))-\widehat{F}_{S}(\mathrm{w}^{*})\geq\max_{M}\left\\{{\frac{\alpha_{\text{mean}}^{2}(n,\rho,d,M)}{2M}}\right\\}$

###### Proof of Proposition 10.

We follow the proof in [9]. Consider dataset
$S=\left\\{{\mathrm{z}_{1},\mathrm{z}_{2},\ldots,\mathrm{z}_{n}}\right\\}$,
$\mathrm{z}_{i}\in\left\\{{-\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}}}\right\\}^{d}$
\- the dataset is therefore constrained to lie in the unit Euclidean ball.
Consider the following function
$f(\mathrm{w},\mathrm{z})=-\left\langle{\mathrm{w}},{\mathrm{z}}\right\rangle$
with the constraint set ${\mathcal{W}}$ being the unit Euclidean ball. It is
easy to see that $f(\cdot,\mathrm{z})$ is $1$-Lipschitz for all $\mathrm{z}$.
The empirical risk becomes
$\widehat{F}_{S}(\mathrm{w})=-\left\langle{\mathrm{w}},{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\rangle$,
the minimum of which over the unit ball is
$\mathrm{w}_{S}^{*}=\frac{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}{\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|}$.

Given an algorithm ${\mathcal{A}}$ for empirical risk minimization, let the
reduced mean estimate be
$\widehat{\mu}(S)=\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|{\mathcal{A}}(S)$.
The accuracy (mean-squared error) of $\widehat{\mu}$ is,

$\displaystyle\left\|{\widehat{\mu}(S)-\mu(S)}\right\|^{2}$
$\displaystyle=\left\|{\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|{\mathcal{A}}(S)-\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|^{2}=\left\|{\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|\left({{\mathcal{A}}(S)-\frac{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}{\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|}}\right)}\right\|^{2}$
$\displaystyle=\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|^{2}\left\|{{\mathcal{A}}(S)-\mathrm{w}_{S}^{*}}\right\|^{2}\leq\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|2\left({\widehat{F}_{S}({\mathcal{A}}(S))-\widehat{F}_{S}(\mathrm{w}^{*})}\right)$

where the last inequality follows using the following computation, wherein we
use the fact all data point are in the unit ball.

$\displaystyle\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|^{2}\left\|{{\mathcal{A}}(S)-\mathrm{w}_{S}^{*}}\right\|^{2}$
$\displaystyle\leq\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|2\left({1-\left\langle{{\mathcal{A}}(S)},{\mathrm{w}_{S}^{*}}\right\rangle}\right)$
$\displaystyle=2\left({\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|-\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|\left\langle{{\mathcal{A}}(S)},{\frac{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}{\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|}}\right\rangle}\right)$
$\displaystyle=2\left({\left\langle{\mathrm{w}^{*}_{S}},{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\rangle-\left\langle{{\mathcal{A}}(S)},{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\rangle}\right)$
$\displaystyle=2(\widehat{F}_{S}({\mathcal{A}}(S))-\widehat{F}_{S}(\mathrm{w}^{*})$

We therefore get,

$\widehat{F}_{S}({\mathcal{A}}(S))-\widehat{F}_{S}(\mathrm{w}^{*})\geq\frac{1}{2\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|}\left\|{\widehat{\mu}(S)-\mu(S)}\right\|^{2}$

There are two things left to show: a bound on
$\frac{1}{2\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|}\left\|{\widehat{\mu}(S)-\mu(S)}\right\|^{2}$
and show that the reduced algorithm $\widehat{\mu}(S)$ is also $\rho$-TV
stable. We proceed with the latter: note that
$\widehat{\mu}(S)=\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|{\mathcal{A}}(S)$.
However the term $\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|$
depends on the dataset, and even if, for a neighbouring dataset $S^{\prime}$,
${\mathcal{A}}(S)$ and ${\mathcal{A}}(S^{\prime})$ are $\rho$-close in total
variation, this data dependent scaling can potentially increase the distance.
However, if instead we define $\widehat{\mu}(S)=M{\mathcal{A}}(S)$, where $M$
is a constant, then it is indeed $\rho$ TV stable. Moreover, for reasonable
values of $M$, the there exists dataset for which
$\left\|{\frac{1}{n}\sum_{i=1}^{n}\mathrm{z}_{i}}\right\|=\Theta(M)$. Finally,
note that by definition,
$\left\|{\widehat{\mu}(S)-\mu(S)}\right\|^{2}\geq\alpha_{\text{mean}}^{2}(n,\rho,d,M)$.
Taking a max over all $M$ gives us the desired statement. ∎

###  F.1 Lower bound for mean computation

In this section, we look at the problem of mean computation with TV stability
constraint. Note that to establish lower bounds on excess empirical risk, we
need to look at mean computation over data sets with means between $M/2$ and
$2M$, for a given $M$. However, we will see the mean computation even over the
unit ball has same accuracy convex ERM. We will therefore establish lower
bounds for the general mean computation problem, but the construction will use
datasets with means $\Theta(M)$ for certain values of $M$. Given a dataset
$S=\left\\{{\mathrm{x}_{1},\mathrm{x}_{2},\ldots,\mathrm{x}_{n}}\right\\}$,
where
$\mathrm{x}_{i}\in\left\\{{-\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}}}\right\\}^{d}$
for all $i,$ the task is to compute the mean
$\mu(S)=\frac{1}{n}\sum_{j=1}\mathrm{x}_{j}$, while ensuring that the
procedure is $\rho$-TV-stable. This task is often considered in the
differential privacy literature, however with the data points being
$\mathrm{x}_{j}\in\left\\{{0,1}\right\\}^{d}$. The mean computation task then
corresponds to releasing all one-way marginals of the database. Since we want
to consider data points which lie inside the Euclidean ball, we therefore
scale it accordingly. Given an algorithm ${\mathcal{A}}(S)$, the accuracy is
defined as mean-squared error:
$\alpha^{2}:=\alpha^{2}_{\text{mean}}(n,\rho,d)=\mathbb{E}{\left\|{{\mathcal{A}}(S)-\mu(S)}\right\|^{2}}$
where the expectation is over the randomization of the algorithm.

We first describe two algorithms for this problem and give upper bounds.

#####  _Subsample-mean_ :

Consider an algorithm which sub-samples a $\rho$-fraction of the dataset and
outputs the mean on it.

######  Claim 11.

The _Subsample-mean_ procedure satisfies $\rho$-TV-stability and has accuracy
$\alpha^{2}\leq O\left({\frac{1}{\rho n}}\right)$.

###### Proof of 11.

The $\rho$-TV stability claim follows since TV distance is witnessed by the
event that a differing sample is sub-sampled, which happens with probability
$\frac{\rho n}{n}=\rho$. The proof of accuracy follows from the proof of
Proposition 1, wherein we computed the gradient on uniformly sub-sampled $m$
out of $n$ points - we showed that the mean on sub-sampled points is an
unbiased estimate of the average gradient. Furthermore, since the gradients
were bounded as well, the expected accuracy of mean computation is the same as
the variance of gradient computation, which we derived to be
$O\left({\frac{1}{m}}\right)=O\left({\frac{1}{\rho n}}\right)$. ∎

#####  _Noisy-mean_ :

The algorithm computes the mean and adds $N(0,\sigma^{2}I)$ noise to it with
$\sigma^{2}=\frac{C}{n^{2}\rho^{2}}$, where $C$ is an appropriate universal
constant.

######  Claim 12.

The _Noisy-mean_ procedure satisfies $\rho$-TV-stability and has accuracy
$\alpha^{2}\leq O\left({\frac{d}{(\rho n)^{2}}}\right)$

###### Proof of 12.

Since the difference in means of two datasets, in norm, is at most
$\frac{2}{n}$, the outputs are two multivariate Gaussians with variance
$\sigma^{2}$ and means separated by $\frac{2}{n}$. From [13], the total
variation distance between such Gaussian sis at most
$O\left({\frac{1}{n\sigma}}\right)=\rho$. For the accuracy, we have
$\alpha^{2}=\mathbb{E}{\left\|{\mu(S)+\xi-\mu(S)}\right\|^{2}}=\mathbb{E}{\left\|{\xi}\right\|^{2}}=d\sigma^{2}=O\left({\frac{d}{n^{2}\rho^{2}}}\right)$.
∎

If the above procedures are optimal, then we expect a lower bound of
$\alpha^{2}\gtrsim\min\left\\{{\frac{1}{\rho n},\frac{d}{(\rho
n)^{2}}}\right\\}$. Equivalently, for a fixed accuracy $\alpha$, we expect a
sample complexity lower bound of
$n\gtrsim\min\left\\{{\frac{1}{\rho\alpha^{2}},\frac{\sqrt{d}}{\rho\alpha}}\right\\}$.

####  F.1.1 Lower bound I

In this section, we give a $\Omega\left({\frac{1}{\alpha\rho}}\right)$ lower
bound on sample complexity. The key ingredient is the following result, where
the proof is based on a simple reduction argument.

######  Proposition 11.

Suppose there exists a $\rho$-TV-stable algorithm such that for any dataset of
$n$ points, it achieves an accuracy of $\alpha$. Then there exists a $0.1$-TV
stable algorithm such the for any dataset of size $\lceil
100n\alpha\rho\rceil$, it achieves a $0.1$-accuracy.

###### Proof of Proposition 11.

Let $n^{\prime}=\lceil 100n\alpha\rho\rceil$. Consider a dataset $S^{\prime}$
of $n^{\prime}$ points. We construct a dataset $S$ of $n$ points by
concatenating $K=\lceil 0.1/\rho\rceil$ copies of $S^{\prime}$ followed by
$\lceil\frac{n-Kn^{\prime}}{2}\rceil$ copies of a constant sample, all ones
$(\frac{1}{\sqrt{d}},...,\frac{1}{\sqrt{d}})$ and
$\lceil\frac{n-Kn^{\prime}}{2}\rceil$ copies of a constant sample, all ones
$(-\frac{1}{\sqrt{d}},...,-\frac{1}{\sqrt{d}})$.

Consider the algorithm wherein we compute the stable-mean on $D^{\prime}$ by
${\mathcal{A}}^{\prime}$, defined as computing the stable-mean on $D$ using
${\mathcal{A}}$ and adjusting:

${\mathcal{A}}^{\prime}(D^{\prime})=\frac{n}{Kn^{\prime}}{\mathcal{A}}(D)$

Let $\tilde{S}^{\prime}$ be a neighbouring dataset of $S^{\prime}$. By
construction, note that $S$ and $\tilde{S}$ differ by $K$ samples.
Furthermore, since the algorithm ${\mathcal{A}}$ on $D$ is $\rho$-TV stable,
on $K$-neighbouring datasets, it is $K\rho$ = $0.1$-TV. This establish the
stability part of claim. The accuracy, by direct computation is
$\mathbb{E}{\left\|{{\mathcal{A}}^{\prime}(D^{\prime})-\mu(D^{\prime})}\right\|^{2}}=\frac{n^{2}}{K^{2}n^{\prime
2}}\mathbb{E}{\left\|{{\mathcal{A}}(D)-\mu(D)}\right\|^{2}}\leq(0.1)^{2}$. ∎

######  Theorem 6.

For the $d$-dimensional mean computation problem over the Euclidean ball,
there exists a dataset $S$ of $n$ samples with mean
$\left\|{\mu(S)}\right\|=\Theta\left({\frac{1}{\rho n}}\right)$ such that the
accuracy of any $\rho$ TV stable algorithm is
$\alpha\geq\Omega\left({\frac{1}{\rho n}}\right)$.

###### Proof of Theorem 6.

Even for accuracy $\alpha_{0}=0.1$ accuracy and $\rho_{0}=0.1$ stability, we
need at least one sample. Hence, using Proposition 10, we get that sample
complexity is $n\geq\Omega\left({\frac{1}{\rho\alpha}}\right)$, which
equivalently gives the claimed accuracy lower bound. Note that for this one-
sample dataset $S^{\prime}$, $\left\|{\mu(S^{\prime})}\right\|=1$. Finally,
from the reduction in Proposition 10, the mean of dataset $S$ becomes
$\left\|{\mu(S)}\right\|=\lceil\frac{0.1}{\rho n}\rceil$, which finishes the
proof. ∎

####  F.1.2 Lower bound II

In this section, we will prove the
$\Omega\left({\frac{1}{\alpha^{2}\rho}}\right)$ lower bound. We first
introduce a technical assumption.

######  Assumption 1.

For any dataset $S$, we assume that the probability distribution
${\mathcal{A}}(S)$ is defined over the unit Euclidean ball, is absolutely
continuous with respect to the uniform measure (in the unit Euclidean ball)
and its probability density function, with respect to the uniform measure, is
bounded by $K$ in absolute value.

As a remark, the above assumption can also be stated with respect to the
Lebesgue measure, but then we would get a scaling of
$\frac{\pi^{d/2}}{\Gamma\left({1+\frac{d}{2}}\right)}$, which is the Lebesgue
volume of the $B_{d}(0,1)$, to some of our terms. In order to simplify, we
therefore use the uniform measure.

######  Theorem 7.

Let $n\geq 72,\alpha\leq\frac{1}{4}$ and $\frac{1}{n}\leq\rho\leq\frac{1}{4}$.
Let ${\mathcal{A}}$ be any $\rho$-TV-stable algorithm satisfying Assumption 1
with $K\leq 2^{d}$. For large enough dimension $d$, there exists a dataset $S$
of $n$ points with $\left\|{\mu(S)}\right\|=\Theta\left({\frac{1}{\sqrt{\rho
n}}}\right)$ such that accuracy is lower bounded as
$\alpha\geq\Omega\left({\frac{1}{\sqrt{\rho n}}}\right)$.

###### Proof of Theorem 7.

We will prove the result by contradiction. Let "Vol" of a set refer to its
volume with respect to the uniform measure on the unit ball. Consider the
following high-dimensional setup. Consider a dataset $S$ (or $S^{0}$) which
mean $\mu(S)$ such that
$\left\|{\mu(S)}\right\|=\Theta\left({\frac{1}{\sqrt{\rho n}}}\right)$. It is
easy to construct such datasets by considering points such that sum of
$n-\lceil\sqrt{\frac{n}{\rho}}\rceil$ points is $0$ and the rest of points is
the same point repeated - this uses the assumption that $\rho\geq\frac{1}{n}$.
Now consider neighbouring datasets $S^{i}$’s, $i\in[n]$ such that the means of
$S^{i}$’s are all $\frac{1}{n}$ far from that of $S$, in norm. We also need
that the means of any two datasets
$\left\|{\mu(S^{i})-\mu(S^{j})}\right\|\geq\frac{1}{2n}$ for $i,j=0$ to $n$
and $i\neq j$. It is easy to see the existence of such datasets, by
considering the means of $S^{i}$’s in near orthogonal directions to that of
$S$, which is possible when $d$ is large enough.

Suppose the algorithm ${\mathcal{A}}$ has expected error $\alpha^{2}$ i.e.
$\mathbb{E}{\left\|{{\mathcal{A}}(S)-\mu(S)}\right\|}^{2}\leq\alpha^{2}$ with
$72\leq n\leq\frac{1}{\alpha^{2}\rho}$. Consider
$B_{d}\left({\mu(S),\frac{1}{K^{1/d}}}\right)$, the $d$ dimensional Euclidean
ball centered at $\mu(S)$ of radius $\frac{1}{K^{1/d}}$. From Markov’s
inequality, we have that $\mathbb{P}\left[{{\mathcal{A}}(S)\not\in
B_{d}\left({\mu(S),\frac{1}{K^{1/d}}}\right)}\right]\leq\mathbb{P}\left[{{\mathcal{A}}(S)\not\in
B_{d}\left({\mu(S),\frac{1}{2}}\right)}\right]=\mathbb{P}\left[{\left\|{{\mathcal{A}}(S)-\mu(S)}\right\|^{2}\geq\frac{1}{4}}\right]\leq\frac{\mathbb{E}{\left\|{{\mathcal{A}}(S)-\mu(S)}\right\|}^{2}}{(1/4)}\leq
4\alpha^{2}$, where in the first inequality, we used the assumption $K\leq
2^{d}$. Therefore, we have $\mathbb{P}\left[{{\mathcal{A}}(S)\in
B_{d}\left({\mu(S),\frac{1}{K^{1/d}}}\right)}\right]\geq 1-4\alpha^{2}$.

We now setup some additional notation. Let $A_{i}$ denote the set
$B_{d}\left({\mu(S^{i}),\frac{1}{K^{1/d}}}\right)\backslash\left({\cup_{j=0,j\neq
i}^{n}B_{d}\left({\mu(S^{j}),\frac{1}{K^{1/d}}}\right)}\right)$ i.e. the
region in the ball $B_{d}(\mu(S^{i})$ which is not contained in any of the
other balls. Let $B_{ij}$ denote the region of intersection between
$B_{d}\left({\mu(S^{i}),\frac{1}{K^{1/d}}}\right)$ and
$B_{d}\left({\mu(S^{j}),\frac{1}{K^{1/d}}}\right)$ where $i\neq j$ and $i$ and
$j$ go from $0$ to $n$. Note that set $B_{ij}$ is constituted of two spherical
caps. By construction the centers of the intersecting spheres are at least
$\frac{1}{2n}$ apart. To study the properties of such a set, we define cap as
the region in a $d$ dimensional sphere of radius $\frac{1}{K^{1/d}}$ which
intersects with another sphere of the same radius but with centers being apart
by $1/2n$. From known results [10], the volume of cap is asymptotic to
$\text{Vol}\left({B_{d}\left({0,\frac{1}{K^{1/d}}}\right)}\right)\left({1-\Phi\left({\frac{\sqrt{d}}{2n}}\right)}\right)$
as $d\rightarrow\infty$ where $\Phi$ is the cumulative distribution function
of a standard normal random variable. We therefore have that
$\lim_{d\rightarrow\infty}\text{Vol({cap})}\sim\lim_{d\rightarrow\infty}\text{Vol}\left({B_{d}\left({0,\frac{1}{K^{1/d}}}\right)}\right)\left({1-\Phi\left({\frac{\sqrt{d}}{2n}}\right)}\right)=0$.
Furthermore, using Assumption 1, we have
$\mathbb{P}\left[{{\mathcal{A}}(S)\in\text{cap}}\right]\leq
K\text{Vol({cap})}\sim
K\text{Vol}\left({B_{d}\left({0,\frac{1}{K^{1/d}}}\right)}\right)\left({1-\Phi\left({\frac{\sqrt{d}}{n}}\right)}\right)\leq
K\left({\frac{1}{K^{1/d}}}\right)^{d}\left({1-\Phi\left({\frac{\sqrt{d}}{n}}\right)}\right)=\left({1-\Phi\left({\frac{\sqrt{d}}{n}}\right)}\right)$
as $d\rightarrow\infty$. Since
$\Phi(t)=\mathbb{P}_{g\sim{\mathcal{N}}(0,1)}[g\leq t]$, we have that
$1-\Phi(t)=\mathbb{P}_{g\sim{\mathcal{N}}(0,1)}[g>t]\leq\frac{e^{-t^{2}/2}}{\sqrt{2\pi}t}$
where the last inequality follows from standard bounds on tails of normal
distribution (See Proposition 2.1.2 in [27]). Therefore, we have
$\mathbb{P}\left[{{\mathcal{A}}(S)\in\textbf{cap}}\right]\lesssim\frac{ne^{-d/4n^{2}}}{\sqrt{d}}$.
For constant $\epsilon>0$, choosing $d\gtrsim
4n^{2}\ln{\left({n/\epsilon}\right)}$ ensures that
$\mathbb{P}\left[{{\mathcal{A}}(S)\in\textbf{cap}}\right]\leq\frac{\epsilon}{2n}$
for large enough $n$ (to be specified later). Since $B_{ij}$ is made up of two
conjoined caps, this gives us that for any $j=0$ to $n$ and $i\neq j$, we have
that $\mathbb{P}\left[{{\mathcal{A}}(S^{i})\in
B_{ij}}\right]\leq\frac{\epsilon}{n}$. Finally, we look at $A_{i}$’s by
removing the mass of all $B_{ij}$’s, and using a union bound, we get that
$\mathbb{P}\left[{{\mathcal{A}}(S^{i})\in
A_{i}}\right]=\mathbb{P}\left[{{\mathcal{A}}(S^{i})\in
B_{d}\left({\mu(S^{i}),\frac{1}{K^{1/d}}}\right)}\right]-\mathbb{P}\left[{{\mathcal{A}}(S^{i})\in\cup_{j=0,j\neq
i}^{n}B_{ij}}\right]\geq 1-4\alpha^{2}-\sum_{j=0,j\neq
i}^{n}\mathbb{P}\left[{{\mathcal{A}}(S^{i})\in B_{ij}}\right]\geq
1-4\alpha^{2}-\epsilon\geq\frac{1}{2}-4\alpha^{2}$ where the last inequality
holds for $\epsilon\leq\frac{1}{2}$. We now evaluate how large $n$ we need for
this regime of $\epsilon$: recall that we set $d\gtrsim
4n^{2}\ln{\left({n/\epsilon}\right)}$, this gives
$\frac{ne^{-d/4n^{2}}}{\sqrt{d}}\leq\frac{\epsilon}{2n\sqrt{\ln{\left({n/\epsilon}\right)}}}$.
We want the right hand side to be at most $\frac{\epsilon}{2n}$ for
$\epsilon\leq 1/2$. Plugging in this worst-case value of $\epsilon$, we get
the condition $\ln{(2n)}\geq 1$ which holds for any $n\geq 1.4$ and therefore
is valid by our assumption of $n$.

We now use the fact that $A_{i}^{\prime}s$ are disjoint by construction.
Therefore the total measure of ${\mathcal{A}}(S)$ on union of
$A_{i}^{\prime}s$ is at most $1$ i.e
$\mathbb{P}\left[{{\mathcal{A}}(S)\in\cup_{i=1}^{n}A_{i}}\right]=\sum_{i=1}^{n}\mathbb{P}\left[{{\mathcal{A}}(S)\in
A_{i}}\right]\leq 1$. Furthermore, since ${\mathcal{A}}(S)$ is $\rho$-TV
stable, we have that $\mathbb{P}\left[{{\mathcal{A}}(S)\in
A_{i}}\right]\geq\mathbb{P}\left[{{\mathcal{A}}(S^{i})\in A_{i}}\right]-\rho$.
Combining this with the previous analysis which gives a lower bound on
$\mathbb{P}\left[{{\mathcal{A}}(S^{i})\in A_{i}}\right]$ yields

$\displaystyle
n\left({\frac{1}{2}-4\alpha^{2}-\rho}\right)\leq\sum_{i=1}^{n}\mathbb{P}\left[{{\mathcal{A}}(S^{i})\in
A_{i}}\right]-\rho\leq\sum_{i=1}^{n}\mathbb{P}\left[{{\mathcal{A}}(S)\in
A_{i}}\right]\leq 1$ (2)

We now proceed in two cases:

Case 1: Suppose $72\leq n\leq\frac{17}{4\alpha^{2}}$. The latter condition
gives us that $4\alpha^{2}\leq\frac{17}{n}$. Using Eq. 2 gives us
$n(1/2-4\alpha^{2}-\rho)\leq 1\iff
4\alpha^{2}\geq\frac{1}{2}-\frac{1}{n}-\rho$. Upper bounding $4\alpha^{2}$ by
$\frac{17}{n}$ gives us that $\frac{18}{n}\geq\frac{1}{2}-\rho\iff
n\leq\frac{18}{(1/2-\rho)}\leq 72$ where in the last inequality we used
$\rho\leq 1/4$. This gives us a contradiction.

Case 2: Suppose $\frac{17}{4\alpha^{2}}\leq n$. We again start with Eq. 2
which gives us $n(1/2-4\alpha^{2}-\rho)\leq
1\iff\rho\geq\frac{1}{2}-\frac{1}{n}-4\alpha^{2}$. We want to prove the right
hand side is at least $\frac{1}{n\alpha^{2}}$, which would give us that
$n\geq\frac{1}{\rho\alpha^{2}}$. Suppose this is not true i.e.
$\frac{1}{2}-\frac{1}{n}-4\alpha^{2}\leq\frac{1}{n\alpha^{2}}\iff\frac{n-2-8\alpha^{2}n}{2n}\leq\frac{1}{n\alpha^{2}}\iff\alpha^{2}n(1-8\alpha^{2})\leq
2(1+\alpha^{2})\iff n\leq\frac{2(1+\alpha^{2})}{\alpha^{2}(1-8\alpha^{2})}$.
Finally using the fact that $\alpha\leq\frac{1}{4}$ gives that
$n\leq\frac{2(1+1/16)}{\alpha^{2}(1-8/16)}\leq\frac{17}{4\alpha^{2}}$ which
yields a contradiction.

Hence, we see that with $n>72$ samples and accuracy $\alpha^{2}$, we have
established that $n\geq\frac{1}{\rho\alpha^{2}}$ and so
$\alpha\geq\frac{1}{\sqrt{\rho n}}$. ∎

##  Appendix G Excess population risk bounds

The goal in machine learning is (population) risk minimization. The population
risk of $\mathrm{w}$, denoted by $F(\mathrm{w})$ is defined as
$F(\mathrm{w}):=\underset{{\mathrm{z}\sim{\mathcal{D}}}}{\mathbb{E}}{f(\mathrm{w},\mathrm{z})}$,
where ${\mathcal{D}}$ is an unknown probability distribution over data points.
Analogously, given an output of algorithm ${\mathcal{A}}$ on dataset
$S=\left\\{{\mathrm{z}_{i}}\right\\}_{i}$ where
$\mathrm{z}_{i}\sim{\mathcal{D}}$ i.i.d., denoted as ${\mathcal{A}}(S)$, we
will give guarantees on the _expected excess population risk_ , defined as
$\mathbb{E}{F({\mathcal{A}}(S))-F(\mathrm{w}^{*})}$, where $\mathrm{w}^{*}$ is
the population risk minimizer:
$\mathrm{w}^{*}\in\arg\min_{\mathrm{w}\in{\mathcal{W}}}F(\mathrm{w})$, and the
expectation is taken with respect to randomness in algorithm ${\mathcal{A}}$
as well as sampling $S$.

###  G.1 Upper bounds

In this section, we will bound the expected excess population risk appealing
to connections between algorithmic stability and generalization [6]. We first
define uniform stability.

######  Definition 5 (Uniform stability).

Let ${\mathcal{A}}:{\mathcal{Z}}^{n}\rightarrow{\mathcal{W}}$ be an algorithm
and ${\mathcal{A}}(S)$ denotes its output on dataset $S$. We say that
${\mathcal{A}}$ is $\epsilon_{\text{stable}}(n)$-uniformly stable if for any
datasets $S$ and $S^{\prime}$ of $n$ points such that they differ by one data
point (i.e. $\Delta(S,S^{\prime})=2$), we have
$\sup_{z\in{\mathcal{Z}}}\mathbb{E}_{{\mathcal{A}}}\left[f({\mathcal{A}}(S),z)-f({\mathcal{A}}(S^{\prime}),z)\right]\leq\epsilon_{\text{stable}}(n)$

A classical result [6] shows that expected excess population risk is at most
uniform stability + expected excess empirical risk: i.e. any
$\mathrm{w}\in{\mathcal{W}}$, we have

$\displaystyle\mathbb{E}\left[F({\mathcal{A}}(S))-F(\mathrm{w})\right]\leq\epsilon_{\text{stable}}(n)+\mathbb{E}\left[\widehat{F}_{S}({\mathcal{A}}(S))-\widehat{F}_{S}(\mathrm{w})\right]$

######  Theorem 8 (Upper bound).

There exists a $\rho$ TV stable algorithm, such that for any function
$f(\cdot,\mathrm{z})$ which is $L$-smooth $G$-Lipschitz convex $\forall\
\mathrm{z}$ and any dataset $S$ of $n$ points, it outputs
$\widehat{\mathrm{w}}_{S}$ which satisfies the following.

$\displaystyle\mathbb{E}{F(\widehat{\mathrm{w}}_{S})-F(\mathrm{w}^{*})}\lesssim\frac{GD}{\sqrt{n}}+GD\min\left\\{{\frac{1}{\sqrt{\rho
n}},\frac{\sqrt{d}}{\rho n}}\right\\}$

###### Proof of Theorem 8.

We use _sub-sample-GD_ (Algorithm 1) and _noisy-m-SGD_ (Algorithm 5). From
Lemma 3.2 in [7], we have that $\epsilon_{\text{stable}}(n)\leq\frac{G^{2}\eta
T}{n}$. From Proposition 1, we set
$\eta=\min\left\\{{\frac{1}{2L},\frac{D}{G\sqrt{T}}}\right\\}$, and
$T=\frac{DL\sqrt{\rho n}}{G}$. We therefore have
$\epsilon_{\text{stable}}(n)\leq\frac{G^{2}T}{2Ln}=\frac{GD\sqrt{\rho}}{\sqrt{\rho
n}}$. Using the excess empirical risk bound from Proposition 1, and the fact
that $\rho\leq 1$, the excess population risk is bounded as,

$\displaystyle\mathbb{E}{F(\widehat{\mathrm{w}}_{S})-F(\mathrm{w}^{*})}\leq\frac{GD\sqrt{\rho}}{\sqrt{n}}+\frac{GD}{\sqrt{\rho
n}}\leq\frac{GD}{\sqrt{n}}+\frac{GD}{\sqrt{\rho n}}$

For _noisy-m-SGD_ , we need to balance the trade-offs more directly. In
Proposition 7, we arrived at that when using $\eta\leq\frac{1}{2L}$, the
expected excess empirical risk is bounded by
$\eta{\mathcal{V}}^{2}+\frac{D^{2}}{\eta T}$. Using the uniform stability
bound of $\frac{G^{2}T\eta}{n}$, the expected excess population risk is
bounded as,

$\displaystyle\mathbb{E}{F(\widehat{\mathrm{w}}_{S})-F(\mathrm{w}^{*})}\leq\frac{G^{2}T\eta}{n}+\eta{\mathcal{V}}^{2}+\frac{D^{2}}{\eta
T}=\eta\left({\frac{G^{2}T}{n}+{\mathcal{V}}^{2}}\right)+\frac{D^{2}}{\eta T}$

Define $\tilde{G}^{2}=\left({\frac{G^{2}T}{n}+{\mathcal{V}}^{2}}\right)$,
where ${\mathcal{V}}^{2}\lesssim G^{2}+\sigma^{2}d\lesssim
G^{2}+\frac{G^{2}Td}{n^{2}\rho}$. Setting
$\eta=\min\left\\{{\frac{1}{2L},\frac{D}{\tilde{G}\sqrt{T}}}\right\\}$, we
get,

$\displaystyle\mathbb{E}{F(\widehat{\mathrm{w}}_{S})-F(\mathrm{w}^{*})}$
$\displaystyle\leq\frac{LD^{2}}{T}+\frac{\tilde{G}D}{\sqrt{T}}$
$\displaystyle\lesssim\frac{LD^{2}}{T}+\frac{G\sqrt{T}D}{\sqrt{T}\sqrt{n}}+\frac{GD}{\sqrt{T}}+\frac{GD\sqrt{T}\sqrt{d}}{\rho
n\sqrt{T}}$
$\displaystyle=\frac{LD^{2}}{T}+\frac{GD}{\sqrt{n}}+\frac{GD}{\sqrt{T}}+\frac{GD\sqrt{d}}{\rho
n}$

Setting $T=\max\left\\{{\min\left\\{{\sqrt{n},\frac{\rho
n}{\sqrt{d}}}\right\\},\frac{LD}{G}\min\left\\{{\sqrt{n},\frac{\rho
n}{\sqrt{d}}}\right\\}}\right\\}$, and combining the two results finishes the
proof. ∎

###  G.2 Lower bounds

In this section, we will prove a lower bound on excess population risk for any
$\rho$-TV stable algorithm. As before, we will consider the Lipschitz constant
$G$ and diameter $D$ to be both $1$, as the bounds scale naturally with these
constants. We first define the following quantity, which denotes the lower
bound on expected excess empirical risk of $\rho$-TV-stable algorithm with $n$
points.

$\displaystyle\widehat{\alpha}(n,\rho):=\inf_{{\mathcal{A}}:\rho\text{-TV-
stable}}\sup_{S:\left|{S}\right|=n}\mathbb{E}_{\mathcal{A}}\widehat{F}_{S}({\mathcal{A}}(S))-\widehat{F}_{S}(\widehat{\mathrm{w}}_{S})$

######  Theorem 9.

For the problem of stochastic convex optimization, there exists a data
distribution ${\mathcal{D}}$, such that any $\rho$-TV-stable algorithm
${\mathcal{A}}$ incurs expected excess population risk, bounded as follows

$\displaystyle\underset{S\sim{\mathcal{D}}^{n},{\mathcal{A}}}{\mathbb{E}}F({\mathcal{A}}(S))-F(\mathrm{w}^{*})\geq\max\left\\{{\Omega\left({\frac{1}{\sqrt{n}}}\right),\widehat{\alpha}(n,\rho)}\right\\}$

###### Proof of Theorem 9.

The $\frac{1}{\sqrt{n}}$ term follows directly since it is the lower bound for
any algorithm, and so applies to $\rho$-TV stable algorithms as well. We now
focus on the second term $\widehat{\alpha}(n,\rho)$ The proof is based on a
standard reduction argument: if there is $\rho$-TV stable algorithm, which
with $n$ i.i.d. samples from any distribution, achieves an expected excess
population risk less than $\widehat{\alpha}(n,\rho)$, then there is an
$\rho$-TV stable algorithm which achieves an expected excess empirical risk
less than $\widehat{\alpha}(n,\rho)$ on any dataset of $n$ samples. Since the
latter contradicts the definition of $\widehat{\alpha}(n,\rho)$, this gives us
that the expected excess population risk is at least or equal to
$\widehat{\alpha}(n,\rho)$. We now focus on the proof of the reduction.
Consider a dataset $S$ of $n$ points. Consider ${\mathcal{A}}$ as the
following algorithm: sample $n$ i.i.d. samples from $S$, call this set
$\tilde{S}$, and run _some_ $\rho$-TV algorithm $\tilde{\mathcal{A}}$ on
$\tilde{S}$. For a fixed $\tilde{S}$, from TV-stable property of
$\tilde{\mathcal{A}}$, for any neighbouring dataset $\tilde{S}^{\prime}$ with
one point differing, we have that
$\text{TV}(\tilde{\mathcal{A}}(\tilde{S}),\tilde{\mathcal{A}}(\tilde{S}^{\prime}))\leq\rho$.
Furthermore, using the _group_ property of TV-stability, for any dataset
$\tilde{S}^{\prime}$, we have
$\text{TV}(\tilde{\mathcal{A}}(\tilde{S}),\tilde{\mathcal{A}}(\tilde{S}^{\prime}))\leq\Delta(S,S^{\prime})\rho$.
Using the maximal coupling characterization of total variation distance, we
have that there exists a coupling $\tilde{\pi}$ of random variables
$\tilde{\mathcal{A}}(\tilde{S})$ and $\tilde{\mathcal{A}}(\tilde{S}^{\prime})$
such that
$\text{TV}(\tilde{\mathcal{A}}(\tilde{S}),\tilde{\mathcal{A}}(\tilde{S}^{\prime}))=\mathbb{E}_{\tilde{\pi}}\mathbb{1}\left\\{{\tilde{\mathcal{A}}(\tilde{S})\neq\tilde{\mathcal{A}}(\tilde{S}^{\prime})}\right\\}$.
We now show that the algorithm ${\mathcal{A}}$ is also TV-stable for dataset
$S$.

Consider dataset $S^{\prime}$ of $n$ points which differs from $S$ in the
first sample. We now generate $\tilde{S}^{\prime}$ by drawing $n$ i.i.d
samples from $S^{\prime}$. For this, consider the following coupling: we draw
$n$ i.i.d samples from $S$, call it $\tilde{S}$. For every draw of the first
sample, replace it by the first sample of $S^{\prime}$, call it
$\tilde{S}^{\prime}$. It is easy to check the $\tilde{S}$ and
$\tilde{S}^{\prime}$ are i.i.d. samples from $S$ and $S^{\prime}$
respectively. We now proceed to show the ${\mathcal{A}}$ is $\rho$-TV stable.
We will use the fact the total variation distance is at most the probability
of disagreement under any coupling. The coupling $\pi$ we consider is that we
first generate $\tilde{S}$ and $\tilde{S}^{\prime}$ using the aforementioned
coupling, and then use the coupling $\tilde{\pi}$ which achieves total
variation distance for worst-case fixed neighbouring datasets $\tilde{S}$ and
$\tilde{S}^{\prime}$. We have,

$\displaystyle\text{TV}({\mathcal{A}}(S),{\mathcal{A}}(S^{\prime}))$
$\displaystyle\leq\mathbb{E}_{\pi}\mathbb{1}\left\\{{{\mathcal{A}}(S)\neq{\mathcal{A}}(S^{\prime})}\right\\}=\mathbb{E}_{\pi}\mathbb{1}\left\\{{\tilde{\mathcal{A}}(\tilde{S})\neq\tilde{\mathcal{A}}(\tilde{S}^{\prime})}\right\\}$
$\displaystyle\leq\mathbb{E}_{\pi}\sup_{\tilde{S},\tilde{S}^{\prime}}\mathbb{1}\left\\{{\tilde{\mathcal{A}}(\tilde{S})\neq\tilde{\mathcal{A}}(\tilde{S}^{\prime})}\right\\}\leq\mathbb{E}_{\pi}\Delta(\tilde{S},\tilde{S}^{\prime})\rho=\rho$

where the last equality follows from direct computation of
$\Delta(\tilde{S},\tilde{S}^{\prime})$: number of differing samples, under
coupling $\pi$.

We now proceed to the accuracy guarantee. From straight-forward computation,
the excess population risk, under the sampling of $\tilde{S}$, is
$\widehat{F}_{S}(\tilde{\mathcal{A}}(\tilde{S}))-\widehat{F}_{S}(\mathrm{w}^{*}_{S})$