Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning

Summary

This paper proposes an unlearning framework based on Langevin dynamics with two key components: - The initially trained model satisfies some differential privacy guarantee - Unlearning relies on DP fine-tuning the model on the rest of the dataset (which quickly reduces the privacy loss on the example to be forgotten). This framework is formalized using the theory of convergence of Langevin dynamics. Specifically, assuming the Log-Sobolev inequality holds for the stationary distribution, the paper establishes a linear rate of convergence of the unlearning step. Notably, these bounds apply for the nonconvex setting as well; however, the constants are quite pessimistic in this case. The explicit constants are given for the convex and strongly convex settings, leading to implementable algorithms. The paper also gives extensions to multiple deletions (sequential and simultaneous). Advantages relative the D2D baseline and retraining from scratch are established as well.

Strengths

This is a very strong paper and generally high quality work. - While it is grounded in RDP, the theoretical advances are original. I love that the paper also explores 2nd order effects of the proposed framework, such as batch/parallel unlearning, etc. - This framework gives the first provable approximate unlearning guarantees in the nonconvex setting and improves upon other approaches in the (strongly) convex setting. I believe these results are very significant and can inspire future work in the area. - The paper is generally well-organized and well-written (although it is not perfect; specific suggestions for improvements are given below).

Weaknesses

- **Clarity**: The paper tackles some advanced technical tools, which may only be known to a niche audience. It would greatly help the broader appeal of the paper to explain the key intuition behind the LSI and why it can be expected to hold. Similarly, it would be nice to consider simple examples in the unlearning setting and give explicit values of the LSI constant. Also, what is its right scaling with respect to other problem parameters such as smoothness, strong convexity, etc.? - The improvements from Langevin unlearning over training from scratch are purely logarithmic. How significant is this factor in the experiments? - The paper uses full gradient steps. How do things change with stochastic gradient steps? What would be the computational complexity of the resulting algorithm? - No experiments in the nonconvex case. Since these are the only provable guarantees in the literature so far, future work in the area would greatly benefit from setting up a benchmark with the results of this work.

Questions

- What are the various degrees of freedom in the privacy-utility-compute tradeoff? I assume that if we fix $\epsilon$ (privacy) and $K$ (compute), then we can tune $\sigma$ to get the desired privacy bound. Are there other degrees of freedom? If there is an extra degree of freedom, what are some rules of thumb for setting the parameters? - Continuiung from the above, it would be nice to see some more plots exploring this tradeoff. Examples: - Fix $K$, plot accuracy vs $\epsilon$ (or vs. $\sigma$) (I believe Fig 3c varies $K$ between the various points) - Fix $\sigma$, plot accuracy vs. $\epsilon$ (or vs. $K$) - Fix $\epsilon$, plot accuracy vs. $K$ - How do $C_k$ and $R_k$ scale with $k$ in the various settings of Theorem 3.2? While the authors acknowledge that the rates in the nonconvex case are pessimistic, it would be nice to discuss exactly how the iteration independent lower-bound scales with various problem parameters. Specifically, the dependence on which parameters do you think can be improved? - Figure 3b: do all of the points have the same utility? - Theorem 3.2(c): The strongly convex case needs $\sigma^2$ small enough. I wonder about the implications of this requirement. Does it mean that unlearning is not possible using the given framework for certain parameter values? Does it mean that a certain minimum amount of compute is necessary to make unlearning possible? It would be great to explore these quantitatively from the established bounds. - Can the established unlearning guarantees be compared analytically to existing ones?

Rating

8

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

Yes, limitations have been adequately addressed.

Summary

This paper focuses on approximate unlearning under a similar definition of Differential privacy (DP), where privacy is defined as statistical indistinguishability to retraining from scratch. To be specific, they propose Langevin unlearning, which is a new framework based on the noisy gradient descent with privacy guarantees for approximate unlearning. The proposed framework has demonstrated many benefits like approximate certified unlearning for non-convex problems, and sequential and batch unlearning for multiple unlearning requests.

Strengths

1. This work studies the theoretical unlearning guarantees of projected noisy gradient descent algorithms for convex problems, which provide fruitful theoretical basics for unlearning with several important algorithmic benefits, like approximate certified unlearning for the non-convex problems, and complexity saving, as well as enabling the sequential and batch unlearning. 2. The proposed Langevin unlearning based on the projected noisy gradient descent provides a unified geometric view of learning and unlearning processes, which is good for the understanding of the main idea. 3. Both theoretical results and empirical evaluation of the logistic regression task are provided to make the work comprehensive and insightful.

Weaknesses

Overall, the reviewer appreciates the idea of Langevin unlearning with the rigorous theoretical analysis for privacy guarantees, below are some comments from the weakness part which are hoped to be constructive for consideration. 1. The current presentation of this work can be further improved by considering clearly stating all the notations at the corresponding position and reorganizing the theoretical results with some intuitive explanation and connection with the empirical evaluation or justifications. 2. Before introducing the Langevin unlearning with the main results, it could be better to explain the motivation for the proposed framework. 3. For the geometric interpretation of the relations between learning and unlearning, what is the connection between this and the later illustration of the sequential unlearning and batch unlearning scenarios, and could the authors also explain the gap between the illustration and the practical learning dynamics for the corresponding problems? 4. For the empirical aspects of Langevin unlearning, how can we understand the corollary 3.4 more intuitively for the benefit obtained by the framework?

Questions

Minor comments and specific questions: 1. It seems there is no conclusion part, it would be better if the author could summarize the main claims and add it.

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

This work has adequately discussed the limitations and there is no significant negative societal impact of this work.

Summary

This paper proposes a novel framework for machine unlearning through noisy gradient descent with Langevin dynamic analysis. This framework has privacy guarantees for approximate unlearning problems and it unifies differential privacy and machine unlearning process, giving benefits including approximate certified unlearning for non-convex problems, complexity saving compared to retraining, sequential and batch unlearning for multiple unlearning requests.

Strengths

1. The authors propose a novel unlearning framework called Langevin unlearning, which is based on noisy gradient descent. This framework provides a new approach to approximate machine unlearning with privacy guarantees. 2. The paper presents a theory that unifies the differential privacy (DP) learning process with the privacy-certified unlearning process, offering algorithmic benefits such as approximate certified unlearning for non-convex problems. 3. This paper provides empirical results showing the practical effectiveness of the proposed framework compared to existing methods.

Weaknesses

1. The writing is not easy for readers unfamiliar with differential privacy to follow. I think including more details and intuitive explanations in the preliminary would help. 2. Although the paper discusses the computational benefits over retraining, the empirical results are limited to toy datasets such as MNIST and CIFAR10. Actual scalability and computational complexity of the Langevin unlearning approach for large-scale machine learning models and datasets need further investigation. 3. The effect of the method is sensitive to hyperparameters such as the standard deviation of the noise.

Questions

How does the unlearning process ensure other learned data are not affected? Are there any empirical results or theoretical guarantees?

Rating

5

Confidence

1

Soundness

3

Presentation

2

Contribution

3

Limitations

While the paper claims to theoretically handle non-convex problems, the practical applicability of the framework for such problems might be limited due to the reliance on certain constants that are either undetermined or can only be loosely determined. The applications may still limited to strong convex problem.

Summary

The paper proposes Langevin unlearning, a new perspective of noisy gradient descent for approximate machine unlearning, which unifies the differential privacy learning process and privacy-certified unlearning process with many algorithmic benefits. The key technique of the proposed method is to carefully track the constant of log-Sobolev inequality. The authors validate the practicality of Langevin unlearning through experiments on MNIST and CIFAR10, and demonstrate its superiority against gradient-descent-plus-output-perturbation based approximate unlearning.

Strengths

1. The authors innovatively interpret the relations between learning and unlearning via a geometric view. 2. The authors provide a rigorous theoretical analysis of privacy guarantees and a framework for certified non-convex approximate unlearning. 3. The theorems and proofs are well-presented. 4. The proposed method supports insufficient training as well as sequential and batch unlearning, aligning well with practical scenarios. 5. The paper is well-organized and the writing is clear overall.

Weaknesses

1. The experiments are not extensive enough and do not consider non-convex problems.

Questions

1. Is it possible to provide experiments on (toy) non-convex problems?

Rating

7

Confidence

4

Soundness

4

Presentation

4

Contribution

4

Limitations

1. Most experiments are binary classification problems, with multiclass classification experiments on CIFAR-10-multi-class deferred to the appendix.

Thanks!

Thank you for the response! I will keep my score. All the best to the authors!