acceptodds
Withdrawn from ICLR 2027

Future Deletions from Past Retraining: Exact Machine Unlearning via Sparse Retraining Archive

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Exact machine unlearning seeks to reproduce retraining outcomes after designated data are removed, but repeated retraining becomes impractical as the number of possible deletion combinations grows exponentially. In this paper, we study the recovery of all deletion targets from sparse retraining archives containing models retrained for only a small fraction of deletion requests, without further data access or retraining. For ridge regression, we show that all deletion responses lie in a low-dimensional space and satisfy a shared affine matrix equation when the curvature contributed by deletable data is low rank. This structure yields a convex decoder that recovers unseen retraining targets from archived models. Under independently and uniformly sampled deletion requests, we establish upper and lower bounds showing that, at fixed rank and confidence, the archive size required for exact recovery grows only linearly with the number of deletable groups despite the exponential catalog size. We further derive uniform recovery bounds for noisy archives, characterizing rank-dependent error amplification, and extend the analysis to approximately low-rank deleted curvature through an explicit spectral-tail term. Controlled experiments recover all 4,096 deletion targets from 96 archived models and support the predicted acquisition and error-amplification mechanisms. Further experiments assess noisy recovery in the convex special case and spectral-tail effects.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Exact Machine Unlearning, Sparse Retraining Archives, Ridge Regression

Reviews

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

The work put forward explores the intersection of exact machine unlearning and model composition. The paper outlines that sparse retraining archives enable exact catalog recovery, using sets of previously retrained models alongside the deletion subsets, to approximate the unlearned model for an arbitrary subset. Through theoretical analysis, the work introduces substantive bounds on the acquisition and precision required of the retraining archive to achieve guaranteed unlearning results. Finally, the theoretical claims are applied in empirical examples to observe the theorised results in deployed settings.

Overall this work presents an interesting delve into the combination of model composition and machine unlearning, offering evidence justifying further work in this area. However, the lack of clarity in presentation, confusing intention, and my concerns regarding the setting in which they place their analysis makes it difficult to recommend acceptance at this time. Given sufficient clarifications from the authors, I would be open to increasing my score.

Critical strengths
  • The work appropriately backs up its theoretical claims with varied empirical measurements across a variety of data modalities and unlearning benchmarks including both visual and text-based tasks.
  • The theoretical claims of the work, while difficult to read, are strong and provide an interesting insight into the intersection of machine unlearning and model composition - which motivates further exploration into this realm.
Critical weaknesses
  • The intention and contribution of the paper is unclear, and difficult to follow. It was confusing and difficult to identify what exactly the authors were trying to present, propose, or analyse.
  • While the main contribution the paper puts forward is the theoretical analysis and bounds - I struggle to find the practicality in the setting the authors have outlined particularly with reference to the existence and availability of this construction of the retraining archive in unlearning settings.
Questions for authors
  • Can the authors outline justifications for studying this setting of the problem?
Reviewer_krfLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how to achieve exact unlearning based on past retraining results without further data access or retraining. The authors show that for ridge regression with low-rank deleted curvature, deletion responses lie in a low-dimensional space and satisfy a shared affine matrix equation. Experiments in controlled settings demonstrate the recovery of all deletion targets based on a few archived retrained models.

Critical strengths
  • This paper studies an interesting exact unlearning question. The authors provide substantial theoretical analysis of the acquisition upper and lower bounds and noise amplification, and develop recovery algorithms.
  • The experiments validate the effectiveness of the proposed recovery algorithms by recovering all deletion targets based on a few archived models.
Critical weaknesses
  • My concern with this paper would be its practical applications. The theoretical analysis largely relies on ridge regression and low-rank deleted curvature. Furthermore, the acquisition complexity is 2r2^r. This makes the real-world application of these results seem limited. The experiments are also conducted in a controlled setting. While the authors provide a quite interesting analysis, it can hardly be transferred to real applications without further evidence.
  • My second concern is linked with the previous one. The authors study the recovery based on a few archived models from past retraining. However, the cost of obtaining such archived models can be high given a large real-world original dataset. This may also limit the practical application.
  • The exact decoder is convex, but the general noisy decoder requires nonconvex rank constraints. The authors have not yet provided an efficient solution.
Questions for authors
  • Can the authors provide more real-world implications of the study? For example, can the authors explain real applications of the controlled settings or add experiments in more practical settings?
  • How does recovery change given small subsets or cumulative deletion requests?
Reviewer_HKijOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies machine unlearning (ridge regression in particular) and how the model parameter would evolve after deleting of random subsets of data groups. Under low rank assumption on the deleted curvature matrix, the authors show that the deletion responses lie in low dimensional (r-dimensional) subspace and have a 2r2^r approximation for all 2M2^M deletion subspace.

Critical strengths

Under the low rank assumption, the result of the existence of low dimensional space for machine unlearning is indeed interesting.

Critical weaknesses
  1. Much of the result rests on the low rank assumption rank(Hdel)≤rrank(H_{del})\leq r. How is this justified in practice? This assumption is what makes the rest of the paper, but for r to be much smaller than M (the interesting region) every feature vector across M groups has to lie in the same r-dimensional subspace. This is very unreasonable to assume.

  2. If we can accept the previous assumption, then the rest of the paper is mostly straight forward.

  3. Some of the constants are super large, which defeats the point of having a useful bound. Example: Appendix B.3 uses constants such as 2e6 for CrobC_{rob}.

  4. The numerical results are not convincing: in table 9, s=2 PSD seems to have an error that exploded to 1055, which needs explanation.

  5. To make my concern of the first weakness even more pronounced, Appendix D.4.1 tested the true rank of HdelH_{del} and reported 512 (the original M), so there is no numerical support for the most important assumption of the paper, which makes the rest of the results not applicable even in a simple setting like CIFAR. The authors had to force low rank features when doing experiment on more advanced models, which is not a kosher practice.

Questions for authors

See weakness, especially the first one.

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

Related papers

Discussion (0)

Sign in to comment.