{"id":"arxiv/2607.20192","url":"https://arxiv.org/abs/2607.20192","tags":["cs.LG","math.OC"],"score":0,"title":"On Optimization Complexity of Second-Order Certified Unlearning","domain":"cs.LG","source":"arxiv","authors":["Nikita Doikov","Anastasia Koloskova"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-22","reactions":{}}