Certified Minimax Unlearning with Generalization Rates and Deletion
  Capacity
Jiaqi Liu Jian Lou Zhan Qin Kui Ren
We study the problem of $(\epsilon,\delta)$-certified machine unlearning for
minimax models. Most of the existing works focus on unlearning from standard
statistical learning models that have a single variable and their unlearning
steps hinge on the direct Hessian-based conventional Newton update. We develop
a new $(\epsilon,\delta)$-certified machine unlearning algorithm for minimax
models. It proposes a minimax unlearning step consisting of a
total-Hessian-based complete Newton update and the Gaussian mechanism borrowed
from differential privacy. To obtain the unlearning certification, our method
injects calibrated Gaussian noises by carefully analyzing the "sensitivity" of
the minimax unlearning step (i.e., the closeness between the minimax unlearning
variables and the retraining-from-scratch variables). We derive the
generalization rates in terms of population strong and weak primal-dual risk
for three different cases of loss functions, i.e.,
(strongly-)convex-(strongly-)concave losses. We also provide the deletion
capacity to guarantee that a desired population risk can be maintained as long
as the number of deleted samples does not exceed the derived amount. With
training samples $n$ and model dimension $d$, it yields the order $\mathcal
O(n/d^{1/4})$, which shows a strict gap over the baseline method of
differentially private minimax learning that has $\mathcal O(n/d^{1/2})$. In
addition, our rates of generalization and deletion capacity match the
state-of-the-art rates derived previously for standard statistical learning
models.