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.

机器遗忘问题中设计高效算法的形式化，包括线性和前缀和查询类的高效遗忘算法以及其在随机凸优化问题和广义线性模型中的应用，提供了不同情况下的遗忘风险和查询复杂度。