- Rating
- 4
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper proves near tight upper-lower bounds on the utility unlearning algorithms can have (with DP like unlearning guarantees) for smooth strongly convex objectives. Their algorithm, which provides the upper-bound, notes that ERM has optimal error rates and so designs a mixture distribution which outputs near ERM solutions with high probability while still also outputting models near the desired retrained from scratch solution. The lower bound comes from a packing argument to show there are distributions which have different optimal solutions but you can remove samples and have identical ERM solutions on the retain set. Overall this paper makes significant progress on our understanding of unlearning and how it differs from differential privacy and other Trustworthy ML goals.
Critical strengths
-
The results on upper and lower bounds are strong and novel. I agree with the authors that this lays the foundation for significant follow-up work.
-
The presentation and techniques are elegant. In particular, I found the intuition that all one needs to do is choose to be near ERM before deletion request very insightful and made the rest of the proofs clear. I also appreciated that the authors chose to strengthen the utility assumptions from past work (i.e., the original training algorithm needs to have high utility) to make it more in line with the often cited goals of unlearning.
Critical weaknesses
I can only name very minor and out-of-scope weaknesses.
-
I believe the results could be extended to non strongly convex losses. I found little discussion on this, though the authors acknowledge removing condition number to do so is important.
-
Future work could now tackle getting computational costs down; the proposed algorithm has relatively high unlearning costs.
Questions for authors
I had no real questions after reading the paper and proofs: most of my margin notes were “cool!”. Below are mostly questions out of curiosity and the authors do not have to answer them.
-
Could the upper-bound results be extended to non strongly convex settings? In particular, DP phased ERM achieves optimal DP convex rates by reducing to a series of regularized objectives where the regularization is dependent on the desired error: is there a reason an analogous algorithm for unlearning would not work?
-
In the definition of approximate unlearning, could you not set without loss of generality; as in define the original training algorithm to be the emptyset unlearning algorithm given it has utility guarantees too? This would just make it clearer the simpler “training algorithm is fixed” view is equivalent to this setup, and given the matching upper-bounds under the weaker assumption, effectively say the literature can just focus on comparing unlearning to fixed training algorithms. Assuming this is correct, I think this is something valuable to further highlight.
We thank the reviewer for their encouraging feedback. In light of the diverging assessments of our work, we hope the reviewer will reiterate their confidence to the AC.
We could indeed use regularization to obtain an upper bound for non-strongly convex unlearning. Assuming global convexity and smoothness of the population objective, with a minimizer in W, the resulting rate is
\lesssim \frac{1}{\sqrt n} +\left(\frac{m}{n}\right)^{2/3} e^{-\frac{2\varepsilon}{3(d+2)}}$$ (holding other parameters constant). However, it is unclear whether iterative localization, analogous to DP phased ERM, improves this bound further: data-dependent deletion requests can make phase $i$’s output depend on phase $i+1$’s data batch, preventing direct application of the standard DP utility analysis. We would be happy to add this corollary and discussion to the revision. > In the definition of approximate unlearning, could you not set $\tilde{A}(\varnothing, Z) := A(Z)$ without loss of generality? **Yes, under our utility definition.** Defining $A(Z):=\widetilde A(\varnothing,Z)$ gives the equivalent requirement $$\widetilde A(U,Z)\approx_{\varepsilon,\delta}A(Z\setminus U),$$ and our utility guarantee already ensures that this fixed reference learner is accurate at every allowed dataset size. We agree that this equivalence is worth highlighting and will make it explicit.