acceptodds
Under review as a conference paper at ICLR 2027

Certified Unlearning as a Stability Tool: Rates, Limits, and Implications

Abstract

The relationship between differential privacy and the generalization of a learning algorithm has long been an open problem. We prove that the existence of a stable “privacy wrapper” implies generalization, a sufficient condition for generalization weaker than differential privacy. Specifically, we view certified unlearning (CU), which guarantees indistinguishability between unlearned and retrained models, as a privacy wrapper for its learning counterpart. We show that an -unlearning certificate, combined with unlearning stability, controls the learner's algorithmic stability and generalization without requiring differential privacy during learning. Our conversion theorem transfers -unlearning certification to algorithmic stability by replacing full-trajectory stability with that accumulated over the shorter unlearning process. The resulting stability bound depends on the certified unlearning dynamic. For a contractive unlearner with an anchored checkpoint, the learner has stability, uniformly in the training horizon . For a non-expansive (but non-contractive) unlearner, the stability bound is . In the expansive regime, the bound admits no vanishing rate in . Another surprising result is “ununlearnablility”. Reversing the conversion theorem yields a contrapositive impossibility result: for nonsmooth convex, expansive smooth nonconvex, and ill-conditioned strongly convex losses, no stable, shallow, and cheaply certifiable unlearner can satisfy the required guarantees. Experiments with linear heads on frozen CIFAR-10 and SST-2 features confirm the predicted scaling laws and phase transitions (Appendix B).

Primary area:
learning theory
Keywords:
Certified Unlearning, Differential Privacy, Generalization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Hk9jOpenReview ↗
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
  1. The applications of their theory to specific loss families to show the difficulty of unlearning seems impactful.

  2. 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
  1. 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.
  2. The writing also leaves a lot of terminology and choices undefined, not explained and I believe misrepresents past work. For example, rTu,pr_{T_u,p} 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 ηt\eta_t 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:

  1. Given existing Langevin unlearning analysis, can you elaborate on what is being added in the discussion on contractive vs. expansive updates?

  2. 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 Δ\Delta term in Theorem 1 would be controlled or measured.

  3. 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.

  4. 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:

  1. 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.

  2. 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.

  3. 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.

  4. 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:

  1. Line 376 says “Equation equation”

  2. 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.

Reviewer_XTU9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper asks whether the existence of a certified unlearning algorithm implies that the underlying learner is algorithmically stable, and hence generalizes, without the learner itself being differentially private.

The main result, the Conversion Theorem, bounds the learner's replace-one stability τ\tau as τ≤Δ+2r≤Δ+PTV(ϵ,δ)\tau \le \Delta + 2r \le \Delta + P^{\mathrm{TV}}(\epsilon,\delta). Here Δ\Delta is defined as the unlearning stability, rr is the worst-case distance between an unlearned model and the retrained-from-scratch model, and PTVP^{\mathrm{TV}} bounds 2r2r using only the (ϵ,δ)(\epsilon,\delta) certified unlearning certificate and the diameter of the parameter domain.

The theorem is instantiated with anchored unlearners in which every deletion run starts from the same training checkpoint.

Critical strengths
  • [S1] The idea that privacy wrapper as a tool for stabilization is really interesting. The relationship between privacy definitions and stability/generalization of the training provides insights from a different perspective of the privacy research.
Critical weaknesses
  • [W1] The presentation needs significant revision. Notation is introduced in the introduction without being explained. In addition, the main contributions, which as I understand them are the Conversion Theorem and its contrapositive, are overly blended with the results adapted from the anchored certified unlearning literature. As a result, it is hard to tell which theoretical contributions are the authors' own.
  • [W2] As I understand from the proofs, a learner has a stable certified unlearner exactly when the learner itself is stable (see Q1-Q3). The paper's central question therefore might have a trivial answer, the unlearning stability might require learning stability in the first place. It should be either more clear or the perspective needs to be changed. Similarly, Thm. 6 rests on known facts about specific learners being unstable rather than anything specific to unlearning.
Questions for authors
  • [Q1] Can you give an example of a learner for which the Conversion Theorem yields a stability or generalization bound that cannot be obtained by analyzing the learner directly?
  • [Q2] Why focus on anchored unlearners? As I understand it, anchoring makes Δ\Delta easy to bound, but bounding rr then requires the learner's own trajectory gap to be bounded. What does the unlearner add in this setting?
  • [Q3] What is the intuition behind unlearning stability, and what does the definition imply? In the anchored setting, is the unlearner stable only because the learner itself is stable?
  • [Q4] Can you clarify in which scenario we want to achieve unlearning stability? For example, when two independent users completely differing on every aspect are compared (i≠ji \neq j), why does one need a bound on this?
Reviewer_qAqvOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies the relationship between differential privacy (DP) and generalization abilities of a learning algorithm AA. More precisely, it explores the direction of when existence of a certified unlearning procedure can imply stability and generalization of AA.

Its main Wasserstein comparison bounds learner stability by deletion-identity stability plus twice the distance between unlearning and retraining. The authors distinguish directly controlled endpoint distances from certificate-based bounds involving the parameter-domain diameter. They analyze anchored deletion procedures under contraction, nonexpansiveness, and PL/quadratic-growth assumptions, and propose conditional impossibility results. The contractive rate is (O(1/n)O(1/n)) under the stated checkpoint comparison; the nonexpansive (n−1/3n^{-1/3}) rate is a conditional optimized (W1W_1) bound, with logarithmic and (δ\delta) terms. Experiments on CIFAR-10 and SST-2 provide finite-pool sensitivity diagnostics.

Critical strengths

I feel Theorem 1 is convincing and interesting but it is difficult the parse because of the unwinding of the multitude of notations and assumptions. It would be nice to have two simple running examples, one where the framework works, and one where it does not.

Critical weaknesses
  1. Some of definitions and assumptions need clarity and more discussion on why those definitions or assumptions and not some other similarly looking ones, as discussed in the questions below? Ideally, what concrete examples ar covered by the framework mentioned, and what is out of reach would be ideal, since there's a lot of notation.

  2. Applications to some concrete models of data would be desired, as discussed in the questions below. Moreover, given that this is a long and technical paper, and in the age of AI, a Lean certificate would be desired as well, just to have a confirmation that no results are false

Questions for authors
  1. With the advent of Gaussian differential privacy (GDP), people have utilized the hypothesis testing based f−f-DP framework over the (ε,δ)(\varepsilon, \delta) formulation in the context of certified unlearning Gaussian certified unlearning in high dimensions: A hypothesis testing approach. Could the authors translate their results into this interpretable and more flexible ff-DP framework?

  2. To me, definition 6 measures the absolute difference between the expected test loss (E[R(A(D))]=E[ℓ(A(D),Z)]\mathbb{E}[R(A(D))] = \mathbb{E}[\ell(A(D), Z)] with Z⊥DZ\perp D) and the expected training loss (E[RD(A(D))]=E[1n∑j=1nℓ(A(D),Zi)]\mathbb{E}[R_D(A(D))]= \mathbb{E}[\frac{1}{n}\sum_{j=1}^n \ell(A(D), Z_i)] with D=(Z1,⋯ ,Zn)D=(Z_1, \cdots, Z_n)) to be small. Could the authors clarify the dependence of τ\tau on the choice of loss ℓ\ell and data distribution PP, and nn (similar explanations for quantities introduced throughout the definitions)?

  3. In comparison, definition 7 measures the stability of the model parameter itself. Could you authors clarify, whether a form permutation invariant learning algorithm would collapse the average in Equations 12 and 13, since each term within the sum is the same quantity?

  4. A collection of definitions of stability are introduced in the appendix. Could you authors clarify, if there is any hierarchy among the definitions? Moreover, from a quick look it seems that most of them are population versions and require us to take expectations over the data distribution and are therefore difficult to verify in practice. Consequently, please explain the utility of these guarantees in practice.

  5. Could the authors clarify on the necessity of bounded parameter set Θ\Theta? How practical is this assumption?

  6. To my understanding, in definition 5 (Equation 10) and many other places, the authors assume that the learning algorithm AA is randomized. It seems to me that large class of natural algorithms will be missed by these definitions. For example, definition 1 becomes trivial unless AA is randomized. Could you authors clarify, how would they address this issue?

  7. Moreover, in definition 1 in several other places, the requirement on allowing every subset of DD as a forget set seems to strong, as its better to retrain from scratch once we want to unlearn most of our training data DD. Please make sure to address this issue in the context of previous papers discussing machine unlearning.

  8. Could the authors give a concrete collection of learning problems where the entire setup that they have bulit applies, and how the conclusion looks like? The examples that come to my mind are regression models like linear or logistic regression, generalized linear model or two layer neural network or signal plus noise models θ+Z\theta+ Z for vectors or matrices or non-convex type models like Z2Z_2 synchonization or Tensor PCA (θ⊗k+Z\theta^{\otimes k} + Z).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.