Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates the optimization complexity of certified unlearning, focusing on the algorithmic challenges of removing memorized training data from models while maintaining optimization accuracy. By employing uniformly convex regularizers, the authors establish new bounds on the distance between initial and unlearned models, revealing that well-predicted data simplifies the optimization process. They introduce a second-order unlearning algorithm that leverages an anisotropic Gaussian mechanism, demonstrating superior global convergence and fast rates for certified unlearning in linear models, particularly for logistic and exponential regressions.
Removing training data doesn't have to mean sacrificing model performance—this new second-order unlearning algorithm proves it can be done efficiently.
We study machine unlearning: the removal of memorized training data from a trained model. Specifically, we investigate the algorithmic complexity of certified unlearning from an optimization perspective. We formalize the goal of an unlearning algorithm as simultaneously achieving certified unlearning and optimization accuracy. Utilizing the notion of uniformly convex regularizers, we prove new bounds on the distance between initial and unlearned models using a novel substitute for generalization error. Thus we theoretically demonstrate that if the removed data is well-predicted by the unlearned model, the corresponding optimization problem is simple. Furthermore, we develop a new second-order unlearning algorithm with an anisotropic Gaussian mechanism and state-of-the-art global convergence. We prove fast rates for our method in achieving certified unlearning for linear models with quasi-self-concordant losses. As a direct application, our theory covers unlearning for logistic and exponential regressions and shows a provable benefit of utilizing second-order information compared to first-order unlearning methods.