A straightforward way to comply with the requirement of exact unlearning is to recompute (or retrain, in context of machine learning). This, however, is often computationally expensive, and hence the goal is to design efficient unlearning algorithms - herein and afterwards, we use efficient, in the context of unlearning, to mean that the runtime is smaller than recompute time.
Most of the prior work focuses on specific structured problems (eg: linear regression, clustering etc.) and the proposed unlearning algorithms carefully leverage this structure for efficiency - see a discussion of useful algorithmic principles like linearity, modularity etc. which enable efficient unlearning, in [1]}.
In this work, we consider a larger class of problems: smooth convex empirical risk minimization (ERM), which includes many machine learning problems, eg: linear and logistic regression, as special cases (see sec:setup for definitions).
This class of smooth convex ERM is sufficiently rich and arguably lacks structure useful in prior works.
Gradient-based optimization is a key algorithmic technique used for smooth convex ERM (and most of machine learning and even beyond).
Unlike prior works where the (learning) algorithms for the specific problems (like linear regression) are tailored enough to the problem to be amenable to efficient unlearning, an optimization method hardly has any such useful structure.
In particular, the sequential nature of gradient descent makes it challenging to design non-trivial unlearning algorithms, at least those which satisfy an exact unlearning criterion.
To elaborate, if the point to be deleted participates in some iteration, then the subsequent steps are dependent on the to-be-deleted point, and there is no known way but to redo the computations.
It is natural to then ask whether we can design unlearning algorithms with non-trivial guarantees for this class of smooth convex ERM problems.
