acceptodds
Under review as a conference paper at ICLR 2027

RePASTA-CU: Certified Unlearning Beyond Global Smoothness and Uniform Gradient Bounds

Abstract

Certified machine unlearning seeks to remove the influence of deleted data without retraining from scratch. Existing first-order guarantees for nonconvex models typically impose global smoothness or uniformly bounded gradients, and some methods use a comparison target different from retraining on the retained data. We propose RePASTA-CU, a checkpoint-based method that keeps non-private training and uses the model obtained by retraining on the retained dataset as its comparison target. It stores a checkpoint after clipped SGD updates, applies PASTA updates using only retained data after deletion, and adds Gaussian noise at release. Public clipping and projection bound the pre-release distance between the unlearned model and the retained-data retraining model; calibrating the release noise to this bound yields bidirectional -certified unlearning without smoothness, Lipschitz continuity, weak convexity, or uniformly bounded gradients. Under weak convexity on a bounded convex domain and a quadratic-growth bound on the raw second moment of stochastic subgradients, we prove an root-mean-square Moreau-stationarity rate before release noise, with a separate noise-dependent term for the released model. Experiments on synthetic, image, text, federated, and convex tasks compare RePASTA-CU with R2D and other certified-unlearning methods across utility, certificate scale, stability, and deletion cost.

Primary area:
learning theory
Keywords:
Certified unlearning, machine learning

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_EVfJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes RePASTA-CU, a pair of learning-unlearning algorithms using non-private training and PASTA updates. The algorithms allow for deletion of training samples and update of the model by using a checkpoint of the initial learning algorithm. The authors establish that the proposed RePASTA-CU is (ϵ,δ)(\epsilon, \delta) certified unlearning, removing the assumptions of bounded gradient oracles, smoothness Lipschitz continuity and weak-convexity of prior literature. They provide also a utility bound under weak convexity and quadratic growth condition on the subgradients, establishing a O(K−1/6)\mathcal{O}(K^{-1/6}) RMS rate before publishing noise injection is conducted. Experiments across different datasets compare the proposed method with other common baselines on unlearning.

Critical strengths
  1. The proposed method is shown to be (ϵ,δ)(\epsilon, \delta) certified unlearning without the assumptions of bounded gradient oracles, smoothness Lipschitz continuity and weak-convexity of prior literature.
  2. Under additional assumptions a rate is established on the RMS before publishing noise is added.
  3. The proposed unlearning method seems to perform a deletion and update of the model significantly fast with respect to an alternative being retraining on the retained dataset.
Critical weaknesses
  1. The paper is difficult to parse and there are few places where notation is not defined, making it difficult for the reader to follow. More specifically,
  • in line 86 condition (7) is referenced even though define only later, breaking the pace of the presentation.
  • In line 132, m is not prior defined
  • In line 142, M is not defined
  • In lines 149-150, G is not defined.

I think a proper rewriting of the paper will improve significantly the presentation and will highlight the contributions.

  1. A rate of O(K−1/6)\mathcal{O}(K^{-1/6}) for the RMS before publishing noise injection is established in the paper. However, there is no comparison with any rates that might exist in prior results so that the reader can appreciate the corresponding contribution. In general, comparison of the established results with the literature is largely lacking in the paper.
  2. The established algorithm does not seem to perform better in all the experiments than prior baselines. More specifically, in Table 1 the method performs better only in the AG News task. I would expect a proper comparison and description of why is that motivating better the use of the algorithm in practice.
Questions for authors

Can you please define the aforementioned in Weaknesses constants? Can you please elaborate on the performance of the method with respect to other prior state-of-the-art baselines?

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

RePASTA-CU studies certified unlearning without global smoothness or uniformly bounded raw gradients. It reuses a training checkpoint, performs retained-data updates using clipped PASTA, and adds Gaussian release noise calibrated to a worst-case parameter-distance bound. Under additional weak-convexity and stochastic-gradient moment assumptions, it also establishes a Moreau-stationarity guarantee.

Critical strengths

Removing global regularity assumptions is a relevant direction for certified unlearning, particularly for nonconvex and nonsmooth objectives.

The paper distinguishes the assumptions required for certification from those required for optimization utility, and uses the specified retained-data retraining algorithm as its reference.

The experiments cover several model families and report both released utility and deletion cost.

Critical weaknesses

The theoretical contribution beyond existing components needs stronger justification. The checkpoint reuse, Gaussian calibration, and anchored optimization mechanism come from prior work. Although adapting these components can require additional analysis, the manuscript does not sufficiently establish what substantive technical advance is needed beyond this combination.

The benefit of removing regularity assumptions is unclear under the resulting certificate. A quantitative comparison of distance bounds and required noise across deletion fractions and update budgets would strengthen the contribution.

The experiments do not isolate the benefit of PASTA. The reported speedup over retraining primarily reflects the inherited checkpoint-reuse strategy. Matched comparisons using the same checkpoint, clipping, projection, release-noise calibration, and update budget are needed to identify the value of the anchored updates.

The experimental results use only one seed. The reported utility differences cannot be interpreted as improvements at the same level of certification budget or noise magnitude.

Questions for authors

Please see weaknesses

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

The paper proposes RePASTA-CU, a checkpoint-based certified unlearning method. Training runs without privacy noise and stores a checkpoint before the final K steps. On a deletion request, the method reruns those K steps with PASTA on the retained data and adds Gaussian noise once at release. Certification against the retrained model is argued through clipping and projection, and a Moreau-stationarity utility bound is given under weak convexity. Experiments on text, image, and federated classification compare released accuracy and deletion time with retraining, R2D, and SCRUB.

Critical strengths

The problem setting is well chosen: the method keeps retraining on the retained data as the comparison target while removing the smoothness and bounded-gradient assumptions that prior first-order methods rely on. The proofs are short and I did not find errors in them.

Critical weaknesses
  1. The certification argument is agnostic to the Phase-2 update rule, and the utility argument is agnostic to the unlearning setting. The distance bound that calibrates the release noise comes only from the clipping radii and step sizes, and the authors note in Section 4.1 that the domain diameter could be used instead. So the checkpoint, the PASTA updates, and the retained-data training play no role in the guarantee. On the other side, the utility theorem is a convergence result for PASTA from an arbitrary starting point and does not involve the deleted data or the retrained model. The conclusion acknowledges that the two analyses use different parts of the construction. Taken together, the paper is closer to R2D with a drop-in PASTA optimizer than to a new certified-unlearning method.
  2. There is no experiment that evaluates certification or privacy. The values of epsilon and delta used in the experiments are not reported, and there is no forget-set accuracy, membership inference, or any other measure of whether the deleted data was actually removed. Only test accuracy and deletion time are shown.
  3. In addition, the deep-network experiments are run with a single seed, even though the gaps between methods in Table 1 are only a few tenths of a percentage point. Without variance estimates, these differences cannot be read as meaningful.
Questions for authors
  1. Can the authors provide any empirical evidence that the deleted data is removed, beyond test accuracy?
  2. The abstract is hard to follow without prior knowledge of this subfield. A clearer abstract organized around problem, method, result, and conclusion would help.
  3. “Arda et al. (Fazla et al., 2026)” in Section 3 should be corrected.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.