From Adaptive Query Release to Machine Unlearning
Enayat Ullah Raman Arora
We formalize the problem of machine unlearning as design of efficient
unlearning algorithms corresponding to learning algorithms which perform a
selection of adaptive queries from structured query classes. We give efficient
unlearning algorithms for linear and prefix-sum query classes. As applications,
we show that unlearning in many problems, in particular, stochastic convex
optimization (SCO), can be reduced to the above, yielding improved guarantees
for the problem. In particular, for smooth Lipschitz losses and any $\rho>0$,
our results yield an unlearning algorithm with excess population risk of
$\tilde O\big(\frac{1}{\sqrt{n}}+\frac{\sqrt{d}}{n\rho}\big)$ with unlearning
query (gradient) complexity $\tilde O(\rho \cdot \text{Retraining
Complexity})$, where $d$ is the model dimensionality and $n$ is the initial
number of samples. For non-smooth Lipschitz losses, we give an unlearning
algorithm with excess population risk $\tilde
O\big(\frac{1}{\sqrt{n}}+\big(\frac{\sqrt{d}}{n\rho}\big)^{1/2}\big)$ with the
same unlearning query (gradient) complexity. Furthermore, in the special case
of Generalized Linear Models (GLMs), such as those in linear and logistic
regression, we get dimension-independent rates of $\tilde
O\big(\frac{1}{\sqrt{n}} +\frac{1}{(n\rho)^{2/3}}\big)$ and $\tilde
O\big(\frac{1}{\sqrt{n}} +\frac{1}{(n\rho)^{1/3}}\big)$ for smooth Lipschitz
and non-smooth Lipschitz losses respectively. Finally, we give generalizations
of the above from one unlearning request to \textit{dynamic} streams consisting
of insertions and deletions.