Hessian-Free Online Certified Unlearning

Authors: Xinbao Qiao, Meng Zhang, Ming Tang, Ermin Wei
Primary area: alignment, fairness, safety, privacy, and societal considerations
Keywords: machine unlearning; certified data removal; privacy

Abstract:
Machine unlearning strives to uphold the data owners' right to be forgotten by enabling models to selectively forget specific data. 
Recent advances suggest pre-computing and storing statistics extracted from second-order information and implementing unlearning through Newton-style updates.
However, the Hessian matrix operations are extremely costly and previous works conduct unlearning for empirical risk minimizer with the convexity assumption, precluding their applicability to high-dimensional over-parameterized models and the nonconvergence condition.
In this paper, we propose an efficient Hessian-free unlearning approach. 
The key idea is to maintain a statistical vector for each training data, computed through affine stochastic recursion of the difference between the retrained and learned models. 
We prove that our proposed method outperforms the state-of-the-art methods in terms of the unlearning and generalization guarantees, the deletion capacity, and the time/storage complexity, under the same regularity conditions.
Through the strategy of recollecting statistics for removing data, we develop an online unlearning algorithm that achieves near-instantaneous data removal, as it requires only vector addition.
Experiments demonstrate that our proposed scheme surpasses existing results by orders of magnitude in terms of time/storage costs with millisecond-level unlearning execution, while also enhancing test accuracy.

Decision: accept (poster)
Reviewer scores: 6, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730378324407

thread_type:
official_review

<thread_object>
creator: reviewer_t2wr

<content>
summary:
This paper proposes a Hessian-free machine unlearning algorithm. The authors theoretically analyze the approximation error for both convex and non-convex loss functions and prove the generalization theory for strongly convex loss functions. Extensive experiments demonstrate the efficiency of the proposed algorithm compared to other Hessian-based algorithms.

strengths:
1. The authors analyze the training trajectory and propose a machine unlearning algorithm, which is practical and innovative.
2. Compared to other Hessian-based algorithms, the proposed Hessian-free algorithm is efficient, especially for high-dimensional problems.
3. The authors conducted comprehensive experiments to validate the effectiveness of their proposed algorithm, and the experimental results are well presented.

weaknesses:
Although the authors provide the approximation error analysis, there is no theoretical guarantee for the generalization performance of the unlearning model in the non-convex case.

questions:
1. The authors propose using HVP to avoid directly calculating the Hessian matrix and reduce computational complexity, as discussed in Section 4.4. Could other algorithms discussed in Section 4.4 also benefit from HVP? For example, for IJ, $H^{-1}\nabla \ell $ can be approximately computed using $K$ steps of the conjugate gradient method, where each step HVP can be applied. Could this approach enable IJ to achieve lower complexity and experiment time, considering the entire process of precomputation and unlearning?  In this case, how does the proposed algorithm compare to IJ?
2. The authors discuss in Appendix E that a small step size leads to a smaller approximation error. However, a small step size may result in insufficient model training. Could the authors further explain the trade-off?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730782401847

thread_type:
official_review

<thread_object>
creator: reviewer_ia1d

<content>
summary:
This paper proposes a Hessian-free approach to certified machine unlearning that aims to improve computational efficiency and scalability in removing specific data points from a model without full retraining. Instead of relying on direct Hessian computations, which are computationally prohibitive in high-dimensional and non-convex settings, the method approximates the impact of data removal through affine stochastic recursions that analyze model update discrepancies. The method achieves computational gains, reducing unlearning time to $\mathcal{O}(md)$ and storage to $\mathcal{O}(nd)$, outperforming existing second-order methods.

strengths:
- Both online learning and certified unlearning are highly significant research areas in machine learning.
 The paper is the first to introduce a Hessian-free approach to certified unlearning, which is a notable change from the dominant reliance on Hessian-based methods in second-order unlearning.

- Experimental validation shows unlearning runtime in milliseconds, robust generalization guarantees, and privacy improvements against membership inference attacks with an added noise mechanism.

- The authors also include relevant code and pseudo-code in the appendix, which is helpful for reproducibility.

weaknesses:
1. The paper’s theoretical guarantees hinge on assumptions of convexity and smoothness (Assumption 1), which restricts the scope of the analysis to settings that are arguably idealized for real-world applications involving non-convex (e.g. deep learning) models. Thus, the authors likely overstate their contributions.

2. I would say, Hessian-free optimization for second-order (and even higher-order) algorithms is an active research area. Beyond the Machine Unlearning domain discussed in detail on page 3 and in Appendix A, the authors should connect the ideas presented here with a broader body of Hessian-free optimization work in classical parametric optimization. A numerical comparison, if feasible, is also encouraged, as this may better highlight the novelty of this paper’s contributions beyond merely applying existing Hessian-free methods to the Machine Unlearning field.

3. While the authors present some experimental results, they lack diversity in dataset selection and only test the approach on ~5 datasets. The efficacy of this unlearning mechanism remains unclear in large-scale or high-dimensional applications where computational efficiency is critical.


4. The writing quality of this work is limited and the presentation should be improved, for instance

- the (2) is simply one case of (1) by replacing the $\mathcal{D}$ with empirical distribution. i.e., the authors could remove (2) for simplicity, or just start from the (1)

- I think the (3) should be written as $\mathbf{w}\_{e, b+1} \leftarrow \mathbf{w}\_{e, b}-\eta\_{e, b} \sum\_{i \in \mathcal{B}_{e, b}} \nabla \ell\left(\mathbf{w}\_{e, b} ; z\_i\right),$ since the linear scaling rule (Goyal et al. 2017) is introduced later in line 163.

- line 156 and algo. 1: as your notation, the total epochs and batches would be $E+1$ and $B+1$. So as your complexity in section 4.4

- when removing the $u\_j$, why the normalization constant of $\eta$ in your (5) is $ \mathcal{B}\_{e, b(u\_j)}$ instead of $ \mathcal{B}\_{e, b(u\_j)}-1$?

- definition 1: how can you ask a learning algorithm within the (solution) parameter space $\mathcal{W}$? Please revise the definition or rephrase your wording

- in your lemma 2, I don't think there exists a valid $G$ such that $G=\max \left\\|\nabla \ell\left(\mathbf{w}_{e, b} ; z\right)\right\\|<\infty$. This should be a consequence of the assumption that the grad of $l$ is uniformly upper bounded. Otherwise, this could be derived by your assumption 1, which is imposed later

- Theorem 4 should be $B=\left\lceil \frac{n}{|\mathcal{B}|} \right\rceil$

- if the intent is for the product to go in reverse order in line 10 of algo. 1, i.e. $\prod_{k=E}^e \prod_{b=B-1}^{b(u)+1}$, the notation should ideally be clarified in the text to avoid misunderstandings

- font size in figures e.g., 1, 2, 7, is too small and needs to be enlarged for clarity

- figure 4 caption: "a comparison comparison between"

questions:
Please refer to weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730875008103

thread_type:
official_review

<thread_object>
creator: reviewer_cnqv

<content>
summary:
The paper proposes a new unlearning algorithm which extracts second-order information in a Hessian-free manner without the need to assume strong convexity. The key idea is to track and remove the impact of a specific sample in the entire update trajectory of the model, which is called affine stochastic recursion between the retrained and learned models in this work. It provides theoretical guarantees on generalization, deletion capacity, and space/time complexities. Experiments are conducted to demonstrate the superiority of the proposed algorithm.

strengths:
Strengths include:
1) The paper proposes affine stochastic recursion to pinpoint the overall impact of a specific sample on the learned model.
2) It makes the unlearning process efficient via the Hessian-free computation.
3) It provides theoretical guarantees that cover generalization, deletion capacity, and space/time complexities. 
4) Experiments are provided to demonstrate the advantages of the proposed unlearning algorithm.

weaknesses:
Weaknesses include:
1) The recollection matrix M looks incorrect, based on the derivation given in Appendix C.1
2) Limitations of the algorithms are not discussed. For example, the proposed algorithm may not perform well on large-scale datasets given the quadratic time complexity in data size.

questions:
1) Could you explain why NS and IJ can't utilize HVP? Although they involve Hessian inverse, it could be approximated by using like least-square which essentially does HVP as well. 
2) Regarding the correlation metric on loss change, could you tell us what stopping rule you use while calculating those loss changes across different algorithms? I feel this is important for gauging performance.
3) It is unclear whether fine-tuning was used for each of the algorithms in experiments.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731089647287

thread_type:
official_review

<thread_object>
creator: reviewer_kjaj

<content>
summary:
This paper addresses the challenge of certified unlearning, where models are required to forget information at the request of data providers. The authors introduce a novel approach leveraging details tracked during model training to approximate how the training process would have proceeded without the data marked for deletion. Notably, the proposed method circumvents the need for full Hessian computations or inversion by using Hessian-vector products for second-order information. Additionally, it does not assume that the original model is an empirical risk minimizer. The authors' theoretical analysis argues that their method offers enhanced unlearning guarantees, efficient storage and precomputation, faster data deletion, and improved generalization bound, particularly for overparameterized models. Empirical results support the approach's claim of rapid unlearning execution.

strengths:
1. The idea of tracking algorithmic updates during training to facilitate unlearning is straightforward yet impactful, with sound theoretical analysis for unlearning privacy guarantee and descent empirical evaluation.
2. Removing the assumption that the initial learned model must be an empirical risk minimizer is significant for the practical applicability of the method.
3. The claimed efficiency improvements are particularly relevant for overparameterized deep models where the batch size is comparable to the number of training epochs, probably covering a substantial portion of common machine learning models.

weaknesses:
1) The claim regarding the efficiency of precomputation and storage (lines 378–387) hinges on two critical assumptions: (i) the model's parameter size $d$ is significantly greater than the training data size $n$, and (ii) the number of epochs $E$ is of the same order as the batch size $|B|$. While the authors state (ii) as typical ("Typically, $E$ and $|B|$ are of the same order"), a reference would strengthen this claim. Moreover, the assumption may not hold in scenarios such as online learning or streaming applications. Qualifying its generality and highlighting this as an assumption similar to Line 299 would be beneficial and avoid misleading readers.

2) The generalization analysis in Section 4.2 considers strong convex loss functions and focuses on excess risk bound. Excess risk bound consist of two terms: the first term comes from (a) the excess risk of the empirical risk minimizer, and the second term comes from (b) unlearning error, (c) optimization error, and (d) the noise for obfuscation (Line 14 of Algorithm 1). There are at least two problems with this analysis and theorem statement.

2.1 In strong convex settings, the assumption that $E$ and $|B|$ are comparable can seem more questionable, especially as the excess risk bound expressed in big-O notations (Line 319) uses this assumption. It might be okay to make this assumption for controlling (b), but $E$ and $B$ also affects (c), i.e. whether the term $C_4$ in Equation 74 is small enough, which conceptually (roughly) translates to whether $w_{E, B}$ is a good empirical minimizer or not. It seems problematic to assert that the number of epoch required for convergence to empirical risk minimizer is the same order of magnitude as batch size. 

2.2 The first term comes from Lemma 9, which cites Shalev-Shwartz et al. (2009). The latter assumes i.i.d. of samples, which should translate to i.i.d. of the set $U$.

questions:
1. In the abstract (Line 017) and introduction (Line 073), the authors claim that previous work requires strong convexity, while in Line 66 the authors said previous work requires convexity. It seems to me that convexity suffices in Sekhari et al. (2021) because unlearning for a convex loss function can be reduced to a problem with strong convex loss. Could the authors clarify what assumptions are needed in previous work? 
2. In Assumption 1 (Line 299), is the loss assumed to be jointly convex in both $z$ and $w$, only $w$, or only $z$? Similar questions for Lipschitzness and smoothness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732168342881

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response

comment:
Dear Senior Area Chairs, Area Chairs, and Reviewers,

We thank all reviewers for their constructive and valuable comments and appreciate the time spent on our manuscript. We have provided responses to the comments to fully address all reviewer concerns, denoted by **[W]** for weaknesses, **[Q]** for questions, **[L]** for lines in our manuscript, and **[R]** for references.  We made minor adjustments to the manuscript and use **[C in L]** to denote the changes in lines in our revised manuscript. We have provided our additional experimental results in an anonymous GitHub repository, and the link is provided in **L107**. 

Here's a summary of our responses:

**Reviewer kjAJ:**

>- We adopt the reviewer’s suggestion to provide descriptions and references regarding complexity to avoid any potential misunderstandings in the revised version. **(C in L266, L380)**
>- We explain the analysis of generalization performance and the statement of the theorem in Section 4.2.
>- We clarify the misunderstanding regarding the analysis of optimization error in the performance analysis.
>- We adopt the reviewer’s suggestion and added the missing description in Lemma 9. **(C in L1407 of Appendix)**
>- We clarify the assumptions between previous works and our work, and provide a more detailed definitions of assumptions to avoid confusion. 

**Reviewer CNQV:**

>- We correct the errors of notation in Matrix $\mathbf{M} $ based on the reviewer’s comments. **(C in L221)**
>- We clarify that our work have discussed a limitations analysis and propose corresponding improvement methods.
>- We explain the reasons why HVP with some approximation techniques are not applicable to previous studies .
>- We explain the setup of the experiments and provide additional explanations in the revised version. **(C in L1031 of Appendix)**

**Reviewer ia1D:**

>- We strive to clarify that our non-convexity claims are only applicable to unlearning methods and their associated theoretical analysis, and we explain why one of our contributions is bridging the gap in non-convex scenarios for certified unlearning methods.
>- We clarify that the optimization methods used in the learning process are unrelated to our approach and explain the connection between existing Hessian-free optimization methods and our unlearning work.
>- We incorporate the reviewer’s suggestion for experiments on more datasets and provide additional clarifications regarding our experimental contributions. **(Additional experiments provided)**
>- We clarify some suggestions from the reviewer regarding definitions and explain why we do not modify these definitions.
>- Based on the reviewer’s suggestions, we modify the typos and inaccurate statements in the paper. **(C in L156, L289, L178, and L1562 of Appendix)**

**Reviewer t2wR:**

>- We explain the assumptions of our algorithm regarding generalization error and listed it as an direction for future work.
>- We explain the reasons why HVP with some approximation techniques for previous unlearning work are not applicable.
>- We clarify the trade-off between learning rate and both learning and unlearning, incorporating the reviewer’s suggestion for trade-off experiments. **(Additional experiments provided)**

**References:**

> [R1] Remember what you want to forget: Algorithms for machine unlearning. Sekhari et al., NeurIPS 2021.
>
> [R2] Algorithms that approximate data removal: New results and limitations. Suriyakumar et al., NeurIPS 2022.
>
> [R3] Certified minimax unlearning with generalization rates and deletion capacity. Liu et al., NeurIPS 2023.
>
> [R4] Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning. Chien et al.,  NeurIPS 2024.
>
> [R5] Certified Machine Unlearning via Noisy Stochastic Gradient Descent. Chien et al.,  NeurIPS 2024.
>
> [R6] How SGD selects the global minima in over-parameterized learning: A dynamical stability perspective. Wu et al., NeurIPS 2018.
>
> [R7]  A loss curvature perspective on training instabilities of deep learning models. Gilmer et al., NeurIPS 2022.
>
> [R8] Fast Model Debias with Machine Unlearning. Chen et al., NeurIPS 2023.
>
> [R9] An Empirical Model of Large-Batch Training. McCandlish et al., NeurIPS 2023.
>
> [R10] A disciplined approach to neural network hyper-parameters: Part 1 -- learning rate, batch size, momentum, and weight decay. Leslie N. Smith, ArXiv 2018.
>
> [R11] Training Deep and Recurrent Networks with Hessian-Free Optimization. James Martens and Ilya Sutskever. 2012.

**Additional Revisions:**

> 1. We shortened the title to allow for more detailed descriptions in Section 1.
>
> 2. We revised the imprecise expression in Appendix C.1.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper studies the problem of certified unlearning in machine learning scenarios. It proposes a "Hessian-free" approach, removing the need for explicit Hessian computation and inversion. As a result, the paper also removes the requirement that the objective function be strongly convex, and for the unlearning part can even handle nonconvex loss functions. For the learning portion of the results, the paper builds on prior work, which requires convexity. Overall, the paper presents interesting contributions in an important and growing area of machine learning.