# Tight Bounds for Machine Unlearning via Differential Privacy

Yiyang Huang
University of New South Wales
<EMAIL_ADDRESS>Clément L. Canonne
University of Sydney
<EMAIL_ADDRESS>
###### Abstract

We consider the formulation of “machine unlearning” of Sekhari, Acharya,
Kamath, and Suresh (NeurIPS 2021), which formalizes the so-called "right to be
forgotten" by requiring that a trained model, upon request, should be able to
’unlearn’ a number of points from the training data, as if they had never been
included in the first place. Sekhari et al. established some positive and
negative results about the number of data points that can be successfully
unlearnt by a trained model without impacting the model’s accuracy (the
“deletion capacity”), showing that machine unlearning could be achieved by
using differentially private (DP) algorithms. However, their results left open
a gap between upper and lower bounds on the deletion capacity of these
algorithms: our work fully closes this gap, obtaining tight bounds on the
deletion capacity achievable by DP-based machine unlearning algorithms.

##  1 Introduction

Machine learning models trained on user data are now routinely used virtually
everywhere, from recommendation systems to predictive models. In many cases,
this user data itself includes some sensitive information (e.g., healthcare or
race) or private aspects (customer habits, geographic data), sometimes even
protected by law. To address this issue – that the models trained on sensitive
datasets must not leak personal or private information – in a principled
fashion, one of the leading frameworks is that of _differential privacy_ (DP)
[DMNS06], which has _de facto_ become the standard for privacy-preserving
machine learning over the past decade.

At its core, DP requires that the output of a randomized algorithm $M$ not
change drastically if one to modify one of the datapoints: that is, if
$X,X^{\prime}$ are two datasets only differing in _one_ user’s data, then for
all possible outputs $S$ of the algorithm one should have roughly the same
probability of observing $S$ under both inputs:

$\Pr\left[\,M(X)\in S\,\right]\leq e^{\varepsilon}\Pr\left[\,M(X^{\prime})\in
S\,\right]+\delta$

where $\varepsilon>0$ and $\delta\in(0,1]$ quantify the privacy guarantee (the
smaller values, the better the privacy; see Section 2 for formal definitions).
Intuitively, an algorithm $M$ being $(\varepsilon,\delta)$-DP means that its
output does not reveal much about any particular user’s data, since the output
would be nearly identical had this user’s data been completely different.

While the use of differential privacy can mitigate many privacy concerns, it
does come with some limitations. The first is the overhead in brings: that is,
ensuring differential privacy for a learning task typically incurs an overhead
in the number of data points needed to achieve the same accuracy guarantee.
Perhaps more importantly, DP does not solve all possible privacy concerns:
even if a ML model is trained on a sensitive dataset in a differentially
private way, the dataset may still be subject to some attacks – e.g., if the
server where the training data is stored is itself compromised. Somewhat
tautologically: DP is not a silver bullet, and only provides meaningful
guarantees against the threat models it was meant to address.

Another type of concerns focuses on the individual _right to maintain control
on one’s own data_ : broadly speaking, this is asking that each user can
(under some reasonable circumstances) require that their personal data and
information be removed from a company’s collected data and trained models.
This so-called “right to be forgotten,” which allow people to request that
their data be deleted entirely from an ML system, has been passed into
legislation or is considered in some form or another by various countries or
entities, prominently the European Union’s General Data Protection Regulation
(GDPR), the California Privacy Rights Act (CCRA), Canada’s proposed Consumer
Privacy Protection Act (CPPA), and most recently in Australia [Kar23].

However, translating this “right to be forgotten” into practice comes with a
host of challenges, starting with [GGV20] that provided a formal definitional
framework using cryptographic concepts – which led to a new area of research
in ML and computer science, that of _machine unlearning_. A naive technical
solution would be for a given company to keep the original training set at all
times, and, upon a deletion request by a user, remove this user’s data from
the set before retraining the whole model on the result. This, of course,
comes up with two major drawbacks: first, the cost to the company, in terms of
time and computational resources, of retraining a large model on a regular
basis. Second, the _privacy cost_ , as keeping the training set for an
indefinite time in order to be able to handle the deletion requests leaves the
door open to potential attacks and data breaches. Fortunately, there have
been, over the past few years, a flurry of better (and more involved)
approaches to machine unlearning, to handle deletion requests much more
efficiently, and requiring to maintain much less of the training set (see,
e.g., [BCCJTZLP21, NHNLYN22], and related work below).

The above discussion, still, brings to light an important question: _is
machine unlearning, paradoxically, at odds with (differential) privacy? What
is the connection between the two notions: are they complementary, or is there
a trade-off between them?_

This is the main question this work sets out to address. Our starting point is
the probabilistic definition of machine unlearning set forth by Sekhari,
Acharya, Kamath, and Suresh [SAKS21], itself reminiscent of the definition of
Differential Privacy (see Definition 2.3 for the formal statement): a pair of
algorithms $(A,\bar{A})$ is an _$(\varepsilon,\delta)$ -unlearning algorithm_
if (1) $A\colon\mathcal{X}^{\ast}\to\mathcal{W}$ is a (randomized) learning
algorithm which, given a dataset $X\subseteq\mathcal{X}^{\ast}$, outputs model
parameters $A(X)\in\mathcal{W}$; and (2)
$\bar{A}\colon\mathcal{X}^{\ast}\times\mathcal{W}\times\mathcal{T}\to\mathcal{W}$
which, on input a set of _deletion requests_ $U\subseteq X$, previous model
parameters $w$, and some succinct additional “side information”
$T(X)\in\mathcal{T}$ about the original dataset, output updated model
parameters $w^{\prime}\in\mathcal{W}$ from which the data from $U$ has been
unlearned, that is, such that

$\Pr\left[\,\bar{A}(U,A(X),T(X))\in W\,\right]\leq
e^{\varepsilon}\Pr\left[\,\bar{A}(\emptyset,A(X\setminus U),T(X\setminus
U))\in W\,\right]+\delta$

and

$\Pr\left[\,\bar{A}(\emptyset,A(X\setminus U),T(X\setminus U))\in
W\,\right]\leq e^{\varepsilon}\Pr\left[\,\bar{A}(U,A(X),T(X))\in
W\,\right]+\delta$

for every possible set $W\subseteq\mathcal{W}$ of model parameters. Loosely
speaking, this requires that the outcomes of (a) training a model $M$ via $A$
on the dataset $X$ then unlearning some of the original training data
$U\subseteq X$ from $M$ using $\bar{A}$, and (b) training a model $M^{\prime}$
via $A$ directly on the dataset $X\setminus U$ then unlearning nothing via
$\bar{A}$, be nearly indistinguishable.

In their paper, Sekhari et al. [SAKS21] focus on generalization guarantees of
unlearning algorithm, i.e., what can be achieved by unlearning algorithms when
focusing on population loss, namely, when aiming to minimize

$F(w)\coloneqq\mathbb{E}_{x\sim\mathcal{D}}[f(w,x)]$

given a prespecified loss function
$f\colon\mathcal{W}\times\mathcal{X}\to\mathbb{R}$, where the expectation is
over the draw of a new datapoint from the underlying distribution $p$ on the
sample space. The quality of a learning algorithm $A$ is then measured by the
expected excess risk

$R(f,A)\coloneqq\mathbb{E}\left[F(A(X))-\inf_{w\in\mathcal{W}}F(w)\right]$

where the expectation is taking over the random choice of a dataset
$X\sim\mathcal{D}^{n}$ of size $n$, and the randomness of $A$ itself. The
focus of [SAKS21], as is ours, is then to quantify the _deletion capacity_
achievable for $(\varepsilon,\delta)$-unlearning given a prespecified loss
function, that is, the maximum number of data points one can ask to be
forgotten (maximum size of the subset $U$) before the excess risk increases by
more than some threshold (see Definition 2.3).

In their paper, [SAKS21] draw a connection between DP learning algorithms and
unlearning ones, showing that DP learning algorithms do provide _some_
unlearning guarantees out-of-the-box, and that one can achieve non-trivial
unlearning guarantees for convex loss functions by leveraging the literature
on differentially private optimization and learning. One of their main results
is showing that these DP-based unlearning algorithms, which crucially _do not
rely on any side information_ (the additional input $T(X)\in\mathcal{T}$
provided to the unlearning algorithm $\bar{A}$) can handle strictly fewer
deletion requests than general unlearning algorithms which _do_ rely on such
side information.

Their results, however, do not fully characterize the deletion capacity of
these “DP-based” machine unlearning algorithms, leaving a significant gap
between their upper and lower bounds. We argue that fully understanding this
quantity is crucial, as DP-based unlearning algorithms are _exactly_ those for
which there is no conflict between the two notions of DP and unlearning –
_instead, this class of algorithms is the one for which they work hand in
hand._ This is in contrast to the more general unlearning algorithms relying
on maintaining and storing side information about the training set, as this
side information can make their deployment susceptible to privacy breaches.

###  1.1 Our contributions

The main contribution of our paper is a tight bound on the “amount of
unlearning” achievable by _any_ machine unlearning algorithm which does not
rely on side information. For the sake of exposition, we state in this section
informal versions of our results.

######  Theorem 1.0 (Unlearning For Convex Loss Functions (Informal; see
Theorems 3 and 3)).

Let $f\colon\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ be a $1$-Lipschitz
convex loss function, where $\mathcal{W}\subseteq\mathbb{R}^{d}$ is the
parameter space. There exists an $(\varepsilon,\delta)$-machine unlearning
algorithm which, trained on a dataset $S\subseteq\mathcal{X}^{n}$, does not
store _any_ side information about the training set besides the learned model,
and can unlearn up to

$m=O\\!\left(\frac{n\varepsilon\alpha}{\sqrt{d\log(1/\delta)}}\right)$

datapoints without incurring excess population risk greater than $\alpha$.
Moreover, this is tight: there exists a $1$-Lipschitz _linear_ loss function
such that no machine unlearning algorithm can unlearn
$\Omega(\frac{n\varepsilon\alpha}{\sqrt{d\log(1/\delta)}})$ data points
without excess population risk $\alpha$, unless it stores side information.

Our techniques also allow us to easily establish the analogue for _strongly_
convex optimization:

######  Theorem 1.0 (Unlearning For Strongly Convex Loss Functions
(Informal)).

Let $f\colon\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ be a $1$-Lipschitz
_strongly_ convex loss function. There exists an
$(\varepsilon,\delta)$-machine unlearning algorithm which, trained on a
dataset $S\subseteq\mathcal{X}^{n}$, does not store _any_ side information
about the training set besides the learned model, and can unlearn up to

$m=O\\!\left(\frac{n\varepsilon\sqrt{\alpha}}{\sqrt{d\log(1/\delta)}}\right)$

datapoints without incurring excess population risk greater than $\alpha$.
Moreover, this is tight.

We note that, prior to our work, only bounds for the convex loss function case
were known, with an upper bound of
$m=\tilde{O}(n\varepsilon\alpha/\sqrt{d\log(e^{\varepsilon}/\delta)})$ (loose
by polylogarithmic factors for $\varepsilon=O(1)$, as well as an
$1/\sqrt{\varepsilon}$ factor for $\varepsilon\gg 1$) and a limited lower
bound stating that $m\geq 1$ is only possible if
$n\varepsilon/\sqrt{d}=\Omega(1)$. We point out that while the high-privacy
($\varepsilon\ll 1$) is sought as desirable, it is common in real-life,
deployed systems to use much larger values of $\varepsilon$, typically
$\varepsilon\gg 1$. We also provide analogous bounds for the case of _pure_
unlearning, i.e., $\delta=0$ (Sections 3 and 3).

Our next contribution, motivated by the similarity of the formalisation of
machine unlearning (without side information) and that of differential
privacy, is to establish the analogue of key properties of DP for machine
unlearning, namely, _post-processing_ and _composition_ of machine unlearning
algorithms. To do so, we first identify a natural property of machine
unlearning algorithms, which, when satisfied, will allow for the composition
properties:

######  Assumption 1.0 (Unlearning Laziness).

An unlearning algorithm $(\bar{A},A)$ is said to be _lazy_ if, when provided
with an _empty_ set of deletion requests, the unlearning algorithm $\bar{A}$
does not update the model. That is, $\bar{A}(\emptyset,A(X),T(X))=A(X)$ for
all datasets $X$.

We again emphasize that this laziness property is not only intuitive, it is
also satisfied by several existing unlearning algorithms, and in particular
those proposed in [SAKS21].

######  Theorem 1.0 (Post-processing of unlearning).

Let $(\bar{A},A)$ be an $(\varepsilon,\delta)$-unlearning algorithm taking no
side information. Let $f\colon\mathcal{W}\to\mathcal{W}$ be an arbitrary
(possibly randomized) function. Then $(f\circ\bar{A},A)$ is also an
$(\varepsilon,\delta)$-unlearning algorithm.

Under our laziness assumption, we also establish the following:

######  Theorem 1.0 (Chaining of unlearning).

Let $(\bar{A},{A})$ be a _lazy_ $(\varepsilon,\delta)$-unlearning algorithm
taking no side information, and able to handle up to $m$ deletion requests.
Then, the algorithm which uses $(\bar{A},{A})$ to sequentially unlearn $k$
disjoint deletion requests $U_{1},\ldots,U_{k}\subseteq X$ such that
$|\cup_{i}U_{i}|\leq m$, outputting

$\bar{A}(U_{k},\ldots,\bar{A}(U_{1},A(X))\ldots)$

is an $(\varepsilon^{\prime},\delta^{\prime})$-unlearning algorithm, with
$\varepsilon^{\prime}=k\varepsilon$ and
$\delta^{\prime}=\delta\cdot\frac{e^{k\varepsilon}-1}{e^{\varepsilon}-1}=O(k\delta)$
(for $k=O(1/\varepsilon)$).

and, finally,

######  Theorem 1.0 (Advanced grouposition of unlearning).

Let $(\bar{A}_{1},A),\ldots,(\bar{A}_{k},A)$ be _lazy_
$(\varepsilon,\delta)$-unlearning (with common learning algorithm $A$) taking
no side information, and define the grouposition of those unlearning
algorithms, $\tilde{A}$ as

$\tilde{A}(U,A(X))=f\left(\bar{A}_{1}(U,A(X)),\ldots,\bar{A}_{k}(U,A(X))\right)\,.$

where $f\colon\mathcal{W}^{k}\to\mathcal{W}$ is any (possibly randomized)
function. Then, for every $\delta^{\prime}>0$, $(\tilde{A},A)$ is an
$(\varepsilon^{\prime},\delta^{\prime})$-unlearning taking no side
information, where
$\varepsilon^{\prime}=\frac{k}{2}\varepsilon^{2}+\varepsilon\sqrt{2k\ln{(1/\delta^{\prime})}}$.

###  1.2 Related work

Albeit recent, the field of machine unlearning has already received
considerable attention from the ML community since introduced in [CY15]. There
emerged an array of studies and papers focusing on practical solutions and
their empirical performance. We focus in this section on the works most
closely related to ours, mostly theoretical.

Literature in machine unlearning that relates to differential privacy branches
to two: (1) models are prone to attacks when attackers have access to both
before and after version when the deletion requests are processed, and (2) the
conceptual similarity of machine unlearning and differential privacy.

The original, stringent definition of unlearning requires $\varepsilon=0$
(full deletion of the user’s data, as if it had never been included in the
training set in the first place) in contrast to differential privacy that
allows $\varepsilon>0$, leaving a possibility for “memorization.” To relax
this definition, [GGVZ19] proposed the probabilistic version of unlearning.
The formalization of machine unlearning problem was proposed by [GGV20],
adapted from [GGVZ19]’s definition, as a _deletion compliance framework_. In
their work, they claimed the free unlearning effects of differential privacy.
However, the main difference with our work is that [GGV20] relied on the
statistical distance in quantifying error (privacy) whereas we adapt the usual
$(\varepsilon,\delta)$-DP notion. In addition, their work does not investigate
the actual learning performance and quantifies the size of samples (deletion
capacity) that we can unlearn.

After the formalization of the unlearning problem, a major line of work that
involves both unlearning with differential privacy emerged to investigate
adversarial scenarios. For instance, [SBBFZ20] discussed differential privacy
as a defense mechanism to combat inference and reconstruction attacks,
similarly for [CZWBHZ21] and [GGMV22].

There has also been considerable past theoretical work on machine unlearning
and DP that are related to our study, yet most works center upon empirical
risk minimization of unlearning algorithms (e.g. [GGHM20, ISCZ20], [NRS21],
[UMRRA21] etc.), which seeks to find an approximate minimizer on the remaining
dataset after deletion. Closest to our work is the recent paper of [SAKS21],
which formulated the notion of machine unlearning used in our paper and
focused on population loss minimization of approximating unlearning algorithm
(i.e., allowing $\varepsilon>0$). Their objectives, however, were somewhat
orthogonal to ours, as they focused for a large part on minimizing the space
requirements for the side information $T(X)$ provided to the unlearning
algorithm (while our paper focuses on algorithms which do _not_ rely on any
such side information, prone to potential privacy leaks). While their work, to
motivate this focus, established partial bounds on the deletion capacity of
unlearning algorithm that do not take in extra statistics, these bounds were
not tight, and one of our main contributions is closing this gap.

Following [SAKS21], the notion of _online_ unlearning algorithm – which
receive the deletion requests sequentially – was put forward and studied in
[SW22], again with memory efficiency with respect to the side information in
mind; however, their primary focus is on the empirical performance of
unlearning algorithm.

Another work closely to ours is the notion of _certified data removal_
proposed by [GGHM20]. The main difference between
$(\varepsilon,\delta)$-certified removal and the definition from [SAKS21] is
that, in the former, the unlearning mechanism requires access not only to the
samples to be deleted (the set $U\subseteq X$), but also to the full original
training set $X$: this is exactly the type of constraints our work seeks to
avoid, due to the risk of data breach this entails.

###  1.3 Organization of the paper

We first provide the necessary background and notion on differential privacy,
learning, and the formulation of machine unlearning used throughout the paper
in Section 2. We then provide a detailed outline of the proof of our main
result, Theorem 1.1, in Section 3, before concluding with a discussion of
results and future work in Section 4. Finally, proofs are presented in
Appendix.

##  2 Preliminaries

In this section, we recall some notions and results we will extensively rely
on in our proofs and theorems, starting with differential privacy.

###  2.1 Differential Privacy

######  Definition 2.0 ((Central) Differential Privacy (DP)).

Fix $\varepsilon>0$ and $\delta\in[0,1]$. An algorithm
$M\colon\mathcal{X}^{n}\to\mathcal{Y}$ satisfies _$(\varepsilon,\delta)$
-differential privacy_ (DP) if for every pair of neighboring datasets
$X,X^{\prime}$, and every (measurable) subset $S\subseteq\mathcal{Y}$:

$\Pr\left[\,M(X)\in S\,\right]\leq e^{\varepsilon}\Pr\left[\,M(X^{\prime})\in
S\,\right]+\delta.$

We further say that $M$ satisfies _pure_ differential privacy
($\varepsilon$-DP) if $\delta=0$, otherwise it is _approximate_ differential
privacy.

We now recall another notion of differential privacy in terms of Renyi
Divergence, from [BS16].

######  Definition 2.0 (Zero-Concentrated Differential Privacy (zCDP)).

A randomized algorithm $M:\mathcal{X}^{n}\to\mathcal{Y}$ satisfies
$(\xi,\rho)$-zCDP if for every neighboring datasets (differing on a single
entry) $X,X^{\prime}\in\mathcal{X}^{n}$, and $\forall\alpha\in(1,\infty)$:

$\operatorname{D}_{\alpha}(M(X)\|M(X^{\prime}))\leq\xi+\rho\alpha$

where $\operatorname{D}$ is the $\alpha$-Renyi divergence between
distributions of $M(X)$ and $M(X^{\prime})$. We say that $M$ is $\rho$-zCDP
when $\xi=0$.

We use the following group privacy property of zCDP in the proof later.

######  Proposition 2.0 ($k$-distance group privacy of $\rho$-zCDP [BS16,
Proposition 1.9]).

Let $M:\mathcal{X}^{n}\to\mathcal{Y}$ satisfy $\rho$-zCDP. Then, $M$ is
$(k^{2}\rho)$-zCDP for every $X,X^{\prime}\in\mathcal{X}^{n}$ that differs in
at most $k$ entries.

###  2.2 Learning

We also will require some definitions on learning, specifically with respect
to minimizing population loss. Fix any loss function
$f\colon\mathcal{W}\times\mathcal{X}$, where $\mathcal{W}$ is the (model)
parameter space and $\mathcal{X}$ is the sample space. Then, the
generalization loss is defined as

$F(w)\coloneqq\mathbb{E}_{x\sim D}[f(w,x)]$

in which the expectation is over the distribution of $x$ (one sample) and $w$
is the learning output.

Then, let $F^{*}=\inf_{w\in\mathcal{W}}F(w)$ be the minimized population risk
and $w^{\ast}$ is the corresponding minimizer. Define learning algorithm
$A:\mathcal{X}^{n}\to\mathcal{W}$ that takes in dataset $S\in\mathcal{X}^{n}$
and returns hypothesis $w\coloneqq A(S)\in\mathcal{W}$. Then we can define
excess risk as:

$R(f,A)\coloneqq\mathbb{E}\left[F(A(S))-F^{*}\right]$

where the expectation is over the randomness of $A$ and $S$.

Finally, we could define the sample complexity as following ([SAKS21,
Definition 1]), which is analogous to deletion capacity, in which will be
stated later.

######  Definition 2.0 (Sample complexity of learning).

The $\alpha$-sample complexity of a problem is defined as:

$n(\alpha)\coloneqq\min\left\\{n\mid\exists A\text{ s.t.
}\mathbb{E}\left[F(A(S))\right]-F^{*}\leq\alpha,\>\forall\mathcal{D}\right\\}$

###  2.3 Unlearning

As previously discussed, we rely on the definition of unlearning proposed in
by [SAKS21], and maintain same notation. Note that $T(S)$ denotes the data
statistics (which could be the entire dataset $S$ or any form of statistic)
available to $\bar{A}$.

######  Definition 2.0 ($(\varepsilon,\delta)$-unlearning).

For all $S$ of size $n$ and delete requests $U\subseteq S$ such that $|U|\leq
m$, and $W\subseteq\mathcal{W}$, a learning algorithm $A$ and an unlearning
algorithm $\bar{A}$ is $(\varepsilon,\delta)$-unlearning if:

$\Pr\left[\,\bar{A}(U,A(S),T(S))\in W\,\right]\leq
e^{\varepsilon}\Pr\left[\,\bar{A}(\emptyset,A(S\setminus U),T(S\setminus
U))\in W\,\right]+\delta$

and

$\Pr\left[\,\bar{A}(\emptyset,A(S\setminus U),T(S\setminus U))\in
W\,\right]\leq e^{\varepsilon}\Pr\left[\,\bar{A}(U,A(S),T(S))\in
W\,\right]+\delta,$

Our results will be phrased in terms of the deletion capacity, which captures
the number of deletion requests an unlearning algorithm can handle before
seeing a noticeable drop in its output’s accuracy:

######  Definition 2.0 (Deletion Capacity).

Let $\varepsilon,\delta>0$, $S$ be a dataset of size $n$ drawn i.i.d. from
$\mathcal{D}$ and let $\ell(w,z)$ be a loss function. For a pair of learning
and unlearning algorithm $A,\bar{A}$ that are
$(\varepsilon,\delta)$-unlearning, the deletion capacity
$m^{A,\bar{A}}_{\varepsilon,\delta}$ is defined as the maximum size of
deletions requests set $|U|$ that we can unlearn without doing worse in excess
population risk than $\alpha$:

$m^{A,\bar{A}}_{\varepsilon,\delta}(\alpha):=\max\\{m\mid\mathbb{E}\left[\max_{U\subseteq
S:|U|\leq m}F(\bar{A}(U,A(S),T(S)))-F^{*}\right]\leq\alpha\\}$

where $F^{*}=\min_{w\in\mathcal{W}}F(w)$.

##  3 Main result

In this section, we provide a detailed outline of our main result on
unlearning for convex loss functions, Theorem 1.1, for which we prove the
upper and lower bounds separately.

Note that all proofs in this paper are presented in the Appendix.

######  Theorem 3.0 (Deletion capacity from unlearning via DP, Lower Bound).

Suppose $\mathcal{W}\subseteq\mathbb{R}^{d}$, and fix any Lipschitz convex
loss function. Then there exists a lazy ($\varepsilon,\delta)$-unlearning
algorithm $(\bar{A},A)$, where $\bar{A}$ has the form
$\bar{A}(U,A(S),T(S)):=A(S)$ (and thus, in particular, takes no side
information) with deletion capacity

$m_{\varepsilon,\delta}^{A,\bar{A}}(\alpha)\geq\Omega\left(\frac{\varepsilon
n\alpha}{\sqrt{d\log{(1/\delta)}}}\right)$

where the constant in the $\Omega(\cdot)$ only depends on the properties of
the loss function.

######  Theorem 3.0 (Deletion capacity from unlearning via DP, Upper Bound).

There exists a Lipschitz convex loss function (indeed, _linear_) for which any
$(\varepsilon,\delta)$-unlearning algorithm $(\bar{A},A)$ which takes no side
information must have deletion capacity

$m^{A,\bar{A}}_{\varepsilon,\delta}(\alpha)\leq O\left(\frac{\varepsilon
n\alpha}{\sqrt{d\log{(1/\delta)}}}\right)\,.$

We note that the proof of Theorem 1.1 follows from a very similar argument; we
refer the reader to the Appendix for the convex version.

We also present analogous deletion capacity bounds for the
$\varepsilon$-unlearning case:

######  Theorem 3.0 (Deletion capacity from unlearning via DP, Lower Bound).

Suppose $\mathcal{W}\subseteq\mathbb{R}^{d}$, and fix any $L$-Lipschitz
(strongly) convex loss function. Then there exists a lazy
$(\varepsilon,\delta)$-unlearning algorithm $(\bar{A},A)$, where $\bar{A}$ has
the form $\bar{A}(U,A(S),T(S)):=A(S)$ (and thus, in particular, which takes no
side information) with deletion capacity

$m^{A,\bar{A}}_{\varepsilon,\delta}(\alpha)\geq{\Omega\left(\frac{\varepsilon
n\alpha^{2}}{d}\right)}.$

######  Theorem 3.0 (Deletion capacity from unlearning via DP, Upper Bound).

There exists a Lipschitz convex loss function for which any
$\varepsilon$-unlearning algorithm $(\bar{A},A)$ which takes no side
information must have deletion capacity

$m^{A,\bar{A}}_{\varepsilon,\delta}(\alpha)\leq O\left(\frac{\varepsilon
n\alpha}{d}\right)\,.$

##  4 Discussion and future work

Our work fully characterizes the deletion capacity of any unlearning algorithm
$(\bar{A},A)$ minimizing population risk under both convex and strongly convex
loss functions, when only given the model parameters (output of the learning
algorithm) and the set of deletion requests. This restriction, namely that the
unlearning algorithm does not rely on any additional side information, is
motivated by the potential privacy risks storing (non-private) side
information can entail.

We hope our work will lead to further study of the interplay between
differential privacy and machine unlearning, and to additional study of “DP-
like” properties of machine unlearning, such as the postprocessing and
composition properties our present work identified. In view of the myriad
applications these properties have had in privacy-preserving algorithm design,
we believe that their analogue for machine unlearning will prove very useful.

We leave for future work the question of whether variants of the standard
threat model for differential privacy (specifically, pan-privacy, or privacy
under continual observation) could have implications for machine unlearning in
an online setting where deletion requests come sequentially.

#### One final remark.

Before concluding, we believe it is important to reiterate a key point about
our work. One could view our main results as focusing on what can be achieved
by unlearning algorithms “which, upon a deletion request, do not do anything,”
since they leverage the guarantees already provided by differential privacy.
However, this does _not_ mean that the algorithm “does nothing” _overall_ :
instead, the point here is that the algorithms considered already satisfy the
very stringent notion of DP, and as such already paid some utility cost to
provide this guarantee: as a result, _having paid that price_ , they benefit
from some “unlearning bonus” for free.

Put differently, the aim of this paper is not to promote or justify when it
comes to unlearning, but instead to characterize exactly how much unlearning
guarantees come “for free” if one decides or already has to offer the strong
guarantee of differential privacy. Thus, our aim is not to discourage
unlearning-only solutions when DP is not required; but instead, by
understanding the interplay between DP and unlearning, to show that the joint
(and seemingly daunting) requirement of both differential privacy and right to
be forgotten requirement is more affordable than it seems.

## References

  * [BCCJTZLP21] Lucas Bourtoule, Varun Chandrasekaran, Christopher A. Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie and Nicolas Papernot  “Machine Unlearning”  In _42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021_ IEEE, 2021, pp. 141–159
  * [BFTT19] Raef Bassily, Vitaly Feldman, Kunal Talwar and Abhradeep Guha Thakurta  “Private Stochastic Convex Optimization with Optimal Rates”  In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems_ , 2019, pp. 11279–11288
  * [BS16] Mark Bun and Thomas Steinke  “Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds”  In _Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I_ 9985, Lecture Notes in Computer Science, 2016, pp. 635–658
  * [BST14] Raef Bassily, Adam D. Smith and Abhradeep Thakurta  “Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds”  In _55th IEEE Annual Symposium on Foundations of Computer Science, FOCS_ IEEE Computer Society, 2014, pp. 464–473
  * [CY15] Yinzhi Cao and Junfeng Yang  “Towards Making Systems Forget with Machine Unlearning”  In _2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, May 17-21, 2015_ IEEE Computer Society, 2015, pp. 463–480
  * [CZWBHZ21] Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert and Yang Zhang  “When Machine Unlearning Jeopardizes Privacy”  In _CCS ’21: 2021 ACM SIGSAC Conference on Computer and Communications Security, Virtual Event, Republic of Korea, November 15 - 19, 2021_ ACM, 2021, pp. 896–911
  * [DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith  “Calibrating Noise to Sensitivity in Private Data Analysis”  In _Proceedings of the 3rd Conference on Theory of Cryptography_ , TCC ’06  Berlin, Heidelberg: Springer, 2006, pp. 265–284
  * [FKT20] Vitaly Feldman, Tomer Koren and Kunal Talwar  “Private Stochastic Convex Optimization: Optimal Rates in Linear Time”  In _Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2020  Chicago, IL, USA: Association for Computing Machinery, 2020, pp. 439–449
  * [GGHM20] Chuan Guo, Tom Goldstein, Awni Y. Hannun and Laurens Maaten  “Certified Data Removal from Machine Learning Models”  In _Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event_ 119, Proceedings of Machine Learning Research  PMLR, 2020, pp. 3832–3842
  * [GGMV22] Ji Gao, Sanjam Garg, Mohammad Mahmoody and Prashant Nalini Vasudevan  “Deletion inference, reconstruction, and compliance in machine (un)learning”  In _Proc. Priv. Enhancing Technol._ 2022.3, 2022, pp. 415–436
  * [GGV20] Sanjam Garg, Shafi Goldwasser and Prashant Nalini Vasudevan  “Formalizing Data Deletion in the Context of the Right to be Forgotten”, Cryptology ePrint Archive, Paper 2020/254, 2020
  * [GGVZ19] Antonio A. Ginart, Melody Y. Guan, Gregory Valiant and James Y. Zou  “Making AI Forget You: Data Deletion in Machine Learning”  In _Neural Information Processing Systems_ , 2019
  * [ISCZ20] Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri and James Y. Zou  “Approximate Data Deletion from Machine Learning Models: Algorithms and Evaluations”, 2020  arXiv:2002.10077
  * [Kar23] Paul Karp  “Australia to consider European-style right to be forgotten privacy laws”  In _The Guardian_ , 2023
  * [NHNLYN22] Thanh Tam Nguyen, Thanh Trung Huynh, Phi Le Nguyen, Alan Wee-Chung Liew, Hongzhi Yin and Quoc Viet Hung Nguyen  “A Survey of Machine Unlearning”  In _CoRR_ abs/2209.02299, 2022  arXiv:2209.02299
  * [NRS21] Seth Neel, Aaron Roth and Saeed Sharifi-Malvajerdi  “Descent-to-Delete: Gradient-Based Methods for Machine Unlearning”  In _Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide_ 132, Proceedings of Machine Learning Research  PMLR, 2021, pp. 931–962
  * [SAKS21] Ayush Sekhari, Jayadev Acharya, Gautam Kamath and Ananda Theertha Suresh  “Remember What You Want to Forget: Algorithms for Machine Unlearning”  In _Advances in Neural Information Processing Systems_ 34 Curran Associates, Inc., 2021, pp. 18075–18086
  * [SBBFZ20] Ahmed Salem, Apratim Bhattacharya, Michael Backes, Mario Fritz and Yang Zhang  “Updates-Leak: Data Set Inference and Reconstruction Attacks in Online Learning”  In _29th USENIX Security Symposium, USENIX Security 2020, August 12-14, 2020_ USENIX Association, 2020, pp. 1291–1308
  * [SSSS09] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro and Karthik Sridharan  “Stochastic Convex Optimization”  In _Annual Conference Computational Learning Theory_ , 2009
  * [SU16] Thomas Steinke and Jonathan R. Ullman  “Between Pure and Approximate Differential Privacy”  In _J. Priv. Confidentiality_ 7.2, 2016
  * [SW22] Vinith M. Suriyakumar and Ashia C. Wilson  “Algorithms that Approximate Data Removal: New Results and Limitations”  In _NeurIPS_ , 2022
  * [UMRRA21] Enayat Ullah, Tung Mai, Anup Rao, Ryan A. Rossi and Raman Arora  “Machine Unlearning via Algorithmic Stability”  In _Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA_ 134, Proceedings of Machine Learning Research  PMLR, 2021, pp. 4126–4142
  * [Vad17] Salil P. Vadhan  “The Complexity of Differential Privacy”  In _Tutorials on the Foundations of Cryptography_ Springer International Publishing, 2017, pp. 347–450

##  Appendix A Proof of Theorem 3.1 (Lower Bound)

######  Theorem A.0 (Deletion capacity from unlearning via DP, Lower Bound
(Theorem 3.1 in Submission)).

Suppose $\mathcal{W}\subseteq\mathbb{R}^{d}$, and fix any Lipschitz convex
loss function. Then there exists a lazy $(\varepsilon,\delta)$-unlearning
algorithm $(\bar{A},A)$, where $\bar{A}$ has the form
$\bar{A}(U,A(S),T(S)):=A(S)$ (and thus, in particular, takes no side
information) with deletion capacity

$m_{\varepsilon,\delta}^{A,\bar{A}}(\alpha)\geq\Omega\left(\frac{\varepsilon
n\alpha}{\sqrt{d\log{(1/\delta)}}}\right)$

where the constant in the $\Omega(\cdot)$ only depends on the properties of
the loss function.

######  Lemma A.0 (zCDP mini-batch noisy SGD [FKT20]).

Fix any $L$-Lipschitz convex loss function over a convex subset $\mathcal{B}$
of $\mathbb{R}^{d}$ of diameter $D$. Then there exists an algorithm $A$ which
satisfies $(\rho^{2}/2)$-zCDP with excess population loss:

$\mathbb{E}\left[F(\theta)-\min_{\theta\in\mathcal{B}}F(\theta)\right]\leq
O\left(DL\cdot\left(\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{\rho n}\right)\right)$

where the expectation is taken over the randomness of $A$.

###### Proof of Section 3.

The proof follows the same setting as in [SAKS21]. The main change is that we
apply group privacy bounds in terms of zCDP instead of the standard DP
guarantee provided by [BFTT19, Theorem 3.2].

We first establish a tighter bound for algorithm that achieves $m$-entries
group privacy via Appendix A. [FKT20] provides a zCDP version of [BFTT19,
Theorem 3.2] with $\rho^{2}/2$-zCDP, hence by group privacy, we yield
$\frac{m^{2}\rho^{2}}{2}$-zCDP by Section 2.1 for neighboring datasets
differing in $m$ entries. Then, translating $\frac{m^{2}\rho^{2}}{2}$-zCDP to
$(\varepsilon,\delta)$-DP yields
$\varepsilon=O\left({m\rho\sqrt{\log{(1/\delta)}}}\right)$.

By the above discussion, using this zCDP-private learning algorithm with
$\rho=\Theta\left(\frac{\varepsilon}{m\sqrt{\ln{(1/\delta)}}}\right)$, we get
an excess population loss bounded by

$O\left(DL\left(\frac{1}{\sqrt{n}}+\frac{m\sqrt{d\ln{(1/\delta)}}}{\varepsilon
n}\right)\right)$ (1)

It only remains to show how the claimed deletion capacity bound follows from
this excess population risk guarantee. Construct, as discussed earlier, an
unlearning algorithm $\bar{A}$ that returns the input without making any
changes (and in particular does not require any additional statistics $T(S)$,
and satisfies the laziness assumption). Since $A$ is
$(\varepsilon,\delta)$-DP, for any set $U\subseteq S,|U|=m$, and
$W\subseteq\mathcal{W}$,

$\displaystyle\Pr\left[\,A(S)\in W\,\right]$ $\displaystyle\leq
e^{\varepsilon}\Pr\left[\,A(S^{\prime})\in W\,\right]+\delta$
$\displaystyle\Pr\left[\,A(S^{\prime})\in W\,\right]$ $\displaystyle\leq
e^{\varepsilon}\Pr\left[\,A(S)\in W\,\right]+\delta$

. But since $\bar{A}(U,A(S))=A(S)$, this readily yields, letting
$S^{\prime}:=S\setminus U$:

$\displaystyle\Pr\left[\,\bar{A}(U,A(S))\in W\,\right]$ $\displaystyle\leq
e^{\varepsilon}\Pr\left[\,\bar{A}(\emptyset,A(S^{\prime}))\in
W\,\right]+\delta$
$\displaystyle\Pr\left[\,\bar{A}(\emptyset,A(S^{\prime}))\in W\,\right]$
$\displaystyle\leq e^{\varepsilon}\Pr\left[\,\bar{A}(U,A(S))\in
W\,\right]+\delta$

which implies that $(A,\bar{A})$ is indeed $(\varepsilon,\delta)$-unlearning
for $U$ of size (up to) $m$.

Recalling the definition of deletion capacity, we finally deduce from (1) the
deletion capacity with excess population risk less than $\alpha$:

$m^{A,\bar{A}}_{\varepsilon,\delta}(\alpha)\geq
m=\Omega\left(\frac{\varepsilon n\alpha}{\sqrt{d\ln{(1/\delta)}}}\right)$

where the $O(\cdot)$ hides constant factors depending only on the loss
function (namely, the Lipschitz function $L$, and the diameter $D$). ∎

##  Appendix B Proof of Theorem 3.2 (Upper Bound)

######  Theorem B.0 (Deletion capacity from unlearning via DP, Upper Bound
(Theorem 3.3 in Submission)).

There exists a Lipschitz convex loss function (indeed, _linear_) for which any
$(\varepsilon,\delta)$-unlearning algorithm $(\bar{A},A)$ which takes no side
information must have deletion capacity

$m^{A,\bar{A}}_{\varepsilon,\delta}(\alpha)\leq O\left(\frac{\varepsilon
n\alpha}{\sqrt{d\log{(1/\delta)}}}\right)\,.$

###### Proof of Section 3.

We will consider the following linear (and therefore convex and Lipschitz)
loss function $\mathcal{L}(\theta,S)$:

$\mathcal{L}(\theta,S):=-\langle\theta,\sum^{n}_{i=1}x_{i}\rangle$ (2)

for dataset $S$ of $n$ points
$x_{1},\dots,x_{n}\in\\{-\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}}\\}^{d}$. We
also define the 1-way marginal query, i.e. average, as:

$q(S):=\frac{1}{n}\sum^{n}_{i=1}x_{i}\,.$ (3)

To establish our deletion capacity lower bound with respect to this loss
function, we will proceed in three stages: the first, relatively standard, is
to relate population loss (what we are interested in) to _empirical_ loss –
which allows us to focus on the existence of a “hard dataset.” The second step
is then to establish a sample complexity lower bound on the empirical risk
(for this loss function) of any $(\varepsilon,\delta)$-DP algorithm, via a
reduction to differentially private computing of 1-marginals. This step is
similar to the one underlying the (weaker) lower bound of [SAKS21] (itself
relying on an argument of [BFTT19]), although a more careful choice of
building blocks for the reduction already allows us to obtain an improvement
by logarithmic factors.

Third, lift this DP lower bound to a stronger lower bound for DP with respect
to edit distance $m$. This step is quite novel, as it morally corresponds to
establishing the converse of the grouposition property of differential privacy
(for our specific setting), a converse which does _not_ hold in general. Our
argument, relatively simple, will crucially rely on the linearity of our loss
function.

We omit the details of the first step (reduction from population to empirical
loss) in this detailed outline, as it is quite standard. For the second step,
our starting point is the following lower bound of Steinke and Ullman:

######  Theorem B.0 (Lower bound for one-way marginals [SU16, Main Theorem]).

For every $\varepsilon\in(0,1)$, every function $\delta=\delta(n)$ such that
$\delta\geq 2^{-o(n)}$ and $\delta\leq 1/n^{1+\Omega({1}})$, and for every
$\alpha\leq 1/10$, if $A:\\{\pm 1\\}^{n\times d}\to[\pm 1]^{d}$ is
$(\varepsilon,\delta)$-differentially private and
$\mathbb{E}\left[\|\mathcal{A}(S)-q(S)\|_{1}\right]\leq\alpha d$ (i.e., with
average-case accuracy $\alpha$) for all $S\in\\{\pm 1\\}^{n\times d}$, then we
must have

$n\geq\Omega\left({\frac{\sqrt{d\ln{(1/\delta)}}}{\varepsilon\alpha}}\right).$

Using this lower bound as a blackbox, we then can adapt the argument of
[BST14, Lemma 5.1, Part 2] to obtain the following stronger result:

######  Lemma B.0 (Lower bound for Privately Computing 1-way Marginals).

Let $n,d\in\mathbb{N},\varepsilon>0,2^{-o{n}}\leq\delta(n)\leq
1/n^{1+\Omega(1)}$. For all $\alpha\leq 1/10$, if $\mathcal{A}$ is
$(\varepsilon,\delta)$-differentially private. Then, for
$S\subseteq\\{\pm\frac{1}{\sqrt{d}}\\}^{n\times d}$, one must have

$\mathbb{E}\left[\|\mathcal{A}(S)-q(S)\|_{2}\right]=\min\left(\alpha,\Omega\left(\frac{\sqrt{d\ln{(1/\delta)}}}{n\varepsilon}\right)\right)\,,$

where $q(S)=\frac{1}{n}\sum^{n}_{i=1}x_{i}$ as before. Moreover, this still
holds under the assumption that
$\|q(S)\|_{2}\in[\frac{M-1}{n},\frac{M+1}{n}]$, where
$M=\Omega(\min(n\alpha,\frac{\sqrt{d\ln{(1/\delta)}}}{\varepsilon}))$.

###### Proof of Appendix B.

Our proof follows the same outline as in [BST14], but using the result of
Appendix B as a black-box instead of the packing argument of [BST14]. Before
doing so, we have to translate the result from Theorem B into our setting, and
handle the slightly different choice of parameterization ($\\{\pm 1\\}^{d}$
instead of $\\{\pm 1/\sqrt{d}\\}^{d}$).

Let $n_{\alpha}\coloneqq
C\cdot\frac{\sqrt{d\ln{(1/\delta)}}}{\varepsilon\alpha}$, where $C>0$ is
(strictly smaller than) the constant hidden in the $\Omega(\cdot)$ of Appendix
B. By contradiction, suppose that, for some $n\leq n_{\alpha}$, we have an
$(\varepsilon,\delta)$-differentially private algorithm $\mathcal{A}$ that
takes in a dataset $S\subseteq\\{\pm\frac{1}{\sqrt{d}}\\}^{n\times d}$ and
outputs an estimate $\mathcal{A}(S)$ of $q(S)$ with expected $L_{2}$ error
$\alpha$. Rescaling, we get that the algorithm $\mathcal{A}^{\prime}$ which,
on input $S^{\prime}\subseteq\\{\pm 1\\}^{n\times d}$, computes $S\coloneqq
S^{\prime}/\sqrt{d}\subseteq\\{\pm\frac{1}{\sqrt{d}}\\}^{n\times d}$ and
outputs $\sqrt{d}\cdot\mathcal{A}(S)$ is (1) $(\varepsilon,\delta)$-DP by
post-processing, and (2) since $q$ is linear, has error related to that of
$\mathcal{A}$ by

$\mathbb{E}\left[\|\mathcal{A}^{\prime}(S^{\prime})-q(S^{\prime})\|_{2}\right]=\sqrt{d}\cdot\mathbb{E}\left[\|\mathcal{A}(S)-q(S)\|_{2}\right]\leq\sqrt{d}\cdot\alpha$
(4)

However, by Appendix B, $\mathcal{A}^{\prime}$ must have expected $L_{1}$
error at least $\alpha d$ since $n\leq n_{\alpha}$. By Cauchy–Schwarz,

$\alpha
d<\mathbb{E}\left[\|\mathcal{A}^{\prime}(S^{\prime})-q(S^{\prime})\|_{1}\right]\stackrel{{\scriptstyle\rm{}CS}}{{\leq}}\sqrt{d}\cdot\mathbb{E}\left[\|\mathcal{A}^{\prime}(S^{\prime})-q(S^{\prime})\|_{2}\right]\stackrel{{\scriptstyle\eqref{eq:bound:l2:error:Aprime}}}{{\leq}}\sqrt{d}\cdot(\alpha\sqrt{d})=\alpha
d$

leading to a contradiction. So for $n\leq n_{\alpha}$, any
$(\varepsilon,\delta)$-DP algorithm to estimate $q$ must have expected $L_{2}$
error at least $\alpha$, i.e.,
$\mathbb{E}\left[\|\mathcal{A}(S)-q(S)\|_{2}\right]\geq\alpha$. Further, one
can see by inspection of the proof of Appendix B that $\|q(S)\|_{2}$ satisfies
the assumption in the "Moreover."

Now, for $n\geq n_{\alpha}$ (assume, for simplicity and without loss of
generality, that $n-n_{\alpha}$ is even), we use a padding argument to
establish the other part of the bound. Let $\mathcal{A}$ be any
$(\varepsilon,\delta)$-differentially private algorithm for answering $q$ on
datasets of size $n$. Suppose for the sake of contradiction, that
$\mathcal{A}$ satisfies

$\mathbb{E}\left[\|\mathcal{A}(S)-q(S)\|_{2}\right]<\frac{n_{\alpha}}{n}\cdot\alpha$
(5)

for every dataset $S$ of size $n$.

Fix an arbitrary point $\mathbf{c}\in\\{\pm 1/\sqrt{d}\\}^{d}$. Given any
dataset $S=(x^{(1)},\dots,x^{(n_{\alpha})})\in\left\\{\pm 1\right\\}^{d\times
n_{\alpha}}$ of size $n_{\alpha}$, we construct $\hat{S}$ of size $n$ as
follows. Its first $n_{\alpha}$ entries are $x^{(1)},\dots,x^{(n_{\alpha})}$;
then for the remaining $n-n_{\alpha}$, we have (1) the first
$\lceil\frac{n-n_{\alpha}}{2}\rceil$ (i.e. the first half) of those entries
are all copies of $\mathbf{c}$, and (2) the remaining
$\lfloor\frac{n-n_{\alpha}}{2}\rfloor$ are copies of $-\mathbf{c}$.

Note that we have

$q(\hat{S})=\frac{n_{\alpha}}{n}q(S)$

for every $S$, and in particular $\|q(\hat{S})\|_{2}$ satisfies the assumption
in the "Moreover."

Now, we define an algorithm $\hat{\mathcal{A}}$ for approximating $q$ on
datasets of size $n_{\alpha}$ as follows. On input $S\in\left\\{\pm
1\right\\}^{d\times n_{\alpha}}$, $\hat{\mathcal{A}}$:

  1. 1.

Computes $\hat{S}\in\left\\{\pm 1\right\\}^{d\times n}$ as above

  2. 2.

Outputs $\frac{n}{n_{\alpha}}\mathcal{A}(\hat{S})$

Since $\mathcal{A}$ is already differentially private, $\hat{\mathcal{A}}$ is
also $(\varepsilon,\delta)$-DP due to the post-processing property of
differential privacy. Moreover,

$\mathbb{E}\left[\|\hat{\mathcal{A}}(S)-q(S)\|_{2}\right]=\mathbb{E}\left[\left\|\frac{n}{n_{\alpha}}\mathcal{A}(\hat{S})-\frac{n}{n_{\alpha}}q(\hat{S})\right\|_{2}\right]=\frac{n}{n_{\alpha}}\mathbb{E}\left[\left\|\mathcal{A}(\hat{S})-q(\hat{S})\right\|_{2}\right]\stackrel{{\scriptstyle\eqref{eq:assumption:for:contradiction:padding}}}{{<}}\frac{n}{n_{\alpha}}\cdot\frac{n_{\alpha}}{n}\alpha=\alpha$

and so $\hat{\mathcal{A}}$ achieves expected error strictly smaller than
$\alpha$ on datasets of size $n_{\alpha}$; which contradicts the first part of
the lower bound we already established. So for $n>n_{\alpha}$, any
$(\varepsilon,\delta)$-DP algorithm to estimate $q$ must have expected $L_{2}$
error at least
$\frac{n_{\alpha}}{n}\cdot\alpha=C\cdot\frac{\sqrt{d\ln(1/\delta)}}{n\varepsilon}$.

Finally, we we have shown that for every $n$ and every $\varepsilon>0$, there
is a constant $C>0$ such that every $(\varepsilon,\delta)$-differentially
private algorithm $\mathcal{A}$ answering the linear query $q$ must have, on
some dataset $S$ of size $n$, expected $L_{2}$ error at least

$\mathbb{E}\left[\|\mathcal{A}(S)-q(S)\|_{2}\right]=\min\left(\alpha,C\cdot\frac{\sqrt{d\ln(1/\delta)}}{n\varepsilon}\right).$

proving the lemma. ∎

Combining the above with the argument strategy of [BST14, Theorem 5.3] finally
yields the main lemma for the second step of our proof for Section 3:

######  Lemma B.0 (Lower bound on empirical loss of $(\varepsilon,\delta)$-DP
algorithms).

Let $n,d\in\mathbb{N},\varepsilon>0$, and $\delta=o(1/n)$. For every
$(\varepsilon,\delta)$-differentially private algorithm with output
$\theta^{priv}$, there is a dataset
$S=\\{x_{1},\ldots,x_{n}\\}\subseteq\\{-\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}}\\}^{d}$
such that

$\mathbb{E}\left[\mathcal{L}(\theta^{priv},S)-\mathcal{L}(\theta^{*},S)\right]=\min\left(\alpha^{2},\Omega\left(\frac{d\log(1/\delta)}{n^{2}\varepsilon^{2}}\right)\right)$

where $\theta^{*}:=\frac{\sum^{n}_{i=1}x_{i}}{\|\sum^{n}_{i=1}x_{i}\|_{2}}$ is
the minimizer of
$\mathcal{L}(\theta,S):=-\langle\theta,\frac{1}{n}\sum^{n}_{i=1}x_{i}\rangle$
(which is linear and, as such, Lipschitz and convex).

###### Proof of Appendix B.

This proof follows the same structure as that of [BST14, Theorem 5.3] but
adapt the bound in terms of expectation.

First, observe that for any $\theta\in\mathbb{B}$ and dataset $S$ we have:

$\mathcal{L}(\theta,S)-\mathcal{L}(\theta^{*},S)=\frac{1}{2}\|q(S)\|_{2}\|\theta-\theta^{*}\|^{2}_{2},$

since
$\|\theta-\theta^{*}\|^{2}_{2}=\|\theta^{*}\|^{2}_{2}+\|\theta\|^{2}_{2}-2\langle\theta,\theta^{*}\rangle=2(1-\langle\theta,\theta^{*}\rangle)$
using the fact that $\theta^{*},\theta\in\mathbb{B}$ have
$\|\theta\|_{2},\|\theta^{\ast}\|_{2}=1$.

Suppose that there is an $(\varepsilon,\delta)$-differentially private
algorithm $\mathcal{A}$ that outputs $\theta^{priv}$ such that, for every
dataset $S\subseteq\\{-\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}}\\}^{d}$, we have:

$\mathbb{E}\left[\mathcal{L}(\theta^{priv},S)-\mathcal{L}(\theta^{*},S)\right]\leq\Delta$

for a sufficiently small constant $C>0$, and some $\Delta\geq 0$. We will
prove a lower bound on $\Delta$. To do so, recall
$q(S)=\theta^{*}\cdot\|q(S)\|_{2}$; and that the lower bound from Appendix B
still holds when the dataset $S$ is promised to be such that $q(S)\in[(M\pm
1)/n]$, for $M=\Theta(\min(n\alpha,\sqrt{d\log(1/\delta)}/\varepsilon)$.

Consider the algorithm (private by post-processing) $\mathcal{A}$ which
outputs $\mathcal{A}(S)=\frac{M}{n}\theta^{priv}$. Then, for any dataset $S$
such that $\|\sum_{i=1}^{n}x_{i}\|_{2}\in[M-1,M+1]$,

$\mathbb{E}\left[\|\mathcal{A}(S)-q(S)\|_{2}\right]\leq\mathbb{E}\left[\|\mathcal{A}(S)-q(S)\|_{2}^{2}\right]^{1/2}=\mathbb{E}\left[\|\frac{M}{n}\theta^{priv}-q(S)\|_{2}^{2}\right]^{1/2}\,.$

On the other hand,

$\displaystyle\mathbb{E}\left[\|\frac{M}{n}\theta^{priv}-q(S)\|_{2}^{2}\right]$
$\displaystyle\leq
2\left(\mathbb{E}\left[\|q(S)\|_{2}^{2}\|\theta^{priv}-\theta^{*}\|_{2}^{2}\right]+\mathbb{E}\left[\|\frac{M}{n}\theta^{priv}-\|q(S)\|_{2}\theta^{priv}\|_{2}^{2}\right]\right)$
$\displaystyle=4\|q(S)\|_{2}\mathbb{E}\left[\mathcal{L}(\theta^{priv},S)-\mathcal{L}(\theta^{*},S)\right]+2\left(\frac{M}{n}-\|q(S)\|_{2}\right)^{2}$
$\displaystyle\leq\frac{4(M+1)}{n}\mathbb{E}\left[\mathcal{L}(\theta^{priv},S)-\mathcal{L}(\theta^{*},S)\right]+\frac{2}{n^{2}}$
(as $n\|q(S)\|_{2}\in[M-1,M+1]$)
$\displaystyle\leq\frac{4(M+1)\Delta}{n}+\frac{2}{n^{2}}$

By Appendix B, we know that
$\mathbb{E}\left[\|\mathcal{A}(S)-q(S)\|_{2}\right]=\min\left(\alpha,C\cdot\frac{\sqrt{d\ln(1/\delta)}}{n\varepsilon}\right)$,
for some absolute constant $C>0$, in the worst case. Hence, we must have

$\frac{\Delta\cdot
M}{n}\geq\min\left(\alpha^{2},\frac{d\ln(1/\delta)}{n^{2}\varepsilon^{2}}\right);$

recalling the setting of $M$, we get
$\mathbb{E}\left[\mathcal{L}(\theta^{priv},S)-\mathcal{L}(\theta^{*},S)\right]=\min\left(\alpha,\Omega\left(\sqrt{\frac{d\ln(1/\delta)}{n\varepsilon}}\right)\right)$.
∎

The above lemma establishes a lower bound on the empirical loss of any
$(\varepsilon,\delta)$-differentially private algorithm. To derive from this
our claimed lower bound on unlearning algorithms, we need to introduce a
dependence on $m$, the deletion capacity (i.e., number of points to unlearn).
This is done in the last (third) step of our argument, via a reduction which
establishes a (restricted) converse to the grouposition property of DP.

Recall that an algorithm $M\colon\mathcal{X}^{n}\to\mathcal{Y}$ satisfies
$(\varepsilon,\delta)$-DP for edit distance $m$ if for every pair of
neighboring datasets _$X,X^{\prime}$ that differ in up to $m$ entries_, and
every $S\subseteq\mathcal{Y}$:

$\Pr\left[\,M(X)\in S\,\right]\leq e^{\varepsilon}\Pr\left[\,M(X^{\prime})\in
S\,\right]+\delta.$

We apply this $m$-edit distance $(\varepsilon,\delta)$-DP on Appendix B by a
reduction that shows: for any differentially private algorithm with respect to
edit distance at most $m$ must incur an empirical loss given by Appendix B.

######  Lemma B.0.

Suppose there exists an $m$-edit distance $(\varepsilon,\delta)$-DP algorithm
$\mathcal{M}$ that takes in a dataset $S$ of size $n$ to approximate $q(S)$
(as defined in (3)), with empirical loss $\gamma$. Then, we can construct a
$1$-edit distance (i.e., standard) $(\varepsilon,\delta)$-DP algorithm
$\mathcal{M}^{\prime}$ that, on input a dataset $S^{\prime}$ of $N=n/m$ data
points, approximates $q(S^{\prime})$ to error $\gamma$.

###### Proof of Appendix B.

The reduction is quite simple: given $\mathcal{M}$, construct
$\mathcal{M}^{\prime}$ as follows for $N=\frac{n}{m}$ inputs:

$\mathcal{M}^{\prime}(x_{1},\ldots,x_{N})=\mathcal{M}(\underbrace{x_{1},\ldots,x_{1},}_{m}\underbrace{x_{2},\ldots,x_{2}}_{m},\ldots,\underbrace{x_{N},\ldots,x_{N}}_{m})\,.$

We immediately have that $\mathcal{M}^{\prime}$ is $(\varepsilon,\delta)$-DP
for the usual $1$-edit distance between datasets, since $\mathcal{M}$ is DP
with respect to edit distance $m$. The sample complexity and error bound then
follows direction from $n=N\times m$, where $n\geq N,N\in\mathbb{N},m\geq 1$,
and the fact that
$q(x_{1},\dots,x_{N})=q(x_{1},\dots,x_{1},x_{2},\dots,x_{2},\dots,x_{N},\dots,x_{N})$
due to the definition of $q$. ∎

Combining Lemma B with Appendix B, we get that any $m$-edit distance
$(\varepsilon,\delta)$-DP algorithm $\mathcal{M}$ approximating $q$ on
datasets of size $n=N\times m$ must have error $\gamma$ at least

$\min\left(\alpha,\Omega\left(\frac{\sqrt{d\log(1/\delta)}}{N\varepsilon}\right)\right)=\min\left(\alpha,\Omega\left(\frac{m\sqrt{d\log(1/\delta)}}{n\varepsilon}\right)\right)$

which, reorganising the terms and recalling the definition of deletion
capacity, yields the claimed bound on $m^{A,\bar{A}}_{\varepsilon,\delta}$,
and hence completes the proof for Section 3. ∎

The proof of Theorem 1.2 (the strongly convex case), restated below, is
analogous to those of Sections 3 and 3, but using [FKT20, Theorem 5.1] for the
upper bound (instead of Appendix A) and [SU16, Theorem 5.2] for the lower
bound (instead of Appendix B).

######  Theorem B.0 (Unlearning For Strongly Convex Loss Functions (Theorem
1.2, restated)).

Let $f\colon\mathcal{W}\times\mathcal{X}\to\mathbb{R}$ be a $1$-Lipschitz
_strongly_ convex loss function. There exists an
$(\varepsilon,\delta)$-machine unlearning algorithm which, trained on a
dataset $S\subseteq\mathcal{X}^{n}$, does not store _any_ side information
about the training set besides the learned model, and can unlearn up to

$m=O\\!\left(\frac{n\varepsilon\sqrt{\alpha}}{\sqrt{d\log(1/\delta)}}\right)$

datapoints without incurring excess population risk greater than $\alpha$.
Moreover, this is tight.

##  Appendix C Proof of Theorems 3.3 and 3.4

######  Lemma C.0 (Lower bound on empirical loss of $\varepsilon$-DP
algorithms).

Let $n,d\in\mathbb{N},\varepsilon>0$. For every $\varepsilon$-differentially
private algorithm with output $\theta^{priv}$, there is a dataset
$S=\\{x_{1},\ldots,x_{n}\\}\subseteq\\{-\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}}\\}^{d}$
such that

$\mathbb{E}\left[\mathcal{L}(\theta^{priv},S)-\mathcal{L}(\theta^{*},S)\right]=\min\left(1,\Omega\left(\frac{d}{n\varepsilon}\right)\right)$

where $\theta^{*}:=\frac{\sum^{n}_{i=1}x_{i}}{\|\sum^{n}_{i=1}x_{i}\|_{2}}$ is
the minimizer of
$\mathcal{L}(\theta,S):=-\langle\theta,\frac{1}{n}\sum^{n}_{i=1}x_{i}\rangle$
(which is linear and, as such, Lipschitz and convex).

###### Proof.

We translate [BST14, Theorem 5.2] in to expected value for the sake of
coherence throughout this paper. From [BST14, Theorem 5.2], we have that, for
some constant $c>0$, the statement can be expressed as:

$\Pr\left[\,\mathcal{L}(\theta^{priv},S)-\mathcal{L}(\theta^{*},S)\geq
c\cdot\min(n,d/\varepsilon)\,\right]\geq 1/2$

Then since $\mathcal{L}(\theta^{priv},S)-\mathcal{L}(\theta^{*},S)\geq 0$,

$\mathbb{E}\left[\mathcal{L}(\theta^{priv},S)-\mathcal{L}(\theta^{*},S)\right]\geq
c\cdot\min(n,d/\varepsilon)\cdot\Pr\left[\,\mathcal{L}(\theta^{priv},S)-\mathcal{L}(\theta^{*},S)\geq
c\cdot\min(n,d/\varepsilon)\,\right]$

we get

$\mathbb{E}\left[\mathcal{L}(\theta^{priv},S)-\mathcal{L}(\theta^{*},S)\right]\geq\frac{c}{2}\cdot\min(1,\frac{d}{n\varepsilon})$

by re-normalizing the loss function by $\frac{1}{n}$. ∎

######  Theorem C.0 (Upper bound on number of removable samples for
$\varepsilon$-unlearning algorithm).

Suppose $\mathcal{W}\subseteq\mathbb{R}^{d}$, and fix any Lipschitz convex
loss function. Then there exists a lazy $\varepsilon$-unlearning algorithm
$(\bar{A},A)$, where $\bar{A}$ has the form $\bar{A}(U,A(S),T(S)):=A(S)$ (and
thus, in particular, takes no side information) with deletion capacity

$m^{A,\bar{A}}_{\varepsilon,\delta}(\alpha)\leq
O\left(\frac{n\alpha\varepsilon}{d}\right)\,.$

###### Proof.

Using what we have from Appendix C, we can apply the similar reductions as in
Appendix B (from ERM to SCO, and from 1-distance DP to $m$-distance DP through
Appendix B.

Hence the lower bound on the expected excess risk of generalization error is
given by, $N=\frac{n}{m}$, where $N$ is the total number of samples in the
reduction in Appendix B with $\delta=0$:

$\min\left(1,{\Omega\left(\frac{d}{N\varepsilon}\right)}\right)=\min\left(1,{\Omega\left(\frac{md}{n\varepsilon}\right)}\right)$

then by rearranging with the expected excess risk bound $\alpha$, we get the
desired deletion capacity $m$. ∎

######  Theorem C.0 (Lower bound on number of removable samples for
$\varepsilon$-unlearning algorithm).

Suppose $\mathcal{W}\subseteq\mathbb{R}^{d}$, and fix any $L$-Lipschitz
$\Delta$-(strongly) convex loss function. Then there exists a lazy
$(\varepsilon,\delta)$-unlearning algorithm $(\bar{A},A)$, where $\bar{A}$ has
the form $\bar{A}(U,A(S),T(S)):=A(S)$ (and thus, in particular, takes no side
information) with deletion capacity

$m^{A,\bar{A}}_{\varepsilon,\delta}(\alpha)\geq{\Omega\left(\frac{\varepsilon
n\alpha^{2}\Delta}{dL}\right)}.$

###### Proof Sketch.

By adapting the proof of given in [SSSS09, Section 5.4], which relies on an
expected guarantee before applying Markov’s inequality, we get the following
variant of [BST14, Theorem F.1]:

######  Theorem C.0.

Let $\ell$ be an $L$-Lipschitz, $\Delta$-strongly convex loss function. Then,
for any parameter $\theta$ (possibly depending on $\mathcal{D}$), the
following holds over the randomness of sampling the data set $\mathcal{D}$:

$\mathbb{E}\left[\mathrm{ExcessRisk}(\theta)\right]\leq\sqrt{\frac{2L^{2}}{n\Delta}}\mathbb{E}\left[\sqrt{(\mathcal{L}(\theta,\mathcal{D})-\mathcal{L}(\theta^{\ast}(\mathcal{D}),\mathcal{D}))}\right]+\frac{4L^{2}}{n\Delta}$

In particular, applying this to the output
$\hat{\theta}=\hat{\theta}(\mathcal{D})$ of any randomized algorithm, and
using Jensen’s inequality, we get

$\mathbb{E}\left[\mathrm{ExcessRisk}(\hat{\theta})\right]\leq\sqrt{\frac{2L^{2}}{n\Delta}}\sqrt{\mathbb{E}\left[\mathcal{L}(\hat{\theta},\mathcal{D})-\mathcal{L}(\theta^{\ast}(\mathcal{D}),\mathcal{D}))\right]}+\frac{4L^{2}}{n\Delta}$
(6)

where the expectation is over the draw of the dataset $\mathcal{D}$ and the
randomness of the algorithm.

Then, applying this theorem with the upper bound of the $\varepsilon$-DP
algorithm from [BST14], we have

$\mathbb{E}\left[\mathrm{ExcessRisk}(\hat{\theta})\right]\leq
C\cdot\left(\sqrt{\frac{L^{2}}{n\Delta}}\sqrt{\frac{d}{\varepsilon}}+\frac{L^{2}}{n\Delta}\right)$
(7)

for some absolute constant $C>0$.

By using Appendix B again, we have:

$\mathbb{E}\left[\mathrm{ExcessRisk}(\hat{\theta})\right]\leq
C\cdot\left(\sqrt{\frac{mdL^{2}}{\varepsilon
n\Delta}}+\frac{mL^{2}}{n\Delta}\right)$ (8)

which gives the desired lower bound. ∎

##  Appendix D Proof of $(\varepsilon,\delta)$-unlearning properties

The laziness (Assumption 1.1) is essential for the proof, and a natural
requirement for practical applications.

######  Theorem D.0 (Post-processing of unlearning (Theorem 1.4 in
Submission)).

Let $(\bar{A},A)$ be an $(\varepsilon,\delta)$-unlearning algorithm taking no
side information. Let $f\colon\mathcal{W}\to\mathcal{W}$ be an arbitrary
(possibly randomized) function. Then $(f\circ\bar{A},A)$ is also an
$(\varepsilon,\delta)$-unlearning algorithm.

###### Proof.

The proof follows exactly same as post-processing property of differential
privacy. We consider the case that $f$ is a deterministic function here
without loss of generality.

Let $T=\\{r\in\mathbb{R}^{d}\mid f(r)\in\mathcal{Y}\\}$ and
$\mathcal{Y}\subseteq\mathbb{R}^{d}$. Consider for any
$\mathcal{Y}\subseteq\mathbb{R}^{d}$:

$\displaystyle\Pr\left[\,f(\bar{A}(A(S),U))\in\mathcal{Y}\,\right]$
$\displaystyle=\Pr\left[\,\bar{A}(A(S),U)\in T\,\right]$ $\displaystyle\leq
e^{\varepsilon}\Pr\left[\,\bar{A}(A(S),U)\in T\,\right]+\delta$
$\displaystyle=e^{\varepsilon}\Pr\left[\,f(\bar{A}(A(S),U))\in\mathcal{Y}\,\right]+\delta$

∎

Under our laziness assumption, we can establish bounds on applying unlearning
algorithm repeatedly when the overall deletion requests is within the deletion
capacity:

######  Theorem D.0 (Chaining of unlearning (Theorem 1.5 in Submission)).

Let $(\bar{A},{A})$ be a _lazy_ $(\varepsilon,\delta)$-unlearning algorithm
taking no side information, and able to handle up to $m$ deletion requests.
Then, the algorithm which uses $(\bar{A},{A})$ to sequentially unlearn $k$
disjoint deletion requests $U_{1},\ldots,U_{k}\subseteq X$ such that
$|\cup_{i}U_{i}|\leq m$, outputting

$\bar{A}(U_{k},\ldots,\bar{A}(U_{1},A(X))\ldots)$

is an $(\varepsilon^{\prime},\delta^{\prime})$-unlearning algorithm, with
$\varepsilon^{\prime}=k\varepsilon$ and
$\delta^{\prime}=\delta\cdot\frac{e^{k\varepsilon}-1}{e^{\varepsilon}-1}=O(k\delta)$
(for $k=O(1/\varepsilon)$).

###### Proof.

We proceed by induction on $n\geq 1$. Given a pair of
$(\varepsilon,\delta)$-unlearning algorithm $(\bar{A},A)$ and deletion
requests $D_{1},\ldots,D_{n}\subseteq S\in\mathbb{R}^{n\times d}$ such that
$|\cup_{i}D_{i}|\leq m^{\bar{A},A}_{\varepsilon,\delta}$ with $D_{i}\cap
D_{j}=,\forall i\neq j$ for $i,j\in[n]$.

(1) For $n=1$:

$\Pr\left[\,\bar{A}(A(S),D_{1})\in T\,\right]\leq
e^{n\varepsilon}\Pr\left[\,\bar{A}(A(S\setminus
D_{1}),\emptyset)\,\right]+\delta$

by the definition of $(\varepsilon,\delta)$-unlearning. Hence the case $n=1$
holds.

(2) Assume $n=k$ is true:

$\Pr\left[\,\bar{A}(\ldots\bar{A}(A(S),D_{1}),\ldots,D_{k})\in T\,\right]\leq
e^{k\varepsilon}\Pr\left[\,\bar{A}(A(S\setminus\bar{D}_{k}),\emptyset)\,\right]+\sum^{k-1}_{i=0}e^{i\varepsilon}\cdot\delta$
(9)

(3) Then for $n=k+1$:

$\displaystyle\Pr\left[\,\bar{A}(\ldots\bar{A}(A(S),D_{1}),\ldots,D_{k+1})\in
T\,\right]$
$\displaystyle\stackrel{{\scriptstyle(\ref{eq:chaining:n=k})}}{{\leq}}e^{k\varepsilon}\Pr\left[\,\bar{A}(\bar{A}(A(S\setminus\bar{D}_{k}),\emptyset),D_{k+1})\,\right]+\sum^{k-1}_{i=0}e^{i\varepsilon}\cdot\delta$
$\displaystyle=e^{k\varepsilon}\Pr\left[\,\bar{A}(A(S\setminus\bar{D}_{k}),D_{k+1})\,\right]+\sum^{k-1}_{i=0}e^{i\varepsilon}\cdot\delta$
$\displaystyle\leq
e^{(k+1)\varepsilon}\Pr\left[\,\bar{A}(A(S\setminus\bar{D}_{k+1}),\emptyset)\in
T\,\right]+\sum^{(k+1)-1}_{i=0}e^{i\varepsilon}\cdot\delta$

where the first and third inequality result from the definition of
$(\varepsilon,\delta)$-unlearning and the second equality is due to Laziness
Assumption 1.1.

Hence, by induction, the claim holds for all $n\in\mathbb{N}$. ∎

######  Theorem D.0 (Advanced grouposition of unlearning).

Let $(\bar{A}_{1},A),\ldots,(\bar{A}_{k},A)$ be _lazy_
$(\varepsilon,\delta)$-unlearning (with common learning algorithm $A$) taking
no side information, and define the composition of those unlearning
algorithms, $\tilde{A}$ as

$\tilde{A}(U,A(X))=f\left(\bar{A}_{1}(U,A(X)),\ldots,\bar{A}_{k}(U,A(X))\right)\,.$

where $f\colon\mathcal{W}^{k}\to\mathcal{W}$ is any (possibly randomized)
function. Then, for every $\delta^{\prime}>0$, $(\tilde{A},A)$ is an
$(\varepsilon^{\prime},\delta^{\prime})$-unlearning taking no side
information, where
$\varepsilon^{\prime}=\frac{k}{2}\varepsilon^{2}+\varepsilon\sqrt{2k\ln{(1/\delta^{\prime})}}$.

###### Proof.

The proof follows the same argument as in [Vad17, Lemma 2.4]. We consider the
case of $\delta>0$ only as the $\delta=0$ is same with the pure DP proof.

Fix two datasets, $S$ (original dataset) and $S^{\prime}\coloneqq S\setminus
U$ (“forgotten dataset”) where $U$ is the set of delete requests with $|U|\leq
m^{\bar{A},A}_{\varepsilon,\delta}$. Note that $S,S^{\prime}$ differs in $m$
entries.

For an output $y=(y_{1},\ldots,y_{k})\in\mathcal{Y}$, define “memory” loss
(which is just privacy loss in differential privacy) to be:

$\mathcal{L}_{\mathcal{A}}^{S\to
S^{\prime}}(y)=\ln\frac{\Pr\left[\,\mathcal{A}(A(S),U)=y\,\right]}{\Pr\left[\,\mathcal{A}(A(S^{\prime}),\emptyset)=y\,\right]}$

where $|\mathcal{L}_{\mathcal{A}}^{S\to S^{\prime}}(y)|\leq\varepsilon$.

Then, by [Vad17, Lemma 1.5] we know that
$\bar{A}_{i}(A(S),U),\bar{A}_{i}(A(S^{\prime}),\emptyset)$ are
$(\varepsilon,\delta)$-indistinguishable, hence there are events
$E=E_{1}\wedge\ldots\wedge E_{k},E^{\prime}=E^{\prime}_{1}\wedge\ldots\wedge
E^{\prime}_{k}$ such that w.p. at least $1-k\delta$ by, for all
$y_{i},i\in[k]$,

$\displaystyle\mathbb{E}\left[\mathcal{L}_{\mathcal{A}}^{S\to
S^{\prime}}(y)\right]$
$\displaystyle=\mathbb{E}\left[\ln\frac{\Pr\left[\,\mathcal{A}(A(S),U)=y\;\middle|\;E\,\right]}{\Pr\left[\,\mathcal{A}(A(S^{\prime}),\emptyset)=y\;\middle|\;E^{\prime}\,\right]}\right]$
$\displaystyle=\sum^{k}_{i=1}\mathbb{E}\left[\ln\left(\frac{\Pr\left[\,\bar{A}_{i}(A(S),U)=y\;\middle|\;E_{i}\,\right]}{\Pr\left[\,\bar{A}_{i}(A(S^{\prime}),\emptyset)=y\;\middle|\;E^{\prime}_{i}\,\right]}\right)\right]$
$\displaystyle=\sum^{k}_{i=1}\mathbb{E}\left[\mathcal{L}^{S\to
S^{\prime}}_{\bar{A}_{i}}(y)\right]$

where we observe that the expectation of the loss is just KL-divergence
between the distributions of $\bar{A}_{i}(A(S),U)$ and
$\bar{A}_{i}(A(S^{\prime}),\emptyset)$ conditioned on $E$ and $E^{\prime}$.
Hence:

$\mathbb{E}\left[\mathcal{L}_{\mathcal{A}}^{S\to
S^{\prime}}(y)\right]=\sum^{k}_{i=1}\text{D}_{\text{KL}}(\bar{A}_{i}(A(S),U)\|\bar{A}_{i}(A(S^{\prime}),\emptyset))\leq\frac{k}{2}\varepsilon^{2}$

where the inequality is a result from [BS16, Proposition 3.3] when $\alpha=1$.
This proposition is applicable because the conditional distribution of
$\bar{A}_{i}$ is $(\varepsilon,\delta)$-indistinguishable, which shares the
max-divergence definition.

Then by Hoeffding’s inequality where the loss is bounded by
$[-\varepsilon,\varepsilon]$, with probability at least $1-\delta^{\prime}$,
we have:

$\displaystyle\exp{\left(-\frac{t^{2}}{2k\varepsilon^{2}}\right)}$
$\displaystyle\geq\Pr\left[\,\mathcal{L}_{\mathcal{A}}^{S\to
S^{\prime}}(y)>\mathbb{E}\left[\mathcal{L}_{\mathcal{A}}^{S\to
S^{\prime}}(y)\right]+t\,\right]$
$\displaystyle\geq\Pr\left[\,\mathcal{L}_{\mathcal{A}}^{S\to
S^{\prime}}(y)>\frac{k}{2}\varepsilon^{2}+t\,\right]$
$\displaystyle=\Pr\left[\,\mathcal{L}_{\mathcal{A}}^{S\to
S^{\prime}}(y)>\varepsilon^{\prime}\,\right]$

Now for $\delta^{\prime}\coloneqq\exp{(-\frac{t^{2}}{2k\varepsilon^{2}})}$, we
have $t=\varepsilon\sqrt{2k\ln{(1/\delta^{\prime})}}$ and
$\varepsilon^{\prime}\coloneqq\frac{k}{2}\varepsilon^{2}+\varepsilon\sqrt{2k\ln{(1/\delta^{\prime})}}$.

Hence, for any set $T\in\mathcal{Y}$:

$\displaystyle\Pr\left[\,\mathcal{A}(A(S),U)\in T\,\right]$
$\displaystyle\leq\Pr\left[\,\mathcal{L}^{S\to
S^{\prime}}_{\mathcal{A}}(y)>\varepsilon^{\prime}\,\right]+\sum_{y\in
T:\mathcal{L}^{S\to
S^{\prime}}_{\mathcal{A}}(y)\leq\varepsilon^{\prime}}\Pr\left[\,\mathcal{A}(A(S),U)=y\,\right]$
$\displaystyle\leq\delta^{\prime}+\sum_{y\in T:\mathcal{L}^{S\to
S^{\prime}}_{\mathcal{A}}(y)\leq\varepsilon^{\prime}}e^{\varepsilon^{\prime}}\Pr\left[\,\mathcal{A}(A(S^{\prime}),\emptyset)=y\,\right]$
$\displaystyle\leq\delta^{\prime}+e^{\varepsilon^{\prime}}\Pr\left[\,\mathcal{A}(A(S^{\prime}),\emptyset)\in
T\,\right]$

where the second inequality is from the definition of unlearning. Thus, along
with an application of [Vad17, Lemma 1.5], this proves that
$\mathcal{A}=(\bar{A}_{1},\ldots,\bar{A}_{k})$ is indeed
$(\varepsilon^{\prime},\delta^{\prime}+k\delta)$-unlearning w.r.t. learning
algorithm $A$. ∎