Certified Unlearning with Mild Regularization and non-Isotropic Data

The growing demand for privacy and increase in regulatory requirements have made the problem of honoring requests to be forgotten increasingly important. This motivates the problem of machine unlearning: simulating the effect of the removal of a given set of samples without triggering a full retrain. Existing methods for provable machine unlearning typically combine a fast but approximate update such as a single Newton step, with noise calibrated to an upper bound on its distance from the ideal unlearned model. However, even for the relatively simple case of logistic regression, existing certified unlearning algorithms either come at a severe cost to the model's predictive power, or often trigger a retrain even for small removal requests. We show that these limitations stem from a dependence on Newton step error bounds that require very strong regularization (resulting in a significant bias), and do not adapt to the geometry of the data (making the noise more detrimental to the model's predictions). We introduce UNCLE (Unlearning Certifiably via Local Estimates) – a new algorithm for certified unlearning, which overcomes both of these issues. We obtain these improvements by applying a novel method for bounding the distance of any initial estimate from the ideal unlearned model, using only local properties of the loss landscape.