As data privacy regulations grant users the "right to be forgotten," machine learning faces a unique technical challenge: deleting a user's data from a database does not erase its lingering influence on a model's weights. Because neural networks implicitly memorize training patterns, completely removing a data point's impact traditionally requires retraining the model from scratch. However, full retraining is computationally prohibitive for large-scale applications. A comprehensive overview of this dilemma and its emerging paradigms is provided by Jie Xu et al. in Machine Unlearning: Solutions and Challenges.
To bypass full retraining, a prominent research direction leverages second-order optimization techniques. By analyzing the local curvature of the loss landscape, these methods calculate a precise parameter update that shifts the model into a state approximating what it would have reached had the forgotten data never existed (Chuan Guo et al. in Certified Data Removal from Machine Learning Models; Ayush Sekhari et al. in Remember What You Want to Forget: Algorithms for Machine Unlearning).
Deforming the Loss Landscape
To understand why second-order unlearning works, we can visualize the geometry of a model's loss landscape. Suppose a model has optimal parameters $\theta^*$ trained on a full dataset $D$. At this point, the model sits at the global minimum of the full loss function $L_D(\theta)$, meaning its gradient is zero:
$$\nabla L_D(\theta^*) = 0$$
When a subset of data $S$ needs to be forgotten, the target objective function shifts to the loss of the remaining data, $L_{D \setminus S}(\theta) = L_D(\theta) - L_S(\theta)$. Because we have subtracted the loss contribution of $S$, the original minimum $\theta^*$ is no longer at the bottom of the valley. If we evaluate the gradient of this new loss function at the old parameters $\theta^*$, we find:
$$\nabla L_{D \setminus S}(\theta^*) = \nabla L_D(\theta^*) - \nabla L_S(\theta^*) = -\nabla L_S(\theta^*)$$
This reveals a elegant geometric truth: the force pulling the model toward the new retrained minimum is exactly the negative gradient of the data to be forgotten.
The Geometry of a Newton Step
A naive approach would be to take a standard first-order gradient step in the direction of $-\nabla L_S(\theta^*)$. However, as Pang Wei Koh et al. demonstrate in On the Accuracy of Influence Functions for Measuring Group Effects, first-order influence functions often fail to track the true retraining path because they ignore how the loss surface curves. If the valley is narrow in some parameter dimensions and wide in others, first-order steps can easily overshoot or stall.
To account for this curvature, we can form a first-order Taylor expansion of the optimality condition around $\theta^*$. This introduces the Hessian matrix $H$—the matrix of second-order derivatives that captures the local topography of the loss landscape. Solving this expansion yields the single-step Newton update:
$$\Delta \theta \approx H^{-1} \nabla L_S(\theta^*)$$
By scaling the gradient of the forgotten data by the inverse Hessian, the model performs a curvature-aware adjustment. This mechanism allows the parameters to directly "jump" to the new optimal state, bypassing iterative gradient descent (Yi Liu et al. in The Right to be Forgotten in Federated Learning: An Efficient Realization with Rapid Retraining; Stanley Wei et al. in Provable unlearning in topic modeling and downstream tasks). The inverse Hessian acts as a preconditioner, warping the parameter space so that the update is damped along sharp ridges and accelerated along flat valleys (Yushun Dong et al. in IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks; Chao Pan et al. in Unlearning Graph Classifiers with Limited Data Resources).
Certified Unlearning and Privacy
The primary advantage of this second-order approximation is that it enables certified unlearning. By injecting a calibrated amount of noise during initial training or during the unlearning step, the authors can mathematically guarantee that the approximate update yields a parameter distribution statistically indistinguishable from a model retrained entirely from scratch (Chuan Guo et al. in Certified Data Removal from Machine Learning Models).
This rigorous privacy framework has been successfully adapted to graph-structured data, allowing for the rapid removal of nodes, edges, or features in Graph Neural Networks (Chao Pan et al. in Certified Graph Unlearning; Eli Chien et al. in Efficient Model Updates for Approximate Unlearning of Graph-Structured Data). Furthermore, Lu Yi et al. demonstrate in Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier that these second-order updates can scale to billion-edge graphs while maintaining strict privacy bounds. Beyond privacy, the same second-order mathematical framework can be leveraged to ensure that data removal does not inadvertently break algorithmic fairness constraints (Alex Oesterling et al. in Fair Machine Unlearning: Data Removal while Mitigating Disparities).
Overcoming Computational Bottlenecks
Despite its elegance, computing and inverting the Hessian matrix presents a massive computational bottleneck, scaling cubically ($O(d^3)$) with the number of parameters $d$. To make second-order unlearning practical for deep networks, several optimization strategies have emerged:
- Localization: Instead of updating the entire model, updates can be isolated to a small subset of parameters. For instance, Ronak Mehta et al. in Deep Unlearning via Randomized Conditionally Independent Hessians identify a "Markov Blanket" of parameters relevant to the deleted data, restricting the Hessian calculation to this subset and drastically lowering the computational cost. Similarly, Wenhao Yang et al. in Factor Decorrelation Enhanced Data Removal from Deep Predictive Models use localized parameter adjustments to achieve near-retraining accuracy efficiently.
- Dimension Reduction: Zihao Cao et al. in Machine Unlearning Method Based On Projection Residual shift the focus to feature dimensions rather than the total dataset size, reducing the complexity of the second-order update to $O(k^2 d)$.
- Quasi-Newton Approximations: In distributed environments like federated learning, where a central server cannot access raw data or client gradients directly, computing the exact Hessian is impossible. To circumvent this, Ziyao Liu et al. in Privacy-Preserving Federated Unlearning with Certified Client Removal employ quasi-Newton methods like L-BFGS to approximate the trajectory of the remaining clients' updates using only historical second-order information.
- Source-Free Estimation: What if the remaining training data is completely unavailable due to privacy or storage constraints? Sk Miraj Ahmed et al. show in Towards Source-Free Machine Unlearning that it is possible to estimate the Hessian of the remaining data using only the samples targeted for deletion. However, as noted by Alexandra Peste et al. in SSSE: Efficiently Erasing Samples from Trained Machine Learning Models, calibrating these approximate steps against the true loss landscape can still introduce a partial retraining bottleneck that requires careful scaling.
From Single-Step to Iterative Updates
The single-step Newton update relies on the assumption that the loss landscape is locally quadratic. While this holds for convex objectives, highly non-linear architectures like Large Language Models (LLMs) break this assumption, causing single-step influence functions to suffer from severe approximation errors.
To unlock second-order unlearning for these massive models, Jinghan Jia et al. in SOUL: Unlocking the Power of Second-Order Optimization for LLM Unlearning propose the iterative application of second-order updates. By taking multiple curvature-aware steps, their framework compensates for landscape non-linearities, successfully erasing targeted knowledge while preserving the model's general utility and reasoning capabilities far better than traditional first-order fine-tuning.
Key Foundational Work
Certified Data Removal from Machine Learning Models (2020) — contributed 1 concept elements to this direction.
On the Accuracy of Influence Functions for Measuring Group Effects (2019) — contributed 1 concept elements to this direction.