Pith. sign in

REVIEW 3 major objections 5 minor 56 references

System-Aware Unlearning Algorithms: Use Lesser, Forget Faster

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Traditional unlearning assumes an attacker who knows the full remaining dataset; the paper replaces that with a system-aware definition under which a selective-sampling linear classifier can unlearn exactly while storing only a sublinear…

desk verdict The paper's system-aware unlearning definition and the exact sublinear-memory linear algorithm are real, but the proof of the key monotonicity theorem (4.2) has a repairable indexing gap and the general-function extension is shakier. read the letter →

arxiv 2506.06073 v1 pith:YFW4VPIK submitted 2025-06-06 cs.LG

Linda Lu , Ayush Sekhari , Karthik Sridharan This is my paper
classification cs.LG
keywords machineunlearningsystem-awareselectivesamplingsamplecompressioncoresetslinearclassificationdeletioncapacitydataprivacy
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Machine unlearning traditionally demands that after a deletion request the model be indistinguishable from one retrained on the full remaining dataset, a bar that forces exact unlearning algorithms to store the entire sample. The paper argues this is the wrong threat model: a realistic attacker can only see what the system actually stored, not every point it ever encountered. It introduces system-aware unlearning, where the post-deletion state of the system must be indistinguishable from the state produced by running the same algorithm on $S' \setminus U$ for a fixed subset $S'$ of the training set, and shows that algorithms which learn from a small core set can meet this definition exactly. The concrete payoff is an exact system-aware unlearning algorithm for linear classification whose memory is $O(dT^\kappa \log T)$, sublinear in the sample size, with corresponding bounds on deletion capacity, excess risk, and deletion time.

What carries the argument

The load-bearing object is the state-of-system mapping $I_A(S,U)$ together with the fixed subset $S' \subseteq S$ that the definition lets the algorithm choose; the paper sets $S' = C(S)$, where $C(S)$ is the core set of points a selective sampler queried. Core-set algorithms satisfy $A(S) = A(C(S))$, so the system only ever stores $C(S)$. The property that carries the argument is monotonicity: the BBQSAMPLER's query condition is label-independent, so deleting points strengthens the query statistic, giving $C(C(S)\setminus U)=C(S)\setminus U$ for every deletion set. This means no re-sampling is needed at unlearning time; the update is just an ERM re-solve on $C(S)\setminus U$, and in the general case the same role is played by a generalized sampler whose query complexity is controlled by an eluder-dimension-like quantity of the function class.

What would settle it

To test the core claim, search for the smallest dataset $S$ and deletion set $U$ for which running the selective sampler on $C(S)\setminus U$ fails to query all of $C(S)\setminus U$. Theorem 4.2 asserts this never happens; a counterexample would break the equality $C(C(S)\setminus U)=C(S)\setminus U$ and with it the exactness guarantee, since the unlearned state would no longer coincide with a fresh run on the core set.

Watch

Extended reading notes

Core claim

The central discovery is that exact unlearning becomes easy once the guarantee is tied to what the system stores rather than to the whole dataset. The paper's Algorithm 1 learns a linear classifier with a selective sampler and takes $S' = C(S)$, the set of queried points. Because the sampler's query condition $x^\top A^{-1} x > T^{-\kappa}$ depends only on inputs, not labels, deleting a point can only raise the query statistic for every remaining point; hence running the sampler on $C(S) \setminus U$ re-queries exactly $C(S) \setminus U$. The unlearned state $I_A(S,U) = (A(S,U), C(S)\setminus U)$ is then identical to the state produced by direct learning on $C(S)\setminus U$, so Algorithm 1 is exact system-aware unlearning, with $\varepsilon=\delta=0$, and the same monotonicity gives an extension to general function classes through a generalized sampler.

Load-bearing premise

The whole guarantee rests on the threat model in Definition 2.3: an attacker can see only the system's stored state after unlearning and cannot reconstruct the full remaining dataset $S \setminus U$; if a realistic attacker can get $S\setminus U$, the exactness of Algorithm 1 does not imply privacy against a retraining comparison.

Editorial extensions

If this is right

  • Exact unlearning for linear classification is achieved with $O(dT^\kappa \log T)$ memory, sublinear in the sample size, a regime the paper states is impossible under the traditional unlearning definition.
  • Deletion requests outside the core set are processed for free, so the practical deletion capacity is governed by how often deleted points fall in $C(S)$; under a uniform deletion distribution the system can tolerate $\Theta(K T / (d T^\kappa \log T))$ total deletions with high probability.
  • The expected deletion time under uniform deletions is at most $O(d^3 T^\kappa \log T / T)$, which for large $T$ beats the per-deletion cost of exact retraining-based unlearning.
  • The approach extends to general function classes: exact system-aware unlearning holds for any class where a monotonic selective sampler exists, with memory bounded by the class's eluder-dimension-like quantity, and with uniform stability of the regression oracle controlling the deletion capacity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Accepting system-aware unlearning changes what "deleted" means legally and practically: the guarantee is indistinguishability from a system that only ever stored the core set, not from one trained on all $S\setminus U$, so an auditor who can reconstruct $S\setminus U$ would not be satisfied.
  • The monotonic query-condition trick suggests a general design recipe for unlearning-friendly learners: make each algorithm's data usage monotone under deletion so unlearning is an exact reversal of learning; other online or streaming algorithms with label-independent updates may inherit the same property.
  • A complementary route the paper leaves open is approximate system-aware unlearning: perturbing the core-set ERM with differential privacy (as in the paper's interpolation example) could cut memory or computation further, or handle non-monotonic samplers, at the cost of $(\varepsilon,\delta)$-indistinguishability.
  • The strongest practical test would be on linear probing layers of large pretrained models, where the core set is the small set of influential probe examples; measuring deletion time, memory, and membership-inference resistance there would show whether sublinear-memory exact unlearning survives real representation spaces.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes a new notion of machine unlearning, called system-aware unlearning, in which the guarantee is stated with respect to a subset S' of the original sample S that the learning algorithm actually relies on; the attacker is assumed to observe only the state-of-system after unlearning, not the full remaining dataset S\U. The authors argue that this generalizes traditional certified unlearning (which corresponds to S'=S) and that core-set and sample-compression algorithms are natural instantiations. The main algorithmic contribution is an exact system-aware unlearning algorithm for linear classification (Algorithm 1), built on the BBQSAMPLER selective-sampling procedure, with claimed memory O(d T^kappa log T), sublinear in the sample size for kappa<1, together with a deletion-capacity bound and an expected-deletion-time analysis. A second algorithm (Algorithm 2) extends the scheme to general function classes via a pool-based active-learning query rule. The paper also reports experiments on two datasets comparing Algorithm 1 with SISA and exact retraining.

Significance. The definitional proposal is a substantive and debatable contribution: it makes explicit that the strength of an unlearning guarantee depends on what an attacker can observe, and it provides a framework in which algorithms that rely on few stored points can achieve exact unlearning at low memory cost. If the technical results are correct, the linear-classification algorithm is notable because it evades the lower bound of Cherapanamjeri et al. (2025) by changing the threat model rather than by contradicting it. The paper is also honest that the guarantee is relative to the new definition and that a traditional attacker who can recover S\U would not be protected. The exactness argument is by construction rather than circular, and the selective-sampling connection is a useful conceptual bridge. However, several load-bearing proof steps in the current manuscript are incorrect or incomplete, so the advertised results are not yet established as written.

major comments (3)
  1. [Section 4, Theorem 4.2 and its proof] The proof of Theorem 4.2 contains a false inequality that is load-bearing for the exactness claim. Algorithm 1 queries at time t when x_t^T A_{t-1}^{-1} x_t > T^{-kappa}, but the proof states that a queried point satisfies x_t^T A_t^{-1} x_t > T^{-kappa}. These are not equivalent: by Sherman-Morrison, x_t^T A_t^{-1} x_t = q/(1+q) with q = x_t^T A_{t-1}^{-1} x_t, and q/(1+q) can be below T^{-kappa} even when q > T^{-kappa}. The displayed Sherman-Morrison comparison is then performed with A_t, so the argument does not establish that rerunning on C(S)\U queries every remaining point. Since Theorem 4.1 relies directly on Theorem 4.2, the central exactness proof has a gap. The gap appears repairable, e.g. by working with A_{t-1} and using that deleting x_j before time t replaces A_{t-1} by the smaller matrix A_{t-1} - x_j x_j^T, whose inverse is larger, but the manuscript as written is not correct.
  2. [Appendix D, Theorem D.8 and Lemma D.4 / Corollary D.5] The same pre-update/post-update confusion appears in the query-complexity argument that supports the sublinear-memory claim. In the proof of Theorem D.8, r_t is defined as x_t^T A_t^{-1} x_t, and the query count is written as NT = sum over {r_t > T^{-kappa}} 1. But Algorithm 1 queries when x_t^T A_{t-1}^{-1} x_t > T^{-kappa}; for points with leverage just above threshold, the post-update value q/(1+q) is below T^{-kappa}, so the displayed sum undercounts the true number of queries. A correct bound would use the pre-update leverage or threshold the post-update leverage at T^{-kappa}/(1+T^{-kappa}). In addition, Lemma D.4 and Corollary D.5 are stated for arbitrary x with no precondition, but the asserted bound x^T A_{T\U}^{-1} x <= e T^{-kappa} fails for directions that have not been observed (the quadratic form can be as large as 1/lambda). The induction proof has no valid base case. These issues affect the memory bound of Theorem 4.3 and the stability estimates used for deletion capacity, although they also appear to be repairable.
  3. [Section 5, Theorem 5.2 and its proof] The exactness of Algorithm 2 for general function classes rests on Theorem 5.2, but the proof as written does not establish the claimed monotonicity of the GENERALBBQSAMPLER. The key step asserts that the argmax of D^2 over the remaining pool is unchanged after deleting a previously queried point. Coordinate-wise monotonicity of D^2 under deletion does not imply this: removing a point from the denominator can increase D^2(x; .) by different factors for different x, so the greedy maximizer can change, and a point that was queried in the original run may never be selected in the rerun. The displayed expression D^2(x, Q'_l* \ {x_j}) is also not the quantity that the algorithm uses, since x_j is not in the rerun's queried set. Because Theorem 5.1 depends on Theorem 5.2, the general-function-class exact-unlearning claim is not established as written. The authors should either prove the property under additional assumptions on the query criterion, modify Algorithm 2 so that the unlearning update actually reruns the sampler on C(S)\U and store the resulting queried set, or substantially qualify the general-class contribution.
minor comments (5)
  1. [Section 3, Theorem 3.1] The proof and surrounding text refer to 'the traditional definition of unlearning (Definition 2.3)', but Definition 2.3 is system-aware unlearning; the traditional definition is Definition 2.1.
  2. [Section 4.1, first paragraph] The text says 'the deletion capacity bound in Theorem 4.1 only applies to core set deletions', but the capacity bound is Theorem 4.3; Theorem 4.1 is the exactness statement.
  3. [Algorithm 1 and Theorem D.8] Algorithm 1 states 0 <= kappa <= 1, but Theorem D.8 and its proof use quantities such as 1/kappa and assume kappa in (0,1); the endpoint case kappa=0 should be clarified or excluded.
  4. [Appendix D, Lemma D.4] Lemma D.4 should state the condition under which the initial bound x^T A_T^{-1} x <= T^{-kappa} holds (e.g. for points that were unqueried at their arrival time), since the claim as written is false without this restriction.
  5. [Algorithm 1, lines 17-20] The function returns only sign(w^T x), while the state-of-system definition in Theorem 4.1 includes (A(S,U), C(S)\U); the return statement should make explicit that the remaining core set and the updated matrices are part of the returned state.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: Algorithm 1's exact system-aware guarantee is verified against Definition 2.3 by construction, and the memory/risk tradeoffs rest on independent external bounds.

full rationale

The derivation chain is self-contained with respect to its own definition. Definition 2.3 specifies a new comparison target S'\setminus U, and Theorem 4.1 verifies Algorithm 1 against that target: after deletion the state is (ERM(C(S)\setminus U), C(S)\setminus U), and the algorithm run on C(S)\setminus U has the same state provided C(C(S)\setminus U)=C(S)\setminus U. This equality is a claimed property of the BBQSAMPLER query rule, not an assumption of the desired indistinguishability; the exactness conclusion is not used as an input. The query-complexity bound N_T=O(dT^\kappa\log T), the excess-risk bound, and the deletion-capacity analysis use standard external results (Cesa-Bianchi et al. 2009; Dekel et al. 2012; Agarwal 2013; Kakade and Tewari 2008; Gentile et al. 2022; Ben-Hamou et al. 2018), so no fitted parameter is later renamed as a prediction. The citation to Cherapanamjeri et al. (2025), which includes co-author A. Sekhari, is used to motivate the new threat model and the contrast with traditional unlearning, but no proof step depends on that lower bound, so it is not load-bearing self-citation. One non-circular correctness caveat: the published proof of Theorem 4.2 writes x_t^T A_t^{-1} x_t > T^{-\kappa} although the query condition in Algorithm 1 is x_t^T A_{t-1}^{-1} x_t > T^{-\kappa}; because A_t = A_{t-1} + x_t x_t^T, the displayed inequality does not follow directly. This is a gap in the proof as written, not a circularity, and it appears repairable by comparing with A_{t-1} minus the deleted point. It does not change the circularity verdict.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The paper's claims rest on the new system-aware threat model and on standard selective sampling and generalization bounds. The algorithm has user-chosen parameters kappa and K, but they are not fitted to data. The state-of-system mapping I_A is a formal modeling device, not a new physical or algorithmic entity.

free parameters (2)
  • sampling parameter kappa
    User-chosen exponent in the query threshold T^{-kappa} (Algorithm 1); controls the tradeoff between memory O(dT^kappa log T) and deletion capacity K=O(epsilon^2 T^kappa/(d log T log(1/delta))). It is an input, not fitted to data.
  • regularization, deletion capacity K
    Input parameter lambda=K in the BBQSAMPLER ridge initialization (Algorithm 1); also bounds the number of core-set deletions the algorithm can tolerate. The theory treats it as an input, not a fitted constant.
assumptions (5)
  • domain assumption Binary linear classification is realizable: there exists u with ||u||<=1 and E[y_t|x_t]=u^T x_t, with ||x_t||<=1.
    Stated in Section 4 'Assumptions'. The excess risk and regret bounds rely on this realizability condition; without it the Bayes optimal classifier is not sign(u^T x).
  • domain assumption The attacker can observe only the state-of-system I_A(S,U) after unlearning, not the full remaining dataset S\U.
    The paper's threat model introduced in Definitions 2.2 to 2.3 and argued in Section 2.1. All system-aware guarantees are relative to this attacker; if the attacker knows S\U, Definition 2.3 reduces to traditional unlearning and the sublinear-memory claim becomes vacuous.
  • standard math Standard selective sampling and generalization bounds from the literature are correct: BBQSAMPLER regret and query bounds (Cesa-Bianchi et al. 2009; Dekel et al.
    Used as black boxes in Theorems 4.3, D.8, and 5.3; proofs are referenced but not reproduced in this paper.
  • domain assumption For the general-function-class extension, the regression oracle has uniform stability with rate beta(N_T) and the ERM satisfies the squared-loss bound with high probability.
    Theorem 5.5 states this conditionally; it is not verified for specific classes beyond linear, so the general extension inherits this unproven assumption.
  • domain assumption Deletion requests are drawn without replacement from a distribution mu(x) that depends only on the point x.
    Assumed in Theorem 4.4 and Lemma 4.5 to derive expected deletion capacity and time; the proof also uses a worst-case condition mu(x)>mu(x') implies nu(x)>=nu(x') that is asserted rather than derived.

how reviews work

0 comments
Cite this review

Pith. "Pith review of System-Aware Unlearning Algorithms: Use Lesser, Forget Faster." pith.science (2026). https://pith.science/paper/YFW4VPIK

@misc{pith2026250606073,
  author       = {Pith},
  title        = {Pith review of: System-Aware Unlearning Algorithms: Use Lesser, Forget Faster},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YFW4VPIK}},
  note         = {Machine review of arXiv:2506.06073}
}
abstract

Machine unlearning addresses the problem of updating a machine learning model/system trained on a dataset $S$ so that the influence of a set of deletion requests $U \subseteq S$ on the unlearned model is minimized. The gold standard definition of unlearning demands that the updated model, after deletion, be nearly identical to the model obtained by retraining. This definition is designed for a worst-case attacker (one who can recover not only the unlearned model but also the remaining data samples, i.e., $S \setminus U$). Such a stringent definition has made developing efficient unlearning algorithms challenging. However, such strong attackers are also unrealistic. In this work, we propose a new definition, system-aware unlearning, which aims to provide unlearning guarantees against an attacker that can at best only gain access to the data stored in the system for learning/unlearning requests and not all of $S\setminus U$. With this new definition, we use the simple intuition that if a system can store less to make its learning/unlearning updates, it can be more secure and update more efficiently against a system-aware attacker. Towards that end, we present an exact system-aware unlearning algorithm for linear classification using a selective sampling-based approach, and we generalize the method for classification with general function classes. We theoretically analyze the tradeoffs between deletion capacity, accuracy, memory, and computation time.

Figures

Figures reproduced from arXiv: 2506.06073 by the authors.

Figure 1
Figure 1. Consider a deletion on a hard margin SVM where the state-of-system IA(S, U) is the set of support vectors (in dark blue) and the unlearned model A(S, U). Let S ′ be the set of support vectors . Thus, we have A(S, ∅) = A(S ′ , ∅). Under traditional unlearning definitions, when a support vector is deleted, we need to recover the hypothesis from training a new hard margin SVM on the remaining data points A(S ∖ U, ∅) ( … view at source ↗
Figure 2
Figure 2. The test accuracy of each unlearning method over the course 80,000 label dependent deletions. B. Experimental Evaluation Our theoretical results provide guarantees for the worst case deletions. We experimentally verify our theory, and we demonstrate that in practice, Algorithm 1 can maintain small excess error beyond the core set deletion capacities proven in Theorem 4.1. Furthermore, Algorithm 1 is significantly mo… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

56 extracted references · 37 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Selective sampling algorithms for cost-sensitive multiclass prediction

    Agarwal, A. Selective sampling algorithms for cost-sensitive multiclass prediction. In Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume 28, ICML'13, pp.\ III–127–III–135. JMLR.org, 2013

    work page 2013

  3. [3]

    Pan-private uniformity testing

    Amin, K., Joseph, M., and Mao, J. Pan-private uniformity testing. In Abernethy, J. and Agarwal, S. (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp.\ 183--218. PMLR, 09--12 Jul 2020. URL https://proceedings.mlr.press/v125/amin20a.html

    work page 2020

  4. [4]

    Probing classifiers: Promises, shortcomings, and advances

    Belinkov, Y. Probing classifiers: Promises, shortcomings, and advances. Computational Linguistics, 48 0 (1): 0 207--219, 2022

    work page 2022

  5. [5]

    Weighted sampling without replacement

    Ben-Hamou, A., Peres, Y., and Salez, J. Weighted sampling without replacement. Brazilian Journal of Probability and Statistics, 32 0 (3): 0 657--669, 2018. ISSN 01030752, 23176199

    work page 2018

  6. [6]

    Is Retain Set All You Need in Machine Unlearning? Restoring Performance of Unlearned Models with Out-Of-Distribution Images

    Bonato, J., Cotogni, M., and Sabetta, L. Is retain set all you need in machine unlearning? restoring performance of unlearned models with out-of-distribution images, 2024. URL https://arxiv.org/abs/2404.12922

    work page Pith review arXiv 2024

  7. [7]

    A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N

    Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C. A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp.\ 141--159. IEEE, 2021

    2021

  8. [8]

    and Elisseeff, A

    Bousquet, O. and Elisseeff, A. Stability and generalization. Journal of Machine Learning Research, 2: 0 499–526, mar 2002. ISSN 1532-4435

    work page 2002

Show all 56 references
  1. [9]

    Title 1.81.5

    California Consumer Privacy Act . Title 1.81.5. california consumer privacy act of 2018 [1798.100 - 1798.199.100], 2018

    2018

  2. [10]

    and Yang, J

    Cao, Y. and Yang, J. Towards making systems forget with machine unlearning. In 2015 IEEE Symposium on Security and Privacy, pp.\ 463--480, 2015

    2015

  3. [11]

    Extracting training data from large language models

    Carlini, N., Tram \`e r, F., Wallace, E., Jagielski, M., Herbert-Voss, A., Lee, K., Roberts, A., Brown, T., Song, D., Erlingsson, \'U ., Oprea, A., and Raffel, C. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), pp.\ ...

    2021

  4. [12]

    Robust bounds for classification via selective sampling

    Cesa-Bianchi, N., Gentile, C., and Orabona, F. Robust bounds for classification via selective sampling. In Proceedings of the 26th Annual International Conference on Machine Learning, ICML '09, pp.\ 121–128, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 97...

    2009

  5. [13]

    Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. Differentially private empirical risk minimization, 2011. URL https://arxiv.org/abs/0912.0071

    2011 arXiv

  6. [14]

    The space complexity of learning-unlearning algorithms, 2025

    Cherapanamjeri, Y., Garg, S., Rajaraman, N., Sekhari, A., and Shetty, A. The space complexity of learning-unlearning algorithms, 2025

    2025

  7. [15]

    and Ullman, J

    Cheu, A. and Ullman, J. The limits of pan privacy and shuffle privacy for learning and estimation, 2020. URL https://arxiv.org/abs/2009.08000

    2020 arXiv

  8. [16]

    Langevin unlearning: A new perspective of noisy gradient descent for machine unlearning

    Chien, E., Wang, H., Chen, Z., and Li, P. Langevin unlearning: A new perspective of noisy gradient descent for machine unlearning. arXiv preprint arXiv:2401.10371, 2024

    2024

  9. [17]

    and Shah, N

    Chourasia, R. and Shah, N. Forget unlearning: Towards true data-deletion in machine learning. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceed...

    2023

  10. [18]

    Chowdhury, S. B. R., Choromanski, K., Sehanobish, A., Dubey, A., and Chaturvedi, S. Towards scalable exact machine unlearning using parameter-efficient fine-tuning. arXiv preprint arXiv:2406.16257, 2024

    2024 arXiv

  11. [19]

    and Vapnik, V

    Cortes, C. and Vapnik, V. Support-vector networks. Mach. Learn., 20 0 (3): 0 273–297, September 1995. ISSN 0885-6125. doi:10.1023/A:1022627411411. URL https://doi.org/10.1023/A:1022627411411

    1995 doi

  12. [20]

    and Yu, L

    Cuff, P. and Yu, L. Differential privacy as a mutual information constraint. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS’16. ACM, October 2016. doi:10.1145/2976749.2978308. URL http://dx.doi.org/10.1145/2976749.2978308

    2016

  13. [21]

    Selective sampling and active learning from single and multiple teachers

    Dekel, O., Gentile, C., and Sridharan, K. Selective sampling and active learning from single and multiple teachers. Journal of Machine Learning Research, 13 0 (86): 0 2655--2697, 2012

    2012

  14. [22]

    Avoiding copyright infringement via large language model unlearning, 2024

    Dou, G., Liu, Z., Lyu, Q., Ding, K., and Wong, E. Avoiding copyright infringement via large language model unlearning, 2024. URL https://arxiv.org/abs/2406.10952

    2024 arXiv

  15. [23]

    N., and Yekhanin, S

    Dwork, C., Naor, M., Pitassi, T., Rothblum, G. N., and Yekhanin, S. Pan-private streaming algorithms. In International Conference on Supercomputing, 2010. URL https://api.semanticscholar.org/CorpusID:7916594

    2010

  16. [24]

    The algorithmic foundations of differential privacy

    Dwork, C., Roth, A., et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science , 9 0 (3--4): 0 211--407, 2014

    2014

  17. [25]

    and Warmuth, M

    Floyd, S. and Warmuth, M. Sample compression, learnability, and the vapnik-chervonenkis dimension. Machine learning, 21 0 (3): 0 269--304, 1995

    1995

  18. [26]

    J., Rakhlin, A., Simchi-Levi, D., and Xu, Y

    Foster, D. J., Rakhlin, A., Simchi-Levi, D., and Xu, Y. Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective, 2020. URL https://arxiv.org/abs/2010.03104

    2020 arXiv

  19. [27]

    Fast machine unlearning without retraining through selective synaptic dampening, 2023

    Foster, J., Schoepf, S., and Brintrup, A. Fast machine unlearning without retraining through selective synaptic dampening, 2023. URL https://arxiv.org/abs/2308.07707

    2023 arXiv

  20. [28]

    Regulation (eu) 2016/679 of the european parliament and of the council of 27 april 2016, 2016

    General Data Protection Regulation . Regulation (eu) 2016/679 of the european parliament and of the council of 27 april 2016, 2016

    2016

  21. [29]

    Fast rates in pool-based batch active learning, 2022

    Gentile, C., Wang, Z., and Zhang, T. Fast rates in pool-based batch active learning, 2022. URL https://arxiv.org/abs/2202.05448

    2022 arXiv

  22. [30]

    Ticketed learning–unlearning schemes

    Ghazi, B., Kamath, P., Kumar, R., Manurangsi, P., Sekhari, A., and Zhang, C. Ticketed learning–unlearning schemes. In Neu, G. and Rosasco, L. (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp.\ 5110--5...

    2023

  23. [31]

    Ginart, A., Guan, M., Valiant, G., and Zou, J. Y. Making ai forget you: Data deletion in machine learning. In Wallach, H., Larochelle, H., Beygelzimer, A., d Alch\' e -Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 32. Curra...

    2019

  24. [32]

    Towards adversarial evaluations for inexact machine unlearning, 2023

    Goel, S., Prabhu, A., Sanyal, A., Lim, S.-N., Torr, P., and Kumaraguru, P. Towards adversarial evaluations for inexact machine unlearning, 2023. URL https://arxiv.org/abs/2201.06640

    2023 arXiv

  25. [33]

    Eternal sunshine of the spotless net: Selective forgetting in deep networks

    Golatkar, A., Achille, A., and Soatto, S. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2020

    2020

  26. [34]

    Certified data removal from machine learning models

    Guo, C., Goldstein, T., Hannun, A., and Van Der Maaten, L. Certified data removal from machine learning models. In International Conference on Machine Learing (ICML), 2019

    2019

  27. [35]

    Adaptive machine unlearning, 2021

    Gupta, V., Jung, C., Neel, S., Roth, A., Sharifi-Malvajerdi, S., and Waites, C. Adaptive machine unlearning, 2021. URL https://arxiv.org/abs/2106.04378

    2021 arXiv

  28. [36]

    Hager, W. W. Updating the inverse of a matrix. SIAM Rev., 31: 0 221--239, 1989

    1989

  29. [37]

    and Kontorovich, A

    Hanneke, S. and Kontorovich, A. Stable sample compression schemes: New applications and an optimal svm margin bound. In Algorithmic Learning Theory, pp.\ 697--721. PMLR, 2021

    2021

  30. [38]

    Hanneke, S. et al. Theory of disagreement-based active learning. Foundations and Trends in Machine Learning , 7 0 (2-3): 0 131--309, 2014

    2014

  31. [39]

    Inexact unlearning needs more careful evaluations to avoid a false sense of privacy

    Hayes, J., Shumailov, I., Triantafillou, E., Khalifa, A., and Papernot, N. Inexact unlearning needs more careful evaluations to avoid a false sense of privacy. arXiv preprint arXiv:2403.01218, 2024

    2024 arXiv

  32. [40]

    A., Chaudhuri, K., and Zou, J

    Izzo, Z., Smart, M. A., Chaudhuri, K., and Zou, J. Approximate data deletion from machine learning models. In International Conference on Artificial Intelligence and Statistics, pp.\ 2008--2016. PMLR, 2021

    2008

  33. [41]

    Knowledge unlearning for mitigating privacy risks in language models

    Jang, J., Yoon, D., Yang, S., Cha, S., Lee, M., Logeswaran, L., and Seo, M. Knowledge unlearning for mitigating privacy risks in language models. arXiv preprint arXiv:2210.01504, 2022

    2022 arXiv

  34. [42]

    and Tewari, A

    Kakade, S. and Tewari, A. Concentration, erm, and compression bounds, 2008. URL https://home.ttic.edu/ tewari/lectures/lecture8.pdf

    2008

  35. [43]

    Local Rademacher complexities and oracle inequalities in risk minimization

    Koltchinskii, V. Local Rademacher complexities and oracle inequalities in risk minimization . The Annals of Statistics, 34 0 (6): 0 2593 -- 2656, 2006. doi:10.1214/009053606000001019. URL https://doi.org/10.1214/009053606000001019

    2006 doi

  36. [44]

    Kornblith, S., Shlens, J., and Le, Q. V. Do better imagenet models transfer better? In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp.\ 2661--2671, 2019

    2019

  37. [45]

    Towards unbounded machine unlearning, 2023

    Kurmanji, M., Triantafillou, P., Hayes, J., and Triantafillou, E. Towards unbounded machine unlearning, 2023. URL https://arxiv.org/abs/2302.09880

    2023 arXiv

  38. [46]

    Learning with square loss: Localization through offset rademacher complexity

    Liang, T., Rakhlin, A., and Sridharan, K. Learning with square loss: Localization through offset rademacher complexity. In Grünwald, P., Hazan, E., and Kale, S. (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research...

    2015

  39. [47]

    Mir, D. J. Information-theoretic foundations of differential privacy. In Garcia-Alfaro, J., Cuppens, F., Cuppens-Boulahia, N., Miri, A., and Tawbi, N. (eds.), Foundations and Practice of Security, pp.\ 374--381, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. ISBN 978-3-...

    2013

  40. [48]

    Descent-to-delete: Gradient-based methods for machine unlearning

    Neel, S., Roth, A., and Sharifi-Malvajerdi, S. Descent-to-delete: Gradient-based methods for machine unlearning. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT), 2021

    2021

  41. [49]

    Z., Lu, Y., Sekhari, A., Kamath, G., and Neel, S

    Pawelczyk, M., Di, J. Z., Lu, Y., Sekhari, A., Kamath, G., and Neel, S. Machine unlearning fails to remove data poisoning attacks, 2025. URL https://arxiv.org/abs/2406.17216

    2025

  42. [50]

    and Van Roy, B

    Russo, D. and Van Roy, B. Eluder dimension and the sample complexity of optimistic exploration. In Burges, C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K. (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013

    2013

  43. [51]

    Sekhari, A., Acharya, J., Kamath, G., and Suresh, A. T. Remember what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34: 0 18075--18086, 2021

    2021

  44. [52]

    Selective sampling and imitation learning via online regression

    Sekhari, A., Sridharan, K., Sun, W., and Wu, R. Selective sampling and imitation learning via online regression. 2023

    2023

  45. [53]

    Learnability, stability and uniform convergence

    Shalev-Shwartz, S., Shamir, O., Srebro, N., and Sridharan, K. Learnability, stability and uniform convergence. Journal of Machine Learning Research, 11 0 (90): 0 2635--2670, 2010

    2010

  46. [54]

    and Barron, A

    Yang, Y. and Barron, A. Information-theoretic determination of minimax rates of convergence . The Annals of Statistics, 27 0 (5): 0 1564 -- 1599, 1999. doi:10.1214/aos/1017939142. URL https://doi.org/10.1214/aos/1017939142

    1999

  47. [55]

    A survey on large language model (llm) security and privacy: The good, the bad, and the ugly

    Yao, Y., Duan, J., Xu, K., Cai, Y., Sun, Z., and Zhang, Y. A survey on large language model (llm) security and privacy: The good, the bad, and the ugly. High-Confidence Computing, pp.\ 100211, 2024

    2024

  48. [56]

    and Nowak, R

    Zhu, Y. and Nowak, R. Efficient active learning with abstention. Advances in Neural Information Processing Systems, 35: 0 35379--35391, 2022

    2022

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.