- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper provides a bound on the distance between training on two adjacent dataset (i.e., algorithmic stability) via certified unlearning guarantees and a term controlling how different unlearning two forget sets is. The theory is focused on when langevin dynamics (with a rewind to delete start) is used for unlearning, and presumably also training though this is not explicitly stated. The paper later studies specific instantiations of their theory, and how bounds on relevant terms may be obtained.
Critical strengths
-
The applications of their theory to specific loss families to show the difficulty of unlearning seems impactful.
-
The experiments seems to be the start of a valuable research direction into empirically estimating the contractiveness of Langevin dynamics for unlearning. Note past work typically uses worst-case bounds.
Critical weaknesses
- It is not made clear what parts of the theory and techniques are new to the literature on unlearning. Several papers have already studied Langevin unlearning [1,2], including how the number of steps to unlearn depends on the distance between the original models and retrained models [2]. Moreover, the connection between unlearning and algorithmic stability has been explored in other work (e.g., [3]). Given much of the analysis seems to reinvent Langevin convergence (e.g., analyzing when we have contractive updates is standard across the literature), I could not isolate what was new to the literature. Furthermore, the experiments seem to largely be checking if updates are contractive or not and at what rate: this seems useful but not is sufficiently elaborated on to contrast with past findings.
- The writing also leaves a lot of terminology and choices undefined, not explained and I believe misrepresents past work. For example, is the worst-case distance to retraining, but worst-case over what randomness. Similarly, it is not explicitly stated whether the training algorithm is also Langevin; I assume this is true, but the paper only states T steps with step sizes and then only later defines what the unlearning algorithm is (that too somewhat indirectly through first assuming an abstract anchor and then stating what the anchor they study is). Beyond these, many choices such as working with Wasserstein distances and the two-sided unlearning inequality for the unlearning definition (note unlearning is also often treated as a one-sided) makes it hard to parse how the paper builds on existing ideas. Moreover, I believe the framing of the paper in the introduction misrepresents existing results (which I think underlies later issues).
[1] Chien, Eli, et al. "Langevin unlearning: A new perspective of noisy gradient descent for machine unlearning." Advances in neural information processing systems 37 (2024)
[2] Sepahvand, Nazanin Mohammadi, et al. "Leveraging per-instance privacy for machine unlearning." International Conference on Machine Learning (2025).
[3] Ullah, Enayat, et al. "Machine unlearning via algorithmic stability." Conference on Learning Theory. PMLR, 2021.
Questions for authors
Overall I believe the paper needs to better contextualize itself with existing results, in order disambiguate what are the new contributions and clearly explaining the impact of these. I believe answering my questions below can help with that, and am willing to raise my score:
-
Given existing Langevin unlearning analysis, can you elaborate on what is being added in the discussion on contractive vs. expansive updates?
-
Given existing relationships between “algorithmic stability” and unlearning, can you elaborate on what the conversion theorems adds. My understanding is typically we have number of steps for unlearning (with Langevin) is bounded by algorithmic stability notions, and the conversion theorem seems to provide the other direction. However, I could not understand how the term in Theorem 1 would be controlled or measured.
-
My understanding of the main results of Section 5 is that there are several classes of losses where the worst-case unlearning for Langevin takes longer than retraining. Can you elaborate on what the worst-case means here: both dataset, forget set and instance of loss function? I believe this is actually the main result of the paper, and the authors could restructure the paper to focus on this and make the exposition better explain the assumptions and the impact of this.
-
Can you expand the experimental section to re-elaborate on what the quantities being measured are and why they matter. For example, existing work already discusses the number of steps needed for Langevin unlearning [2]. However, estimating the contraction rate (vs when it is expansive) seems important and the authors could highlight their findings on this.
Below are specific comments on writing which may also help improve the contributions of the paper:
-
I believe the relationship between DP and generalization has been explored somewhat extensively. For example, see [5], and the authors already cite the known tight utility-privacy trade-offs for DP-SCO. I would rephrase the opening intro paragraph.
-
It is known not being DP is important to generalize. This is implied from the tight DP-SCO bounds (which have an explicit additional error term from DP), but also from results on how memorization is necessary for learning [6]. I would change the second paragraph of the introduction (and hence how the rest of the results are motivated) accordingly.
-
Section 2.1 introduces terms only defined later in 2.2 (or in the appendix). I would instead define all terms necessary to understand the paper upfront.
-
Note the geometric decrease in divergence discussed in 3.2 is not new if the update is contractive. Consider rephrasing this or cutting to focus on what the new results are.
Minor comments and typos:
-
Line 376 says “Equation equation”
-
What is the coupling used in Definition 7? Consider restating it there, and given it seems central to theorem 1, bring it into the main body.
[5] Bun, Mark, et al. "Stability is stable: Connections between replicability, privacy, and adaptive generalization." Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 2023.
[6] Feldman, Vitaly. "Does learning require memorization? a short tale about a long tail." Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing. 2020.