acceptodds
Under review as a conference paper at ICLR 2027

How Much Must a Ridge Learner Remember to Delete Data?

Abstract

An offline ridge learner retains a finite-bit summary; a decoder receives deleted records and approximates the retained-data optimum without accessing the retained records. How do regularization, accuracy, and deletion size determine the necessary memory? For bounded grid inputs, , and a fixed deletion fraction, the worst-case memory is bits within one factor , for sufficiently small additive or relative error . When and the deletion budget vanishes, the additive law becomes within a precision logarithm. For bounded noiseless teachers, a joint rank law is matching when is bounded. A determinantal response envelope extends its upper bound to every budget with an overhead. A routing construction proves that an overhead is necessary along explicit families, despite a common teacher, original optimizer, and legal requests. Thus the law persists within polylogarithmic factors for , while extensions beyond that scale can fail. The lower bounds allow pointwise randomized success; deterministic summaries attain the upper bounds. Residual importance sampling gives a polynomial bit encoder for a general-label DPP bound. Controlled and frozen-feature experiments assess accuracy and storage. These guarantees concern optimization utility, not distributional certification of unlearning.

Primary area:
learning theory
Keywords:
machine unlearning, ridge regression, memory complexity, finite-bit summaries, determinantal point processes

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_c9GtOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies how much information a ridge-regression learner must store to approximate retraining after deleting data, without accessing the remaining records. It proposes encoding methods, proves nearly matching memory bounds in several settings, and gives error bounds that can be computed from the saved information and deleted records. Experiments on synthetic data and fixed image features compare storage requirements and approximation errors across methods.

Critical strengths
  1. I consider the nearly matching upper and lower memory bounds the paper’s strongest contribution. They establish how close the proposed methods come to the best possible storage requirements. For me, this is the main reason to support acceptance, even though the practical benefits of some algorithmic extensions are less clear.

  2. I also find the computable error bounds in Section 6 useful. Being able to certify a target error in the ridge objective for a particular deletion request is valuable since most of the time exact retraining is unavailable for comparison.

Critical weaknesses

The authors acknowledge the mixed empirical results, but I still find the practical case for the additional methods limited. Legal midpoint reduces excess ridge loss compared with fixed midpoint in 123 of 216 configurations. Its error bound certifies the chosen tolerance in 146 configurations, compared with 139 for fixed midpoint. The more elaborate methods generally perform worse at the same storage budget, leaving it unclear when their additional complexity is worthwhile. The compression gains highlighted in Table 1 also occur outside the regime where the worst-case bounds predict compression. While this is consistent with the theory, the paper provides limited guidance on how to use those bounds to choose storage in practice.

Questions for authors

Clarification questions:

  1. Is the condition n=Θ(d/ρ)n=\Theta(d/\rho) essential to the two-regime memory law in Theorem 3? Which parts of the result extend to a fixed sample size with a varying deletion budget?
  2. What properties of the data or deletion requests would make the more elaborate methods preferable to the midpoint baselines at the same storage budget?
Reviewer_9TctOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper discusses the memory requirements of approximate unlearning for ridge regression based on the Gram matrix-based exact continual unlearning method from Quan et al. This paper develops compressed Gram matrix summaries and analyses how the required memory storage depends on regularization, target accuracy and deletion budget. It provides both the theoretical upper and lower memory bounds for compression and the unavoidable memory requirement. The empirical analysis shows the trade-off between storage and accuracy, and the error bounds.

Critical strengths

The paper provides an extensive theoretical analysis of the proposed method, including how regularization affects the memory required for approximate unlearning in ridge regression. To the parts I managed to check during the review period, the mathematical claims appear to be coherent and correct.

Critical weaknesses
  1. Motivation of the work: The practical motivation for approximate unlearning in ridge regression is insufficiently justified. The method from Quan et al. already provides an efficient exact unlearning method for ridge regression, and the Gram matrix imposes a modest memory cost at common feature dimensions (e.g. 512, 1024, etc.). Although the experiment shows that, at rank 32, the proposed method requires 132 KiB for summaries compared with 1,030 KiB for exact statistics, the absolute memory savings are modest by modern hardware standards. It remains unclear when these savings justify the approximation error and additional complexity.
Questions for authors

The paper itself provides extensive insights into the theoretical properties of the proposed method. Thus, I do not have questions about the theory. However, the authors need to clarify the practical motivation for the work. Otherwise, the problem appears to have been fabricated to suit the proposed method rather than motivated by a concrete need.

  1. Can the authors identify concrete scenarios in which a ridge regression system requires approximate unlearning under memory constraints so strict that even the modest absolute memory savings reported are critical?
Reviewer_STQvOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper seems to be quantifying memorization requirements for unlearning a ridge-regression model.

Critical strengths

N/A

Critical weaknesses
  1. This paper is impossible to read. I'm not sure how much human effort went into the writing here. The abstract is hard to decrypt. One sentence to another -- there is no context. The intro is poorly written. A very small example: lines 45-46 convey nothing. Another example: the last two paragraphs of Section 1 are very confusing. There is no transition from one sentence to another. Everything seems to be said out of context, even paragraph to paragraph! I am not going to waste my time reading this.
Questions for authors

N/A

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.