\section{Introduction}
 The right to be forgotten (RtbF) is considered a fundamental human right in many legal systems~\cite{rosen2011right, mcgoldrick2013developments, bygrave2014right}. The proliferation of techniques that employ user data to do things such as training and validating machine learning across a variety of organizations has led to reconsideration of how to interpret RtbF. The European Union's General Data Protection Regulation (GDPR), California's Consumer Privacy Act (CCPA), and Canada's proposed Consumer Privacy Protection Act (CPPA) are all examples of new pieces of legislation which attempt to codify the RtbF by requiring companies and organizations to delete a user's data by request~\cite{voigt2017eu}.

 But \textit{what does it mean to delete a user's data?} User data, for example, can be recovered from trained machine learning models~\cite{shokri2017membership} and hyperparameter tuning procedures~\cite{papernot2021hyperparameter}. This suggests that data deletion should require organizations to take action on the models and algorithms derived from the data as well. This interpretation is consistent with the Federal Trade Commission's recent action ordering companies to delete the data from users who deleted their account as well as the models and algorithms derived from the users' data~\cite{FTC}. Forcing organizations to comply with each deletion request by retraining, however, comes with potentially significant monetary and time costs. Thus, it is worth asking if these costs can be managed while still maintaining model performance.

The cost concerns associated with RtbF compliance have prompted several recent works which formalize and study the problem of unlearning~\cite{cao2015towards}. The aim of these works is to develop techniques which delete user data from models that are inexpensive in both computation and memory while maintaining reasonable performance.
Most unlearning algorithms proposed so far focus on unlearning models obtained via empirical risk minimization~\cite{guo2020certified,sekhari2021remember,bourtoule2021machine,neel2021descent,marchant2021hard}. However, several of these methods are memory intensive~\cite{bourtoule2021machine, gupta2021adaptive}, requiring organizations to store several states of the model while training. We build on recent works~\cite{guo2020certified, sekhari2021remember} which show that for models that approximately minimize convex and sufficiently smooth ERM objectives, a Newton update to the current model can be applied in order to approximately unlearn in certain data directions. We show a different Newton estimate based on the classical infinitesimal jacknife developed in the robust statistics literature ~\cite{jaeckel1972infinitesimal,efron1982jackknife} results in a more computationally efficient unlearning algorithm in the online setting. While the current legislation only requires companies to satisfy delete requests in 30 days there are scenarios where immediate (online) delete requests are necessary such as the UK Biobank~\cite{ginart2019making}. We also show how to utilize the proximal infinitesimal jackknife~\cite{wilson2020approximate} to unlearn in settings when the model was trained using an ERM objective that is not smooth. Finally, we present an important and concerning failure mode of all approximate unlearning algorithms.

Our principal contributions are three-fold.
\begin{itemize}[leftmargin=15pt]
   \item  {\em A less expensive batch algorithm for data removal.} We develop an online unlearning algorithm to unlearn a sequence of $m$ datapoints from a model that approximately minimizes a smooth and convex ERM objective that requires $O(d^2)$ storage and has running time $O(md^2)$.
    To unlearn $m$ datapoints in an online manner (i.e. through several batch requests), the algorithms developed in prior works~(e.g. \cite{guo2020certified, sekhari2021remember}) requires a similar storage, but have a longer $O(md^3)$ running time. By avoiding the cost of computing and inverting a different Hessian at each deletion request we improve on the computational requirements of previous memory efficient unlearning algorithms, while maintaining the same generalization, unlearning and deletion capacity guarantees. We empirically demonstrate significant computational savings without sacrificing test set accuracy on multiple datasets.

    \item {\em Accommodating non-smooth regularizers.} We provide a generalization of our unlearning algorithm based on the proximal Newton method that can be used to efficiently delete data from models that minimize objective functions with non-smooth penalties.
    We provide state-of-the art unlearning, deletion capacity and generalization guarantees for our new unlearning method. We empirically demonstrate significant computational savings without sacrificing test set accuracy in predicting Warfarin dosages.
    \item {\em Uncovering failure modes of unlearning algorithms.} Most data processing pipelines are not as simple as writing down an objective function and running an algorithm out-of-the-box which returns the approximate empirical risk minimizer. A more common practice is to tune hyperparameters using techniques such as cross-validation.
    We reveal a fundamental limitation of most data removal processes developed so far when hyperparameter tuning takes place.
\end{itemize}

\section{Related Work}
Given the increasing concerns around privacy of user data,
recent research on \textit{machine unlearning} studies how we can efficiently delete datapoints used to train models without retraining from scratch. This work was first initiated by~\citet{cao2015towards} whose definition requires the outputs of an unlearning algorithm to be identical to the outputs of the model produced by retraining. Since then, several works have provided different definitions of machine unlearning which can be separated as exact unlearning~(\cite{bourtoule2021machine, thudi2021necessity, gupta2021adaptive, garg2020formalizing}) or approximate unlearning~(\cite{guo2020certified, sekhari2021remember, ginart2019making, dwork2014algorithmic, neel2021descent}).

Our work is focused on satisfying approximate unlearning definitions inspired by differential privacy~\cite{dwork2014algorithmic} defined by~\cite{guo2020certified} as $(\epsilon, \delta)$-certified removal or by~\cite{sekhari2021remember} as $(\epsilon, \delta)$-unlearning. This definition requires the output distribution of the unlearning algorithm to be similar to that obtained by retraining from scratch using the original training set with the requested datapoints removed from it. We focus on this definition because algorithms for exact unlearning such as statistical query learning~\cite{cao2015towards}, SISA~\cite{bourtoule2021machine}, and its adaptive variant~\cite{gupta2021adaptive} have high computational and memory cost.

Prior algorithms developed for approximate unlearning use a variety of techniques: perturbed gradient descent~\cite{neel2021descent, ullah2021machine}, Newton style updates~\cite{guo2020certified, sekhari2021remember}, and projected residual updates~\cite{izzo2021approximate}. The perturbed gradient descent and projected residual update methods provide theoretical error guarantees for the empirical training loss but fail to provide any generalization guarantees. In addition, while these methods reduce the computation burden associated with exact unlearning, their high memory costs are still similar to exact unlearning methods.

Given these issues, Newton update unlearning algorithms were proposed to efficiently satisfy approximate unlearning. Our work is closest to~\cite{guo2020certified, sekhari2021remember} who use Newton updates to efficiently delete data for generalized linear models.~\citet{sekhari2021remember} improve upon~\citet{guo2020certified} in multiple ways: (i) by not requiring full access to the training dataset, providing (ii) generalization guarantees, and (iii) removing the requirement for randomization in the learning algorithm itself (which often reduces utility). Yet the algorithm developed by~\cite{sekhari2021remember} targets the batch setting which is unrealistic in practice and they provide no empirical results demonstrating the efficacy of their algorithm. If implemented in an online way, their algorithm would suffer a much larger computational cost given the requirement to compute and invert a new Hessian for each delete request. Finally, neither of these algorithms provide theoretical guarantees for the commonly used models that are obtained from objective functions with non-smooth penalties.

We address several of these issues using the (proximal) infinitesimal jacknife~\cite{giordano2019swiss, jaeckel1972infinitesimal, efron1982jackknife}. Our algorithm can handle online delete requests selected in an adaptively adversarial manner (a failure mode of many previous algorithms pointed out by~\citet{gupta2021adaptive}) making it more practical for real world use. Furthermore, we provide generalization and deletion capacity guarantees similar to~\citet{sekhari2021remember} for both smooth and non-smooth regularizers. To do so, we leverage similar guarantees found in approximate cross-validation literature~\cite{wilson2020approximate}. Finally, inspired by recent working showing that hyperparameter tuning can leak user data~\cite{papernot2021hyperparameter} we demonstrate that all approximate unlearning algorithms introduced so far fail to unlearn in settings where hyperparameter tuning has taken place to choose a model.

\section{Methods and Results}
\label{sec:methods_results}
\paragraph{Learning} Consider the objective function
comprised of a loss function $\ell$, a regularizer $\pi$ and regularization parameter $\lambda \in \Lambda \subseteq [0,\infty]$.
The goal of learning is to find a parameter $\theta^\ast(\lambda)$ which minimizes the population risk
\begin{align*}

   F(z, \theta, \lambda) \triangleq \ \mathbb{E}_{z \sim \mathcal{D}} [\ell (z, \theta)] + \lambda \pi(\theta

\end{align*}
Given the distribution $\mathcal{D}$ is often inaccessible, practitioners often instead find a model $ \hat{\theta}_n(\lambda)$ which (at least approximately) minimizes the empirical risk
\begin{talign}\label{eq:erm}
 F_n(z, \theta, \lambda)
   \triangleq  \tfrac{1}{n} \sum_{i=1}^n \ell(z_i, \theta) + \lambda \pi(\theta,)

\end{talign}
corresponding to a given dataset $S= (z_1, \dots z_n)$
\paragraph{Unlearning} Having used a dataset $S$ to train and publish a model $\hat{\theta}_n(\lambda)$, a set of $m$ users in the training set $U\subset S$ might request that their datapoints be deleted and that any models produced using their data be removed. To comply with this request, an organization might find the minimizer  $\theta_{n, -U}(\lambda)$ of the leave-$U$-out objective
\balignt\label{eq:cvest}
F_{n, -U}(z, \theta, \lambda)  \triangleq \tfrac{1}{n-m}{\textstyle\sum}_{z \in S\backslash U} \ell (z,\theta) + \lambda\reg(\theta).
\ealignt

While {\em reoptiminzing the leave-one-out objective from scratch constitutes a baseline for the problem of unlearning}, the computational cost makes complying with every data delete request in this way undesirable.
Training from scratch satisfies the notion of unlearning~\citep{sekhari2021remember} formalized in~\cref{def:unlearn}.

\begin{definition}[$(\epsilon,\delta)$-unlearning \citep{sekhari2021remember}]\label{def:unlearn}
Let $S$ be a fixed training set and $A: S \rightarrow \theta$ be an algorithm that trains on  $S$ and outputs a model $\theta \in \Theta$. For an $\epsilon>0$ and set of delete requests $U \subseteq S$, we say that a removal mechanism $M$ is $(\epsilon, \delta)$-unlearning for learning algorithm $A$ if $\forall\, \mathcal{T} \subseteq {\Theta}$ and $S \subseteq \mathcal{Z}$, the following two conditions are satisfied:

\begin{align*}
 P(M(U, A(S), T(S))\in \mathcal{T})&\leq e^{\epsilon} P(M(\emptyset, A(S \backslash U), T(S \backslash U))\in \mathcal{T}) + \delta, \quad \text{and}\\
P(M(\emptyset, A(S \backslash U), T(S \backslash U))\in \mathcal{T})&\leq e^{\epsilon} P(M(U, A(S), T(S))\in \mathcal{T}) + \delta
\end{align*}

\end{definition}

Finally, we point out that like most previously proposed unlearning algorithms, we do not require $T(S)$ to contain the entire training set, but instead propose unlearning algorithms for which $T(S)$ is independent of $n$.
\subsection{Unlearning models obtained via regularized empirical risk minimization} We recommend use of the following proximal operator to comply with delete requests
\begin{align}\label{eq:prox-operator}
{\bf \text{ prox}}_{\lambda\pi}^{H}(v)\triangleq \argmin_{\theta \in \mathbb{R}^d} \frac{1}{2} \| v- \theta\|_{H}^2 + \lambda \pi(\theta)
\end{align}
which allows us to handle objective functions that incorporate non-smooth regularizers, such as the $\ell_1$, elastic net or nuclear norm penalty. More specifically, having deleted the datapoints in the set $U$, we propose~\cref{algo:1} to delete the data of an additional user $j$.
\begin{algorithm}[ht!]
\begin{algorithmic}
\State {\bf Input:} $|U| = m$, Hessian of  loss or objective, $\tilde{\theta}_{n,-U}(\lambda)$, $\bar{\theta}^N_{n,-U}(\lambda)$ $\hat{\theta}_{n}(\lambda)$, and delete request $j$
\State {\bf Set:} $H _\ell= \frac{1}{n}\sum_{i=1}^n\nabla^2_{\theta}\loss(z_i,\hat{\theta}_n)$, $H _f= \frac{1}{n}\sum_{i=1}^n\nabla^2_{\theta}f(z_i,\hat{\theta}_n,\lambda)$, $\bar{\theta}_{n, -\emptyset}^N(\lambda) = \tilde{\theta}_{n, -\emptyset}(\lambda) = \estt$
\State {\bf If $\pi$ is not smooth:}
\State {}\quad \quad {\bf Compute:}
\begin{subequations}
\begin{talign}
\bar{\theta}_{n, -(U\cup \{j\})}(\lambda) &= {\bf \text{ prox}}_{\lambda\pi}^{H_\ell}\Big( \bar{\theta}_{n, -U}^N(\lambda) + \frac{1}{n}H_\ell^{-1}\nabla \ell(z_j, \hat{\theta}_{n}(\lambda)  )\Big)\\
c&= \frac{(m+1)^2(2CL\mu + ML)}{\mu^2n^2}\frac{\sqrt{2\ln(1.25/\delta)}}{\epsilon}
\end{talign}
\end{subequations}
\State {}\quad \quad {\bf Store: }$\bar{\theta}_{n, -(U\cup \{j\})}^N(\lambda) = \bar{\theta}_{n, -U}^N(\lambda) + \frac{1}{n}H_\ell^{-1}\nabla \ell(z_j, \hat{\theta}_{n}(\lambda)  )$\\
\State{\bf Else compute:}
\begin{subequations}
\begin{talign}
\bar{\theta}_{n, -(U\cup \{j\})}(\lambda) &= \tilde{\theta}_{n, -U}(\lambda) + \frac{1}{n}H_f^{-1}\nabla \ell(z_j, \hat{\theta}_{n}(\lambda)  )\\
c& = \frac{(2m+1)(2CL\mu + ML)}{\mu^2n^2}\frac{\sqrt{2\ln(1.25/\delta)}}{\epsilon}
\end{talign}
\end{subequations}
\State {\bf Sample:} $\sigma \sim \mathcal{N}(0, cI)$ \\
{\bf Return:} $\tilde{\theta}_{n, -(U\cup \{j\})}(\lambda)  := \bar{\theta}_{n, -(U\cup \{j\})}(\lambda) + \sigma$\\
\end{algorithmic}
\caption{Infinitesimal Jacknife (\textbf{IJ}) Online Unlearning Algorithm}
\label{algo:1}
\end{algorithm}

\paragraph{Guarantees}
While we give guarantees for functions that are strongly convex, we rely on standard reductions from the convex setting to the strongly convex setting (i.e. based on defining a objective function $ F(\theta) = \tilde{F}(\theta) + (\mu/2)\|\theta\|^2$ when $\tilde{F}$ is convex). Furthermore, similar to~\citet[3.3]{guo2020certified} our methods can be used for unlearning in the non-convex setting when the deep learning model applies a simple convex model to a differentially private feature extractor~\cite{abadi2016deep}.
\begin{assumption}[Smooth regularizer]\label{ass:1}
For any $z \in \mathcal{Z}$, the objective function $F(\theta, z,\lambda)$ is $\mu$-strongly convex and $L$-Lipschitz with $M$-smooth Hessian. The loss has $C$-Lipschitz Hessians.
\end{assumption}
\begin{assumption}[Non-smooth regularizer]\label{ass:2}
For any $z \in \mathcal{Z}$, the loss function $\loss(\theta, z)$ is $\mu$-strongly convex and $L$-Lipschitz with $M$-smooth and $C$-Lipschitz Hessians. The regularizer $\pi(\theta)$ is convex.
\end{assumption}
With either of these assumptions, it's possible to show that the denoised output of~\cref{algo:1} is $O(m^2/n^2)$ close to the exact unlearned model. We formalize this proximity result in the following~\cref{lemma:noise}.

\begin{lemma}[Proximity to the baseline estimator]\label{lemma:noise}
Suppose $F$ satisfies Assumption~\ref{ass:1} or Assumption~\ref{ass:2}. Let $S$ be the dataset of size $n$ sampled from $\mathcal{D}$ and $U \subseteq S$ denote the set of $m$ delete requests. Consider $\bar{\theta}_{n,-U}(\lambda)$, i.e. the output of~\cref{algo:1} without noise term $\sigma$ added and the model $\hat{\theta}_{n,-U}(\lambda)$ obtained by minimizing the leave-U-out objective $F_{n,-U}$. Then,
\begin{subequations}
\begin{talign}
\twonorm{ \hat{\theta}_n(\lambda)- \hat{\theta}_{n, -U}(\lambda)}
 &\leq \frac{m L}{\mu n}, \quad \quad \text{\em and}\\
\label{eq:ineq1}\|\hat{\theta}_{n,-U}(\lambda) - \bar{\theta}_{n, -U}(\lambda) \|_2 &\leq \frac{2m^2 CL}{n^2\mu^2 } + \frac{m^2 ML^2}{n^2 \mu^3}  .
\end{talign}
\end{subequations}
\end{lemma}
\cref{lemma:noise} implies adding the noise term $\sigma \propto O(m^2/n^2)$ will result in the desired unlearning guarantee.
The following~\cref{thm:1} outlines this guarantee as well as the proximity of the unlearnt model to the test loss minimizer.  The proof is contained in Appendix~\ref{app:closeness_proof}.
\begin{theorem}[Unlearning and generalization guarantees]\label{thm:1} Suppose the loss function satisfies Assumption~\ref{ass:1} or~Assumption~\ref{ass:2} and consider any learning algorithm that returns a model $O(1/n^2)$ close to the empirical risk minimizer $\hat{\theta}_n(\lambda)$ trained on any dataset $S \sim \mathcal{D}$ of size $n$. Then

    the output $\tilde{\theta}_{n,-U}(\lambda)$ of~\cref{algo:1}, where $|U| = m$, satisfies the test error bound
    \begin{talign*}\mathbb{E}[F(\tilde{\theta}_{n, -U}(\lambda)) -  F(\theta^\ast(\lambda))] \leq O\left( \frac{(2m^2CL^2\mu + ML^3m^2}{\mu^3n^2}\cdot\frac{\sqrt{d}\sqrt{ln(1/\delta)}}{\epsilon} + \frac{4mL^2}{\mu n}\right).\end{talign*}
    Furthermore, the unlearning~\cref{algo:1} results in $(\epsilon, \delta)$-certifiable removal of $\forall {\bf z} \in U\subseteq S$.
\end{theorem}

\subsubsection{Deletion Capacity}

\citet{sekhari2021remember} introduce the notion of deletion capacity which formalizes how many samples can be deleted from a the model parameterized by the original empirical risk minimizer $\estt$ while maintaining reasonable guarantees on the test loss. We restate the definition here.
    \begin{definition}[Deletion capacity~\cite{sekhari2021remember}]Let $\epsilon,\delta,\gamma>0$ and $S$ be a dataset of size $n$ drawn i.i.d From $\mathcal{D}$, and let $F(\theta,z,\lambda)$ be an objective function. For a learning algorithm and removal mechanism $M$ that satisfies $(\epsilon,\delta)$-unlearning of all ${\bf z} \in U$, where $U$ is the set of delete requests, the deletion capacity $m_{\epsilon,\delta,\gamma}^{A,M}(d,n)$ is defined as the maximum number of samples that can be unlearned while still ensuring the excess population risk is $\gamma$. Specifically,
    \begin{talign*}
    m_{\epsilon,\delta,\gamma}^{A,M}(d,n) \triangleq \max \left\{m \,|\, \mathbb{E}\left[\max_{U\subseteq S: |U| \leq m} F(M(A(S),S, U) - F(\theta(\lambda)^\ast) \right] \leq \gamma\right\}
    \end{talign*}
where the expectation is with respect to $S \sim \mathcal{D}$ and output of the learning algorithm
$A$ and removal mechanism $M$.
\end{definition}

\citet{sekhari2021remember} provide both an upper bound and lower bound on the deletion capacity of unlearning algorithms. We recount both bounds and show our algorithm achieves the same bounds.

\begin{theorem}[Deletion capacity upper bound~\citep{sekhari2021remember}]
Let $\delta \leq 0.005$ and $\epsilon = 1$. There exists a 4-Lipschitz and 1-strongly convex loss function f, and a distribution $\mathcal{D}$ such that for any learning algorithm $A$ and removal mechanism $M$ that satisfies $(\epsilon, \delta)$-unlearning and has access to all undeleted samples $S \backslash U$, then the deletion capacity is:
\begin{align*}
m_{\epsilon,\delta,\gamma}^{A,M}(d,n) \leq c n,
\end{align*}
where the constant $c$ depends on the Lipschitz constants $L$, $M$, strongly convex constant $\mu$, and boundedness constant $C$ from Assumptions~\ref{ass:1} or~\ref{ass:2} and $c < 1$.

\end{theorem}

\begin{theorem}[Deletion capacity lower bound~\citep{sekhari2021remember}] \label{thm:del_cap_lower}
    Let $\epsilon, \delta > 0$ and $\gamma = 0.01$, $S$ be a dataset of size $n$ drawn i.i.d from $\mathcal{D}$, and  $F(\theta,z,\lambda)$ be an objective function satisfying Assumption~\ref{ass:1} or Assumptions~\ref{ass:2}. Consider a learning algorithm $A$ that returns the empirical risk minimizer and unlearning algorithm $M$. Then the deletion capacity is:
    \begin{talign}\label{eq:lb}
    m_{\epsilon,\delta, 0.01}^{A,M}(d,n) \geq c \cdot \frac{n \sqrt{\epsilon}}{(d \text{\em log}(1/\delta))^{\frac{1}{4}}}
    \end{talign}
    where the constant $c$ depends on the Lipschitz constants $L$, $C$, and $M$.
    \end{theorem}

\begin{theorem}[Deletion capacity from unlearning via DP~\citep{sekhari2021remember}] There exists a polynomial time learning algorithm $A$ and removal mechanism $M$ of the form $M(U, A(S), T(S)) = A(S)$ such that the deletion capacity is:
\begin{talign*}
 m_{\epsilon,\delta, 0.01}^{A,M}(d,n) \geq \tilde{\Omega}\left(\frac{n\epsilon}{\sqrt{d\log(e^{\epsilon}/\delta})}\right)
\end{talign*}
where the constant in $\Omega$-notation depends on the properties of the loss function $f$.

\end{theorem}
As an extensions of a result developed by~\citet[Section C]{bassily2019private}, \citet{sekhari2021remember} show that any unlearning algorithm that ignores the samples $U$ can't improve upon the DP lower bound. This motivates the study of algorithms specifically designed for unlearning which leverage samples from $U$ instead of algorithms based on DP.
In~\cref{app:del_cap}, we provide details showing that our Algorithm~\ref{algo:1} achieves the lower bound~\eqref{eq:lb}, where the constant $c$ depends on the Lipschitz constants $L$, $M$, strongly convex constant $\mu$, and boundedness constant $C$.

\paragraph{Comparison to previous results}
We compare our method to~\citet{sekhari2021remember} and~\citet{guo2020certified} who propose optimizing a second-order Taylor approximation (\textbf{TA}) to the leave-$U$-out objective function~\eqref{eq:cvest} for batch removal of $U$. This results in the Newton-like removal mechanism~\eqref{eq:s}.
\begin{talign}\label{eq:s}
\tilde{\theta}_{n,-U}(\lambda) = \estt + \frac{1}{n-m}\left(\frac{1}{n-m}\sum_{z \inS \backslash U}\nabla^2_\theta F(z,\estt,\lambda)\right)^{-1}  \sum_{z\in U}\nabla\ell(z,\estt).
\end{talign}

{\em Comparison of Assumptions. } On the one hand, our Assumption~\ref{ass:1} is slightly more restrictive than that of~\citet{sekhari2021remember} given we require boundedness of the Hessian loss to obtain our unlearning, generalization and deletion capacity guarantees. Notably, this assumption does not rule out any of the most common convex objective functions (e.g. least squares, logistic, hinge, or cross entropy loss functions). On the other hand, our technique allows for non-smooth regularizers which are common in modern machine learning pipelines.

{\em Comparison of Computation.}
~\cref{algo:1} entails calculating and inverting the full Hessian $H_f$ or $H_\ell$ and storing it (memory cost $O(d^2)$ and computation cost $O(d^3)$). It also entails storing the gradient of each point evaluated on the full data model $\estt$, as well as the current model $\tilde{\theta}_{n, -U}(\lambda)$. In the setting where $\pi$ is not smooth, $\bar{\theta}_{n,-U}(\lambda)$ must be stored. During runtime,~\cref{algo:1} requires matrix-vector multiplication and vector addition (as well as proximal step in the non-smooth setting).
For unlearning in settings where deletion requests come in a online manner, our technique is computationally more efficient. This is because removal mechanism~\eqref{eq:s} requires computing and inverting a different Hessian that depends on the user requesting the deletion. Therefore, outside simple settings, complying with such requests involves a computational cost of $O(md^3)$ to remove $m$ datapoints.

 {\em Comparison of unlearning, generalization and deletion capacity.} As summarized above, the generalization, unlearning and deletion capacity results for our removal mechanism are essentially equivalent to the unlearning, generalization, and deletion capacity results of~\cite{sekhari2021remember}.

\begin{remark}[Extending~\citet{sekhari2021remember} to non-smooth regularizers] Following from the equivalence we show between the batch and online setting in Appendix~\ref{app:batch_eq_stream}, we can extend our use of the proximal operator to~\eqref{eq:s} which would extend the results of~\citet{sekhari2021remember} to non-smooth regularizers. Similar unlearning, deletion capacity and generalization results are obtained. We provide details in~\cref{app:ext}.
\end{remark}
\section{Experiments}
In this section we will refer to retraining from scratch as \textbf{RT}, the Algorithm~\eqref{eq:s} as \textbf{TA} and our \cref{algo:1} as \textbf{IJ}.
We empirically demonstrate the benefits  of our algorithm over both \textbf{RT} and \textbf{TA} in three different settings: (i) smooth regularizers where we train a logistic regression model with an $\ell_2$ penalty to predict between the digit 3 and 8 from the MNIST dataset~\cite{lecun1998mnist}, (ii) non-smooth regularizers where we train a logistic regression model with an $\ell_1$ penalty to predict whether an individual was prescribed a Warfarin dosage of $> 30$ mg/week from a dataset released by the International Warfarin
Pharmacogenetics Consortium~\cite{international2009estimation}, and (iii) non-convex training where we apply a logistic regression model with an $\ell_2$ penalty to predict street digits signs 3 and 8 from SVHN~\cite{netzer2011reading} on representations extracted from a differentially private feature extractor with $\epsilon = 0.1$ (similar to the setup of~\citet{guo2020certified}). For all algorithms, we tune $\lambda$ over the set $\{10^{-3}, 10^{-4}, 10^{-5}, 10^{-6}\}$. In the Appendix~\ref{app:datasets}, we provide further details about each dataset and the code to produce our models is attached separately.

 We present results in the main paper for $\lambda = 1^{-3}$ and provide other results in Appendix~\ref{app:exps}. All models are trained on a single NVIDIA Tesla T4 GPU and 16 2.10GHz Xeon(R) Silver 4110 CPU cores. We focus our evaluation on total runtime in seconds and test set accuracy as the number of delete requests increases. Given that the current window for complying with delete requests for GDPR is one month, the runtime savings on our plots occur at month X where X is provided by the y-axis. We note that the "Right to Be Forgotten" is a much broader right and our experimental findings demonstrate that this can be satisfied much more efficiently for convex problems.  For all results, we provide the average over three different runs and provide standard error bars.

\begin{figure}[t!]
\centering
\begin{subfigure}{.4\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/MNIST_runtime.png}
  \label{fig:mnist_runtime}
\end{subfigure}%
\begin{subfigure}{.6\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/mnist_test_acc_final.png}
  \label{fig:mnist_test_acc}
\end{subfigure}
\caption{\textbf{IJ} vs. \textbf{RT} \& \textbf{TA} for smooth regularizers. Comparing both the runtime and test accuracy of the unlearned models in our $\ell_2$ logistic regression setup for predicting 3's and 8's on MNIST. For GDPR, the y-axis of the runtime graph denotes the runtime at month X under the current one month delete request window.}
\label{fig:mnist}
\end{figure}

\paragraph{Logistic Regression with Smooth Regularizers}

In this experiment we simulate an online data deletion setup using the MNIST dataset. For simplicity, we restrict the problem to binary classification by predicting between 3s and 8s. This is the same setup used by~\citet{guo2020certified} to evaluate their approximate unlearning algorithm.
We flatten the MNIST image into a 1-D vector and train an $\ell_2$ regularized logistic regression model for each algorithm. We evaluate the impact of a deleting a sequence of 5000 datapoints (approximately 40\% of the total dataset) both randomly and in an adaptively chosen manner. In these experiments we consider noise at $c=0.01$.

  On average, \textbf{IJ} was 2611x faster than \textbf{RT} and 2045x faster than \textbf{TA} (Figure~\ref{fig:mnist}). We find that this improvement in runtime comes at very minimal cost to the test performance of the model returned by our algorithm compared to the test performance of \textbf{TA} (Figure~\ref{fig:mnist}). Furthermore, we observe that these results also hold when the delete requests are chosen adaptively (Figure~\ref{fig:mnist}). As discussed previously, the main savings in computation for our algorithm comes from only inverting the hessian once while \textbf{TA} requires a hessian inversion for every delete request.

\begin{figure}[h]
\centering
\begin{subfigure}{.25\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/Prox_runtime.png}
  \label{fig:prox_runtime}
\end{subfigure}%
\quad\quad\hspace{10pt}
\begin{subfigure}{.25\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/prox_test_acc.png}
  \label{fig:prox_test_acc}
\end{subfigure}
\caption{\textbf{IJ} vs. \textbf{RT} for non-smooth regularizers. Comparing both the runtime and test accuracy of the unlearned models in our $\ell_1$ logistic regression setup for predicting warfarin dosage. For GDPR, the y-axis of the runtime graph denotes the runtime at month X under the current one month delete request window.}
\label{fig:prox}
\vspace{-0.7mm}
\end{figure}

\paragraph{Logistic Regression with Non-Smooth Regularizers}

This experiment showcases the performance of our proximal Newton algorithm on a problem with a non-smooth regularizer. We focus on predicting warfarin dosing from patient demographic and physiological data because it a practical setting where $\ell_1$ regularization has been demonstrated to be preferred~\cite{sharabiani2015revisiting}. Given that \textbf{TA} does not naturally support non-smooth regularizers we only compare \textbf{IJ} to \textbf{RT}. In these experiments we consider a logistic regression objective, $\ell_1$ regularizer, and noise level of $c=0.01$.
 On average, \textbf{IJ} was 30x faster than \textbf{RT} (Figure~\ref{fig:prox}). This improvement in runtime only comes at small cost to the test accuracy of the model returned by our algorithm compared to the test performance of \textbf{TA} (Figure~\ref{fig:prox}).

 \paragraph{Non-Convex: Logistic Regression with Differentially Private Feature Extractor}
 \begin{figure}[h]
\centering
\begin{subfigure}{.3\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/SVHN_runtime.png}
  \label{fig:sub1}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/SVHN_test_acc_final.png}
  \label{fig:sub2}
\end{subfigure}
\caption{\textbf{IJ} vs. \textbf{TA} and \textbf{RT} for non-convex training. Comparing both the runtime and test accuracy of the unlearned models in our DP feature extractor + $\ell_2$ logistic regression setup for predicting digits in photos of street signs from SVHN. For GDPR, the y-axis of the runtime graph denotes the runtime at month X under the current one month delete request window.}
\label{fig:svhn}
\vspace{-0.5mm}
\end{figure}
 We demonstrate the ability to use our unlearning algorithm in non-convex settings. Similar to~\citet{guo2020certified} we train a differentially private feature extractor with $\epsilon = 0.1$ on street digit signs from SVHN to extract representations which a logistic regression model can be applied on top of.  Similar to previous experiments, we pick digits 3 and 8 for simplicity and  observe significant speedups using \textbf{IJ}. On average, \textbf{IJ} was 15036x faster than \textbf{RT} and 17x faster than \textbf{TA} and these speedups come at a marginal cost to the test accuracy of our algorithm even as the number of delete requests increase (Figure~\ref{fig:svhn}).

\section{Unlearning hyperparameter-tuned models}
\label{sec:failure_mode}
One of the most common techniques for hyperparameter tuning is {\em cross-validation}. Here datapoints are used to validate and select models using the following cross-validation error objective
\begin{talign}\label{eq:cverror}
\text{CV}(\lambda) = \frac{1}{n}\sum_{i=1}^n \ell(z_i, \hat{\theta}_{n,-i}(\lambda)).
\end{talign}
Specifically, the model selection pipeline oftentimes entails selecting $\lambda \in \Lambda$ that minimizes the CV error~\eqref{eq:cverror}. Given each datapoint is used to select models, one might hope  it is possible to unlearn models using~\cref{algo:1} when CV is used to select the model. However, as the following proposition illustrates, the $(\epsilon,\delta)$-unlearning guarantees of Theorem~\ref{thm:1} no longer apply when CV has taken place.

\begin{proposition}\label{prop:1} Suppose cross-validation is used to select $\lambda \in \Lambda$ and the empirical risk minimizer $\estt$ is returned. Consider a delete request by user $i$ and the model returned by unlearning procedure~\eqref{eq:s} or~\eqref{algo:1}, which we denote $\tilde{\theta}_{n,-i}(\lambda)$. Then it is possible $\|\tilde{\theta}_{n,-i}(\lambda) - \hat{\theta}_{n,-i}(\lambda')\| = o(1/n)$ where $\hat{\theta}_{n,-i}(\lambda')$ is the model selected after deleting user $i$ and performing cross-validation again to select $\lambda' \in \Lambda$ before returning the empricial risk minizer.

\end{proposition}
{\em Proof of~\cref{prop:1}.}
Suppose $\ell(z,\theta) = \frac{1}{2}(z - \theta)^2$, $\pi(\theta) = \theta^2$ and $\Lambda = \{0, \infty\}$. Note that $\hat{\theta}_n(\lambda) = \frac{1}{1+\lambda} \bar{z}$ where $\bar{z} = \frac{1}{n} \sum_{i=1}^n z_i$ is the sample average. Consider a dataset consisting of $n-1$ points (group A) with value $-\frac{1}{n}$ and a remaining point (group B) with value $n$ with $n\geq2$, and suppose the user in group B requests to delete their data.
Performing cross-validation on this dataset will entail computing two kinds of sample averages, one where we have deleted a point from group $A$, $\bar{z}_{-i_A} = \frac{1}{n-1}(-\frac{n-2}{n} + n)$, and one where we have deleted the point from group $B$, $\bar{z}_{-i_B} =-\frac{1}{n}$. Recall the CV error
\begin{talign*}
    \text{CV}(\lambda) = \frac{1}{2n} \sum_{i=1}^n (z_i - \hat{\theta}_{n,-i}(\lambda))^2 = \frac{n-1}{2n}(\frac{1}{1+\lambda}\frac{1}{n-1}(n-\frac{n-2}{n} )-\frac{1}{n})^2 + \frac{1}{2n}(n + \frac{1}{1+\lambda}\frac{1}{n})^2
\end{talign*}
When minimized over the set $\Lambda = \{0,\infty\}$, $\lambda = \infty$ is optimal for any $n\geq2$. This results in estimator $\hat{\theta}_{n}(\lambda) =\hat{\theta}_{n}(\infty) = 0$. The leave-one-out approximation is the same for estimators~\eqref{algo:1} and~\eqref{eq:s}, given $\nabla_{\theta}^2 F(z,\theta,\lambda)^{-1} = \frac{1}{1 + \lambda}$. Subsequently, $\tilde{\theta}_{n,-i}(\lambda) = \hat{\theta}_{n}(\lambda) + \frac{1}{n}\frac{1}{1+\lambda}( \hat{\theta}_{n}(\lambda) - z_i )$ results in the approximation $\tilde{\theta}_{n,-i}(\infty) = 0$. On the other hand, having deleted the datapoint from group $B$, we have a new sample mean $\bar{z} = -\frac{1}{n}$ and CV error, given by
\begin{talign*}
\text{CV}(\lambda) = \frac{1}{2n} \sum_{i=1}^n (z_i - \hat{\theta}_{n,-i}(\lambda))^2 = \frac{1}{2n}(-\frac{1}{n} + \frac{1}{1+\lambda} \frac{1}{n})^2
\end{talign*}
is minimized by $\lambda = 0$. This results in leave-one-out minimizer $\hat{\theta}_{n,-i}(0) = -\frac{1}{n}$. $\qedsymbol$

An implication of~\cref{prop:1} is that~\cref{algo:1} as well as the algorithms proposed by~\cite{sekhari2021remember,guo2020certified}  do not unlearn models when cross-validation is used to selected hyperparameters.  This is because the noise term $\sigma \propto O(m^2/n^2)$ is no longer sufficient to guarantee datapoint $i$ is unlearned.
This means that organizations which train their models using cross-validation and use approximate unlearning algorithms could still be leaking information about the data which they delete.

\section{Discussion}

A main contribution of our study is the development of an efficient online/batch data deletion algorithm for non-smooth problems. The only previous work proposing a low-memory online algorithm is~\citet{guo2020certified}. However,~\citet{marchant2021hard} show that this algorithm is susceptible to poisoning attacks rendering it highly inefficient.
While exact unlearning algorithms such as SISA and retraining naturally work in an online setting, our work is the first to make this work for approximate unlearning algorithms. Further development of data deletion algorithms should focus more minimizing computational cost on the streaming batch setting to ensure practical use. Also, while the current form of GDPR legislation allows quite a bit of time for companies to comply (30 days), we believe that showing a tool can provide the same empirical performance and theoretical guarantees with immediate deletion is beneficial toward encouraging companies to complying with GDPR requests more swiftly (and might encourage lawmakers to necessitate faster compliance). When individuals request to delete their data, it is sometimes because they are concerned about the risk of potential harm if their data remains available; this risk is potentially compounded the longer it takes for the data to be deleted. By showing it can be done quickly, companies may be encouraged to act more expeditiously and less harm might occur.

The infinitesimal jacknife has been previously been used to perform cross-validation. We note deep connections between the approximate cross-validation algorithms and approximate machine unlearning algorithms. The algorithm developed by~\cite{sekhari2021remember}, for example, can be viewed as an analog of the approximate cross-validation algorithm proposed by~\cite{beirami2017optimal, rad2019scalable}. Additionally, the model selection error bounds provided in the approximate cross-validation literature for example in~\cite{wilson2020approximate} are very similar to the generalization guarantees proved in our work and~\cite{sekhari2021remember} where we are concerned with the error introduced by our approximation to the unlearning baseline.
 We believe further connections could be exploited to provide unlearning algorithms when hyperparameter tuning has taken place.

 In this work and in several others we consider a definition of data deletion that is parameterized by two values $\epsilon$ and $\delta$. As is the case with differential privacy, it is currently unclear what the impact of satisfying different levels of $\epsilon$ means practically. Developing auditing algorithms~\cite{thudi2021necessity} similar to those recently seen in the DP community~\cite{NEURIPS2020_fc4ddc15, nasr2021adversary} can help provide more transparency on the meaning of the $(\epsilon, \delta)$-unlearning guarantee.

Finally, we return to the broader question we posed at the beginning: \textit{what does it mean to delete data from a  machine learning pipeline?} Most existing work focuses on data deletion in the model training process. Yet, the machine learning and data analysis pipeline is much broader than just model training. As evidenced in Section~\ref{sec:failure_mode}, the lack of research on data deletion in model selection could potentially result in information being leaked from previously proposed unlearning algorithms. Given this result, it is likely that all unlearning algorithms ({\em both exact and inexact}) still leak information about deleted data in other stages of the machine learning pipeline such as exploratory data analysis and feature selection. We encourage the community to explore definitions of data deletion which encompass the entire machine learning pipeline.

\section{Acknowledgements} The authors would like to thank the NeurIPS 2022 reviewers and area chair for their comments and feedback. The authors acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center for providing (HPC, database, consultation) resources that have contributed to the research results reported within this paper/report. VMS is supported by a Wellcome Trust Fellowship.

\clearpage

\section{Introduction}
Machine learning models are increasingly trained on personal data.

Key question is what does it mean to delete a users data. Data is used for many things, including tuning hyperparameters and learning and validating machine learning models. Does deleting one's data mean initiating the entire learning process with a new dataset consisting of the deleted datapoint?

\paragraph{Contributions}
\begin{itemize}
\item We develop efficient tools for generating ``unlearned'' models . In contrast to recently proposed methods, our technique guarantees for non-smooth functions and never trigger retraining.
\item

\end{itemize}

\section{Methods and Results}
\paragraph{Learning} Consider the objective function
comprised of a loss function $\ell$, a regularizer $\pi$ and regularization parameter $\lambda \in [0,\infty)$.
The goal of learning is to find the parameter $\theta^\ast(\lambda)$ which minimizes the population risk
\begin{align*}

   F(z, \theta, \lambda) \triangleq \ \mathbb{E}_{z \sim \mathcal{D}} [\ell (z, \theta)] + \lambda \pi(\theta

\end{align*}
Given the distribution $\mathcal{D}$ is often inaccessible,  we instead find the model $ \hat{\theta}_n(\lambda)$ which minimizes the empirical risk
\begin{talign}\label{eq:erm}
 F_n(z, \theta, \lambda)
   \triangleq  \tfrac{1}{n} \sum_{i=1}^n \ell(z_i, \theta) + \lambda \pi(\theta,)

\end{talign}
corresponding to a given a dataset $S= (z_1, \dots z_n) \in \mathcal{Z}$.
\paragraph{Unlearning} Having used a dataset $S$ to train and published a model $\hat{\theta}_n(\lambda)$, a user might request that their datapoint $z_i$ be deleted and any models produced using their data be removed. To comply with this request, an organization might retrain any the machine learning model from scratch by finding a minimizer  $\theta_{n, -i}(\lambda)$ of the leave-one-out objective
\balignt\label{eq:cvest}
F_{n, -i}(z, \theta, \lambda)  \triangleq \tfrac{1}{n-1}{\textstyle\sum}_{j \neq i} \ell (z_j,\theta) + \lambda\reg(\theta).
\ealignt

{\em Retraining from scratch constitutes a baseline for the problem of unlearning.}

- Talk about computational burden.

- Talk about what it means to unlearn and how the following definition is sufficient (and is met by retraining)
\begin{definition}[$(\epsilon,\delta)$-certified removal] For an $\epsilon>0$, we say that a remove mechanism $M$ performs an $\epsilon$-certified removal of datapoint $\mathbf{x} \in \mathcal{D}$ for learning algorithm $A$ if $\forall \mathcal{T} \subseteq \mathcal{H}$, $\mathcal{D} \subseteq \mathcal{X}$
\begin{talign*}
 P(A(\mathcal{D}\backslash \mathbf{x}) \in \mathcal{T})\leq e^{\epsilon} P(M(A(\mathcal{D}), \mathcal{D}, \mathbf{x}) \in \mathcal{T} ) + \delta \\
P(M(A(\mathcal{D}), \mathcal{D}, \mathbf{x}) \in \mathcal{T} )\leq e^{\epsilon} P(A(\mathcal{D}\backslash \mathbf{x}) \in \mathcal{T}) + \delta
\end{talign*}
\end{definition}

\subsection{Previously introduced unlearning algorithms}
We review several procedures that have been introduced for the purpose of unlearning a model efficiently. The first group of unlearning algorithms are based on ... . The second group of unlearning algorithms recently introduced can be viewed as resulting from minimizing quadratic approximations to the leave-one-out objective function~\eqref{eq:cvest}.

\paragraph{Deterministic Unlearning} \citet{bourtoule2021machine} introduce a deterministic method for unlearning which they denote as Sharded Isolated Slices Aggregated (SISA) training. In SISA, there are two changes to the traditional training process: sharding and slicing. For sharding, the dataset is partitioned into $k$ disjoint subsets and separate models are trained on each of these subsets. For slicing, the model in each shard is sequentially trained on each slice and a checkpoint is saved for each slice further reducing the need to retrain a model. The models predictions are then aggregated by majority vote.

\citet{gupta2021adaptive} develop an attack on SISA by leveraging the lack of randomness across deletion updates. They demonstrate that an adversary can easily distinguish between the outputs of SISA and full retraining when it chooses data points to delete sequentially and adaptively (i.e. based on the outputs of SISA at previous iterations). Using differential privacy they are able to reduce non-adaptive deletion guarantees to adaptive deletion guarantees.  Furthermore, they discuss how approximate unlearning algorithms such as those in \cite{guo2020certified, sekhari2021remember, neel2021descent} and the ones we propose already provide deletion guarantees for adaptive sequences.

\paragraph{Unlearning via Differential Privacy} Several works~(\cite{guo2020certified, sekhari2021remember, bourtoule2021machine, gupta2021adaptive}) demonstrate that differential privacy~\cite{} provides probabilistic deletion guarantees but that this is a naive method for unlearning which results in utility loss and reduced deletion capacity (with respect to maintaining the same test loss).

\paragraph{Unlearning via Taylor approximation} To delete a datapoint $z_i$ from an estimator $\hat{\theta}(\lambda)$, both \citet{guo2020certified} and \citet{sekhari2021remember} propose the following leave-one-out estimator which (approximately) minimizes a noisy  second-order Taylor approximation (TA) of the leave-one-objective:
\begin{subequations}\label{eq:TA}
\begin{talign}
\hat\theta_{\text{TA},-i}(\lambda) &= \text{argmin}_{\theta} \left\{\tilde{F_2}(\mathbb{P}_{n, -i}, \theta, \lambda)  \triangleq \sum_{k=0}^2 \frac{\nabla_\theta^k F_{n,-i}(z, \est_n(\lambda), \lambda)[\theta - \est_n(\lambda) - \sigma]^{\otimes k} }{k!}\right\} \\
& =
\hat{\theta}(\lambda) + \frac{1}{n}  \nabla^2_{\theta}F_{n, -i}(z, \hat{\theta}(\lambda), \lambda)^{-1}\nabla \ell(z_i, \hat{\theta}(\lambda)) + \sigma
\end{talign}
\end{subequations}
with $\sigma \sim \mathcal{N}(0, c I)$.~\cite{beirami2017optimal, wilson2020approximate} and~\cite{rad2019scalable} study~\eqref{eq:TA} when $c = 0$ for the purposes of approximating cross-validation. These works show $\| \hat{\theta}_{n, -i} -\hat\theta_{\text{TA},-i}(\lambda) \| = O(1/n^2)$ under mild assumptions on the objective function (e.g. strong convexity, bounded gradients and smooth Hessians).

For the purposes of unlearning, ~\citet{guo2020certified} incorporate the update~\eqref{eq:TA} in an unlearning procedure that incorporates retraining in the event some threshold is met. More specifically,
suppose each datapoint $z = (x,y)$ can be decomposed in terms of an set of features $x$ and outcome variable $y$ and that the classifier is linear, i.e.  $\ell(\theta; z)\equiv \ell (\theta^\top x; y)$ and $\pi(\theta) = \frac{n}{2}\| \theta\|^2$.~\citet{guo2020certified} compute the gradient residual bound after each unlearning request and trigger complete retraining from scratch once this gradient residual bound surpasses the threshold of $\frac{\sigma \varepsilon}{c}$. This trigger for retraining from scratch is exploited by~\citet{marchant2021hard} by setting up a bilevel optimization problem where a malicious adversary crafts poisoned examples which result in retraining to occur much more often significantly reducing the efficiency of the certified data removal mechanism.

Suppose the risk function $F$ is $\mu$-strongly convex, $M$-Lipschitz, and has $L$-smooth Hessians.~\citet{sekhari2021remember}[Theorem] show that the learning algorithm~\eqref{eq:erm} and unlearning procedure~\eqref{eq:TA} are $(\epsilon,\delta)$-unlearned when $ c =  2ML^2\sqrt{2\ln(5/4\delta)}/\mu^3\epsilon n^2$.

Finally, \citet{neel2021descent} take an optimization perspective on SISA. Thye design a distributed variant of perturbed gradient descent which is run on each partition and the average of the parameters is taken as the final model from which the published predictions are given. The unlearning procedure for this training algorithm first replaces the datapoint being removed with another datapoint in the dataset and then reruns perturbed gradient descent on the partitions where the datapoint was removed and replaced. Finally, the authors provide non-asymptotic guarantees for their algorithm focusing on convex regularized losses (i.e. strongly convex objectives).

\paragraph{Improvements Upon Related Work}

\begin{itemize}
    \item Less computationally expensive in both time and memory then~\cite{guo2020certified, bourtoule2021machine, sekhari2021remember}
    \item Naturally defends against adaptive sequences of deletion requests which SISA does not
    \item Handles the streaming setting which is more natural than the batch setting proposed by~\cite{sekhari2021remember}
    \item Both smooth and non-smooth regularizers
\end{itemize}

\paragraph{Remaining Questions}

\begin{itemize}
    \item What can we say about the nonconvex setting with a non-trivial setup?
\end{itemize}

\section{Unlearning Algorithms}

We propose using the infinitessimal jackknife as a tool to estimate the leave-one-out model
\begin{talign*}
\hat\theta_{\text{IF},-i}(\lambda) &=  \text{argmin}_{\theta} \left\{ \frac{1}{n}\langle \nabla \ell(z_i, \hat{\theta}_n(\lambda)), \theta \rangle + \frac{1}{2}\nabla_\theta^2 F_n(z, \hat{\theta}_n(\lambda), \lambda)[\theta - \hat{\theta}_n(\lambda) - \sigma ]^{\otimes 2}   \right\}\\
&= \hat{\theta}(\lambda) + \frac{1}{n}\nabla_\theta^2 F_n(z, \hat{\theta}(\lambda), \lambda)^{-1} \nabla \ell(z_i, \hat{\theta}(\lambda)) + \sigma
\end{talign*}
Unlike the Taylor approximation~\eqref{ } it involves computing the Hessian of the full empirical objective~\eqref{eq: }. The advantage of using the full Hessian,

\begin{assumption}\label{ass:1}
For any $z \in \mathcal{Z}$, the function $f(\theta, z)$ is $\mu$-strongly convex, $L$-Lipschitz and $M$-Hessian Lipschitz with respect to $\theta$.
\end{assumption}

\begin{lemma} Suppose the loss function satisfies~\cref{ass:1}.
\begin{subequations}
\begin{talign}
\|\hat{\theta}_{n,-i} - \hat\theta_n\| &\leq \frac{2L}{n\mu} \label{eq:ineq1}\\
 \|\hat{\theta}_{n,-m} - \tilde{\theta}_{n,-m}\|
 &\leq \frac{2m^2 C L}{\mu^{2} n^2} + \frac{2Mm^2 L^2}{2 \mu^3 n^2}\label{eq:ineq2}\\
\|\theta_{\text{IF},-i}(\lambda) - \hat\theta_{\text{TA},-i}(\lambda)\|_2 &\leq \frac{\|\nabla_{\theta}^{2}\ell(z_{i}, \hat{\theta(\lambda)})\|_{op}\|\nabla_{\theta}\ell(z_{i}, \hat{\theta(\lambda)})\|_{2}}{\lambda^2 n^2} \label{eq:ineq3}
\end{talign}
\end{subequations}
\end{lemma}
Given~\cref{thm:2} we can extend the guarantees from Theorem 3 in~\cite{sekhari2021remember} to unlearning via influence functions.

\begin{theorem}\label{thm:1} Suppose the loss function satisfies~\cref{ass:1}. Then,
\begin{itemize}
    \item Any learning algorithm that returns the empirical risk minimizer $\hat{\theta}_n(\lambda)$ trained on the full dataset satisfies:
    $$\mathbb{E}_{S\sim\mathcal{D}^n}[F(\hat{\theta_n}(\lambda)) - \text{min}_{\theta \in \Theta}F(\theta)] \leq \frac{4L^2}{\mu n}$$
    \item For any dataset $S \sim \mathcal{D}^{n}$, output from learning algorithm minimizing empirical risk $\hat{\theta}_{n}(\lambda)$, and an online delete request $z_{i}$, the output $\hat{\theta}_{IF,-i}(\lambda)$ satisfies:
    $$\mathbb{E}[F(\tilde{\theta}_{n, -m}) - F(\theta^{*})] \leq O\left( \frac{(2C\mu + ML) \sqrt{d}L^2m^2}{\mu^3n^2}\frac{\sqrt{ln(1/\delta)}}{\epsilon} + \frac{4mL^2}{\mu n}\right)$$
    \item Any learning algorithm that returns the empirical risk minimizer $\hat{\theta}_n(\lambda)$ trained on the full dataset and the unlearning~\cref{alg:1} are $(\epsilon, \delta)$-unlearned.
\end{itemize}
\end{theorem}

\begin{theorem}[Deletion Capacity Guarantee]

\end{theorem}

If the delete requests come in a streaming online manner, deletion algorithms based on the infinitesimal jacknife is significantly cheaper than that based on Taylor approximation. We present two algorithms to deleting  user $j$ from model $\theta_{n,-i}$ having deleted user $i$.
\begin{algorithm}[h!]
\begin{algorithmic}
\State {\bf Input:} Full Hessian $H$, current model $\hat{\theta}_{n,-i}(\lambda)$ and full model $\hat{\theta}_{n}(\lambda)$, delete request $j$, number of deleted points $m$

\State {\bf Set:} $\gamma = $ and $c = $
\State Sample $\sigma \sim \mathcal{N}(0, cI)$ where $c = [\frac{m^2}{n^2} - \frac{(m-1)^2}{n^2}][\frac{2CL}{\mu^{2}} - \frac{ML^2}{\mu^{3}}]\frac{\sqrt{2\text{ln}(1.25/\delta)}}{\epsilon}$
\State Compute: \begin{talign*}
\hat{\theta}_{n, -m,-j}(\lambda) &= \hat{\theta}_{n, -m}(\lambda) + \frac{1}{n} H^{-1} \nabla \ell(z_j, \theta_{n}(\lambda)) + \sigma
\end{talign*}
\end{algorithmic}
\caption{Streaming Unlearning Algorithm $A_{IF}$}
\label{alg:1}
\end{algorithm}
\begin{lemma}

\end{lemma}

\paragraph{Counter-example?}

Consider the loss function $\ell(z,\theta) = \frac{1}{2}\sum_{i=1}^n (\theta - z_i)^2$ and regularizer $\pi(\theta) = \theta^2$. The gradient of the objective, loss and regularizer is given by $$\nabla_{\theta} \ell(z,\theta) = \theta - \bar{z} \quad \quad \nabla_{\theta} F(z, \theta, \lambda) = (1 + \lambda) \theta - \bar{z}$$ and $$\nabla^2_\theta F(z, \theta, \lambda) =  1  + \lambda \quad \quad \nabla^2_\theta F(z, \theta, \lambda) ^{-1} = \frac{1}{1+ \lambda}.$$
Note that $ \hat{\theta}_n(\lambda) = \frac{1}{1 + \lambda} \bar{z}$\\

Now consider a dataset consisting of $n>2$ points where $n-1$ the points (group A) have the value $-\frac{1}{n}$ and the remaining point (group B) has the value $n$, so that $\bar{z} = \frac{1}{n}(-\frac{n-1}{n} + n)$. Now if we delete a point from group $A$ then $\bar{z}_{-i} = \frac{1}{n-1}(-\frac{n-2}{n} + n) $. Similarly, if we delete a point from group $B$, $\bar{z}_{-i} = -\frac{1}{n} $. Recall that the CV error is
$$\text{CV}(\lambda) = \frac{1}{n}\sum_{i=1} (z_i - \har{\theta}_{n,-i})^2 = \frac{n-1}{n}(-\frac{1}{n} +\frac{1}{1+\lambda}\frac{1}{n-1}(-\frac{n-2}{n} + n))^2 + \frac{1}{n} (n + \frac{1}{1+\lambda}\frac{1}{n} )^2$$
I think $\lambda = \infty$ minimizes this CV error. Therefore $ \hat{\theta}_n(\infty) = 0$. We can also calculate the estimated leave one out estimator
$$\tilde{\theta}_{n,-i}(\infty) =  \hat{\theta}_n(\infty) + \frac{1}{n} \frac{1}{1+\infty} ( \hat{\theta}_n(\infty) - z_i) = 0 + \frac{1}{n} \frac{1}{1+\infty} (0 - n) =0  $$

Now suppose the user in group B requests to delete their data so that the new sample mean is $\bar{z} = -\frac{1}{n}$. The new leave one out value becomes $\bar{z}_{-i} =  -\frac{1}{n}$.
The CV error
\begin{align*} \text{CV}(\lambda) = \frac{1}{n}\sum_{i=1} (z_i - \hat{\theta}_{n,-i})^2 &= \frac{1}{n}(-\frac{1}{n} +\frac{1}{1+\lambda}\frac{1}{n})^2
\end{align*}
Clearly $\lambda = 0$ minimizes this CV error. Therefore $ \hat{\theta}_n(\infty) = -\frac{1}{n}$.
Note that $$ \|\hat{\theta}_{n,-i}(0) - \tilde{\theta}_{n,-i}(\infty)\| = o(1/n)$$

\subsection{Unlearning Algorithm for models obtained from non-smooth penalties}
Many objective functions used to train modern machine learning models involve non-smooth regularizers that violate~\cref{ass:1}. Common examples include $\ell_1$-penalty terms used to engender sparsity in high-dimensional problems and nuclear norm penalties~\cref{ }. To accomodate the use of non-smooth penalties we present an variants of the unlearning algorithms~\eqref{eq:TA} and \eqref{eq:IF} based perfomring a noisy proximal Newton update. Specifically,

- One might wonder whether we need non-smooth penalties or whether we can used smoothed approximations of influence functions (provide counter example for why you need the prox step)

\balignt
\proxacvest{i}(\lambda)
    	=\text{prox}_{\lambda \reg}^{\acvhess{\loss,i}}\left( \est(\lambda) - H_{\loss,i}^{-1}g_{\loss,i}\right)
    	&
	\triangleq \argmin_{\theta\in\reals^d}\left(\frac{1}{2} \|\est(\lambda) - \theta\|_{H_{\loss,i}}^2 + \theta ^\top g_{\loss,i}+ \lambda \pi(\theta)\right)\label{eq:proxacvest}
\ealignt

\section{Experiments}

\section{Proofs}
\subsection{Closeness of Approximators}
\subsubsection{Optimizer Comparison Lemma~\citep[Lemma 1]{wilson2020approximate}}
Suppose
\balignt\label{eq:obj}
x_{\varphi_1} \in \argmin_x \varphi_1(x)  \quad \text{and} \quad x_{\varphi_2} \in \argmin_x \varphi_2(x).
\ealignt
If $\varphi_2-\varphi_1$ is differentiable and $\varphi_2$ is $\mu_{\varphi_2}$ strongly convex
 then
\balignt
\label{eq:opt_comp_growth}
    &\nu_{\varphi_2}(\twonorm{x_{\varphi_1} - x_{\varphi_2}})
    \leq
    \langle x_{\varphi_1}-x_{\varphi_2},\nabla(\varphi_2-\varphi_1)(x_{\varphi_1})\rangle.

 \ealignt
 Specifically, if $\varphi_2-\varphi_1$ is differentiable and $\varphi_2$ is $\mu_{\varphi_2}$ strongly convex, then
 \balignt
\label{eq:2opt_comp_growth}
    &\frac{\mu_{\varphi_2}}{2}\twonorm{x_{\varphi_1} - x_{\varphi_2}}^2
    \leq
    \langle x_{\varphi_1}-x_{\varphi_2},\nabla(\varphi_2-\varphi_1)(x_{\varphi_1})\rangle

 \ealignt
 and
 \begin{talign}\label{eq:opt_comp_error_bound}
 &\frac{\mu_{\varphi_2}}{2}(\twonorm{x_{\varphi_1} - x_{\varphi_2}}^2
 + \twonorm{x_{\varphi_1} - x_{\varphi_2}}^2) \leq \varphi_2(x_{\varphi_1}) - \varphi_1(x_{\varphi_1}) - (\varphi_2(x_{\varphi_2})
    - \varphi_1(x_{\varphi_2})).
 \end{talign}
\end{lemma}
\subsubsection{Proximal Newton Comparison~\citep}
\begin{lemma}\label{lemma:prox} For any $\theta, g \in \mathbb{R}^d$, invertible $H, \tilde{H} \in \mathbb{R}^{d \prod d}$, and convex $\upvarphi_0$, the proximal Newton estimators

\begin{talign*}
\theta_{H} = \text{prox}_{H}^{\varphi_0}(\theta - H^{-1}g) &  &  \theta_{\tilde{H}} = \text{prox}_{\tilde{H}}^{\varphi_0}(\theta - \tilde{H}^{-1}g)
\end{talign*}

satisfy

\begin{talign*}
\|\theta_{H} - \theta_{\tilde{H}}\|_2 \leq \frac{\|\tilde{H} - H\|_{op} \|\theta_{H} - \theta\|_{2} }{\text{mineig}(\tilde{H})\vee 0}
\end{talign*}

\subsubsection{Proof of~\eqref{eq:ineq1}: Closeness of $\hat{\theta}_n(\lambda)$ and $\hat{\theta}_{n, -m}(\lambda)$}
Define $\tilde{F}_{n-m} = \frac{n-m}{n} F_{n-m}$ where $F_{n-m} = \frac{1}{n-m}\sum_{i \in S\U} f(z_i, \theta, \lambda)$ and note the have the same minimizers. We will work with $\tilde{F}_{n-m} $
By the optimizer comparison theorem~\eqref{eq:2opt_comp_growth} and strong convexity of $F_{n}$
\begin{talign*}
\mu\twonorm{ \hat{\theta}_n(\lambda)- \hat{\theta}_{n, -m}(\lambda)}^2 &\leq \langle \hat{\theta}_n(\lambda)- \hat{\theta}_{n, -m}(\lambda), \nabla F_{n}(z,\hat{\theta}_n(\lambda), \lambda)  - \nabla \tilde{F}_{n-m}(z, \hat{\theta}_n(\lambda), \lambda)\rangle\\
& = \frac{1}{n}\langle \hat{\theta}_n(\lambda)- \hat{\theta}_{n, -m}(\lambda), \sum_{i\in U}\nabla \ell(z_i,\hat{\theta}_n(\lambda))\rangle \\
&\leq \frac{1}{n}\|\hat{\theta}_n(\lambda)- \hat{\theta}_{n, -i}(\lambda) \|\|\sum_{i\in U}\nabla \ell(z_i,\hat{\theta}_n(\lambda))\|\\
&\leq \frac{1}{n}\|\hat{\theta}_n(\lambda)- \hat{\theta}_{n, -i}(\lambda) \| \cdot m L
\end{talign*}
 Dividing both sides by $\| \hat{\theta}_n(\lambda)- \hat{\theta}_{n, -i}(\lambda)\|$, using the $M$-Lipschitz of $\ell$ and rearranging gives the desired bound of
 $$ \twonorm{ \hat{\theta}_n(\lambda)- \hat{\theta}_{n, -m}(\lambda)}
 \leq \frac{m L}{\mu n}$$

\subsubsection{Proof of~\eqref{eq:ineq1}: Closeness of $\hat{\theta}_{\text{IF},-i}(\lambda)$ and $\hat{\theta}_{n, -i}(\lambda)$}

Define:

\begin{enumerate}
    \item $\psi_{1} = \tilde{F}_{n,-m}(z, \theta, \lambda)$
    \item $\psi_{2} = \langle \nabla \tilde{F}_{n, -m}(\hat{\theta}_{n}), \hat{\theta}_{n} - \theta \rangle + \langle \hat{\theta}_{n} - \theta, \nabla_{\theta}^{2}\tilde{F}_{n, -m}}(\hat{\theta_{n}})[\hat{\theta}_{n} - \theta]\rangle$
    \item $\psi_{3} = \langle \nabla \tilde{F}_{n, -m}(\hat{\theta}_{n}), \hat{\theta}_{n} - \theta \rangle + \langle \hat{\theta}_{n} - \theta, \nabla_{n}^{2}\tilde{F}(\hat{\theta_{n}})[\hat{\theta}_{n} - \theta]\rangle$
    \item $\hat{\theta}_{n,-m} = \argmin \psi_{1}(\theta)$,
    \item $\Tilde{\theta}_{n,-m}} = \argmin\psi_{3}(\theta)$
\end{enumerate}.

The optimizer comparison theorem and strong convexity of $F_n$ implies the following upper bound:

\begin{talign*}
\frac{\mu}{2}\|\hat{\theta}_{n,-m} - \tilde{\theta}_{n,-m}\|^{2} &\leq \langle \hat{\theta}_{n,-m} - \tilde{\theta}_{n,-m}, \nabla(\psi_{3} - \psi_{1})(\hat{\theta}_{n,-m})\rangle \\
&\leq \|\hat{\theta}_{n,-m} - \tilde{\theta}_{n,-m}\|\|\nabla(\psi_{3} - \psi_{1})(\hat{\theta}_{n,-m})\| \\
\frac{\mu}{2}\|\hat{\theta}_{n,-m} - \tilde{\theta}_{n,-m}\| &\leq \|\nabla(\psi_{3} - \psi_{1})(\hat{\theta}_{n,-m})\| \\
& \leq \| \nabla(\psi_{3})(\hat{\theta}_{n,-m}) - \nabla(\psi_{2})(\hat{\theta}_{n,-m}) + \nabla(\psi_{2})(\hat{\theta}_{n,-m})  - \nabla(\psi_{1})(\hat{\theta}_{n,-m}) \| \\
&\leq \| \nabla(\psi_{3})(\hat{\theta}_{n,-m}) - \nabla(\psi_{2})(\hat{\theta}_{n,-m})\| + \|\nabla(\psi_{2})(\hat{\theta}_{n,-m})  - \nabla(\psi_{1})(\hat{\theta}_{n,-m}) \| \\
& \leq \|[\nabla_{\theta}^{2}\tilde{F}_{n}(\hat{\theta}_{n,-m}) - \nabla_{\theta}^{2}\tilde{F}_{n,-m}(\hat{\theta}_{n,-m})]\|\|\hat{\theta}_{n} - \hat{\theta}_{n,-m}\| + \|\nabla(\psi_{2})(\hat{\theta}_{n,-m})  - \nabla(\psi_{1})(\hat{\theta}_{n,-m}) \| \\
& \leq \frac{m^2 C L}{\mu n^2} + \|\nabla(\psi_{2})(\hat{\theta}_{n,-m})  - \nabla(\psi_{1})(\hat{\theta}_{n,-m}) \| \\
& \leq \frac{m^2 C L}{\mu n^2} + \frac{M}{2}\|\hat{\theta}_{n,-m} - \hat{\theta}_{n}\|^2 \\
& \leq \frac{m^2 C L}{\mu n^2} + \frac{M}{2}\cdot \frac{m^2 L^2}{\mu^2 n^2} \\
& \leq \frac{m^2 C L}{\mu n^2} + \frac{Mm^2 L^2}{2 \mu^2 n^2}
\end{talign*}

 Dividing both sides by $\frac{\mu}{2}$, gives the desired bound of
 $$ \|\hat{\theta}_{n,-m} - \tilde{\theta}_{n,-m}\|
 \leq \frac{2m^2 C L}{\mu^{2} n^2} + \frac{2Mm^2 L^2}{2 \mu^3 n^2}$$

\subsubsection{Proof of (\eqref{eq:ineq3}): Proximity of Taylor Approximation and Influence Function Estimators}

We use a lemma (Section D.1) from~\cite{wilson2020approximate} to upper bound the difference between two Newton estimators.

\end{lemma}

\begin{proof}[Proof of (\ref{thm:2})]

Now we fix any $\lambda$ and $i \in [n]$, and let

\begin{talign*}
\tilde{H} = \sum_{j\neq i}^n \nabla_{\theta}^{2}m( z_j, \hat{\theta(\lambda)}, \lambda) & & H = \sum_{i=1}^n\nabla_{\theta}^{2}m(z_i, \hat{\theta(\lambda)}, \lambda)
\end{talign*}

By~\cref{ass:1}, $\text{mineig}(\tilde{H}) \geq \lambda$.

Now we apply ~\cref{lemma:prox} with $\theta_{H} = \theta_{\text{IF},-i}(\lambda)$ and $\theta_{\tilde{H}} = \hat\theta_{\text{TA},-i}(\lambda), \theta = \hat{\theta}(\lambda)$, and $\varphi_{0} \equiv 0$ to show that

\begin{talign*}
\|\hat{\theta}_{IF,-i}(\lambda) - \hat\theta_{\text{TA},-i}(\lambda)\|_2 & \leq \frac{1}{\mu}\|\nabla_{\theta}^{2}F_{n,-i}(z, \hat{\theta}_n(\lambda), \lambda) - \nabla_{\theta}^{2}F_n(z, \hat{\theta}(\lambda), \lambda) \|_{op} \|\hat{\theta}_{IF,-i}(\lambda) - \hat{\theta}_n(\lambda)\|_2 \\
& = \frac{1}{\mu}\|\frac{1}{n}\nabla_{\theta}^{2}\ell(z_i , \hat{\theta(\lambda)})\|_{op}\|\frac{1}{n}\nabla_{\theta}^{2}F_n(z, \hat{\theta(\lambda)}, \lambda)^{-1}\nabla_{\theta}\ell(z_i , \hat{\theta(\lambda)})\|_2 \\
& \leq \frac{1}{n^2} \frac{1}{\mu} \|\nabla_{\theta}^{2}\ell(z_{i}, \hat{\theta}(\lambda))\|_{op}\|\nabla_{\theta}\ell(z_{i}, \hat{\theta}(\lambda))\|_{2}
\end{talign*}

\end{proof}

\begin{lemma}[Claim 6.2 in Shalev-Shwartz]\label{lemma:shalev}
For any $z \in \mathcal{Z}$ let $F(\theta_{n},z)$ be an $L$-Lipschitz and $\gamma$-strongly convex function in variable $\theta_{n}$. Given any distribution $\mathcal{D}$, let $S=\{z_{i}\}_{i=1}^{n}$ where $S \sim \mathcal{D}^{n}$. Then,

$$\mathbb{E}[F(\hat{\theta_n }) - F(\theta^{*})] \leq \frac{4L^2}{\lambda n}$$

\end{lemma}

\subsubsection{Proof of (\ref{thm:1})}
\begin{proof}[Proof of (\ref{thm:1})]
First, we prove the learning guarantee of any empirical risk minimizer given Assumption~\ref{ass:1}.

\begin{lemma}[Learning guarantee for $\hat{\theta_{n}}$]
For any distribution $\mathcal{D}$, the empirical minimizer $\hat{\theta_{n}}$ of $F_n(\theta, \lambda, z)$ satisfies:

$$\mathbb{E}[F(\hat{\theta_n })] - F(\theta^{*}) \leq \frac{4L^2}{\lambda n}$$

\begin{proof}
Since $F$ is $L$-Lipschitz and $\lambda$-strongly convex the guarantee follows from Lemma~\ref{lemma:shalev}.
\end{proof}

\end{lemma}F

Second, we prove the excess empirical risk of our unlearning algorithm~(\ref{algo:1}).

\begin{lemma}
For any dataset $S$, output $\hat{\theta}_{n}$, and a set of online delete requests $U = (u_1, ..., u_m )$, the output $\hat{\theta}_{IF, -U}$ satisfies:

$$\mathbb{E}[F(\hat{\theta}_{IF, -U}) - F(\theta^{*})] \leq O((\frac{2Mm^{3}L^{3}\sqrt{d}}{\lambda^{3}n^2} - \frac{(m^2 +mn)L^2\sqrt{d}}{\lambda n})\cdot \frac{\sqrt{\text{ln}(1/\delta)}}{\epsilon} + \sum_{j = 1}^{m}[\frac{1}{(n - j) \lambda} ]mL^{2}+ \frac{4L^2}{\lambda n})$$

where the expectation is taken with respect to $S$ and $\sigma$.
\end{lemma}

\begin{proof}
Recall that,

$$\hat{\theta}_{IF,-U} = \hat{\theta}_{n} + \sum_{j = 1}^{m}[\frac{1}{n - j}H^{-1}(\nabla \ell (z_j , \hat{\theta}_{n})) + \sigma]$$

where $\sigma \in \mathbb{R}^{n}$ is drawn independently from $\mathcal{N}(0, c^2 \mathbb{I}^{d})$ with $c$ given by $\frac{\sqrt{2ln(1.25/\delta)}}{\epsilon} \cdot (\frac{2Mm^{2}L^{2}}{\lambda^{3}n^{2}} - \frac{(m+n)L}{\lambda n})$ (Given by Lemma~\ref{lemma:noise}).

Thus,

\begin{talign}
\mathbb{E}[F(\hat{\theta}_{IF, -U}) - F(\theta^{*})] &= \mathbb{E}[F(\hat{\theta}_{IF, -U}) - F(\hat{\theta}_{n}) + F(\hat{\theta}_{n}) - F(\theta^{*})] \\
&= \mathbb{E}[F(\hat{\theta}_{IF, -U}) - F(\hat{\theta}_{n})] + \mathbb{E}[F(\hat{\theta}_{n}) - F(\theta^{*})] \\
& \leq \mathbb{E}[L\|\hat{\theta}_{IF,-U} - \hat{\theta}_{n}\|] + \frac{4L^2}{\lambda n}
\end{talign}

where the second term in the inequality comes from Lemma~\ref{lemma:shalev}. Now we focus on the first term in the inequality:

\begin{talign*}
\mathbb{E}[\|\hat{\theta}_{IF,-U} - \hat{\theta}_{n}\|] &= \mathbb{E}[\|\sum_{j = 1}^{m}[\frac{1}{n - j}H^{-1}(\nabla \ell (z_j , \hat{\theta}_{n})) + \sigma]\|] \\
&= \mathbb{E}[\|\sum_{j = 1}^{m}[\frac{1}{n - j}]\sum_{j = 1}^{m}[H^{-1}(\nabla \ell (z_j , \hat{\theta}_{n}))] + \sum_{j = 1}^{m}[\sigma]\|] \\
&= \mathbb{E}[\|\sum_{j = 1}^{m}[\frac{1}{n - j}]\sum_{j = 1}^{m}[H^{-1}(\nabla \ell (z_j , \hat{\theta}_{n}))] + m\sigma\|] \\
&= \mathbb{E}[\|\sum_{j = 1}^{m}[\frac{1}{n - j}]\sum_{j = 1}^{m}[H^{-1}(\nabla \ell (z_j , \hat{\theta}_{n}))]\|] + \mathbb{E}[\|m\sigma\|] \\
& \leq \sum_{j = 1}^{m}\frac{1}{(n-j)\lambda} \mathbb{E}[\|\nabla \ell(z, \hat{\theta}_{n})\|] + m\sqrt{\mathbb{E}[\|\sigma\|^{2}} \\
& \leq \sum_{j = 1}^{m}\frac{1}{(n-j)\lambda}\mathbb{E}[\|\sum_{j=1}^{m}\nabla \ell(z_j, \hat{\theta}_{n})\|] + m\sqrt{d}c \\
& \leq [\sum_{j=1}^{m}\frac{1}{(n-j)\lambda}]mL + m\sqrt{d}c
\end{talign*}

where the first inequality follows from the triangle inequality, the second inequality holds due to Assumption~\ref{ass:1} which implies that $\nabla^{2}_{\theta}F(\hat{\theta}_{n}) \succcurlyeq \lambda \mathbb{I}^{d}$ and the application of Jensen's inequality to $\mathbb{E}[\|\sigma\|]$. Finally, we get the last inequality because $F(z, \hat{\theta_{n}}, \lambda)$ is $L$-Lipschitz. Finally, we plug the above bound back into (12) and get:

$$\leq [\sum_{j=1}^{m}\frac{1}{(n-j)\lambda}]mL^2 + m\sqrt{d}cL + \frac{4L^2}{\lambda n}$$

We get the final guarantee by plugging in the value for $c$.
\end{proof}

Finally, we prove the our unlearning algorithm satisfies $(\epsilon, \delta)$-unlearning.

\begin{lemma}[Unlearning guarantee]
For any distribution $\mathcal{D}$, dataset $S$, and set of online delete requests $U \subseteq S$, the learning algorithm $A$, hessian $H_{n}$ of the output of learning algorithm run on input dataset $S$,  and unlearning algorithm $A_{IF}$ satisfy the following guarantees for any set $\Theta \in \mathbb{R}^d$.

\begin{enumerate}
    \item $\mathbb{P}(A_{IF}(U, A(S), H_{n}) \in \Theta) \leq e^{\epsilon}\mathbb{P}(A_{IF}(\emptyset, A(S \backslash U), H_{n,-U}) \in \Theta) + \delta$
    \item $\mathbb{P}(A_{IF}(\emptyset, A(S \backslash U), H_{n,-m}) \in \Theta) \leq e^{\epsilon}\mathbb{P}(A_{IF}(U, A(S), H_{n}) \in \Theta) + \delta$
\end{enumerate}

\begin{proof} Similar to the proof of Lemma 10 in~\citet{sekhari2021remember}, our proof follows from the proof of the differential privacy guarantee for the Gaussian mechanism~\cite{dwork2014algorithmic}. Recall~\ref{eq:ineq2},

 $$ \|\hat{\theta}_{n,-m} - \tilde{\theta}_{n,-m}\|
 \leq \frac{2m^2 C L}{\mu^{2} n^2} + \frac{2Mm^2 L^2}{2 \mu^3 n^2}$$

Given noise $\sigma \sim \mathcal{N}(0, c^2 \mathbb{I^d})$ with $\c = (\frac{2m^2 C L}{\mu^{2} n^2} + \frac{2Mm^2 L^2}{2 \mu^3 n^2}) \cdot \frac{\sqrt{2 \text{ln}(1.25/\delta)}}{\epsilon}$, we can follow the same proof as~\citet{dwork2014algorithmic} (Theorem A.1) and get that for any set $\Theta$,

$$\mathbb{P}(\hat{\theta}_{IF, n} \in \Theta) \leq e^{\epsilon}\mathbb{P}(\hat{\theta}_{IF}_{-U} \in \Theta) + \delta$$

and,

$$\mathbb{P}(\hat{\theta}_{IF, -U} \in \Theta) \leq e^{\epsilon}\mathbb{P}(\hat{\theta}_{IF, n} \in \Theta) + \delta$$

resulting in the $(\epsilon, \delta)$ unlearning guarantee.

\end{proof}

\end{lemma}

The three statements found in the Theorem are proven by the above Lemmas respectively. We note to the reader that if at every online delete request we store the gradients for each example than our streaming algorithm reduces to the batch setting at additional storage cost of $O(dn)$. For this variant of the algorithm $A_{IF}$ the proofs from~\cite{sekhari2021remember} hold for this Theorem.
\end{proof}

\begin{proof}[Proof of Lemma~\ref{lemma:noise}]

First, we prove an intermediary Lemma.
\begin{lemma}
The outputs $\hat{\theta}_{n}$ and $\hat{\theta}_{n, -U}$, satisfy the following guarantee:

$$\|\hat{\theta}_{n} - \hat{\theta}_{n, -U}\| \leq \frac{2mL}{\lambda n}$$
\begin{proof}
Given $F$ satisfies Assumption~\ref{ass:1}, the proof follows from Section C.1 of~\citet{sekhari2021remember}.
\end{proof}
\end{lemma}

Finally, given that $F$ satisfies Assumption~\ref{ass:1}, the proof also follows from Section C.1 of~\citet{sekhari2021remember}. To be added but it is written out already on paper.

\end{proof}
\end{lemma}

\section{Introduction}
 The right to be forgotten (RtbF) is considered a fundamental human right in many legal systems~\cite{rosen2011right, mcgoldrick2013developments, bygrave2014right}. The proliferation of techniques that employ user data to do things such as training and validating machine learning across a variety of organizations has led to reconsideration of how to interpret RtbF. The European Union's General Data Protection Regulation (GDPR), California's Consumer Privacy Act (CCPA), and Canada's proposed Consumer Privacy Protection Act (CPPA) are all examples of new pieces of legislation which attempt to codify the RtbF by requiring companies and organizations to delete a user's data by request~\cite{voigt2017eu}.

 But \textit{what does it mean to delete a user's data?} User data, for example, can be recovered from trained machine learning models~\cite{shokri2017membership} and hyperparameter tuning procedures~\cite{papernot2021hyperparameter}. This suggests that data deletion should require organizations to take action on the models and algorithms derived from the data as well. This interpretation is consistent with the Federal Trade Commission's recent action ordering companies to delete the data from users who deleted their account as well as the models and algorithms derived from the users' data~\cite{FTC}. Forcing organizations to comply with each deletion request by retraining, however, comes with potentially significant monetary and time costs. Thus, it is worth asking if these costs can be managed while still maintaining model performance.

The cost concerns associated with RtbF compliance have prompted several recent works which formalize and study the problem of unlearning~\cite{cao2015towards}. The aim of these works is to develop techniques which delete user data from models that are inexpensive in both computation and memory while maintaining reasonable performance.
Most unlearning algorithms proposed so far focus on unlearning models obtained via empirical risk minimization~\cite{guo2020certified,sekhari2021remember,bourtoule2021machine,neel2021descent,marchant2021hard}. However, several of these methods are memory intensive~\cite{bourtoule2021machine, gupta2021adaptive}, requiring organizations to store several states of the model while training. We build on recent works~\cite{guo2020certified, sekhari2021remember} which show that for models derived from minimizing convex and sufficiently smooth ERM objectives, a Newton update to the current model can be applied in order to approximately unlearn in certain data directions. We show a different Newton estimate based on the classical infinitesimal jacknife developed in the robust statistics literature ~\cite{jaeckel1972infinitesimal,efron1982jackknife} results in a more computationally efficient unlearning algorithm in the online setting. We also show how to utilize the proximal infinitesimal jackknife~\cite{wilson2020approximate} to unlearn in settings when the model was trained using an ERM objective that is not smooth. Finally, we present an important and concerning failure mode of all approximate unlearning algorithms.

Our principal contributions are three-fold.
\begin{itemize}[leftmargin=15pt]
   \item  {\em Computationally efficient online algorithm.} We develop an online unlearning algorithm to unlearn a sequence of $m$ datapoints from a model $\estt$ that approximately minimizes a smooth and convex ERM objective that requires $O(d^2)$ storage and has running time $O(md^2)$.
    To unlearn $m$ datapoints in an online manner, the algorithms developed in prior works~(e.g. \cite{guo2020certified, sekhari2021remember}) requires a similar storage, but have a longer $O(md^3)$ running time. By avoiding the cost of computing and inverting a different Hessian at each deletion request we improve on the computational requirements of previous memory efficient unlearning algorithms, while maintaining the same generalization, unlearning and deletion capacity guarantees. We empirically demonstrate significant computational savings without sacrificing test set accuracy on multiple datasets.

    \item {\em Accommodating non-smooth regularizers.} We provide a generalization of our unlearning algorithm based on the proximal Newton method that can be used to efficiently delete data from models that minimize objective functions with non-smooth penalties.
    We provide state-of-the art unlearning, deletion capacity and generalization guarantees for our new unlearning method. We empirically demonstrate significant computational savings without sacrificing test set accuracy in predicting Warfarin dosages.
    \item {\em Failure modes.} Most data processing pipelines are not as simple as writing down an objective function and running an algorithm out-of-the-box which returns the approximate empirical risk minimizer. A more common practice is to tune hyperparameters using techniques such as cross-validation.
    We reveal a fundamental limitation of all (approximate) data removal processes developed so far when hyperparameter tuning takes place.
\end{itemize}

\section{Related Work}
Given the increasing concerns around privacy of user data,
recent research on \textit{machine unlearning} studies how we can efficiently delete datapoints used to train models without retraining from scratch. This work was first initiated by~\citet{cao2015towards} whose definition requires the outputs of an unlearning algorithm to be identical to the outputs of the model produced by retraining. Since then, several works have provided different definitions of machine unlearning which can be separated as exact unlearning~(\cite{bourtoule2021machine, thudi2021necessity, gupta2021adaptive, garg2020formalizing}) or approximate unlearning~(\cite{guo2020certified, sekhari2021remember, ginart2019making, dwork2014algorithmic, neel2021descent}).

Our work is focused on satisfying approximate unlearning definitions inspired by differential privacy~\cite{dwork2014algorithmic} defined by~\cite{guo2020certified} as $(\epsilon, \delta)$-certified removal or by~\cite{sekhari2021remember} as $(\epsilon, \delta)$-unlearning. This definition requires the output distribution of the unlearning algorithm to be similar to that obtained by retraining from scratch using the original training set with the requested datapoints removed from it. We focus on this definition because algorithms for exact unlearning such as statistical query learning~\cite{cao2015towards}, SISA~\cite{bourtoule2021machine}, and its adaptive variant~\cite{gupta2021adaptive} have high computational and memory cost.

Prior algorithms developed for approximate unlearning use a variety of techniques: perturbed gradient descent~\cite{neel2021descent, ullah2021machine}, Newton style updates~\cite{guo2020certified, sekhari2021remember}, and projected residual updates~\cite{izzo2021approximate}. The perturbed gradient descent and projected residual update methods provide theoretical error guarantees for the empirical training loss but fail to provide any generalization guarantees. In addition, while these methods reduce the computation burden associated with exact unlearning, their high memory costs are still similar to exact unlearning methods.

Given these issues, Newton update unlearning algorithms were proposed to efficiently satisfy approximate unlearning. Our work is closest to~\cite{guo2020certified, sekhari2021remember} who use Newton updates to efficiently delete data for generalized linear models.~\citet{sekhari2021remember} improve upon~\citet{guo2020certified} in multiple ways: (i) by not requiring full access to the training dataset, providing (ii) generalization guarantees, and (iii) removing the requirement for randomization in the learning algorithm itself (which often reduces utility). Yet the algorithm developed by~\cite{sekhari2021remember} targets the batch setting which is unrealistic in practice and they provide no empirical results demonstrating the efficacy of their algorithm. If implemented in an online way, their algorithm would suffer a much larger computational cost given the requirement to compute and invert a new Hessian for each delete request. Finally, neither of these algorithms provide theoretical guarantees for the commonly used models that are obtained from objective functions with non-smooth penalties.

We address several of these issues using the (proximal) infinitesimal jacknife~\cite{giordano2019swiss, jaeckel1972infinitesimal, efron1982jackknife}. Our algorithm can handle online delete requests selected in an adaptively adversarial manner (a failure mode of many previous algorithms pointed out by~\citet{gupta2021adaptive}) making it more practical for real world use. Furthermore, we provide generalization and deletion capacity guarantees similar to~\citet{sekhari2021remember} for both smooth and non-smooth regularizers. To do so, we leverage similar guarantees found in approximate cross-validation literature~\cite{wilson2020approximate}. Finally, inspired by recent working showing that hyperparameter tuning can leak user data~\cite{papernot2021hyperparameter} we demonstrate that all approximate unlearning algorithms introduced so far fail to unlearn in settings where hyperparameter tuning has taken place to choose a model.

\section{Methods and Results}
\label{sec:methods_results}
\paragraph{Learning} Consider the objective function
comprised of a loss function $\ell$, a regularizer $\pi$ and regularization parameter $\lambda \in \Lambda \subseteq [0,\infty]$.
The goal of learning is to find a parameter $\theta^\ast(\lambda)$ which minimizes the population risk
\begin{align*}

   F(z, \theta, \lambda) \triangleq \ \mathbb{E}_{z \sim \mathcal{D}} [\ell (z, \theta)] + \lambda \pi(\theta

\end{align*}
Given the distribution $\mathcal{D}$ is often inaccessible, practitioners often instead find a model $ \hat{\theta}_n(\lambda)$ which (at least approximately) minimizes the empirical risk
\begin{talign}\label{eq:erm}
 F_n(z, \theta, \lambda)
   \triangleq  \tfrac{1}{n} \sum_{i=1}^n \ell(z_i, \theta) + \lambda \pi(\theta,)

\end{talign}
corresponding to a given dataset $S= (z_1, \dots z_n)$
\paragraph{Unlearning} Having used a dataset $S$ to train and publish a model $\hat{\theta}_n(\lambda)$, a set of $m$ users in the training set $U\subset S$ might request that their datapoints be deleted and that any models produced using their data be removed. To comply with this request, an organization might find the minimizer  $\theta_{n, -U}(\lambda)$ of the leave-$U$-out objective
\balignt\label{eq:cvest}
F_{n, -U}(z, \theta, \lambda)  \triangleq \tfrac{1}{n-m}{\textstyle\sum}_{z \in S\backslash U} \ell (z,\theta) + \lambda\reg(\theta).
\ealignt

While {\em reoptiminzing the leave-one-out objective from scratch constitutes a baseline for the problem of unlearning}, the computational cost makes complying with every data delete request in this way undesirable.
Training from scratch satisfies the notion of unlearning~\citep{guo2020certified} formalized in~\cref{def:unlearn}, motivated by the definition of differential privacy.

\begin{definition}[$(\epsilon,\delta)$-unlearning of datapoint $\mathbf{z}$ \citep{guo2020certified}]\label{def:unlearn} Let $S$ be a fixed training set and $A: S \rightarrow \theta$ be an algorithm that trains on  $S$ and outputs a model $\theta \in \Theta$.  For an $\epsilon>0$, we say that a removal mechanism $M$ performs an $\epsilon$-certified removal of datapoint $\mathbf{z} \in S$ for learning algorithm $A$ if $\forall\, \mathcal{T} \subseteq {\Theta}$ and $S \subseteq \mathcal{Z}$, the following two conditions are satisfied:
\begin{align*}
 P(A(S\backslash \mathbf{z}) \in \mathcal{T})&\leq e^{\epsilon} P(M(A(S), T(S), \mathbf{z}) \in \mathcal{T} ) + \delta, \quad \text{and}\\
P(M(A(S), T(S), \mathbf{z}) \in \mathcal{T} )&\leq e^{\epsilon} P(A(S\backslash \mathbf{z}) \in \mathcal{T}) + \delta
\end{align*}
where $T(S)$ denotes the data statistics available to the removal mechanism $M$
\end{definition}
That is, the certified removal of ${\bf z}$ means that the likelihood ratio between the model produced by the unlearning algorithm and a model that was obtained using a dataset without ${\bf z}$ to begin with is close to all models in the hypothesis set, for all possible datasets and removed samples. As~\citet{guo2020certified} points out, this is similar to the definition of differential privacy, which states that for any two datasets $S$ and $S'$ that differ by a one datapoint a differentialy private algorithm algorithm must produce models that are close. That is, an $\epsilon$-diffenetially private algorithm~\cite{dwork2011} satisfies the condition
\begin{talign*}
\forall \mathcal{T} \subseteq {\Theta}, S, S': e^{-\epsilon} &\leq  \frac{P(A(S) \in \mathcal{T})}{P(A(S') \in \mathcal{T})} \leq e^{\epsilon}.
\end{talign*}
Finally, we point out that like most previously proposed unlearning algorithms, we do not require $T(S)$ to contain the entire training set, but instead propose unlearning algorithms for which $T(S)$ is independent of $n$.
\subsection{Unlearning models obtained via regularized empirical risk minimization} We recommend use of the following proximal operator to comply with delete requests
\balign\label{eq:prox-operator}
{\bf \text{ prox}}_{\lambda\pi}^{H}(v)\triangleq \argmin_{\theta \in \mathbb{R}^d} \half \| v- \theta\|_{H}^2
+ \lambda \pi(\theta),
\ealign
which allows us to handle objective functions that incorporate non-smooth regularizers, such as the $\ell_1$, elastic net or nuclear norm penalty. More specifically, having deleted the datapoints in the set $U$, we propose~\cref{algo:1} to delete the data of an additional user $j$.
\begin{algorithm}[ht!]
\begin{algorithmic}
\State {\bf Input:} $|U| = m$, Hessian of  loss or objective, $\tilde{\theta}_{n,-U}(\lambda)$, $\bar{\theta}^N_{n,-U}(\lambda)$ $\hat{\theta}_{n}(\lambda)$, and delete request $j$
\State {\bf Set:} $H _\ell= \frac{1}{n}\sum_{i=1}^n\nabla^2_{\theta}\loss(z_i,\hat{\theta}_n)$, $H _f= \frac{1}{n}\sum_{i=1}^n\nabla^2_{\theta}f(z_i,\hat{\theta}_n,\lambda)$, $\bar{\theta}_{n, -\emptyset}^N(\lambda) = \tilde{\theta}_{n, -\emptyset}(\lambda) = \estt$
\State {\bf If $\pi$ is not smooth:}
\State {}\quad \quad {\bf Compute:}
\begin{subequations}
\begin{talign}
\bar{\theta}_{n, -(U\cup \{j\})}(\lambda) &= {\bf \text{ prox}}_{\lambda\pi}^{H_\ell}\Big( \bar{\theta}_{n, -U}^N(\lambda) + \frac{1}{n}H_\ell^{-1}\nabla \ell(z_j, \hat{\theta}_{n}(\lambda)  )\Big)\\
c&= \frac{(m+1)^2(2CL\mu + ML)}{\mu^2n^2}\frac{\sqrt{2\ln(1.25/\delta)}}{\epsilon}
\end{talign}
\end{subequations}
\State {}\quad \quad {\bf Store: }$\bar{\theta}_{n, -(U\cup \{j\})}^N(\lambda) = \bar{\theta}_{n, -U}^N(\lambda) + \frac{1}{n}H_\ell^{-1}\nabla \ell(z_j, \hat{\theta}_{n}(\lambda)  )$\\
\State{\bf Else compute:}
\begin{subequations}
\begin{talign}
\bar{\theta}_{n, -(U\cup \{j\})}(\lambda) &= \tilde{\theta}_{n, -U}(\lambda) + \frac{1}{n}H_f^{-1}\nabla \ell(z_j, \hat{\theta}_{n}(\lambda)  )\\
c& = \frac{(2m+1)(2CL\mu + ML)}{\mu^2n^2}\frac{\sqrt{2\ln(1.25/\delta)}}{\epsilon}
\end{talign}
\end{subequations}
\State {\bf Sample:} $\sigma \sim \mathcal{N}(0, cI)$ \\
{\bf Return:} $\tilde{\theta}_{n, -(U\cup \{j\})}(\lambda)  := \bar{\theta}_{n, -(U\cup \{j\})}(\lambda) + \sigma$\\
\end{algorithmic}
\caption{Infinitesimal Jacknife (\textbf{IJ}) Online Unlearning Algorithm}
\label{algo:1}
\end{algorithm}

\paragraph{Guarantees}
While we give guarantees for functions that are strongly convex, we rely on standard reductions from the convex setting to the strongly convex setting (i.e. based on defining a objective function $ F(\theta) = \tilde{F}(\theta) + (\mu/2)\|\theta\|^2$ when $\tilde{F}$ is convex). Furthermore, similar to~\citet[3.3]{guo2020certified} our methods can be used for unlearning in the non-convex setting when the deep learning model applies a simple convex model to a differentially private feature extractor~\cite{abadi2016deep}.
\begin{assumption}[Smooth regularizer]\label{ass:1}
For any $z \in \mathcal{Z}$, the objective function $F(\theta, z,\lambda)$ is $\mu$-strongly convex and $L$-Lipschitz with $M$-smooth Hessian. The loss has $C$-Lipschitz Hessians.
\end{assumption}
\begin{assumption}[Non-smooth regularizer]\label{ass:2}
For any $z \in \mathcal{Z}$, the loss function $\loss(\theta, z)$ is $\mu$-strongly convex and $L$-Lipschitz with $M$-smooth and $C$-Lipschitz Hessians. The regularizer $\pi(\theta)$ is convex.
\end{assumption}
With either of these assumptions, it's possible to show that the denoised output of~\cref{algo:1} is $O(m^2/n^2)$ close to the exact unlearned model. We formalize this proximity result in the following~\cref{lemma:noise}.

\begin{lemma}[Proximity to the baseline estimator]\label{lemma:noise}
Suppose $F$ satisfies Assumption~\ref{ass:1} or Assumption~\ref{ass:2}. Let $S$ be the dataset of size $n$ sampled from $\mathcal{D}$ and $U \subseteq S$ denote the set of $m$ delete requests. Consider $\bar{\theta}_{n,-U}(\lambda)$, i.e. the output of~\cref{algo:1} without noise term $\sigma$ added and the model $\hat{\theta}_{n,-U}(\lambda)$ obtained by minimizing the leave-U-out objective $F_{n,-U}$. Then,
\begin{subequations}
\begin{talign}
\twonorm{ \hat{\theta}_n(\lambda)- \hat{\theta}_{n, -U}(\lambda)}
 &\leq \frac{m L}{\mu n}, \quad \quad \text{\em and}\\
\label{eq:ineq1}\|\hat{\theta}_{n,-U}(\lambda) - \bar{\theta}_{n, -U}(\lambda) \|_2 &\leq \frac{2m^2 CL}{n^2\mu^2 } + \frac{m^2 ML^2}{n^2 \mu^3}  .
\end{talign}
\end{subequations}
\end{lemma}
\cref{lemma:noise} implies adding the noise term $\sigma \propto O(m^2/n^2)$ will result in the desired unlearning guarantee.
The following~\cref{thm:1} outlines this guarantee as well as the proximity of the unlearnt model to the test loss minimizer.  The proof is contained in Appendix~\ref{app:closeness_proof}.
\begin{theorem}[Unlearning and generalization guarantees]\label{thm:1} Suppose the loss function satisfies Assumption~\ref{ass:1} or~Assumption~\ref{ass:2} and consider any learning algorithm that returns a model $O(1/n^2)$ close to the empirical risk minimizer $\hat{\theta}_n(\lambda)$ trained on any dataset $S \sim \mathcal{D}$ of size $n$. Then

    the output $\tilde{\theta}_{n,-U}(\lambda)$ of~\cref{algo:1}, where $|U| = m$, satisfies the test error bound
    \begin{talign*}\mathbb{E}[F(\tilde{\theta}_{n, -U}(\lambda)) -  F(\theta^\ast(\lambda))] \leq O\left( \frac{(2m^2CL^2\mu + ML^3m^2}{\mu^3n^2}\cdot\frac{\sqrt{d}\sqrt{ln(1/\delta)}}{\epsilon} + \frac{4mL^2}{\mu n}\right).\end{talign*}
    Furthermore, the unlearning~\cref{algo:1} results in $(\epsilon, \delta)$-certifiable removal of $\forall {\bf z} \in U\subseteq S$.
\end{theorem}

\subsubsection{Deletion Capacity}

\citet{sekhari2021remember} introduce the notion of deletion capacity which formalizes how many samples can be deleted from a the model parameterized by the original empirical risk minimizer $\estt$ while maintaining reasonable guarantees on the test loss. We restate the definition here.
    \begin{definition}[Deletion capacity~\cite{sekhari2021remember}]Let $\epsilon,\delta,\gamma>0$ and $S$ be a dataset of size $n$ drawn i.i.d From $\mathcal{D}$, and let $F(\theta,z,\lambda)$ be an objective function. For a learning algorithm and removal mechanism $M$ that satisfies $(\epsilon,\delta)$-certified removal of all ${\bf z} \in U$, where $U$ is the set of delete requests, the deletion capacity $m_{\epsilon,\delta,\gamma}^{A,M}(d,n)$ is defined as the maximum number of samples that can be unlearned while still ensuring the excess population risk is $\gamma$. Specifically,
    \begin{talign*}
    m_{\epsilon,\delta,\gamma}^{A,M}(d,n) \triangleq \max \left\{m \,|\, \mathbb{E}\left[\max_{U\subseteq S: |U| \leq m} F(M(A(S),S, U) - F(\theta(\lambda)^\ast) \right] \leq \gamma\right\}
    \end{talign*}
where the expectation is with respect to $S \sim \mathcal{D}$ and output of the learning algorithm
$A$ and removal mechanism $M$.
\end{definition}

\citet{sekhari2021remember} provide both an upper bound and lower bound on the deletion capacity of unlearning algorithms. We recount both bounds and show our algorithm achieves the same bounds.

\begin{theorem}[Deletion capacity upper bound~\citep{sekhari2021remember}]
Let $\delta \leq 0.005$ and $\epsilon = 1$. There exists a 4-Lipschitz and 1-strongly convex loss function f, and a distribution $\mathcal{D}$ such that for any learning algorithm $A$ and removal mechanism $M$ that satisfies $(\epsilon, \delta)$-certified removal and has access to all undeleted samples $S \backslash U$, then the deletion capacity is:
\begin{align*}
m_{\epsilon,\delta,\gamma}^{A,M}(d,n) \leq c n,
\end{align*}
where the constant $c$ depends on the Lipschitz constants $L$, $M$, strongly convex constant $\mu$, and boundedness constant $C$ from Assumptions~\ref{ass:1} or~\ref{ass:2} and $c < 1$.

\end{theorem}

\begin{theorem}[Deletion capacity lower bound~\citep{sekhari2021remember}] \label{thm:del_cap_lower}
    Let $\epsilon, \delta > 0$ and $\gamma = 0.01$, $S$ be a dataset of size $n$ drawn i.i.d from $\mathcal{D}$, and  $F(\theta,z,\lambda)$ be an objective function satisfying Assumption~\ref{ass:1} or Assumptions~\ref{ass:2}. Consider a learning algorithm $A$ that returns the empirical risk minimizer and unlearning algorithm $M$. Then the deletion capacity is:
    \begin{talign}\label{eq:lb}
    m_{\epsilon,\delta, 0.01}^{A,M}(d,n) \geq c \cdot \frac{n \sqrt{\epsilon}}{(d \text{\em log}(1/\delta))^{\frac{1}{4}}}
    \end{talign}
    where the constant $c$ depends on the Lipschitz constants $L$, $C$, and $M$.
    \end{theorem}

\begin{theorem}[Deletion capacity from unlearning via DP~\citep{sekhari2021remember}] There exists a polynomial time learning algorithm $A$ and removal mechanism $M$ of the form $M(U, A(S), T(S)) = A(S)$ such that the deletion capacity is:
\begin{talign*}
 m_{\epsilon,\delta, 0.01}^{A,M}(d,n) \geq \tilde{\Omega}\left(\frac{n\epsilon}{\sqrt{d\log(e^{\epsilon}/\delta})}\right)
\end{talign*}
where the constant in $\Omega$-notation depends on the properties of the loss function $f$.

\end{theorem}
As an extensions of a result developed by~\citet[Section C]{bassily2019private}, \citet{sekhari2021remember} show that any unlearning algorithm that ignores the samples $U$ can't improve upon the DP lower bound. This motivates the study of algorithms specifically designed for unlearning which leverage samples from $U$ instead of algorithms based on DP.
In~\cref{app:del_cap}, we provide details showing that our Algorithm~\ref{algo:1} achieves the lower bound~\eqref{eq:lb}, where the constant $c$ depends on the Lipschitz constants $L$, $M$, strongly convex constant $\mu$, and boundedness constant $C$.

\paragraph{Comparison to previous results}
We compare our method to~\citet{sekhari2021remember} and~\citet{guo2020certified} who propose optimizing a second-order Taylor approximation (\textbf{TA}) to the leave-$U$-out objective function~\eqref{eq:cvest} for batch removal of $U$. This results in the Newton-like removal mechanism~\eqref{eq:s}.
\begin{talign}\label{eq:s}
\tilde{\theta}_{n,-U}(\lambda) = \estt + \frac{1}{n-m}\left(\frac{1}{n-m}\sum_{z \inS \backslash U}\nabla^2_\theta F(z,\estt,\lambda)\right)^{-1}  \sum_{z\in U}\nabla\ell(z,\estt).
\end{talign}

{\em Comparison of Assumptions. } On the one hand, our Assumption~\ref{ass:1} is slightly more restrictive than that of~\citet{sekhari2021remember} given we require boundedness of the Hessian loss to obtain our unlearning, generalization and deletion capacity guarantees. Notably, this assumption does not rule out any of the most common convex objective functions (e.g. least squares, logistic, hinge, or cross entropy loss functions). On the other hand, our technique allows for non-smooth regularizers which are common in modern machine learning pipelines.

{\em Comparison of Computation.}
~\cref{algo:1} entails calculating and inverting the full Hessian $H_f$ or $H_\ell$ and storing it (memory cost $O(d^2)$ and computation cost $O(d^3)$). It also entails storing the gradient of each point evaluated on the full data model $\estt$, as well as the current model $\tilde{\theta}_{n, -U}(\lambda)$. In the setting where $\pi$ is not smooth, $\bar{\theta}_{n,-U}(\lambda)$ must be stored. During runtime,~\cref{algo:1} requires matrix-vector multiplication and vector addition (as well as proximal step in the non-smooth setting).
For unlearning in settings where deletion requests come in a online manner, our technique is computationally more efficient. This is because removal mechanism~\eqref{eq:s} requires computing and inverting a different Hessian that depends on the user requesting the deletion. Therefore, outside simple settings, complying with such requests involves a computational cost of $O(md^3)$ to remove $m$ datapoints.

 {\em Comparison of unlearning, generalization and deletion capacity.} As summarized above, the generalization, unlearning and deletion capacity results for our removal mechanism are essentially equivalent to the unlearning, generalization, and deletion capacity results of~\cite{sekhari2021remember}.

\begin{remark}[Extending~\citet{sekhari2021remember} to non-smooth regularizers] Following from the equivalence we show between the batch and online setting in Appendix~\ref{app:batch_eq_stream}, we can extend our use of the proximal operator to~\eqref{eq:s} which would extend the results of~\citet{sekhari2021remember} to non-smooth regularizers. Similar unlearning, deletion capacity and generalization results are obtained. We provide details in~\cref{app:ext}.
\end{remark}
\section{Experiments}
In this section we will refer to retraining from scratch as \textbf{RT}, the Algorithm~\eqref{eq:s} as \textbf{TA} and our \cref{algo:1} as \textbf{IJ}.
We empirically demonstrate the benefits  of our algorithm over both \textbf{RT} and \textbf{TA} in three different settings: (i) smooth regularizers where we train a logistic regression model with an $\ell_2$ penalty to predict between the digit 3 and 8 from the MNIST dataset~\cite{lecun1998mnist}, (ii) non-smooth regularizers where we train a logistic regression model with an $\ell_1$ penalty to predict whether an individual was prescribed a Warfarin dosage of $> 30$ mg/week from a dataset released by the International Warfarin
Pharmacogenetics Consortium~\cite{international2009estimation}, and (iii) non-convex training where we apply a logistic regression model with an $\ell_2$ penalty to predict street digits signs 3 and 8 from SVHN~\cite{netzer2011reading} on representations extracted from a differentially private feature extractor with $\epsilon = 0.1$ (similar to the setup of~\citet{guo2020certified}). For all algorithms, we tune $\lambda$ over the set $\{10^{-3}, 10^{-4}, 10^{-5}, 10^{-6}\}$. In the Appendix~\ref{app:datasets}, we provide further details about each dataset and the code to produce our models is attached separately.

 We present results in the main paper for $\lambda = 1^{-3}$ and provide other results in Appendix~\ref{app:exps}. All models are trained on a single NVIDIA Tesla T4 GPU and 16 2.10GHz Xeon(R) Silver 4110 CPU cores. We focus our evaluation on total runtime in seconds and test set accuracy as the number of delete requests increases. For all results, we provide the average over three different runs and provide standard error bars.

\begin{figure}[t!]
\centering
\begin{subfigure}{.4\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/MNIST_runtime.png}
  \label{fig:mnist_runtime}
\end{subfigure}%
\begin{subfigure}{.6\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/mnist_test_acc_final.png}
  \label{fig:mnist_test_acc}
\end{subfigure}
\caption{\textbf{IJ} vs. \textbf{RT} for non-smooth regularizers. Comparing both the runtime and test accuracy of the unlearned models in our $\ell_2$ logistic regression setup for predicting 3's and 8's on MNIST.}
\label{fig:mnist}
\end{figure}

\paragraph{Logistic Regression with Smooth Regularizers}

In this experiment we simulate an online data deletion setup using the MNIST dataset. For simplicity, we restrict the problem to binary classification by predicting between 3s and 8s. This is the same setup used by~\citet{guo2020certified} to evaluate their approximate unlearning algorithm.
We flatten the MNIST image into a 1-D vector and train an $\ell_2$ regularized logistic regression model for each algorithm. We evaluate the impact of a deleting a sequence of 5000 datapoints (approximately 40\% of the total dataset) both randomly and in an adaptively chosen manner. In these experiments we consider noise at $c=0.01$.

  On average, \textbf{IJ} was 2611x faster than \textbf{RT} and 2045x faster than \textbf{TA} (Figure~\ref{fig:mnist}). We find that this improvement in runtime comes at very minimal cost to the test performance of the model returned by our algorithm compared to the test performance of \textbf{TA} (Figure~\ref{fig:mnist}). Furthermore, we observe that these results also hold when the delete requests are chosen adaptively (Figure~\ref{fig:mnist}). As discussed previously, the main savings in computation for our algorithm comes from only inverting the hessian once while \textbf{TA} requires a hessian inversion for every delete request.

\sub

\begin{figure}[h]
\centering
\begin{subfigure}{.3\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/Prox_runtime.png}
  \label{fig:prox_runtime}
\end{subfigure}%
\quad\quad\hspace{10pt}
\begin{subfigure}{.3\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/prox_test_acc.png}
  \label{fig:prox_test_acc}
\end{subfigure}
\caption{\textbf{IJ} vs. \textbf{RT} for non-smooth regularizers. Comparing both the runtime and test accuracy of the unlearned models in our $\ell_1$ logistic regression setup for predicting warfarin dosage.}
\label{fig:prox}
\vspace{-0.5mm}
\end{figure}

\paragraph{Logistic Regression with Non-Smooth Regularizers}

This experiment showcases the performance of our proximal Newton algorithm on a problem with a non-smooth regularizer. We focus on predicting warfarin dosing from patient demographic and physiological data because it a practical setting where $\ell_1$ regularization has been demonstrated to be preferred~\cite{sharabiani2015revisiting}. Given that \textbf{TA} does not naturally support non-smooth regularizers we only compare \textbf{IJ} to \textbf{RT}. In these experiments we consider a logistic regression objective, $\ell_1$ regularizer, and noise level of $c=0.01$.
 On average, \textbf{IJ} was 30x faster than \textbf{RT} (Figure~\ref{fig:prox}). This improvement in runtime only comes at small cost to the test accuracy of the model returned by our algorithm compared to the test performance of \textbf{TA} (Figure~\ref{fig:prox}).

 \paragraph{Non-Convex: Logistic Regression with Differentially Private Feature Extractor}
 \begin{figure}[h]
\centering
\begin{subfigure}{.35\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/SVHN_runtime.png}
  \label{fig:sub1}
\end{subfigure}%
\begin{subfigure}{.55\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/SVHN_test_acc_final.png}
  \label{fig:sub2}
\end{subfigure}
\caption{\textbf{IJ} vs. \textbf{TA} and \textbf{RT} for non-convex training. Comparing both the runtime and test accuracy of the unlearned models in our DP feature extractor + $\ell_2$ logistic regression setup for predicting digits in photos of street signs from SVHN.}
\label{fig:svhn}
\end{figure}
 We demonstrate the ability to use our unlearning algorithm in non-convex settings. Similar to~\citet{guo2020certified} we train a differentially private feature extractor with $\epsilon = 0.1$ on street digit signs from SVHN to extract representations which a logistic regression model can be applied on top of.  Similar to previous experiments, we pick digits 3 and 8 for simplicity and  observe significant speedups using \textbf{IJ}. On average, \textbf{IJ} was 15036x faster than \textbf{RT} and 17x faster than \textbf{TA} and these speedups come at a marginal cost to the test accuracy of our algorithm even as the number of delete requests increase (Figure~\ref{fig:svhn}).

\section{Unlearning hyperparameter-tuned models}
\label{sec:failure_mode}
One of the most common techniques for hyperparameter tuning is {\em cross-validation}. Here datapoints are used to validate and select models using the following cross-validation error objective
\begin{talign}\label{eq:cverror}
\text{CV}(\lambda) = \frac{1}{n}\sum_{i=1}^n \ell(z_i, \hat{\theta}_{n,-i}(\lambda)).
\end{talign}
Specifically, the model selection pipeline oftentimes entails selecting $\lambda \in \Lambda$ that minimizes the CV error~\eqref{eq:cverror}. Given each datapoint is used to select models, one might hope  it is possible to unlearn models using~\cref{algo:1} when CV is used to select the model. However, as the following proposition illustrates, the $(\epsilon,\delta)$-unlearning guarantees of Theorem~\ref{thm:1} no longer apply when CV has taken place.

\begin{proposition}\label{prop:1} Suppose cross-validation is used to select $\lambda \in \Lambda$ and the empirical risk minimizer $\estt$ is returned. Consider a delete request by user $i$ and the model returned by unlearning procedure~\eqref{eq:s} or~\eqref{algo:1}, which we denote $\tilde{\theta}_{n,-i}(\lambda)$. Then it is possible $\|\tilde{\theta}_{n,-i}(\lambda) - \hat{\theta}_{n,-i}(\lambda')\| = o(1/n)$ where $\hat{\theta}_{n,-i}(\lambda')$ is the model selected after deleting user $i$ and performing cross-validation again to select $\lambda' \in \Lambda$ before returning the empricial risk minizer.

\end{proposition}
{\em Proof of~\cref{prop:1}.}
Suppose $\ell(z,\theta) = \frac{1}{2}(z - \theta)^2$, $\pi(\theta) = \theta^2$ and $\Lambda = \{0, \infty\}$. Note that $\hat{\theta}_n(\lambda) = \frac{1}{1+\lambda} \bar{z}$ where $\bar{z} = \frac{1}{n} \sum_{i=1}^n z_i$ is the sample average. Consider a dataset consisting of $n-1$ points (group A) with value $-\frac{1}{n}$ and a remaining point (group B) with value $n$ with $n\geq2$, and suppose the user in group B requests to delete their data.
Performing cross-validation on this dataset will entail computing two kinds of sample averages, one where we have deleted a point from group $A$, $\bar{z}_{-i_A} = \frac{1}{n-1}(-\frac{n-2}{n} + n)$, and one where we have deleted the point from group $B$, $\bar{z}_{-i_B} =-\frac{1}{n}$. Recall the CV error
\begin{talign*}
    \text{CV}(\lambda) = \frac{1}{2n} \sum_{i=1}^n (z_i - \hat{\theta}_{n,-i}(\lambda))^2 = \frac{n-1}{2n}(\frac{1}{1+\lambda}\frac{1}{n-1}(n-\frac{n-2}{n} )-\frac{1}{n})^2 + \frac{1}{2n}(n + \frac{1}{1+\lambda}\frac{1}{n})^2
\end{talign*}
When minimized over the set $\Lambda = \{0,\infty\}$, $\lambda = \infty$ is optimal for any $n\geq2$. This results in estimator $\hat{\theta}_{n}(\lambda) =\hat{\theta}_{n}(\infty) = 0$. The leave-one-out approximation is the same for estimators~\eqref{algo:1} and~\eqref{eq:s}, given $\nabla_{\theta}^2 F(z,\theta,\lambda)^{-1} = \frac{1}{1 + \lambda}$. Subsequently, $\tilde{\theta}_{n,-i}(\lambda) = \hat{\theta}_{n}(\lambda) + \frac{1}{n}\frac{1}{1+\lambda}( \hat{\theta}_{n}(\lambda) - z_i )$ results in the approximation $\tilde{\theta}_{n,-i}(\infty) = 0$. On the other hand, having deleted the datapoint from group $B$, we have a new sample mean $\bar{z} = -\frac{1}{n}$ and CV error, given by
\begin{talign*}
\text{CV}(\lambda) = \frac{1}{2n} \sum_{i=1}^n (z_i - \hat{\theta}_{n,-i}(\lambda))^2 = \frac{1}{2n}(-\frac{1}{n} + \frac{1}{1+\lambda} \frac{1}{n})^2
\end{talign*}
is minimized by $\lambda = 0$. This results in leave-one-out minimizer $\hat{\theta}_{n,-i}(0) = -\frac{1}{n}$. $\qedsymbol$

An implication of~\cref{prop:1} is that~\cref{algo:1} as well as the algorithms proposed by~\cite{sekhari2021remember,guo2020certified}  do not unlearn models when cross-validation is used to selected hyperparameters.  This is because the noise term $\sigma \propto O(m^2/n^2)$ is no longer sufficient to guarantee datapoint $i$ is unlearned.
This means that organizations which train their models using cross-validation and use approximate unlearning algorithms could still be leaking information about the data which they delete.

\section{Discussion}

A main contribution of our study is the development of an efficient online data deletion algorithm for non-smooth problems. The only previous work proposing a low-memory online algorithm is~\citet{guo2020certified}. However,~\citet{marchant2021hard} show that this algorithm is susceptible to poisoning attacks rendering it highly inefficient.
While exact unlearning algorithms such as SISA and retraining naturally work in an online setting, our work is the first to make this work for approximate unlearning algorithms. Further development of data deletion algorithms should focus more on the online setting to ensure practical use.

The infinitesimal jacknife has been previously been used to perform cross-validation. We note deep connections between the approximate cross-validation algorithms and approximate machine unlearning algorithms. The algorithm developed by~\cite{sekhari2021remember}, for example, can be viewed as an analog of the approximate cross-validation algorithm proposed by~\cite{beirami2017optimal, rad2019scalable}. Additionally, the model selection error bounds provided in the approximate cross-validation literature for example in~\cite{wilson2020approximate} are very similar to the generalization guarantees proved in our work and~\cite{sekhari2021remember} where we are concerned with the error introduced by our approximation to the unlearning baseline.
 We believe further connections could be exploited to provide unlearning algorithms when hyperparameter tuning has taken place.

 In this work and in several others we consider a definition of data deletion that is parameterized by two values $\epsilon$ and $\delta$. As is the case with differential privacy, it is currently unclear what the impact of satisfying different levels of $\epsilon$ means practically. Developing auditing algorithms~\cite{thudi2021necessity} similar to those recently seen in the DP community~\cite{NEURIPS2020_fc4ddc15, nasr2021adversary} can help provide more transparency on the meaning of the $(\epsilon, \delta)$-unlearning guarantee.

Finally, we return to the broader question we posed at the beginning: \textit{what does it mean to delete data from a  machine learning pipeline?} Most existing work focuses on data deletion in the model training process. Yet, the machine learning and data analysis pipeline is much broader than just model training. As evidenced in Section~\ref{sec:failure_mode}, the lack of research on data deletion in model selection could potentially result in information being leaked from previously proposed unlearning algorithms. Given this result, it is likely that all unlearning algorithms ({\em }both exact and inexact}) still leak information about deleted data in other stages of the machine learning pipeline such as exploratory data analysis and feature selection. We encourage the community to explore definitions of data deletion which encompass the entire machine learning pipeline.

\clearpage

\section{Introduction}
 The right to be forgotten (RtbF) is considered a fundamental human right in many legal systems~\cite{rosen2011right, mcgoldrick2013developments, bygrave2014right}. The proliferation of techniques that employ user data to do things such as training and validating machine learning across a variety of organizations has led to reconsideration of how to interpret RtbF. The European Union's General Data Protection Regulation (GDPR), California's Consumer Privacy Act (CCPA), and Canada's proposed Consumer Privacy Protection Act (CPPA) are all examples of new pieces of legislation which attempt to codify the RtbF by requiring companies and organizations to delete a user's data by request~\cite{voigt2017eu}.

 But \textit{what does it mean to delete a user's data?} User data, for example, can be recovered from trained machine learning models~\cite{shokri2017membership} and hyperparameter tuning procedures~\cite{papernot2021hyperparameter}. This suggests that data deletion should require organizations to take action on the models and algorithms derived from the data as well. This interpretation is consistent with the Federal Trade Commission's recent action ordering companies to delete the data from users who deleted their account as well as the models and algorithms derived from the users' data~\cite{FTC}. Forcing organizations to comply with each deletion request by retraining, however, comes with potentially significant monetary and time costs. Thus, it is worth asking if these costs can be managed while still maintaining model performance.

The cost concerns associated with RtbF compliance have prompted several recent works which formalize and study the problem of unlearning~\cite{cao2015towards}. The aim of these works is to develop techniques which delete user data from models that are inexpensive in both computation and memory while maintaining reasonable performance.
Most unlearning algorithms proposed so far focus on unlearning models obtained via empirical risk minimization~\cite{guo2020certified,sekhari2021remember,bourtoule2021machine,neel2021descent,marchant2021hard}. However, several of these methods are memory intensive~\cite{bourtoule2021machine, gupta2021adaptive}, requiring organizations to store several states of the model while training. We build on recent works~\cite{guo2020certified, sekhari2021remember} which show that for models derived from minimizing convex and sufficiently smooth ERM objectives, a Newton update to the current model can be applied in order to approximately unlearn in certain data directions. We show a different Newton estimate based on the classical infinitesimal jacknife developed in the robust statistics literature ~\cite{jaeckel1972infinitesimal,efron1982jackknife} results in a more computationally efficient unlearning algorithm in the online setting. While the current legislation only requires companies to satisfy delete requests in 30 days there are scenarios where immediate (online) delete requests are necessary such as the UK Biobank~\cite{ginart2019making}. We also show how to utilize the proximal infinitesimal jackknife~\cite{wilson2020approximate} to unlearn in settings when the model was trained using an ERM objective that is not smooth. Finally, we present an important and concerning failure mode of all approximate unlearning algorithms.

Our principal contributions are three-fold.
\begin{itemize}[leftmargin=15pt]
   \item  {\em Computationally efficient online algorithm.} We develop an online unlearning algorithm to unlearn a sequence of $m$ datapoints from a model $\estt$ that approximately minimizes a smooth and convex ERM objective that requires $O(d^2)$ storage and has running time $O(md^2)$.
    To unlearn $m$ datapoints in an online manner, the algorithms developed in prior works~(e.g. \cite{guo2020certified, sekhari2021remember}) requires a similar storage, but have a longer $O(md^3)$ running time. By avoiding the cost of computing and inverting a different Hessian at each deletion request we improve on the computational requirements of previous memory efficient unlearning algorithms, while maintaining the same generalization, unlearning and deletion capacity guarantees. We empirically demonstrate significant computational savings without sacrificing test set accuracy on multiple datasets.

    \item {\em Accommodating non-smooth regularizers.} We provide a generalization of our unlearning algorithm based on the proximal Newton method that can be used to efficiently delete data from models that minimize objective functions with non-smooth penalties.
    We provide state-of-the art unlearning, deletion capacity and generalization guarantees for our new unlearning method. We empirically demonstrate significant computational savings without sacrificing test set accuracy in predicting Warfarin dosages.
    \item {\em Failure modes.} Most data processing pipelines are not as simple as writing down an objective function and running an algorithm out-of-the-box which returns the approximate empirical risk minimizer. A more common practice is to tune hyperparameters using techniques such as cross-validation.
    We reveal a fundamental limitation of all (approximate) data removal processes developed so far when hyperparameter tuning takes place.
\end{itemize}

\section{Related Work}
Given the increasing concerns around privacy of user data,
recent research on \textit{machine unlearning} studies how we can efficiently delete datapoints used to train models without retraining from scratch. This work was first initiated by~\citet{cao2015towards} whose definition requires the outputs of an unlearning algorithm to be identical to the outputs of the model produced by retraining. Since then, several works have provided different definitions of machine unlearning which can be separated as exact unlearning~(\cite{bourtoule2021machine, thudi2021necessity, gupta2021adaptive, garg2020formalizing}) or approximate unlearning~(\cite{guo2020certified, sekhari2021remember, ginart2019making, dwork2014algorithmic, neel2021descent}).

Our work is focused on satisfying approximate unlearning definitions inspired by differential privacy~\cite{dwork2014algorithmic} defined by~\cite{guo2020certified} as $(\epsilon, \delta)$-certified removal or by~\cite{sekhari2021remember} as $(\epsilon, \delta)$-unlearning. This definition requires the output distribution of the unlearning algorithm to be similar to that obtained by retraining from scratch using the original training set with the requested datapoints removed from it. We focus on this definition because algorithms for exact unlearning such as statistical query learning~\cite{cao2015towards}, SISA~\cite{bourtoule2021machine}, and its adaptive variant~\cite{gupta2021adaptive} have high computational and memory cost.

Prior algorithms developed for approximate unlearning use a variety of techniques: perturbed gradient descent~\cite{neel2021descent, ullah2021machine}, Newton style updates~\cite{guo2020certified, sekhari2021remember}, and projected residual updates~\cite{izzo2021approximate}. The perturbed gradient descent and projected residual update methods provide theoretical error guarantees for the empirical training loss but fail to provide any generalization guarantees. In addition, while these methods reduce the computation burden associated with exact unlearning, their high memory costs are still similar to exact unlearning methods.

Given these issues, Newton update unlearning algorithms were proposed to efficiently satisfy approximate unlearning. Our work is closest to~\cite{guo2020certified, sekhari2021remember} who use Newton updates to efficiently delete data for generalized linear models.~\citet{sekhari2021remember} improve upon~\citet{guo2020certified} in multiple ways: (i) by not requiring full access to the training dataset, providing (ii) generalization guarantees, and (iii) removing the requirement for randomization in the learning algorithm itself (which often reduces utility). Yet the algorithm developed by~\cite{sekhari2021remember} targets the batch setting which is unrealistic in practice and they provide no empirical results demonstrating the efficacy of their algorithm. If implemented in an online way, their algorithm would suffer a much larger computational cost given the requirement to compute and invert a new Hessian for each delete request. Finally, neither of these algorithms provide theoretical guarantees for the commonly used models that are obtained from objective functions with non-smooth penalties.

We address several of these issues using the (proximal) infinitesimal jacknife~\cite{giordano2019swiss, jaeckel1972infinitesimal, efron1982jackknife}. Our algorithm can handle online delete requests selected in an adaptively adversarial manner (a failure mode of many previous algorithms pointed out by~\citet{gupta2021adaptive}) making it more practical for real world use. Furthermore, we provide generalization and deletion capacity guarantees similar to~\citet{sekhari2021remember} for both smooth and non-smooth regularizers. To do so, we leverage similar guarantees found in approximate cross-validation literature~\cite{wilson2020approximate}. Finally, inspired by recent working showing that hyperparameter tuning can leak user data~\cite{papernot2021hyperparameter} we demonstrate that all approximate unlearning algorithms introduced so far fail to unlearn in settings where hyperparameter tuning has taken place to choose a model.

\section{Methods and Results}
\label{sec:methods_results}
\paragraph{Learning} Consider the objective function
comprised of a loss function $\ell$, a regularizer $\pi$ and regularization parameter $\lambda \in \Lambda \subseteq [0,\infty]$.
The goal of learning is to find a parameter $\theta^\ast(\lambda)$ which minimizes the population risk
\begin{align*}

   F(z, \theta, \lambda) \triangleq \ \mathbb{E}_{z \sim \mathcal{D}} [\ell (z, \theta)] + \lambda \pi(\theta

\end{align*}
Given the distribution $\mathcal{D}$ is often inaccessible, practitioners often instead find a model $ \hat{\theta}_n(\lambda)$ which (at least approximately) minimizes the empirical risk
\begin{talign}\label{eq:erm}
 F_n(z, \theta, \lambda)
   \triangleq  \tfrac{1}{n} \sum_{i=1}^n \ell(z_i, \theta) + \lambda \pi(\theta,)

\end{talign}
corresponding to a given dataset $S= (z_1, \dots z_n)$
\paragraph{Unlearning} Having used a dataset $S$ to train and publish a model $\hat{\theta}_n(\lambda)$, a set of $m$ users in the training set $U\subset S$ might request that their datapoints be deleted and that any models produced using their data be removed. To comply with this request, an organization might find the minimizer  $\theta_{n, -U}(\lambda)$ of the leave-$U$-out objective
\balignt\label{eq:cvest}
F_{n, -U}(z, \theta, \lambda)  \triangleq \tfrac{1}{n-m}{\textstyle\sum}_{z \in S\backslash U} \ell (z,\theta) + \lambda\reg(\theta).
\ealignt

While {\em reoptiminzing the leave-one-out objective from scratch constitutes a baseline for the problem of unlearning}, the computational cost makes complying with every data delete request in this way undesirable.
Training from scratch satisfies the notion of unlearning~\citep{sekhari2021remember} formalized in~\cref{def:unlearn}.

\begin{definition}[$(\epsilon,\delta)$-unlearning \citep{sekhari2021remember}]\label{def:unlearn}
Let $S$ be a fixed training set and $A: S \rightarrow \theta$ be an algorithm that trains on  $S$ and outputs a model $\theta \in \Theta$. For an $\epsilon>0$ and set of delete requests $U \subseteq S$, we say that a removal mechanism $M$ is $(\epsilon, \delta)$-unlearning for learning algorithm $A$ if $\forall\, \mathcal{T} \subseteq {\Theta}$ and $S \subseteq \mathcal{Z}$, the following two conditions are satisfied:

\begin{align*}
 P(M(U, A(S), T(S))\in \mathcal{T})&\leq e^{\epsilon} P(M(\emptyset, A(S \backslash U), T(S \backslash U))\in \mathcal{T}) + \delta, \quad \text{and}\\
P(M(\emptyset, A(S \backslash U), T(S \backslash U))\in \mathcal{T})&\leq e^{\epsilon} P(M(U, A(S), T(S))\in \mathcal{T}) + \delta
\end{align*}

\end{definition}

Finally, we point out that like most previously proposed unlearning algorithms, we do not require $T(S)$ to contain the entire training set, but instead propose unlearning algorithms for which $T(S)$ is independent of $n$.
\subsection{Unlearning models obtained via regularized empirical risk minimization} We recommend use of the following proximal operator to comply with delete requests
\balign\label{eq:prox-operator}
{\bf \text{ prox}}_{\lambda\pi}^{H}(v)\triangleq \argmin_{\theta \in \mathbb{R}^d} \half \| v- \theta\|_{H}^2
+ \lambda \pi(\theta),
\ealign
which allows us to handle objective functions that incorporate non-smooth regularizers, such as the $\ell_1$, elastic net or nuclear norm penalty. More specifically, having deleted the datapoints in the set $U$, we propose~\cref{algo:1} to delete the data of an additional user $j$.
\begin{algorithm}[ht!]
\begin{algorithmic}
\State {\bf Input:} $|U| = m$, Hessian of  loss or objective, $\tilde{\theta}_{n,-U}(\lambda)$, $\bar{\theta}^N_{n,-U}(\lambda)$ $\hat{\theta}_{n}(\lambda)$, and delete request $j$
\State {\bf Set:} $H _\ell= \frac{1}{n}\sum_{i=1}^n\nabla^2_{\theta}\loss(z_i,\hat{\theta}_n)$, $H _f= \frac{1}{n}\sum_{i=1}^n\nabla^2_{\theta}f(z_i,\hat{\theta}_n,\lambda)$, $\bar{\theta}_{n, -\emptyset}^N(\lambda) = \tilde{\theta}_{n, -\emptyset}(\lambda) = \estt$
\State {\bf If $\pi$ is not smooth:}
\State {}\quad \quad {\bf Compute:}
\begin{subequations}
\begin{talign}
\bar{\theta}_{n, -(U\cup \{j\})}(\lambda) &= {\bf \text{ prox}}_{\lambda\pi}^{H_\ell}\Big( \bar{\theta}_{n, -U}^N(\lambda) + \frac{1}{n}H_\ell^{-1}\nabla \ell(z_j, \hat{\theta}_{n}(\lambda)  )\Big)\\
c&= \frac{(m+1)^2(2CL\mu + ML)}{\mu^2n^2}\frac{\sqrt{2\ln(1.25/\delta)}}{\epsilon}
\end{talign}
\end{subequations}
\State {}\quad \quad {\bf Store: }$\bar{\theta}_{n, -(U\cup \{j\})}^N(\lambda) = \bar{\theta}_{n, -U}^N(\lambda) + \frac{1}{n}H_\ell^{-1}\nabla \ell(z_j, \hat{\theta}_{n}(\lambda)  )$\\
\State{\bf Else compute:}
\begin{subequations}
\begin{talign}
\bar{\theta}_{n, -(U\cup \{j\})}(\lambda) &= \tilde{\theta}_{n, -U}(\lambda) + \frac{1}{n}H_f^{-1}\nabla \ell(z_j, \hat{\theta}_{n}(\lambda)  )\\
c& = \frac{(2m+1)(2CL\mu + ML)}{\mu^2n^2}\frac{\sqrt{2\ln(1.25/\delta)}}{\epsilon}
\end{talign}
\end{subequations}
\State {\bf Sample:} $\sigma \sim \mathcal{N}(0, cI)$ \\
{\bf Return:} $\tilde{\theta}_{n, -(U\cup \{j\})}(\lambda)  := \bar{\theta}_{n, -(U\cup \{j\})}(\lambda) + \sigma$\\
\end{algorithmic}
\caption{Infinitesimal Jacknife (\textbf{IJ}) Online Unlearning Algorithm}
\label{algo:1}
\end{algorithm}

\paragraph{Guarantees}
While we give guarantees for functions that are strongly convex, we rely on standard reductions from the convex setting to the strongly convex setting (i.e. based on defining a objective function $ F(\theta) = \tilde{F}(\theta) + (\mu/2)\|\theta\|^2$ when $\tilde{F}$ is convex). Furthermore, similar to~\citet[3.3]{guo2020certified} our methods can be used for unlearning in the non-convex setting when the deep learning model applies a simple convex model to a differentially private feature extractor~\cite{abadi2016deep}.
\begin{assumption}[Smooth regularizer]\label{ass:1}
For any $z \in \mathcal{Z}$, the objective function $F(\theta, z,\lambda)$ is $\mu$-strongly convex and $L$-Lipschitz with $M$-smooth Hessian. The loss has $C$-Lipschitz Hessians.
\end{assumption}
\begin{assumption}[Non-smooth regularizer]\label{ass:2}
For any $z \in \mathcal{Z}$, the loss function $\loss(\theta, z)$ is $\mu$-strongly convex and $L$-Lipschitz with $M$-smooth and $C$-Lipschitz Hessians. The regularizer $\pi(\theta)$ is convex.
\end{assumption}
With either of these assumptions, it's possible to show that the denoised output of~\cref{algo:1} is $O(m^2/n^2)$ close to the exact unlearned model. We formalize this proximity result in the following~\cref{lemma:noise}.

\begin{lemma}[Proximity to the baseline estimator]\label{lemma:noise}
Suppose $F$ satisfies Assumption~\ref{ass:1} or Assumption~\ref{ass:2}. Let $S$ be the dataset of size $n$ sampled from $\mathcal{D}$ and $U \subseteq S$ denote the set of $m$ delete requests. Consider $\bar{\theta}_{n,-U}(\lambda)$, i.e. the output of~\cref{algo:1} without noise term $\sigma$ added and the model $\hat{\theta}_{n,-U}(\lambda)$ obtained by minimizing the leave-U-out objective $F_{n,-U}$. Then,
\begin{subequations}
\begin{talign}
\twonorm{ \hat{\theta}_n(\lambda)- \hat{\theta}_{n, -U}(\lambda)}
 &\leq \frac{m L}{\mu n}, \quad \quad \text{\em and}\\
\label{eq:ineq1}\|\hat{\theta}_{n,-U}(\lambda) - \bar{\theta}_{n, -U}(\lambda) \|_2 &\leq \frac{2m^2 CL}{n^2\mu^2 } + \frac{m^2 ML^2}{n^2 \mu^3}  .
\end{talign}
\end{subequations}
\end{lemma}
\cref{lemma:noise} implies adding the noise term $\sigma \propto O(m^2/n^2)$ will result in the desired unlearning guarantee.
The following~\cref{thm:1} outlines this guarantee as well as the proximity of the unlearnt model to the test loss minimizer.  The proof is contained in Appendix~\ref{app:closeness_proof}.
\begin{theorem}[Unlearning and generalization guarantees]\label{thm:1} Suppose the loss function satisfies Assumption~\ref{ass:1} or~Assumption~\ref{ass:2} and consider any learning algorithm that returns a model $O(1/n^2)$ close to the empirical risk minimizer $\hat{\theta}_n(\lambda)$ trained on any dataset $S \sim \mathcal{D}$ of size $n$. Then

    the output $\tilde{\theta}_{n,-U}(\lambda)$ of~\cref{algo:1}, where $|U| = m$, satisfies the test error bound
    \begin{talign*}\mathbb{E}[F(\tilde{\theta}_{n, -U}(\lambda)) -  F(\theta^\ast(\lambda))] \leq O\left( \frac{(2m^2CL^2\mu + ML^3m^2}{\mu^3n^2}\cdot\frac{\sqrt{d}\sqrt{ln(1/\delta)}}{\epsilon} + \frac{4mL^2}{\mu n}\right).\end{talign*}
    Furthermore, the unlearning~\cref{algo:1} results in $(\epsilon, \delta)$-certifiable removal of $\forall {\bf z} \in U\subseteq S$.
\end{theorem}

\subsubsection{Deletion Capacity}

\citet{sekhari2021remember} introduce the notion of deletion capacity which formalizes how many samples can be deleted from a the model parameterized by the original empirical risk minimizer $\estt$ while maintaining reasonable guarantees on the test loss. We restate the definition here.
    \begin{definition}[Deletion capacity~\cite{sekhari2021remember}]Let $\epsilon,\delta,\gamma>0$ and $S$ be a dataset of size $n$ drawn i.i.d From $\mathcal{D}$, and let $F(\theta,z,\lambda)$ be an objective function. For a learning algorithm and removal mechanism $M$ that satisfies $(\epsilon,\delta)$-unlearning of all ${\bf z} \in U$, where $U$ is the set of delete requests, the deletion capacity $m_{\epsilon,\delta,\gamma}^{A,M}(d,n)$ is defined as the maximum number of samples that can be unlearned while still ensuring the excess population risk is $\gamma$. Specifically,
    \begin{talign*}
    m_{\epsilon,\delta,\gamma}^{A,M}(d,n) \triangleq \max \left\{m \,|\, \mathbb{E}\left[\max_{U\subseteq S: |U| \leq m} F(M(A(S),S, U) - F(\theta(\lambda)^\ast) \right] \leq \gamma\right\}
    \end{talign*}
where the expectation is with respect to $S \sim \mathcal{D}$ and output of the learning algorithm
$A$ and removal mechanism $M$.
\end{definition}

\citet{sekhari2021remember} provide both an upper bound and lower bound on the deletion capacity of unlearning algorithms. We recount both bounds and show our algorithm achieves the same bounds.

\begin{theorem}[Deletion capacity upper bound~\citep{sekhari2021remember}]
Let $\delta \leq 0.005$ and $\epsilon = 1$. There exists a 4-Lipschitz and 1-strongly convex loss function f, and a distribution $\mathcal{D}$ such that for any learning algorithm $A$ and removal mechanism $M$ that satisfies $(\epsilon, \delta)$-unlearning and has access to all undeleted samples $S \backslash U$, then the deletion capacity is:
\begin{align*}
m_{\epsilon,\delta,\gamma}^{A,M}(d,n) \leq c n,
\end{align*}
where the constant $c$ depends on the Lipschitz constants $L$, $M$, strongly convex constant $\mu$, and boundedness constant $C$ from Assumptions~\ref{ass:1} or~\ref{ass:2} and $c < 1$.

\end{theorem}

\begin{theorem}[Deletion capacity lower bound~\citep{sekhari2021remember}] \label{thm:del_cap_lower}
    Let $\epsilon, \delta > 0$ and $\gamma = 0.01$, $S$ be a dataset of size $n$ drawn i.i.d from $\mathcal{D}$, and  $F(\theta,z,\lambda)$ be an objective function satisfying Assumption~\ref{ass:1} or Assumptions~\ref{ass:2}. Consider a learning algorithm $A$ that returns the empirical risk minimizer and unlearning algorithm $M$. Then the deletion capacity is:
    \begin{talign}\label{eq:lb}
    m_{\epsilon,\delta, 0.01}^{A,M}(d,n) \geq c \cdot \frac{n \sqrt{\epsilon}}{(d \text{\em log}(1/\delta))^{\frac{1}{4}}}
    \end{talign}
    where the constant $c$ depends on the Lipschitz constants $L$, $C$, and $M$.
    \end{theorem}

\begin{theorem}[Deletion capacity from unlearning via DP~\citep{sekhari2021remember}] There exists a polynomial time learning algorithm $A$ and removal mechanism $M$ of the form $M(U, A(S), T(S)) = A(S)$ such that the deletion capacity is:
\begin{talign*}
 m_{\epsilon,\delta, 0.01}^{A,M}(d,n) \geq \tilde{\Omega}\left(\frac{n\epsilon}{\sqrt{d\log(e^{\epsilon}/\delta})}\right)
\end{talign*}
where the constant in $\Omega$-notation depends on the properties of the loss function $f$.

\end{theorem}
As an extensions of a result developed by~\citet[Section C]{bassily2019private}, \citet{sekhari2021remember} show that any unlearning algorithm that ignores the samples $U$ can't improve upon the DP lower bound. This motivates the study of algorithms specifically designed for unlearning which leverage samples from $U$ instead of algorithms based on DP.
In~\cref{app:del_cap}, we provide details showing that our Algorithm~\ref{algo:1} achieves the lower bound~\eqref{eq:lb}, where the constant $c$ depends on the Lipschitz constants $L$, $M$, strongly convex constant $\mu$, and boundedness constant $C$.

\paragraph{Comparison to previous results}
We compare our method to~\citet{sekhari2021remember} and~\citet{guo2020certified} who propose optimizing a second-order Taylor approximation (\textbf{TA}) to the leave-$U$-out objective function~\eqref{eq:cvest} for batch removal of $U$. This results in the Newton-like removal mechanism~\eqref{eq:s}.
\begin{talign}\label{eq:s}
\tilde{\theta}_{n,-U}(\lambda) = \estt + \frac{1}{n-m}\left(\frac{1}{n-m}\sum_{z \inS \backslash U}\nabla^2_\theta F(z,\estt,\lambda)\right)^{-1}  \sum_{z\in U}\nabla\ell(z,\estt).
\end{talign}

{\em Comparison of Assumptions. } On the one hand, our Assumption~\ref{ass:1} is slightly more restrictive than that of~\citet{sekhari2021remember} given we require boundedness of the Hessian loss to obtain our unlearning, generalization and deletion capacity guarantees. Notably, this assumption does not rule out any of the most common convex objective functions (e.g. least squares, logistic, hinge, or cross entropy loss functions). On the other hand, our technique allows for non-smooth regularizers which are common in modern machine learning pipelines.

{\em Comparison of Computation.}
~\cref{algo:1} entails calculating and inverting the full Hessian $H_f$ or $H_\ell$ and storing it (memory cost $O(d^2)$ and computation cost $O(d^3)$). It also entails storing the gradient of each point evaluated on the full data model $\estt$, as well as the current model $\tilde{\theta}_{n, -U}(\lambda)$. In the setting where $\pi$ is not smooth, $\bar{\theta}_{n,-U}(\lambda)$ must be stored. During runtime,~\cref{algo:1} requires matrix-vector multiplication and vector addition (as well as proximal step in the non-smooth setting).
For unlearning in settings where deletion requests come in a online manner, our technique is computationally more efficient. This is because removal mechanism~\eqref{eq:s} requires computing and inverting a different Hessian that depends on the user requesting the deletion. Therefore, outside simple settings, complying with such requests involves a computational cost of $O(md^3)$ to remove $m$ datapoints.

 {\em Comparison of unlearning, generalization and deletion capacity.} As summarized above, the generalization, unlearning and deletion capacity results for our removal mechanism are essentially equivalent to the unlearning, generalization, and deletion capacity results of~\cite{sekhari2021remember}.

\begin{remark}[Extending~\citet{sekhari2021remember} to non-smooth regularizers] Following from the equivalence we show between the batch and online setting in Appendix~\ref{app:batch_eq_stream}, we can extend our use of the proximal operator to~\eqref{eq:s} which would extend the results of~\citet{sekhari2021remember} to non-smooth regularizers. Similar unlearning, deletion capacity and generalization results are obtained. We provide details in~\cref{app:ext}.
\end{remark}
\section{Experiments}
In this section we will refer to retraining from scratch as \textbf{RT}, the Algorithm~\eqref{eq:s} as \textbf{TA} and our \cref{algo:1} as \textbf{IJ}.
We empirically demonstrate the benefits  of our algorithm over both \textbf{RT} and \textbf{TA} in three different settings: (i) smooth regularizers where we train a logistic regression model with an $\ell_2$ penalty to predict between the digit 3 and 8 from the MNIST dataset~\cite{lecun1998mnist}, (ii) non-smooth regularizers where we train a logistic regression model with an $\ell_1$ penalty to predict whether an individual was prescribed a Warfarin dosage of $> 30$ mg/week from a dataset released by the International Warfarin
Pharmacogenetics Consortium~\cite{international2009estimation}, and (iii) non-convex training where we apply a logistic regression model with an $\ell_2$ penalty to predict street digits signs 3 and 8 from SVHN~\cite{netzer2011reading} on representations extracted from a differentially private feature extractor with $\epsilon = 0.1$ (similar to the setup of~\citet{guo2020certified}). For all algorithms, we tune $\lambda$ over the set $\{10^{-3}, 10^{-4}, 10^{-5}, 10^{-6}\}$. In the Appendix~\ref{app:datasets}, we provide further details about each dataset and the code to produce our models is attached separately.

 We present results in the main paper for $\lambda = 1^{-3}$ and provide other results in Appendix~\ref{app:exps}. All models are trained on a single NVIDIA Tesla T4 GPU and 16 2.10GHz Xeon(R) Silver 4110 CPU cores. We focus our evaluation on total runtime in seconds and test set accuracy as the number of delete requests increases. Given that the current window for complying with delete requests for GDPR is one month, the runtime savings on our plots occur at month X where X is provided by the y-axis. We note that the "Right to Be Forgotten" is a much broader right and our experimental findings demonstrate that this can be satisfied much more efficiently for convex problems.  For all results, we provide the average over three different runs and provide standard error bars.

\begin{figure}[t!]
\centering
\begin{subfigure}{.4\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/MNIST_runtime.png}
  \label{fig:mnist_runtime}
\end{subfigure}%
\begin{subfigure}{.6\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/mnist_test_acc_final.png}
  \label{fig:mnist_test_acc}
\end{subfigure}
\caption{\textbf{IJ} vs. \textbf{RT} \& \textbf{TA} for smooth regularizers. Comparing both the runtime and test accuracy of the unlearned models in our $\ell_2$ logistic regression setup for predicting 3's and 8's on MNIST. For GDPR, the y-axis of the runtime graph denotes the runtime at month X under the current one month delete request window.}
\label{fig:mnist}
\end{figure}

\paragraph{Logistic Regression with Smooth Regularizers}

In this experiment we simulate an online data deletion setup using the MNIST dataset. For simplicity, we restrict the problem to binary classification by predicting between 3s and 8s. This is the same setup used by~\citet{guo2020certified} to evaluate their approximate unlearning algorithm.
We flatten the MNIST image into a 1-D vector and train an $\ell_2$ regularized logistic regression model for each algorithm. We evaluate the impact of a deleting a sequence of 5000 datapoints (approximately 40\% of the total dataset) both randomly and in an adaptively chosen manner. In these experiments we consider noise at $c=0.01$.

  On average, \textbf{IJ} was 2611x faster than \textbf{RT} and 2045x faster than \textbf{TA} (Figure~\ref{fig:mnist}). We find that this improvement in runtime comes at very minimal cost to the test performance of the model returned by our algorithm compared to the test performance of \textbf{TA} (Figure~\ref{fig:mnist}). Furthermore, we observe that these results also hold when the delete requests are chosen adaptively (Figure~\ref{fig:mnist}). As discussed previously, the main savings in computation for our algorithm comes from only inverting the hessian once while \textbf{TA} requires a hessian inversion for every delete request.

\sub

\begin{figure}[h]
\centering
\begin{subfigure}{.25\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/Prox_runtime.png}
  \label{fig:prox_runtime}
\end{subfigure}%
\quad\quad\hspace{10pt}
\begin{subfigure}{.25\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/prox_test_acc.png}
  \label{fig:prox_test_acc}
\end{subfigure}
\caption{\textbf{IJ} vs. \textbf{RT} for non-smooth regularizers. Comparing both the runtime and test accuracy of the unlearned models in our $\ell_1$ logistic regression setup for predicting warfarin dosage. For GDPR, the y-axis of the runtime graph denotes the runtime at month X under the current one month delete request window.}
\label{fig:prox}
\vspace{-0.7mm}
\end{figure}

\paragraph{Logistic Regression with Non-Smooth Regularizers}

This experiment showcases the performance of our proximal Newton algorithm on a problem with a non-smooth regularizer. We focus on predicting warfarin dosing from patient demographic and physiological data because it a practical setting where $\ell_1$ regularization has been demonstrated to be preferred~\cite{sharabiani2015revisiting}. Given that \textbf{TA} does not naturally support non-smooth regularizers we only compare \textbf{IJ} to \textbf{RT}. In these experiments we consider a logistic regression objective, $\ell_1$ regularizer, and noise level of $c=0.01$.
 On average, \textbf{IJ} was 30x faster than \textbf{RT} (Figure~\ref{fig:prox}). This improvement in runtime only comes at small cost to the test accuracy of the model returned by our algorithm compared to the test performance of \textbf{TA} (Figure~\ref{fig:prox}).

 \paragraph{Non-Convex: Logistic Regression with Differentially Private Feature Extractor}
 \begin{figure}[h]
\centering
\begin{subfigure}{.3\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/SVHN_runtime.png}
  \label{fig:sub1}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
  \centering
  \includegraphics[width=\linewidth]{figures/SVHN_test_acc_final.png}
  \label{fig:sub2}
\end{subfigure}
\caption{\textbf{IJ} vs. \textbf{TA} and \textbf{RT} for non-convex training. Comparing both the runtime and test accuracy of the unlearned models in our DP feature extractor + $\ell_2$ logistic regression setup for predicting digits in photos of street signs from SVHN. For GDPR, the y-axis of the runtime graph denotes the runtime at month X under the current one month delete request window.}
\label{fig:svhn}
\vspace{-0.5mm}
\end{figure}
 We demonstrate the ability to use our unlearning algorithm in non-convex settings. Similar to~\citet{guo2020certified} we train a differentially private feature extractor with $\epsilon = 0.1$ on street digit signs from SVHN to extract representations which a logistic regression model can be applied on top of.  Similar to previous experiments, we pick digits 3 and 8 for simplicity and  observe significant speedups using \textbf{IJ}. On average, \textbf{IJ} was 15036x faster than \textbf{RT} and 17x faster than \textbf{TA} and these speedups come at a marginal cost to the test accuracy of our algorithm even as the number of delete requests increase (Figure~\ref{fig:svhn}).

\section{Unlearning hyperparameter-tuned models}
\label{sec:failure_mode}
One of the most common techniques for hyperparameter tuning is {\em cross-validation}. Here datapoints are used to validate and select models using the following cross-validation error objective
\begin{talign}\label{eq:cverror}
\text{CV}(\lambda) = \frac{1}{n}\sum_{i=1}^n \ell(z_i, \hat{\theta}_{n,-i}(\lambda)).
\end{talign}
Specifically, the model selection pipeline oftentimes entails selecting $\lambda \in \Lambda$ that minimizes the CV error~\eqref{eq:cverror}. Given each datapoint is used to select models, one might hope  it is possible to unlearn models using~\cref{algo:1} when CV is used to select the model. However, as the following proposition illustrates, the $(\epsilon,\delta)$-unlearning guarantees of Theorem~\ref{thm:1} no longer apply when CV has taken place.

\begin{proposition}\label{prop:1} Suppose cross-validation is used to select $\lambda \in \Lambda$ and the empirical risk minimizer $\estt$ is returned. Consider a delete request by user $i$ and the model returned by unlearning procedure~\eqref{eq:s} or~\eqref{algo:1}, which we denote $\tilde{\theta}_{n,-i}(\lambda)$. Then it is possible $\|\tilde{\theta}_{n,-i}(\lambda) - \hat{\theta}_{n,-i}(\lambda')\| = o(1/n)$ where $\hat{\theta}_{n,-i}(\lambda')$ is the model selected after deleting user $i$ and performing cross-validation again to select $\lambda' \in \Lambda$ before returning the empricial risk minizer.

\end{proposition}
{\em Proof of~\cref{prop:1}.}
Suppose $\ell(z,\theta) = \frac{1}{2}(z - \theta)^2$, $\pi(\theta) = \theta^2$ and $\Lambda = \{0, \infty\}$. Note that $\hat{\theta}_n(\lambda) = \frac{1}{1+\lambda} \bar{z}$ where $\bar{z} = \frac{1}{n} \sum_{i=1}^n z_i$ is the sample average. Consider a dataset consisting of $n-1$ points (group A) with value $-\frac{1}{n}$ and a remaining point (group B) with value $n$ with $n\geq2$, and suppose the user in group B requests to delete their data.
Performing cross-validation on this dataset will entail computing two kinds of sample averages, one where we have deleted a point from group $A$, $\bar{z}_{-i_A} = \frac{1}{n-1}(-\frac{n-2}{n} + n)$, and one where we have deleted the point from group $B$, $\bar{z}_{-i_B} =-\frac{1}{n}$. Recall the CV error
\begin{talign*}
    \text{CV}(\lambda) = \frac{1}{2n} \sum_{i=1}^n (z_i - \hat{\theta}_{n,-i}(\lambda))^2 = \frac{n-1}{2n}(\frac{1}{1+\lambda}\frac{1}{n-1}(n-\frac{n-2}{n} )-\frac{1}{n})^2 + \frac{1}{2n}(n + \frac{1}{1+\lambda}\frac{1}{n})^2
\end{talign*}
When minimized over the set $\Lambda = \{0,\infty\}$, $\lambda = \infty$ is optimal for any $n\geq2$. This results in estimator $\hat{\theta}_{n}(\lambda) =\hat{\theta}_{n}(\infty) = 0$. The leave-one-out approximation is the same for estimators~\eqref{algo:1} and~\eqref{eq:s}, given $\nabla_{\theta}^2 F(z,\theta,\lambda)^{-1} = \frac{1}{1 + \lambda}$. Subsequently, $\tilde{\theta}_{n,-i}(\lambda) = \hat{\theta}_{n}(\lambda) + \frac{1}{n}\frac{1}{1+\lambda}( \hat{\theta}_{n}(\lambda) - z_i )$ results in the approximation $\tilde{\theta}_{n,-i}(\infty) = 0$. On the other hand, having deleted the datapoint from group $B$, we have a new sample mean $\bar{z} = -\frac{1}{n}$ and CV error, given by
\begin{talign*}
\text{CV}(\lambda) = \frac{1}{2n} \sum_{i=1}^n (z_i - \hat{\theta}_{n,-i}(\lambda))^2 = \frac{1}{2n}(-\frac{1}{n} + \frac{1}{1+\lambda} \frac{1}{n})^2
\end{talign*}
is minimized by $\lambda = 0$. This results in leave-one-out minimizer $\hat{\theta}_{n,-i}(0) = -\frac{1}{n}$. $\qedsymbol$

An implication of~\cref{prop:1} is that~\cref{algo:1} as well as the algorithms proposed by~\cite{sekhari2021remember,guo2020certified}  do not unlearn models when cross-validation is used to selected hyperparameters.  This is because the noise term $\sigma \propto O(m^2/n^2)$ is no longer sufficient to guarantee datapoint $i$ is unlearned.
This means that organizations which train their models using cross-validation and use approximate unlearning algorithms could still be leaking information about the data which they delete.

\section{Discussion}

A main contribution of our study is the development of an efficient online data deletion algorithm for non-smooth problems. The only previous work proposing a low-memory online algorithm is~\citet{guo2020certified}. However,~\citet{marchant2021hard} show that this algorithm is susceptible to poisoning attacks rendering it highly inefficient.
While exact unlearning algorithms such as SISA and retraining naturally work in an online setting, our work is the first to make this work for approximate unlearning algorithms. Further development of data deletion algorithms should focus more on the online setting to ensure practical use.

The infinitesimal jacknife has been previously been used to perform cross-validation. We note deep connections between the approximate cross-validation algorithms and approximate machine unlearning algorithms. The algorithm developed by~\cite{sekhari2021remember}, for example, can be viewed as an analog of the approximate cross-validation algorithm proposed by~\cite{beirami2017optimal, rad2019scalable}. Additionally, the model selection error bounds provided in the approximate cross-validation literature for example in~\cite{wilson2020approximate} are very similar to the generalization guarantees proved in our work and~\cite{sekhari2021remember} where we are concerned with the error introduced by our approximation to the unlearning baseline.
 We believe further connections could be exploited to provide unlearning algorithms when hyperparameter tuning has taken place.

 In this work and in several others we consider a definition of data deletion that is parameterized by two values $\epsilon$ and $\delta$. As is the case with differential privacy, it is currently unclear what the impact of satisfying different levels of $\epsilon$ means practically. Developing auditing algorithms~\cite{thudi2021necessity} similar to those recently seen in the DP community~\cite{NEURIPS2020_fc4ddc15, nasr2021adversary} can help provide more transparency on the meaning of the $(\epsilon, \delta)$-unlearning guarantee.

Finally, we return to the broader question we posed at the beginning: \textit{what does it mean to delete data from a  machine learning pipeline?} Most existing work focuses on data deletion in the model training process. Yet, the machine learning and data analysis pipeline is much broader than just model training. As evidenced in Section~\ref{sec:failure_mode}, the lack of research on data deletion in model selection could potentially result in information being leaked from previously proposed unlearning algorithms. Given this result, it is likely that all unlearning algorithms ({\em }both exact and inexact}) still leak information about deleted data in other stages of the machine learning pipeline such as exploratory data analysis and feature selection. We encourage the community to explore definitions of data deletion which encompass the entire machine learning pipeline.

\clearpage

\section*{\refname}}{}{}{}

\begin{document}

In this general comment, we would like to first thank the reviewers for taking the time to review the submission and the provided comments. Next, we would like to reiterate the contributions of this submission.

 Our work is in keeping with a line of research on different ways the infinitesimal jackknife (also called the influence function) can be used for issues of societal concern, including robustness, explainability, and fairness. To our knowledge, we are the first to introduce it in the context of privacy relating to data removal. For all prior works including ours, the IJ can be applied to non-convex settings but guarantees are virtually non-existent. Providing guarantees in a general non-convex setting would be a significant step forward for all these proposed applications but is outside the scope of our work. Our work notably provides guarantees for a broad range of models generated from both smooth and non-smooth convex ERM problems (e.g. logistic regression, hinge loss, cross entropy loss etc.) as well as specialized non-convex models (see line 144) as was done in previous works. In light of the feedback given, we elaborate on our three contributions:
\begin{itemize}
\item  {\bf An online algorithm:} while the current form of GDPR requires deletion after a month to allow companies time to comply, showing it can be done efficiently and quickly could incentivize a more narrow window for compliance. This, in turn, could mitigate the harm done from potential privacy attacks even further than current legislation. Notably, even in the batch setting our algorithm will be more efficient than all low-memory unlearning algorithms in the literature so far after only two months of complying with requests since it requires inverting a Hessian once and storing it while other methods will require inverting a Hessian monthly. This, we believe, would  more than likely make the IJ approximation the standard technique used for compliance with data removal requests (at least when compared with the presently introduced techniques).
	\item {\bf Application to non-smooth models:} we provide theoretical guarantees of data deletion and experimental result for models with non-smooth regularizers such as the $\ell_1$ penalty. To the best of our knowledge, no current approximate unlearning algorithm and very few memory intensive unlearning algorithms can be applied in this popular setting. Our technique for handling non-smoothness can be applied to the previously introduced Taylor approximation (TA) and we provide theoretical guarantees for this.
	\item { \bf Counterexample:} Hyper-parameter tuning is common in most model generation pipelines. Our work is the first to point out that unlearning via all techniques presented so far does not work when this procedure takes place. While this is the last part of the paper, we feel this contribution alone is a noteworthy one for the community as it could likely prevent unintended harm.
\end{itemize}
We will make all these contributions clearer in the revision. Finally, there were additional concerns regarding motivation of our algorithm, clarity about why the proximal IJ works, and experimental details. We give more detailed responses to each reviewers concerns below.

\section*{Response to Reviewer 1}

\paragraph{While being interesting, I feel jacknife, proximal updates, etc are all well established theoretical tools and there is not much that fundamentally new:}
We appreciate that the reviewer found our application of the Jacknife to be interesting. While these tools are well established in the theory, our work is the first to demonstrate the applicability of the Jacknife to privacy concerns such as unlearning. More broadly, our work is in keeping with a line of research on different ways the IJ can be used for issues of societal concern. For example, {\em notable}\footnote{both papers won best paper awards.} applications of the IJ (aka influence function) have focused on robustness~\cite{giordano2019swiss} and explainability~\cite{koh2017understanding} concerns, and more recently, the jackknife was introduced as a way to ensure fairness~\cite{black2021leave}.

\paragraph{Using the wrong definitions:} In our experiments, we report ERM. We thank the reviewer for pointing out this mismatch. Our algorithm satisfies the definition of unlearning from~\cite{sekhari2021remember} which we also prove in the Appendix. We have updated the paper that we focus on this definition so that our proofs and experiments are aligned.

\paragraph{Suppose we restrict ourselves to generalized linear models...What are the benefits of your algorithm in that case:} In this situation there will be little theoretical and practical difference between the Taylor approximation and the IJ approximation for unlearning datapoints. Our algorithm, however, will be beneficial for non-smooth GLM problems, which previous unlearning algorithms are not designed to handle. We demonstrate the theoretical benefits in Theorem 1 and the empirical runtime benefits in Figure 2.

\paragraph{Do you have any suggessions from mitigating the reported issue in Section 5 for hyperparameter-tuned models ?} We are currently working on this. We think it might be possible to augment the memory requirements of our unlearning algorithm or add more noise to the estimator to preserve the unlearning guarantees for specific types of hyperparameter tuning, but we are still in the beginning stages of proving such adjustments could work.

\section{Reviewer 2}

\subsection*{Questions about why our algorithm works}

\paragraph{How can the proposed method be effective in non-smooth regularized models?}
Our proposed method is effective on non-smooth regularized models because we use the proximal operator, which is commonly used to optimize non-smooth ERM problems. We rely on software packages the glmnet and QUIC which provide efficient computation of the proximal operator for $\ell_1$ penalties to show our method is very efficient. Notably, the proximal operator effectively optimizes the regularizer within a small domain close to the current iterate, which can be done efficiently for simple penalties. This is what allows us to compensate for the lack of second derivative for the non-smooth penalty which hopefully explains why it works in non-smooth regularized models.

Our algorithm does indeed work in this setting and we apologize for the extent to which the reasons why were not made clear. Our paper provides both theoretical guarantees  and experimental evidence that our method is effective for non-smooth regularized in Theorems 1 and 2 and Figure 2 respectively. Our work is the first to our knowledge to develop an algorithm which supports low memory unlearning of non-smooth regularized models. Even many of the memory intensive unlearning algorithms require smoothness~\cite{neel2021descent}. Furthermore, our work is able to extend related work such as~\cite{sekhari2021remember} to support non-smooth regularized models (Remark 1).

\paragraph{The proposed method only inverts the Hessian for one time, but how can it ensure the total error is tolerable:}
Our error guarantee is statistically the same as other methods. This is due to the fact that the leave-one-out Hessian and full Hessian are sufficiently close (in particular $O(1/n)$ close). This, amount of closeness is enough to ensure that the model generated from our unlearning algorithm and the exactly unlearned model are $O(1/n^2)$ close. Adding noise on the order of $O(1/n^2)$ is what ensures the unlearning guarantee. The same kind of approximate unlearning argument is what is used  in previous works.  The statement of our unlearning guarantee for our IJ unlearning algorithm is in Theorem 1 and its proof is contained in Appendix A.3. We will provide additional text in the revision to make sure the structure of this argument is clear.

\subsection*{Comments about implementation}
\paragraph{Supplementary lacks the comparison of runtime in different hyperparameter settings:}
We did not originally include the runtime metrics for the different hyperparameter settings as they did not affect the relative difference in runtimes. For completeness, we have included them in an updated version of the Appendix (please check our current revision) to confirm that the runtime remains the same across hyperparameters.

\paragraph{The candidates of the hyperparameter $\lambda$ may be $\{10^{-3}, 10^{-4}, 10^{-5}, 10^{-6}\}$ rather than $\{1^{-3}, 1^{-4}, 1^{-5}, 1^{-6}\}$:}
Thank you for pointing out this mistake; we have now fixed it in the main text.

\section{Reviewer 3}
\subsection*{Comments on motivation of unlearning in the convex setting}
\paragraph{The authors use data regulations for industrial sized models as motivation of the paper. However, most industrial models of the scale are deep neural networks. The study of only linear models seem ill-suited:}
We appreciate the reviewers concern for the applicabilty of our method to industrial sized models, specifically, neural networks. First, we point the author to several examples of industrial applications where convex (smooth and non-smooth) ERM is used. In healthcare, logistic regression models are used across the entire field for risk estimation~\cite{rudin2018optimized}. In consumer apps such as Airbnb, convex ERM is used for optimizing pricing~\cite{ye2018customized}. Our algorithm is applicable for a broad range of models generated from convex optimization problems, not just linear models.
As a practical matter the IJ can be applied to neural networks, without guarantees of unlearning except in some special settings. We remark on such a setting (line 144 in our paper) where we remark it can be applied directly to non-convex models such as neural networks. The latter case was studied in~\cite{guo2020certified} who also provided similar unlearning guarantees for their algorithm in this non-convex example.

\paragraph{Could you give a concrete example where online data deletion is necessary?} In healthcare, online data deletion is not only desireable but a requirement of some studies. For example, the UK Biobank (which is one of the largest longitudinal health data studies across over 500 000 individuals in the UK) requires data deletion as soon as a participant requests for their data to be removed~\cite{ginart2019making}. In this setting, our algorithm (more broadly online data deletion) is necessary to comply with the study regulations. Importantly, many of the models trained using UK Biobank data are {\em not} neural networks and fall within the scope of our unlearning guarantees.

We will provide these examples and more of where our algorithm can be readily applied in the revision.
\subsection*{Comments on the usefulness of the online setting} While we believe we address several of these concerns in our summary response, we will answer each question specifically here.
\paragraph{The authors argue that the online setting is more practical. However, taking GDPR for example, the companies are obligated to delete user data only within a month instead of immediately. As a result, I find the batched setting to be more realistic where retraining could also be competitive:}

We appreciate the reviewers comment on the need for an online data deletion algorithm since the current format of GDPR allows for delete requests to be performed one month after. We note that  even in the batch setting, our algorithm is less computationally intensive than previous methods after two months of complying with requests since it just needs to invert and store the Hessian once instead of every month, and therefore might {\em still} be preferable/useful to companies complying with monthly requests.
Also, while the current form of GDPR legislation allows quite a bit of time for companies to comply, we believe that showing a tool can provide the same empirical performance and theoretical guarantees with immediate deletion is beneficial toward encouraging companies to complying with GDPR requests more swiftly (and might encourage lawmakers to necessitate faster compliance). When individuals request to delete their data, it is sometimes because they are concerned about the risk of potential harm if their data remains available; this risk is compounded
the longer it takes for the data to be deleted. By showing it can be done quickly, companies may be encouraged to act more expeditiously and less harm might occur.

\paragraph{As a result of the above comment, is it fair to compare IJ against RT and TA in the online setting? I believe it is more reasonable compare against the methods for removing an entire batch.}

We prove in Appendix A.2 that the online setting of the IJ can be easily extended to a batch version. In the batch setting our method is still computationally more efficient than TA at the point where there is more than one batch request. After two months of complying with GDPR, our method will be more efficient than other low memory methods. Indeed, the relative efficiency of our method compounds the more batch delete requests there are. Thus, making our algorithm ideal for, but not restricted to, a streaming setting (this is why we chose to highlight this setting in our experiments). Furthermore, TA was not originally able to support non-smooth regularizers. Our use of the proximal operator and an equivalence we show in Remark 1 are what enables TA to now support non-smooth regularizers and perform these experiments.

\subsection*{More intuition}
\paragraph{The proposed Algorithm 1 would benefit from more detailed description and intuition:}

We apologize for the lack of intuition given and will provide the following intuition in the main text:
In equation 5a (e.g. the smooth regularizer variant), this algorithm is an IJ estimate of the leave-one-out model with some additional noise. The amount of noise added to this approximation (determined by $c$) is dictated by the unlearning guarantees targeted by the company and properties of the function.  The variant designed for the unsmoothed version simply introduces the proximal function to the IJ estimate to handle the non-existence of the Hessian of the regularizer.

\bibliographystyle{abbrv}