- 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
-
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.
-
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:
- Is the condition 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?
- What properties of the data or deletion requests would make the more elaborate methods preferable to the midpoint baselines at the same storage budget?