Hessian-Free Online Certified Unlearning

We sincerely appreciate your support and constructive suggestions. We have made every effort to revise the manuscript based on your valuable suggestions.

We provide our responses to comments, denoted by [W] for weaknesses, [Q] for questions, [L] for lines in our manuscript, and [R] for references in the General Response.

W1: There is no theoretical guarantee for the generalization of unlearning model in the non-convex case.

Our contributions for non-convex assumption primarily focus on unlearning domain. For theoretical analysis involving learning process conclusions, we inherit convexity assumption from prior unlearning works, adopting simple and rigorously assumed conclusions such as Lemma 9.

We appreciate reviewer’s constructive comments. Given that unlearning community are starting to explore generalization in non-convex settings, as a future extension, we plan to provide non-convex theoretical conclusions in later versions or follow-up works.

Q1: Could other algorithms discussed in Section 4.4 benefit from HVP?

We sincerely thank reviewer for their insightful questions and provide following clarifications.

• The key reason is that, to handle deletion requests from unknown users, both NS and IJ require explicit pre-computing of Hessian and its inverse before an unlearning request arrives, which makes HVP impossible.

Recall the technique details of NS and IJ.

For NS, the update step is: $\frac{1}{n-m} { \Big( \frac{1}{n-m}\sum_{i=1}^n \nabla^2 \ell (\hat{\mathbf{w}}; z_i) -\sum_{j \in U} \nabla^2 \ell (\hat{\mathbf{w}};u_j )\Big) }^{-1}\sum_{j \in U} \nabla \ell (\hat{\mathbf{w}}; u_j).$

For IJ, the update step is: $\frac{1}{n} {(\frac{1}{n}\sum_{i=1}^n \nabla^2 \ell (\hat{\mathbf{w}}; z _ i) ) }^{-1} \nabla \ell (\hat{\mathbf{w}}; u _ j).$

However, for Hessian $\sum_{j \in U} \nabla^2 \ell (\hat{\mathbf{w}}; u _ j)$ in NS and gradient $\nabla \ell (\hat{\mathbf{w}}, u_j)$ in both NS and IJ, (i) forgetting sample $u _ j$ is unknown before deletion request arrives, and (ii) model $\hat{\mathbf{w}}$ will be deleted after processing a deletion request, while subsequent unlearned model is also unknown since forgetting sample $u_j$ is unpredictable. Therefore, explicit pre-computing is required for $\sum_{i=1}^n \nabla^2 \ell (\hat{\mathbf{w}}; z_i)$ in NS and ${\left( \sum_{i=1}^n \nabla^2 \ell (\hat{\mathbf{w}}; z_i) \right)}^{-1}$ in IJ.

This is also a unique advantage of our method, which possesses additivity in Theorem 1 (L245), enabling it to efficiently handle multiple deletion requests in online manner. We will make this point clearer in revised manuscript to better highlight our contributions.

• In addition, inaccurate techniques (e.g., as mentioned by reviewer, it could be approximated by using methods like least squares) would also render theoretical bounds not as strong as techniques proposed in NS and IJ. These operations require previous works to re-derive bound, resulting in loss of original $\mathcal{O}(m^2/n^2)$ approximation error advantage.

Given the above reasons, approximate techniques are more suitable for non-privacy scenarios involving heuristic methods that do not require certified theoretical guarantees, such as bias removal based on influence function in R8 .

Q2: Could authors further explain trade-off between smaller approximation error and insufficient model training caused by step size?

We greatly appreciate the insightful questions, which has inspired us with new insights. Below, we provide explanations and present new experiments to support it.

As we demonstrate in Appendix L1806-L1820:

• Theoretical predictions R6 and empirical validation R7 suggest that successful training occurs only when optimization enters a stable region of parameter space, where $\lambda _ 1 \eta _ 1 < 2$ (with $\lambda _ 1$ being largest eigenvalue of Hessian).
• We also observed when step size is below certain threshold $\eta _ {\text{2}}$, increasing step size does not lead to unacceptable errors, e.g., in Table 7, increasing step size from 0.01 to 0.1 results in error increase of only 0.005. However, when step size exceeds 0.1 and increases to 0.3, error becomes uncontrollably large, increasing by 5.553.

Combining the conclusions and observations, there exists a range on step size that ensures successful training during learning phase while preventing errors from escalating in unlearning phase. Our further experiments support this: maintaining a threshold that prevents fluctuations in error often allows for sufficient training (successful training as state in R6) at appropriate step size, as our method is less affected by step size when below a threshold, there is typically no noticeable tradeoff. For detailed code and results, please refer to anonymous repository link provided in L107.

We thank the reviewer for all of your valuable comments. We sincerely hope that this revised manuscript has addressed all your comments and suggestions. We are more than willing to provide further clarification or address any additional concerns.

We provide our responses to the comments, denoted by [W] for weaknesses, [Q] for questions, [L] for lines in our manuscript, and [R] for references.

W1: Theoretical guarantees hinge on assumptions of convexity.

• Unlike previous works, the key distinction of our method lies in its ability to handle non-convex scenarios. This is achieved by avoiding the need for Hessian inversion, meaning that strong convexity is not required to ensure the positive definiteness of the Hessian. Therefore, our unlearning method and its theoretical guarantees do not rely on the assumption of convexity.
• In deriving other performance analyses involving learning process conclusions, such as generalization guarantee, we inherit the convexity assumption from prior unlearning works. As noted in Line 97 and L308-L311, we clarified in the initial manuscript that our proposed method and theoretical unlearning guarantees apply to both convex and non-convex settings, but do not extend to the theoretical analysis of the learning process.

In summary, our contributions for non-convex assumption primarily focus on the unlearning domain. For the theoretical analysis involving the learning process conclusions, we have built upon previous unlearning work, adopting simple and rigorously assumed conclusions such as Lemma 9. As a future extension, we plan to provide non-convex theoretical conclusions for generalization guarantee in later versions or follow-up works.

W2: Authors should connect the ideas presented with a broader body of Hessian-free optimization work in classical parametric optimization.

We appreciate the reviewer’s suggestion. Here, we briefly clarify the connection between our ideas and Hessian-free optimization work. Our unlearning method and previous Hessian-free optimization approaches are parallel lines of research, such as using conjugate gradient with HVP to perform sub-optimization. Different algorithms that use many of the same key principles have appeared in the literature of various communities under different names such as Newton-CG, CG-Steihaug, Newton-Lanczos, and Truncated Newton, as stated in R11. But in any case, the learning and unlearning processes are distinct from each other. The commonality lies in leveraging automatic differentiation tools to compute HVP, avoiding explicit computation of the Hessian, as this provides a numerically stable and precise way to compute the desired directional derivative.

W3: Lack diversity in dataset selection and only test the approach on ~5 datasets.

• We greatly appreciate the valuable suggestion. In addition to MNIST, FMNIST, CIFAR10, CelebA, and LFW, we have conducted experiments on additional datasets for sufficient diversity in dataset selection, including HAPT, Adult, Wine, and Obesity. Our initial manuscript included digit, clothing, object, gender, and human face classification, and we further provided experiments on human activity recognition, income, wine quality, and estimation of obesity levels. These will demonstrate sufficient diversity in our dataset selection. The results show that we achieve good performance across different datasets, demonstrating the advantages of our algorithm. Please refer to the anonymous repository link provided in L107 for detailed code and figures.
• Besides, we would like to clarify our experimental contributions. Previous theoretical works R1, R3 did not include experiments, and R2 only conducted experiments with binary LR. Even the recent certified unlearning works R4 and R5 have experimented with convex models. The datasets used in these works were limited to binary MNIST and CIFAR10. While providing different theoretical insights, the extensive experiments led to space limitations in our writing. This is also why the reviewer raised the concern about the font size in the figure 1 being too small. We have followed the suggestion and increased the font size. However, for the additional experiments suggested by reviewer on the more datasets, we have to place these experiments in the appendix.

Dear Reviewer ia1D,

We would like to express our gratitude for your constructive suggestions and thoughtful reviews, which have proven invaluable in enhancing the quality of our paper. As a follow-up to our rebuttal, we would like to kindly remind you that the deadline for discussion closure is rapidly approaching.

During this open response period, we aim to engage in discussions, address any further inquiries, and further enhance the overall quality of our paper. We would appreciate it if you could confirm whether you have had the opportunity to review our rebuttal, in which we made concerted efforts to address all of your concerns. It is of utmost importance to us that our responses have been thorough and persuasive. We have also attached tables summarizing the experimental results for diverse dataset selection for your convenience.

Should you require any additional information or clarification, please do not hesitate to let us know. Thank you once again for your time and valuable consideration.

Best regards,

Authors

(Submission Number: 830)

I understand that your new algorithm can be applied to both convex and non-convex settings, but much of the analysis is built on convexity, which does present a limitation. It would be nice if you could further discuss that in your work.

Regarding W4.4, my main point is that Assumption 1 should be stated before Lemma 2 rather than in its current position. Otherwise, the upper bound may not hold (unless you explicitly assume it, but the lemma appears to be presented as a result rather than a condition).

That said, given the overall responses, I have revised my stance.

We appreciate the reviewer’s understanding of the contribution our unlearning method makes in bridging the gap in implementing non-convex and non-convergence conditions. We also sincerely thank the reviewer for improving the rating. Below is our response to address your remaining concerns.

• We acknowledge that, while we propose a new method that does not rely on convexity, our analysis builds upon the theoretical framework of previous works for comparison purposes. These prior certified unlearning works, both in terms of methodology and theoretical analysis, were limited to convex settings, which is why much of our theoretical results rely on convexity—except for our unlearning-related conclusions. We briefly discuss the limitation in the revised manuscript (L308, L934). In the future, we plan to extend the existing theoretical framework, though this may require revisiting existing methods and frameworks, or introducing new assumptions to address more complex scenarios.

• In response to the reviewer’s concern on W4.4, we have, following the reviewer’s suggestion, stated Assumption 1 before Lemma 2 in order to ensure that the upper bound holds.

If the reviewer has any further Questions or Weakness that need to be addressed, we would be glad to provide any clarification.

We sincerely appreciate your support and constructive suggestions. We have made every effort to revise the manuscript based on your valuable and constructive suggestions.

We provide our responses to the comments, denoted by [W] for weaknesses, and [Q] for questions. The references, denoted by [R], are provided in the General Response. And we use [L] to represent lines in our manuscript.

W1: The recollection matrix M looks incorrect.

We thank the reviewer's comments, and would like to clarify that the recollection matrix $\mathbf{M}$ is correct because its product requires multiplying $\mathbf{I}-\eta \mathbf{H}$ of the most recent update with those of the past updates.., such as $(\mathbf{I} - \eta _ {E,B} \mathbf{H} _ {E,B})(\mathbf{I} - \eta _ {E,B-1}\mathbf{H} _ {E,B-1})...(\mathbf{I} - \eta _ {E,b(u)+1} \mathbf{H} _ {E,b(u)+1})$. This means the multiplication should begin with the most recent update and continue backward through the previous gradient updates. Can we politely ask what makes the reviewer think that $\mathbf{M}$ seems incorrect? We greatly appreciate the reviewer’s concern, and to avoid any misunderstandings, we have revised the manuscript and added the necessary explanation in Appendix C.1.

W2: Limitations of the algorithms are not discussed, and the proposed algorithm may not perform well on large-scale datasets.

In Appendix B.1 of our initial submission, we provide a detailed description of the limitations of our algorithm and corresponding solutions, including the reviewer’s concern about large-scale datasets. For example, we can consider maintaining vectors for $k$ users instead of $n$ data points ($k \ll n$), which would significantly reduce both computation time and storage, without relying on quadratic time complexity in the data size.

Q1: Why NS and IJ can't utilize HVP?

We sincerely thank the reviewers for their insightful questions and have provided the following clarifications in response.

• The key reason is that, to handle deletion requests from unknown users, both NS and IJ algorithms require explicit pre-computing of the Hessian and its inverse before an unlearning request arrives, which makes HVP impossible.

Let us recall the technique details of NS and IJ.

For NS, the update step is: $\frac{1}{n-m} { \Big( \frac{1}{n-m}\sum_{i=1}^n \nabla^2 \ell (\hat{\mathbf{w}}; z_i) -\sum_{j \in U} \nabla^2 \ell (\hat{\mathbf{w}};u_j )\Big) }^{-1}\sum_{j \in U} \nabla \ell (\hat{\mathbf{w}}; u_j).$

For IJ, the update step is: $\frac{1}{n} { (\frac{1}{n} \sum_{i=1}^n \nabla^2 \ell (\hat{\mathbf{w}}; z _ i) ) }^{-1} \nabla \ell (\hat{\mathbf{w}}; u _ j).$

However, for the Hessian $\sum_{j \in U} \nabla^2 \ell (\hat{\mathbf{w}}; u _ j)$ in NS and the gradient $\nabla \ell (\hat{\mathbf{w}}, u_j)$ in both NS and IJ, (i) the forgetting sample $u _ j$ is unknown before the deletion request arrives, and (ii) the model $\hat{\mathbf{w}}$ will be deleted after processing a deletion request, while the subsequent unlearned model is also unknown because the forgetting sample $u_j$ is unpredictable.

This is also a unique advantage of our method, which possesses additivity in Theorem 1 (L245), enabling it to efficiently handle multiple deletion requests in an online manner. We will make this point clearer in the revised manuscript to better highlight our contributions.

• In addition, inaccurate techniques (e.g., as mentioned by the reviewer, it could be approximated by using methods like least squares) would also render the theoretical bounds of previous works not as strong as the techniques proposed in NS and IJ. These operations require the previous work to re-derive the upper bound, resulting in the loss of the original $\mathcal{O}(m^2/n^2)$ approximation error advantage.

Given the above reasons, these approximate techniques are more suitable for non-privacy scenarios involving heuristic methods that do not require certified theoretical guarantees, such as bias removal based on influence function in R8 .

Q2: What stopping rule do you use while calculating those loss changes across different algorithms?

We trained the model normally until the accuracy no longer increased significantly (e.g., when the model accuracy stabilized or started to decline), at which point we considered the model to have nearly converged, and the training needed to stop.

Q3: Whether fine-tuning was used for each of the algorithms in experiment?

We only used fine-tuning in Figure 3 of Appendix B.4. All other experiments are based on Algorithm 1 without fine-tuning. We briefly introduce fine-tuning in Appendix B.4 because we believe our method can serve as a heuristic algorithm in non-privacy scenarios, where theoretical certified guarantees are not necessary.

Thanks a lot for Reviewer CNQV careful proofreading and for the time you have dedicated to our work. After considering your feedback, we realized that there was indeed an unintended error in the notation of the $\mathbf{M} _ {e, b(u)}$ in Eq. 10. Specifically, we mistakenly formulated the recursive product $\mathbf{M} _ {e, b(u)}$. We have made the necessary corrections to the related content (L221, and L1075, L1180 in the appendix) marked in blue in the revised paper. This correction does not affect the other conclusions of our work. Below are the details of our revisions:

We removed the unnecessary and cumbersome product symbols. In the latest manuscript, we define the recollection matrix as $\mathbf{M} _ {e,b(u)} := \frac{\eta _ {e,b(u)}}{|\mathcal{B} _ {e,b(u)}|} \hat{\mathbf{H}} _ {E,B-1 \rightarrow e,b(u)+1 }$, where $\hat{\mathbf{H}} _ {E,B-1 \rightarrow e,b(u)+1 }= (\mathbf{I}- {\eta _ {E,B-1}}\mathbf{H} _ {E,B-1})\cdot(\mathbf{I}- {\eta _ {E,B-2}}\mathbf{H} _ {E,B-2})...(\mathbf{I}- {\eta _ {e,b(u)+1}}\mathbf{H} _ {e,b(u)+1})$ which represents the product of $\mathbf{I}-\eta \mathbf{H}$ from $E$-th epoch's $B-1$-th update to $e$-th epoch's $b(u)+1$-th update. The improved notation of $\mathbf{M} _ {e,b(u)}$ in the revised version now effectively and clearly conveys its meaning.

We sincerely appreciate your thorough proofreading once again, as well as the meaningful suggestions and questions you raised earlier. If there are any other questions, we would be more than glad to address any further requests from the reviewer.

We sincerely appreciate your support and constructive suggestions. We have made every effort to revise the manuscript based on your valuable and constructive suggestions.

We provide our responses to the comments, denoted by [W] for weaknesses, and [Q] for questions. The references, denoted by [R], are provided in the General Response. And we use [L] to represent lines in our manuscript.

W1: Qualifying the generality of complexity and highlighting this as an assumption similar to Line 299 would be beneficial and avoid misleading readers.

Thank you for your insights. Based on the reviewer's suggestions, we have tried our best to revise the manuscript for descriptions and assumptions similar to L299, and provide additional references, such as R10, to demonstrate that the ratio of $E$ to $B$ is generally small. Additionally, the feedback has inspired us to provide a more precise description of the impact of $E$ and $|B|$ on complexity in our revised version. In fact, the ratio of $E$ to $|B|$ is much smaller than $d$. Therefore, our method works for most scenarios, except in the cases where SGD is over-iterating the epoch to levels in the dimension $d$.

W2: (1) Shalev-Shwartz et al. (2009) assumes i.i.d. of samples, which should translate to i.i.d. of the set. AND (2) The term C4 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 epochs required for convergence to empirical risk minimizer is the same order of magnitude as batch size.

• For (1): We greatly appreciate the constructive suggestions from the reviewer, and we have completed the missing details in Lemma 9 in the revised version.

• For (2): We do not require $w_{E,B}$ to be an empirical risk minimizer in Theorem 6 of Section 4.2. We appreciate the reviewers for spending time on the proofs in our paper and for outlining our proof sketch in the review.

We would like to further clarify that (a) represents the excess risk between the retrained empirical risk minimizer $\hat{w}^{-U}$ and ${w}^*$, while (c) denotes the optimization error between the retrained model ${w}^{-U} _ {E,B}$ and $\hat{w}^{-U}$. Using (a) and (c), we can bound the excess risk of the retrained model ${w}^{-U} _ {E,B}$ relative to ${w}^*$, Note that at this point, we no longer require convergence to the empirical risk minimizer. Furthermore, given (b) and (d), which represent the approximation error and noise of the unlearning model $\tilde{w}^{-U} _ {E,B}$, we can bound the excess risk of the unlearned model $\tilde{w}^{-U} _ {E,B}$ relative to ${w}^*$ in Theorem 6. Therefore, in Theorem 6, we do not need the term C4 to be sufficiently small as it also satisfies $\mathcal{O}(\rho^n)$, and we do not require $w _ {E,B}$ to be an empirical risk minimizer. This is a key distinction that sets our Theorem 6 apart from previous works, as the generalization guarantees in earlier works are derived through implicit assumption about the empirical risk minimizer.

Q1: Convexity suffices in R1 because unlearning for a convex loss can be reduced to a problem with strong convex loss. AND Could the authors clarify what assumptions are needed in previous work?

• First of all, previous algorithms requires strong convexity. The reason that previous work requires strong convexity is to guarantee that the Hessian is positive definite, thus ensuring its invertibility. Simply claiming to require convexity is insufficient because a semi-positive definite Hessian still cannot guarantee invertibility, although R1 can use regularization techniques (such as L2 regularization) to make a logistic regression loss function strongly convex.
• We thank the reviewer's comments and would like to clarify that the assumptions in Assumption 1 is consistent with previous works R1, R2. In addition to this, previous works require the implicit assumption of a unique empirical risk minimizer.

Q2: Is the loss assumed to be jointly convex in both $z$ and $w$?

All assumptions in L299 are made solely with respect to $w$. We appreciate the reviewer’s valuable question and we provide a more detailed explanation of the definition of Assumption 1 in the appendix (L1389-L1403) in revised manuscript.