Second-Order Approximations for Machine Unlearning

25 concepts22 papers1 proposal

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:

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_newton_based_unlearning_922cdac8,
  title = {Newton-based unlearning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/newton-based-unlearning/rdr_922cdac8b4144e77b63916b6f3df5932},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_newton_based_unlearning_922cdac8_v1,
  title = {Newton-based unlearning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/newton-based-unlearning/rdr_922cdac8b4144e77b63916b6f3df5932/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake