Descend or Rewind? Stochastic Gradient Descent Unlearning
Siqiao Mu, Diego Klabjan · 2025
Read Descend or Rewind? Stochastic Gradient Descent Unlearning by Siqiao Mu, Diego Klabjan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-15983.txt.
Introduction
Siqiao Mu and Diego Klabjan compare two stochastic methods for machine unlearning. Unlearning removes the effect of chosen training data from a model without full retraining. Descent-to-Delete and Rewind-to-Delete are full-batch methods with provable guarantees. The stochastic descent version is widely used as a fine-tuning baseline, despite lacking theory for nonconvex losses.
Viewing unlearning as a disturbed gradient system, they prove certified unlearning guarantees for both stochastic methods. The proof covers strongly convex, convex, and nonconvex losses. Descent gives tighter guarantees in the strongly convex case, while rewinding suits convex and nonconvex cases. Experiments confirm the strengths and limits of each approach.
Catalog record
| CREATOR | Siqiao Mu, Diego Klabjan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 99 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-15983
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Descend or Rewind? Stochastic Gradient Descent Unlearning Siqiao Mu, Diego Klabjan Abstract Machine unlearning algorithms aim to remove the impact of selected training data from a model without the computational expenses of retraining from scratch. Two such algorithms are “Descent-to-Delete” (D2D) and “Rewind-to-Delete” (R2D), full-batch gradient descent algorithms that are easy to implement and satisfy provable unlearning guarantees. In particular, the stochastic version of D2D is widely implemented as the “finetuning” unlearning baseline, despite lacking theoretical backing on nonconvex functions. In this work, we prove ( ϵ , δ ) (\epsilon,\delta) certified unlearning guarantees for stochastic R2D and D2D for strongly convex, convex, and nonconvex loss functions, by analyzing unlearning through the lens of disturbed or biased gradient systems, which may be contracting, semi-contracting, or expansive respectively. Our argument relies on optimally coupling the random behavior of the unlearning and retraining trajectories, resulting in a probabilistic sensitivity bound that can be combined with a novel relaxed Gaussian mechanism to achieve ( ϵ , δ ) (\epsilon,\delta) unlearning. We determine that D2D can yield tighter guarantees for strongly convex functions compared to R2D by relying on contraction to a unique global minimum. However, unlike D2D, R2D can achieve unlearning in the convex and nonconvex setting because it draws the unlearned model closer to the retrained model by reversing the accumulated disturbances. 1 Introduction Machine unlearning algorithms aim to remove the influence of specific data from a trained model without retraining from scratch. First introduced in [ 5 ] , machine unlearning has attracted significant attention in recent years, driven by heightened concerns over user privacy, data quality, and the energy expenditures of training massive deep learning models such as large language models (LLMs). Regulatory pressures also play a role: provisions in the European Union’s General Data Protection Regulation (GDPR), the California Consumer Privacy Act (CCPA), and the Canadian Consumer Privacy Protection Act (CPPA), protect a user’s ”right to be forgotten” by requiring that individuals be able to request removal of their personal information, whether stored in databases or retained by models [ 36 ] . Since it is impractical to retrain from scratch every time a user requests removal of their data, we desire cost-saving methods for ”forgetting” information from models after training. Generally, a machine unlearning algorithm aims to produce a model that appears as if it was trained without the unlearned data. This raises the question: how do we mathematically characterize the extent to which a model has truly unlearned? A rich line of work investigates “certified unlearning” algorithms, which are theoretically guaranteed to return model weights that are probabilistically indistinguishable to the weights obtained from retraining from scratch [ 19 , 17 ] . This is typically achieved by first bounding the distance between the weights after unlearning and after retraining, and then injecting appropriately calibrated Gaussian noise, a technique from differential privacy (DP) known as the Gaussian mechanism [ 14 ] . Such provable unlearning guarantees can be a powerful alternative to empirical metrics of unlearning, which can be unreliable or misleading [ 39 , 43 ] . However, many existing certified unlearning algorithms have limited practicality for modern deep learning settings. The vast majority are either second-order methods that require access to the Hessian (or Hessian vector products) [ 41 , 33 , 36 ] or first-order methods that require computing the full gradient [ 31 , 9 , 30 ] . Both settings are computationally intractable for large-scale models, which are typically trained with stochastic gradient descent (SGD) algorithms. While a couple recent works are able to show certified unlearning with stochastic gradients, they either prove a weaker version of certified unlearning [ 27 ] or only apply to convex functions [ 8 ] . To reflect realistic practices, we desire SGD-based certified unlearning algorithms for nonconvex functions. With this goal in mind, we revisit two existing first-order certified unlearning algorithms: Descent-to-Delete (D2D), designed for (strongly) convex loss functions, and Rewind-to-Delete (R2D), designed for nonconvex functions. Both algorithms perform learning via full-batch gradient descent (GD). Upon unlearning, both algorithms perform additional GD steps on the loss function of the retained dataset, but D2D “descends” from the original trained model, whereas R2D “rewinds” to an earlier saved checkpoint during training before performing the unlearning steps. Even though D2D is only theoretically supported for GD on strongly convex functions, its stochastic version is the basis for the “finetuning” unlearning baseline method, which is implemented in virtually all unlearning papers despite the fact that it underperforms on deep neural networks. The authors of [ 30 ] argue that rewinding, instead of descending, is a more appropriate baseline method for nonconvex settings, but their analysis does not apply to stochastic gradients. Therefore, establishing the unlearning properties of the stochastic versions of these two methods is an important open question. In this work, we prove that SGD versions of D2D and R2D do achieve (\epsilon,\delta) certified unlearning and we mathematically characterize their privacy-utility-complexity tradeoffs under looser assumptions than the original works. We first examine R2D with projected SGD (PSGD), for which we can achieve clean guarantees with minimal assumptions on strongly convex, convex, and nonconvex functions. On an unbounded domain, i.e. without projection, we can also prove certified unlearning for SGD R2D for strongly convex, convex, and nonconvex functions, assuming that the second moment of the noise is relatively bounded and the loss is finite at initialization. Finally, we prove certified unlearning for the SGD version of D2D on strongly convex functions. To analyze stochastic R2D, we leverage the contractive properties of gradient systems to carefully track the divergence between the training trajectory and the retraining trajectory. By characterizing SGD on the original loss function as biased or disturbed SGD on the loss function of the retained data samples, we can achieve noise bounds that reflect the contractive, semi-contractive, and expansive properties of strongly convex, convex, and nonconvex functions respectively. For stochastic D2D, we also treat it as biased SGD, but strongly convex functions have additional favorable properties allow the bias to be “folded into” the classic convergence analysis, as long as the proportion of unlearned data is small enough. This approach is completely different from the original proof in [ 31 ] , which considers a highly constrained setting where the function is both strongly convex and Lipschitz continuous. Our approach also relies on a key coupling argument; to achieve a minimal bound on the distance between unlearning and retraining, we can control the coupling between the two randomized SGD trajectories, yielding a probabilistic bound with respect to their joint distribution. In particular, with only a first or second moment bound, we can obtain a tail bound that can be combined with a novel relaxed Gaussian mechanism to yield (\epsilon,\delta) indistinguishability at a small cost to the dependence on \delta . This technique allows a more flexible analysis of SGD algorithms, for which worst-case sensitivity bounds, required by the classic Gaussian mechanism, are challenging to obtain without heavy-handed measures such as bounded gradient assumptions or clipping. Our work reveals deeper insights into the difference between “rewinding” and “descending.” On strongly convex functions, D2D yields tighter probabilistic bounds than R2D. However, D2D is not guaranteed to be more efficient than