Certified Minimax Unlearning with Generalization Rates and Deletion Capacity
This addresses the problem of efficiently and provably removing data from trained minimax models for users in privacy-sensitive applications, representing an incremental advance over existing methods for standard models.
The paper tackles certified machine unlearning for minimax models by developing a new algorithm that uses a total-Hessian-based Newton update and Gaussian noise injection, achieving generalization rates for various loss functions and a deletion capacity of order O(n/d^{1/4}), which improves over a baseline of O(n/d^{1/2}).
We study the problem of $(ε,δ)$-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 $(ε,δ)$-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.