Pith. sign in

REVIEW 2 major objections 6 minor 109 references

The Space Complexity of Learning-Unlearning Algorithms

T0 review · 2 major / 6 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 The paper proves that the memory needed to support later deletions in machine unlearning is governed by the eluder dimension of the hypothesis class in the central model, and by the no-larger star number in the ticketed model, not by VC…

desk verdict Strong, novel results on unlearning memory complexity, but the star-number compression proof has an unrealizable-input gap that needs patching. read the letter →

arxiv 2506.13048 v1 pith:3Z7WOPWW submitted 2025-06-16 cs.LG

Yeshwanth Cherapanamjeri , Sumegha Garg , Nived Rajaraman , Ayush Sekhari , Abhishek Shetty This is my paper
classification cs.LG MSC 68Q32
keywords machineunlearningrighttobeforgottenrealizabilitytestingeluderdimensionstarnumberversionspacecompressionmemorycomplexitylearning-unlearningschemes
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

The paper asks how many bits of auxiliary memory a learning algorithm must keep so that it can later honor deletion requests and still answer whether the remaining data is realizable by a given hypothesis class. It proves that standard learning-theoretic measures—VC dimension, Littlestone dimension, and sample compression—do not capture this cost: there are classes with constant VC and Littlestone dimension for which every unlearning scheme must store Ω(n) bits. The right measure for the central memory model is the eluder dimension (the length of the longest chain of points on which hypotheses consistent with the earlier points still disagree): every central-memory scheme needs Ω(min(n, e(H))) bits, where e(H) is the eluder dimension of the class. In the stronger ticketed model, in which each user holds a small ticket, every class with star number s(H) has a scheme using O(s(H) log|Z| log n)-bit tickets and only one bit of central memory. Because the star number never exceeds the eluder dimension, the paper establishes a separation between central and ticketed memory models for machine unlearning.

What carries the argument

The load-bearing objects are version-space compression and the eluder sequence. A version-space compression is an encoding from which the entire set of hypotheses consistent with a dataset can be recovered; the paper shows this is equivalent to a mergeable compression and, through Lemma 4.11 and Theorem 4.7, that it suffices for a ticketed unlearning scheme with O(C log n)-bit tickets when the compression uses C bits. The eluder sequence, a list of points x1,...,xℓ such that after seeing the first i points two consistent hypotheses still disagree on the next point, forces any central-memory scheme to effectively store one bit per sequence element, giving the Ω(min(n, e(H))) lower bound. The star number upper bound comes from Hanneke and Yang's theorem that any class with star number s has a version-space compression of O(s log|Z|) bits.

What would settle it

Construct a central-memory (ε,δ)-LU scheme for a class with eluder dimension e that uses o(min(n,e)) bits; that would refute Theorem 4.3. A more direct check of the ticketed upper bound is to run the canonical encoding of Lemma 4.11 on an infinite, non-sortable domain (such as the unit ball in R^d) and see whether the LexicographicallySort step can be implemented with finite memory, since the star-number scheme is built from it.

Watch

Extended reading notes

Core claim

The paper's central claim is that the information that must be retained for unlearning realizability testing is characterized, up to logarithmic factors, by the eluder dimension in the central model and by the star number in the ticketed model. Theorem 4.3 shows that for any hypothesis class with eluder dimension e(H), any (ε,δ)-learning-unlearning scheme with δ<1/2 uses Ω(min(n, e(H))) bits of central memory on datasets of size n. Theorem 4.5 shows that any class with star number s(H) admits an exact (0,0)-ticketed scheme with ticket size O(s(H) log|Z| log n) and central memory of one bit. Since s(H) ≤ e(H), the two bounds separate the memory models. The paper also shows VC and Littlestone dimensions do not characterize unlearning (Theorem 3.5), and that when only k deletions are allowed, the hollow star number controls central-memory cost, with matching lower bounds for halfspaces of roughly binomial(d, k) bits.

Load-bearing premise

The ticketed upper bound rests on the external theorem (Hanneke and Yang 2015) that any class with star number s has a version-space compression of O(s log|Z|) bits, together with a canonical encoding that requires the domain to be finite and lexicographically sortable; if that compression is any larger, or the encoding cannot be implemented in bounded memory, the claimed separation between central and ticketed models breaks.

Editorial extensions

If this is right

  • Any hypothesis class with unbounded eluder dimension has no sublinear-memory central unlearning scheme for realizability testing, so space-efficient deletion in the central model requires a bound on eluder dimension.
  • Any class with bounded star number can support an arbitrary number of deletions in the ticketed model with polylogarithmic ticket size and constant server memory.
  • Constant VC or Littlestone dimension does not help: there are such classes for which any unlearning scheme, even ticketed, needs near-linear memory, so unlearning is strictly harder than learning.
  • Version-space compression, not sample compression, is the effective notion of compression for deletion, and it suffices for ticketed schemes.

Reading between the lines

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

  • Because tickets are held by users rather than the server, the central-versus-ticketed separation suggests that policies limiting only server-side storage may underestimate the real cost of the right to be forgotten; the information has to live somewhere.
  • The eluder-sequence lower bound likely generalizes beyond realizability testing: the paper's white-box reduction already extends it to empirical risk minimization, and a plausible principle is that deletion hardness is governed by the length of eluder chains in the class.
  • A testable refinement is whether restricting datasets to a constant margin removes the hardness for halfspaces: the paper's lower-bound construction has margin 1/(2d), leaving open the possibility that constant-margin classes admit small-memory unlearning.
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

2 major / 6 minor

Summary. The paper studies the number of bits of auxiliary memory needed to support deletion requests in machine unlearning, focusing on the task of realizability testing. It formulates central-memory (LU) and ticketed-memory (TiLU) models, and relates their space complexity to combinatorial parameters of the hypothesis class: VC dimension, Littlestone dimension, eluder dimension, star number, and hollow star number. The main results are: (i) a lower bound of Ω(min(n, e(H))) bits for central-memory LU schemes for any class with eluder dimension e(H) (Theorem 4.3); (ii) a ticketed-memory upper bound of O(s(H) log|Z| log n) bits for classes with star number s(H) (Theorem 4.5), giving a central-versus-ticketed separation; (iii) a lower bound showing VC/Littlestone dimension does not characterize unlearning memory (Theorem 3.5); (iv) bounded-deletion upper and lower bounds in terms of the hollow star number, with near-tight bounds for halfspaces (Theorems 5.4, 6.3, 6.4); and (v) a distributional lower bound for halfspaces under i.i.d. sampling (Theorem 6.7). The paper also connects version-space compression to mergeable compression and to ticketed unlearning, and includes reductions from realizability testing to ERM unlearning in the appendix.

Significance. If the results are fully established, the paper makes a substantial contribution to the theory of machine unlearning: it gives parameter-free combinatorial bounds for a natural primitive (realizability testing), and it provides the first general separation between the central and ticketed memory models in terms of the gap between eluder dimension and star number. The information-theoretic lower-bound recipe is standard and clean, the use of version-space compression is conceptually illuminating, and the bounded-deletion results identify a new parameter (hollow star number) that can be much smaller than VC or Littlestone dimension. The paper is also notable for stating open problems and for being careful to attribute the ticketed model and mergeable classes to Ghazi et al. (2023). However, two proof gaps in the appendix need repair: the version-space compression proof does not currently handle unrealizable datasets, and the distributional lower bound contains an invalid truncation step. These gaps are local and likely repairable, and they do not appear to invalidate the main separation theorem, but they must be fixed before the results can be regarded as proved.

major comments (2)
  1. [Appendix D.4 (Theorem 4.12)] The proof of the version-space compression bound does not handle unrealizable datasets. In the pruning step, the manuscript argues that every surviving point z=(x,y) in S''_final has both S''_final and S''_final \ {(x,y)} ∪ {(x, \bar y)} realizable, and concludes |S''_final| ≤ s(H). This reasoning is only valid when H(S''_final) ≠ ∅. For an unrealizable input S, we have H(S'') = ∅; the pruning process can leave a minimal inconsistent set, for which the correct structural property is that S'' is unrealizable while S'' \ {z} is realizable for every z (a hollow-star set). This case is not covered, even though Definition 4.10 requires Enc/Dec to work on all datasets and Lemma 4.11 explicitly uses the encoding of the fixed unrealizable pair Canonical(∅). The gap is likely repairable by showing that the pruned set has size at most s○(H) ≤ s(H)+1 (Lemma B.3), which would preserve Theorem 4.5 asymptotically, but that argument is not supplied in the manuscript.
  2. [Appendix F.3 (Claim F.5)] The reduction from the fixed-size distribution D_{n0} to the random-size distribution D^1_n contains an invalid truncation step. The proof bounds the contribution of dataset sizes n' < n/2 by ne^{-Ω(n)}, using the assertion that Pr(|D^1| ≤ n') ≤ e^{-Ω(n)} for n' ≤ n/2. But |D^0| is Poisson(n/2), and D^1 is D^0 conditioned on a rectangular high-probability event, so Pr(|D^1| ≤ n/2) is bounded away from 0 (approximately 1/2), not exponentially small. Consequently, the displayed inequality 'Σ_{n'=1}^n ... ≤ Σ_{n'=n/2}^n ... + ne^{-Ω(n)}' does not follow, and the claimed identification of some n0 ∈ [n/2,n] with E[|aux(D^0)| | |D^0|=n0] ≤ f(n0,k) is not established. This affects the proof of Theorem 6.7; it is independent of the main central/ticketed separation and appears repairable by retaining the constant-fraction contribution of small n' or by shifting the interval to [cn,n] for a constant c < 1/2.
minor comments (6)
  1. [Section 3.2 / Appendix C.2] The proof of Theorem 3.5 reuses ε both for the privacy parameter and for the parameter β controlling the Littlestone dimension and the query size; in the theorem statement the parameter is β, so the occurrences of 1/ε and m^ε/ε in the proof should be 1/β and m^β/β to avoid confusion.
  2. [Theorem 6.3 / Corollary 6.4] The statements refer to a domain of size 'd+(n k)' without defining n in that expression; the intended size appears to be d + (d choose k), since the dataset family in the proof is indexed by subsets of ([d] choose k) and the final dataset size is at most d + (d choose k).
  3. [Appendix D.4] There are two typos in the proof of Theorem 4.12: 'we don't (x_{i+1}, y_{i+1}) to S′' should read 'we don't add (x_{i+1}, y_{i+1}) to S′', and 'H(S′_{i_j−1})⊆H(S′_{i_j−1})' appears to have a duplicated symbol.
  4. [Appendix F.3] In the proof of Claim F.6, the sentence 'where the last implication uses Claim F.5 which lower bounds H(Z_L)' should refer to Claim F.7, which is the claim that proves the lower bound on H(Z_L).
  5. [Appendix B (Lemma B.3)] In the proof of Lemma B.3, the reference to 'S_n is realizable' should be to the last element S_l of the hollow-star set; the proof otherwise uses the notation S_i for i ∈ [l].
  6. [Table 1] The table entry 'Open Problem 1' under the central bounded star-number/eluder-dimension column is ambiguous; since the text's Open Problem 1 asks whether a central-memory scheme with poly(e(H), log|X|, log n) exists, the table should state this explicitly rather than just naming the open problem.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound is an explicit information-theoretic reduction and the upper bound uses an external, reproduced compression theorem.

full rationale

The derivation chain is not circular. Theorem 4.3 is a parameter-free information-theoretic lower bound: the proof constructs datasets indexed by a uniform secret and shows that any LU scheme's auxiliary memory must carry mutual information about each secret bit via unlearning queries built from an eluder sequence; the bound follows from the chain rule and does not assume the conclusion. The ticketed upper bound (Theorem 4.5) is assembled from Lemma 4.8, which rests on Theorem 4.12 (star number implies O(s(H) log|Z|)-bit version-space compression) and on Lemmas 4.11 and 4.13 (version-space compression and mergeable compression are equivalent). Theorem 4.12 is an external result of Hanneke and Yang (2015) and is also proved in Appendix D.4; the proof is independent of the unlearning claims of this paper, so importing it is legitimate evidence, not a self-referential loop. The equivalence lemmas are constructive under the stated finite-domain assumption and are verified directly from the definitions. The bounded-deletions result (Theorem 5.4) is a combinatorial counting argument over k-critical sets using the definition of hollow star number; it does not rename the theorem's output as an input. The only citation overlap with the present authors is Ghazi et al. (2023) for the ticketed-model definition and for the proof template of Theorem 4.7, but that proof is reproduced in Appendix D.6, so the citation is not load-bearing. I separately note a non-circular correctness concern: the 'for completeness' proof of Theorem 4.12 in Appendix D.4 does not explicitly handle unrealizable datasets, since its pruning argument derives |S''_final| <= s(H) from a star-set property that assumes H(S''_final) is nonempty; for unrealizable S the correct bound would go through the hollow star number (Lemma B.3). This is an omitted case in a proof, not an equivalence between inputs and outputs, and it does not change the circularity verdict. Overall, no step of the derivation reduces, by construction or self-citation, to its own target.

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

The paper's results are conditional on standard learning-theoretic definitions and a finite domain assumption. No free parameters are fit to data. The main external dependencies are: (i) the finite-domain assumption stated in Section 2; (ii) known relations among combinatorial dimensions, in particular s(H) ≤ e(H); (iii) the version-space compression theorem for star number; (iv) standard information-theoretic facts. No new entities such as particles or forces are posited; the hollow star number and k-critical sets are combinatorial definitions drawn from or extending prior work, not ungrounded postulates.

assumptions (5)
  • domain assumption The domain X is finite (stated in Section 2).
    All encodings and bounds use log|Z|; the Canonical function in Lemma 4.11 requires a finite lexicographic order. For infinite domains such as halfspaces, the authors discretize to a finite grid.
  • domain assumption For any class H, s(H) ≤ e(H) (Lemma B.2).
    This inequality is essential for the claimed separation between central lower bound Ω(e) and ticketed upper bound O(s). It is cited from Li et al. (2022) and Hanneke (2024).
  • domain assumption Any class with star number s has a version-space compression of O(s log|Z|) bits (Theorem 4.12).
    The TiLU upper bound (Theorem 4.5) is built on this compression via Lemma 4.11 and Theorem 4.7. The paper includes a proof in Appendix D.4 but the result is from Hanneke and Yang (2015).
  • standard math Standard information-theoretic identities (chain rule, data processing inequality, entropy bounds).
    Used in the lower-bound proofs (Theorems 3.3, 3.5, 4.3, 6.3) to convert unlearning outputs into mutual information about the dataset.
  • domain assumption The (ε,δ)-learning-unlearning model (Definitions 2.3 and 2.4) as the formalization of unlearning.
    All results are with respect to this model introduced by Ghazi et al. (2023); different formalizations (e.g., only functional correctness) could have different memory complexity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Space Complexity of Learning-Unlearning Algorithms." pith.science (2026). https://pith.science/paper/3Z7WOPWW

@misc{pith2026250613048,
  author       = {Pith},
  title        = {Pith review of: The Space Complexity of Learning-Unlearning Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3Z7WOPWW}},
  note         = {Machine review of arXiv:2506.13048}
}
abstract

We study the memory complexity of machine unlearning algorithms that provide strong data deletion guarantees to the users. Formally, consider an algorithm for a particular learning task that initially receives a training dataset. Then, after learning, it receives data deletion requests from a subset of users (of arbitrary size), and the goal of unlearning is to perform the task as if the learner never received the data of deleted users. In this paper, we ask how many bits of storage are needed to be able to delete certain training samples at a later time. We focus on the task of realizability testing, where the goal is to check whether the remaining training samples are realizable within a given hypothesis class \(\mathcal{H}\). Toward that end, we first provide a negative result showing that the VC dimension is not a characterization of the space complexity of unlearning. In particular, we provide a hypothesis class with constant VC dimension (and Littlestone dimension), but for which any unlearning algorithm for realizability testing needs to store \(\Omega(n)\)-bits, where \(n\) denotes the size of the initial training dataset. In fact, we provide a stronger separation by showing that for any hypothesis class \(\mathcal{H}\), the amount of information that the learner needs to store, so as to perform unlearning later, is lower bounded by the \textit{eluder dimension} of \(\mathcal{H}\), a combinatorial notion always larger than the VC dimension. We complement the lower bound with an upper bound in terms of the star number of the underlying hypothesis class, albeit in a stronger ticketed-memory model proposed by Ghazi et al. (2023). Since the star number for a hypothesis class is never larger than its Eluder dimension, our work highlights a fundamental separation between central and ticketed memory models for machine unlearning.

Figures

Figures reproduced from arXiv: 2506.13048 by the authors.

Figure 1
Figure 1. Lower bound for VC classes = d ∑ i=1 I(Zi ; aux ∣ Z<i) (Chain rule) ≥ d ∑ i=1 I(Zi ; aux) (as I(Zi ; Z<i) = 0) = d ∑ i=1 (I(Zi ; aux, Unlearn(Ui , aux)) − I(Zi ; Unlearn(Ui , aux) ∣ aux)) ≥ d ∑ i=1 (I(Zi ; Unlearn(Ui , aux)) − I(Zi ; Unlearn(Ui , aux) ∣ aux)) ≥ d ∑ i=1 (1 − H(1 − δ)) (Explained below) = d ⋅ (1 − H(δ)) The second last inequality follows from Equation (4) and the fact that I(Zi ; Unlearn(Ui , aux) ∣ a… view at source ↗
Figure 2
Figure 2. Picture taken from Ghazi et al. (2023). Illustration of TiLU scheme underlying the proof of Theorem 4.7. The ticket t5 for the example (x5, y5) are the index i and the outputs of Encode applied on the subsets S{1,2,3,4} , S{7,8} , and S{6} . It is immediate to see that the number of bits in txi is d + C ⋅ (d − 1), where d = log(n). Define Learn(S) to return aux = Decode(Encode(S)) and tickets txi as specified above.… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

109 extracted references · 64 canonical work pages

  1. [1]

    The space complexity of approximating the frequency moments

    Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 20--29, 1996

    1996

  2. [2]

    History-Independent Concurrent Objects

    Hagit Attiya, Michael A Bender, Martin Farach-Colton, Rotem Oshman, and Noa Schiller. History-independent concurrent objects. arXiv preprint arXiv:2403.14445, 2024

    work page Pith review arXiv 2024

  3. [3]

    Time-space tradeoffs for learning finite functions from random evaluations, with applications to polynomials

    Paul Beame, Shayan Oveis Gharan, and Xin Yang. Time-space tradeoffs for learning finite functions from random evaluations, with applications to polynomials. In Conference On Learning Theory, pages 843--856. PMLR, 2018

    2018

  4. [4]

    Leace: Perfect linear concept erasure in closed form

    Nora Belrose, David Schneider-Joseph, Shauli Ravfogel, Ryan Cotterell, Edward Raff, and Stella Biderman. Leace: Perfect linear concept erasure in closed form. Advances in Neural Information Processing Systems, 36, 2023

    2023

  5. [5]

    History-independent dynamic partitioning: Operation-order privacy in ordered data structures

    Michael A Bender, Mart \' n Farach-Colton, Michael T Goodrich, and Hanna Koml \'o s. History-independent dynamic partitioning: Operation-order privacy in ordered data structures. Proceedings of the ACM on Management of Data, 2 0 (2): 0 1--27, 2024

    2024

  6. [6]

    Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems

    Moise Blanchard. Gradient descent is pareto-optimal in the oracle complexity and memory tradeoff for feasibility problems, 2024. URL https://arxiv.org/abs/2404.06720

    work page Pith review arXiv 2024

  7. [7]

    Strongly history-independent hashing with applications

    Guy E Blelloch and Daniel Golovin. Strongly history-independent hashing with applications. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 272--282. IEEE, 2007

    2007

  8. [8]

    Machine unlearning

    Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In proceedings of the 42nd IEEE Symposium on Security and Privacy, SP '21. IEEE Computer Society, 2021

    2021

Show all 109 references
  1. [9]

    Proper learning, helly number, and an optimal svm bound

    Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy. Proper learning, helly number, and an optimal svm bound. In Conference on Learning Theory, pages 582--609. PMLR, 2020 a

    2020

  2. [10]

    Proper learning, helly number, and an optimal SVM bound

    Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy. Proper learning, helly number, and an optimal SVM bound. In Jacob D. Abernethy and Shivani Agarwal, editors, Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria] , volume 1...

    2020

  3. [11]

    Mark Braverman, Gillat Kol, Shay Moran, and Raghuvansh R. Saxena. Convex set disjointness, distributed learning of halfspaces, and LP feasibility. CoRR, abs/1909.03547, 2019. URL http://arxiv.org/abs/1909.03547

    1909 arXiv

  4. [12]

    Machine unlearning for random forests

    Jonathan Brophy and Daniel Lowd. Machine unlearning for random forests. In Proceedings of the 38th International Conference on Machine Learning, ICML '21, pages 1092--1104. JMLR, Inc., 2021

    2021

  5. [13]

    Lower and upper bounds on obtaining history independence

    Niv Buchbinder and Erez Petrank. Lower and upper bounds on obtaining history independence. In Advances in Cryptology-CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003. Proceedings 23, pages 445--462. Springer, 2003

    2003

  6. [14]

    Towards making systems forget with machine unlearning

    Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. In 2015 IEEE symposium on security and privacy, pages 463--480. IEEE, 2015

    2015

  7. [15]

    Membership inference attacks from first principles

    Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In S & P, pages 1897--1914, 2022

    1914

  8. [16]

    Extracting training data from diffusion models

    Nicholas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tram \`e r, Borja Balle, Daphne Ippolito, and Eric Wallace. Extracting training data from diffusion models. arXiv preprint arXiv:2301.13188, 2023 a

    2023 arXiv

  9. [17]

    Quantifying memorization across neural language models

    Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. In ICLR, 2023 b

    2023

  10. [18]

    Incremental and decremental support vector machine learning

    Gert Cauwenberghs and Tomaso Poggio. Incremental and decremental support vector machine learning. NIPS, 2000

    2000

  11. [19]

    California consumer privacy act (ccpa)

    CCPA. California consumer privacy act (ccpa). https://oag.ca.gov/privacy/ccpa

  12. [20]

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

    Eli Chien, Haoyu Wang, Ziang Chen, and Pan Li. Langevin unlearning: A new perspective of noisy gradient descent for machine unlearning. arXiv preprint arXiv:2401.10371, 2024

    2024

  13. [21]

    Forget unlearning: Towards true data-deletion in machine learning

    Rishav Chourasia, Neil Shah, and Reza Shokri. Forget unlearning: Towards true data-deletion in machine learning. In ICML, 2023

    2023

  14. [22]

    Towards formalizing the gdpr’s notion of singling out

    Aloni Cohen and Kobbi Nissim. Towards formalizing the gdpr’s notion of singling out. Proceedings of the National Academy of Sciences, 117 0 (15): 0 8344--8352, 2020

    2020

  15. [23]

    Control, confidentiality, and the right to be forgotten

    Aloni Cohen, Adam Smith, Marika Swanberg, and Prashant Nalini Vasudevan. Control, confidentiality, and the right to be forgotten. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 3358--3372, 2023

    2023

  16. [24]

    Characterizations of an empirical influence function for detecting influential cases in regression

    R Dennis Cook and Sanford Weisberg. Characterizations of an empirical influence function for detecting influential cases in regression. Technometrics, 22 0 (4): 0 495--508, 1980

    1980

  17. [25]

    The two-armed-bandit problem with time-invariant finite memory

    T Cover and M Hellman. The two-armed-bandit problem with time-invariant finite memory. IEEE Transactions on Information Theory, 16 0 (2): 0 185--195, 1970

    1970

  18. [26]

    Hypothesis testing with finite statistics

    Thomas M Cover. Hypothesis testing with finite statistics. The Annals of Mathematical Statistics, 40 0 (3): 0 828--835, 1969

    1969

  19. [27]

    Optimal finite memory learning algorithms for the finite sample problem

    Thomas M Cover, Michael A Freedman, and Martin E Hellman. Optimal finite memory learning algorithms for the finite sample problem. Information and Control, 30 0 (1): 0 49--85, 1976

    1976

  20. [28]

    Lifelong anomaly detection through unlearning

    Min Du, Zhi Chen, Chang Liu, Rajvardhan Oak, and Dawn Song. Lifelong anomaly detection through unlearning. In CCS, pages 1283--1297, 2019

    2019

  21. [29]

    SAFE : Machine unlearning with shard graphs

    Yonatan Dukler, Benjamin Bowman, Alessandro Achille, Aditya Golatkar, Ashwin Swaminathan, and Stefano Soatto. SAFE : Machine unlearning with shard graphs. arXiv preprint arXiv:2304.13169, 2023

    2023 arXiv

  22. [30]

    Calibrating noise to sensitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC '06, pages 265--284, Berlin, Heidelberg, 2006. Springer

    2006

  23. [31]

    Verifiable and provably secure machine unlearning

    Thorsten Eisenhofer, Doreen Riepel, Varun Chandrasekaran, Esha Ghosh, Olga Ohrimenko, and Nicolas Papernot. Verifiable and provably secure machine unlearning. arXiv preprint arXiv:2210.09126, 2022

    2022 arXiv

  24. [32]

    Active learning via perfect selective classification

    Ran El-Yaniv and Yair Wiener. Active learning via perfect selective classification. The Journal of Machine Learning Research, 13 0 (1): 0 255--279, 2012

    2012

  25. [33]

    On the foundations of noise-free selective classification

    Ran El-Yaniv et al. On the foundations of noise-free selective classification. Journal of Machine Learning Research, 11 0 (5), 2010

    2010

  26. [34]

    Who's harry potter? approximate unlearning in llms

    Ronen Eldan and Mark Russinovich. Who's harry potter? approximate unlearning in llms. arXiv preprint arXiv:2310.02238, 2023

    2023 arXiv

  27. [35]

    Probabilistic counting algorithms for data base applications

    Philippe Flajolet and G Nigel Martin. Probabilistic counting algorithms for data base applications. Journal of computer and system sciences, 31 0 (2): 0 182--209, 1985

    1985

  28. [36]

    Sample compression, learnability, and the vapnik-chervonenkis dimension

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

    1995

  29. [37]

    Formalizing data deletion in the context of the right to be forgotten

    Sanjam Garg, Shafi Goldwasser, and Prashant Nalini Vasudevan. Formalizing data deletion in the context of the right to be forgotten. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 373--402. Springer, 2020

    2020

  30. [38]

    Extractor-based time-space lower bounds for learning

    Sumegha Garg, Ran Raz, and Avishay Tal. Extractor-based time-space lower bounds for learning. In Proceedings of the 50th Annual ACM Symposium on the Theory of Computing, STOC '18, pages 990--1002, New York, NY, USA, 2018. ACM

    2018

  31. [39]

    Regulation (EU) 2016/679 of the European parliament and of the council of 27 April 2016

    GDPR. Regulation (EU) 2016/679 of the European parliament and of the council of 27 April 2016. Official Journal of the European Union

    2016

  32. [40]

    Ticketed learning-unlearning schemes, 2023

    Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Ayush Sekhari, and Chiyuan Zhang. Ticketed learning-unlearning schemes, 2023

    2023

  33. [41]

    Making AI forget you: Data deletion in machine learning

    Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou. Making AI forget you: Data deletion in machine learning. In Advances in Neural Information Processing Systems 32, NeurIPS '19, pages 3518--3531. Curran Associates, Inc., 2019

    2019

  34. [42]

    Deletion-compliance in the absence of privacy

    Jonathan Godin and Philippe Lamontagne. Deletion-compliance in the absence of privacy. In 2021 18th International Conference on Privacy, Security and Trust (PST), pages 1--10. IEEE, 2021

    2021

  35. [43]

    Towards adversarial evaluations for inexact machine unlearning

    Shashwat Goel, Ameya Prabhu, Amartya Sanyal, Ser-Nam Lim, Philip Torr, and Ponnurangam Kumaraguru. Towards adversarial evaluations for inexact machine unlearning. arXiv preprint arXiv:2201.06640, 2022

    2022 arXiv

  36. [44]

    Corrective machine unlearning

    Shashwat Goel, Ameya Prabhu, Philip Torr, Ponnurangam Kumaraguru, and Amartya Sanyal. Corrective machine unlearning. arXiv preprint arXiv:2402.14015, 2024

    2024 arXiv

  37. [45]

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

    Aditya Golatkar, Alessandro Achille, and Stefano Soatto. 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 a

    2020

  38. [46]

    Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations

    Aditya Golatkar, Alessandro Achille, and Stefano Soatto. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. arXiv:2003.02960, 2020 b

    2003 arXiv

  39. [47]

    Mixed-privacy forgetting in deep networks

    Aditya Golatkar, Alessandro Achille, Avinash Ravichandran, Marzia Polito, and Stefano Soatto. Mixed-privacy forgetting in deep networks. In Proceedings of the 2021 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR '21, pages 792--801. IEEE Compu...

    2021

  40. [48]

    Amnesiac machine learning

    Laura Graves, Vineel Nagisetty, and Vijay Ganesh. Amnesiac machine learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11516--11524, 2021

    2021

  41. [49]

    Certified data removal from machine learning models

    Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In Proceedings of the 37th International Conference on Machine Learning, ICML '20, pages 3832--3842. JMLR, Inc., 2020

    2020

  42. [50]

    Adaptive machine unlearning

    Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Chris Waites. Adaptive machine unlearning. In Advances in Neural Information Processing Systems 34, NeurIPS '21, pages 16319--16330. Curran Associates, Inc., 2021

    2021

  43. [51]

    Theoretical foundations of active learning

    Steve Hanneke. Theoretical foundations of active learning. Carnegie Mellon University, 2009

    2009

  44. [52]

    The star number and eluder dimension: Elementary observations about the dimensions of disagreement

    Steve Hanneke. The star number and eluder dimension: Elementary observations about the dimensions of disagreement. J. Mach. Learn. Res., 247, 2024

    2024

  45. [53]

    Minimax analysis of active learning

    Steve Hanneke and Liu Yang. Minimax analysis of active learning. J. Mach. Learn. Res., 16 0 (1): 0 3487--3602, 2015

    2015

  46. [54]

    Characterizing history independent data structures

    Jason D Hartline, Edwin S Hong, Alexander E Mohr, William R Pentney, and Emily C Rocke. Characterizing history independent data structures. Algorithmica, 42: 0 57--74, 2005

    2005

  47. [55]

    Learning with finite memory

    Martin Edward Hellman. Learning with finite memory. Stanford University, 1969

    1969

  48. [56]

    Tight bounds for machine unlearning via differential privacy

    Yiyang Huang and Cl \'e ment L Canonne. Tight bounds for machine unlearning via differential privacy. arXiv:2309.00886, 2023

    2023 arXiv

  49. [57]

    Preventing verbatim memorization in language models gives a false sense of privacy

    Daphne Ippolito, Florian Tram \`e r, Milad Nasr, Chiyuan Zhang, Matthew Jagielski, Katherine Lee, Christopher A Choquette-Choo, and Nicholas Carlini. Preventing verbatim memorization in language models gives a false sense of privacy. arXiv preprint arXiv:2210.17546, 2022

    arXiv

  50. [58]

    Approximate data deletion from machine learning models

    Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTATS), 2021

    2021

  51. [59]

    Knowledge unlearning for mitigating privacy risks in language models

    Joel Jang, Dongkeun Yoon, Sohee Yang, Sungmin Cha, Moontae Lee, Lajanugen Logeswaran, and Minjoon Seo. Knowledge unlearning for mitigating privacy risks in language models. arXiv preprint arXiv:2210.01504, 2022

    2022 arXiv

  52. [60]

    q-Binomial Coefficients and Linear Algebra over Finite Fields, pages 21--26

    Victor Kac and Pokman Cheung. q-Binomial Coefficients and Linear Algebra over Finite Fields, pages 21--26. Springer New York, New York, NY, 2002. ISBN 978-1-4613-0071-7. doi:10.1007/978-1-4613-0071-7_7. URL https://doi.org/10.1007/978-1-4613-0071-7_7

    2002 doi

  53. [61]

    Multiple incremental decremental learning of support vector machines

    Masayuki Karasuyama and Ichiro Takeuchi. Multiple incremental decremental learning of support vector machines. IEEE Transactions on Neural Networks, 21 0 (7): 0 1048--1059, 2010

    2010

  54. [62]

    Time-space hardness of learning sparse parities

    Gillat Kol, Ran Raz, and Avishay Tal. Time-space hardness of learning sparse parities. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1067--1080, 2017

    2017

  55. [63]

    Towards bridging the gaps between the right to explanation and the right to be forgotten

    Satyapriya Krishna, Jiaqi Ma, and Himabindu Lakkaraju. Towards bridging the gaps between the right to explanation and the right to be forgotten. In ICML, 2023

    2023

  56. [64]

    Towards unbounded machine unlearning

    Meghdad Kurmanji, Peter Triantafillou, and Eleni Triantafillou. Towards unbounded machine unlearning. arXiv preprint arXiv:2302.09880, 2023

    2023 arXiv

  57. [65]

    Understanding the eluder dimension

    Gene Li, Pritish Kamath, Dylan J Foster, and Nati Srebro. Understanding the eluder dimension. Advances in Neural Information Processing Systems, 35: 0 23737--23750, 2022

    2022

  58. [66]

    Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm

    Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2: 0 285--318, 1988

    1988

  59. [67]

    Relating data compression and learnability

    Nick Littlestone and Manfred Warmuth. Relating data compression and learnability. Unpublished manuscript, 1986

    1986

  60. [68]

    Efficient convex optimization requires superlinear memory

    Annie Marsden, Vatsal Sharan, Aaron Sidford, and Gregory Valiant. Efficient convex optimization requires superlinear memory. In Conference on Learning Theory, pages 2390--2430. PMLR, 2022

    2022

  61. [69]

    Graph stream algorithms: a survey

    Andrew McGregor. Graph stream algorithms: a survey. ACM SIGMOD Record, 43 0 (1): 0 9--20, 2014

    2014

  62. [70]

    Finding repeated elements

    Jayadev Misra and David Gries. Finding repeated elements. Science of computer programming, 2 0 (2): 0 143--152, 1982

    1982

  63. [71]

    Sample compression schemes for vc classes

    Shay Moran and Amir Yehudayoff. Sample compression schemes for vc classes. Journal of the ACM (JACM), 63 0 (3): 0 1--10, 2016

    2016

  64. [72]

    Mixing implies lower bounds for space bounded learning

    Dana Moshkovitz and Michal Moshkovitz. Mixing implies lower bounds for space bounded learning. In Conference on Learning Theory, pages 1516--1566. PMLR, 2017

    2017

  65. [73]

    Entropy samplers and strong generic lower bounds for space bounded learning

    Dana Moshkovitz and Michal Moshkovitz. Entropy samplers and strong generic lower bounds for space bounded learning. In Proceedings of the 9th Conference on Innovations in Theoretical Computer Science, ITCS '18, pages 28:1--28:20, Dagstuhl, Germany, 2018. Schloss Dagstuhl--Leib...

    2018

  66. [74]

    On the sample complexity of reinforcement learning with policy space generalization

    Wenlong Mou, Zheng Wen, and Xi Chen. On the sample complexity of reinforcement learning with policy space generalization. arXiv preprint arXiv:2008.07353, 2020

    2008 arXiv

  67. [75]

    Selection and sorting with limited storage

    J Ian Munro and Mike S Paterson. Selection and sorting with limited storage. Theoretical computer science, 12 0 (3): 0 315--323, 1980

    1980

  68. [76]

    Data streams: Algorithms and applications

    Shanmugavelayutham Muthukrishnan et al. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science , 1 0 (2): 0 117--236, 2005

    2005

  69. [77]

    Anti-persistence: History independent data structures

    Moni Naor and Vanessa Teague. Anti-persistence: History independent data structures. In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 492--501, 2001

    2001

  70. [78]

    History-independent cuckoo hashing

    Moni Naor, Gil Segev, and Udi Wieder. History-independent cuckoo hashing. In Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II 35, pages 631--642. Springer, 2008

    2008

  71. [79]

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

    Seth Neel, Aaron Roth, and Saeed Sharifi-Malvajerdi. Descent-to-delete: Gradient-based methods for machine unlearning. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, ALT '21. JMLR, Inc., 2021

    2021

  72. [80]

    Variational B ayesian unlearning

    Quoc Phong Nguyen, Bryan Kian Hsiang Low, and Patrick Jaillet. Variational B ayesian unlearning. In NeurIPS, pages 16025--16036, 2020

    2020

  73. [81]

    A survey of machine unlearning

    Thanh Tam Nguyen, Thanh Trung Huynh, Phi Le Nguyen, Alan Wee-Chung Liew, Hongzhi Yin, and Quoc Viet Hung Nguyen. A survey of machine unlearning. arXiv:2209.02299, 2022

    2022 arXiv

  74. [82]

    In-context unlearning: Language models as few shot unlearners

    Martin Pawelczyk, Seth Neel, and Himabindu Lakkaraju. In-context unlearning: Language models as few shot unlearners. arXiv preprint arXiv:2310.07579, 2023

    2023 arXiv

  75. [83]

    Machine unlearning fails to remove data poisoning attacks

    Martin Pawelczyk, Jimmy Z Di, Yiwei Lu, Gautam Kamath, Ayush Sekhari, and Seth Neel. Machine unlearning fails to remove data poisoning attacks. arXiv preprint arXiv:2406.17216, 2024

    2024

  76. [84]

    Near optimal memory-regret tradeoff for online learning

    Binghui Peng and Aviad Rubinstein. Near optimal memory-regret tradeoff for online learning. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1171--1194. IEEE, 2023

    2023

  77. [85]

    Big data and sketching

    Jeff M Phillips and Jeff M Phillips. Big data and sketching. Mathematical Foundations for Data Analysis, pages 261--281, 2021

    2021

  78. [86]

    Linear adversarial concept erasure

    Shauli Ravfogel, Michael Twiton, Yoav Goldberg, and Ryan D Cotterell. Linear adversarial concept erasure. In International Conference on Machine Learning, pages 18400--18421. PMLR, 2022 a

    2022

  79. [87]

    Adversarial concept erasure in kernel space

    Shauli Ravfogel, Francisco Vargas, Yoav Goldberg, and Ryan Cotterell. Adversarial concept erasure in kernel space. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 6034--6055, 2022 b

    2022

  80. [88]

    Fast learning requires good memory: A time-space lower bound for parity learning

    Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS '16, pages 266--275. IEEE Computer Society, 2016

    2016

  81. [89]

    Incremental and decremental learning for linear support vector machines

    Enrique Romero, Ignacio Barrio, and Llu \' s Belanche. Incremental and decremental learning for linear support vector machines. In ICANN, pages 209--218, 2007

    2007

  82. [90]

    Eluder dimension and the sample complexity of optimistic exploration

    Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, 26, 2013

    2013

  83. [91]

    Remember what you want to forget: Algorithms for machine unlearning

    Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want to forget: Algorithms for machine unlearning. In NeurIPS, pages 18075--18086, 2021

    2021

  84. [92]

    Fundamental limits of online and distributed algorithms for statistical learning and estimation

    Ohad Shamir. Fundamental limits of online and distributed algorithms for statistical learning and estimation. Advances in Neural Information Processing Systems, 27, 2014

    2014

  85. [93]

    Memory-sample tradeoffs for linear regression with small error

    Vatsal Sharan, Aaron Sidford, and Gregory Valiant. Memory-sample tradeoffs for linear regression with small error. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 890--901, 2019

    2019

  86. [94]

    Membership inference attacks against machine learning models

    Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In S & P, pages 3--18, 2017

    2017

  87. [95]

    Memory bounds for the experts problem

    Vaidehi Srinivas, David P Woodruff, Ziyu Xu, and Samson Zhou. Memory bounds for the experts problem. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1158--1171, 2022

    2022

  88. [96]

    Minimax rates for memory-bounded sparse linear regression

    Jacob Steinhardt and John Duchi. Minimax rates for memory-bounded sparse linear regression. In Conference on Learning Theory, pages 1564--1587. PMLR, 2015

    2015

  89. [97]

    Memory, communication, and statistical queries

    Jacob Steinhardt, Gregory Valiant, and Stefan Wager. Memory, communication, and statistical queries. In Conference on Learning Theory, pages 1490--1516. PMLR, 2016

    2016

  90. [98]

    Algorithms that approximate data removal: New results and limitations

    Vinith M Suriyakumar and Ashia C Wilson. Algorithms that approximate data removal: New results and limitations. In NeurIPS, 2022

    2022

  91. [99]

    Unrolling SGD : Understanding factors influencing machine unlearning

    Anvith Thudi, Gabriel Deza, Varun Chandrasekaran, and Nicolas Papernot. Unrolling SGD : Understanding factors influencing machine unlearning. In EuroS&P, pages 303--319, 2022

    2022

  92. [100]

    Incremental and decremental proximal support vector classification using decay coefficients

    Amund Tveit, Magnus Lie Hetland, and H avard Engum. Incremental and decremental proximal support vector classification using decay coefficients. In DaWak, pages 422--429, 2003

    2003

  93. [101]

    Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27 0 (11): 0 1134--1142, 1984

    1984

  94. [102]

    The nature of statistical learning theory, 1995

    Vladimir N Vapnik. The nature of statistical learning theory, 1995

    1995

  95. [103]

    Kga: A general machine unlearning framework based on knowledge gap alignment

    Lingzhi Wang, Tong Chen, Wei Yuan, Xingshan Zeng, Kam-Fai Wong, and Hongzhi Yin. Kga: A general machine unlearning framework based on knowledge gap alignment. arXiv preprint arXiv:2305.06535, 2023

    2023 arXiv

  96. [104]

    A compression technique for analyzing disagreement-based active learning

    Yair Wiener, Steve Hanneke, and Ran El-Yaniv. A compression technique for analyzing disagreement-based active learning. J. Mach. Learn. Res., 16: 0 713--745, 2015

    2015

  97. [105]

    Open problem: The oracle complexity of convex optimization with limited memory

    Blake Woodworth and Nathan Srebro. Open problem: The oracle complexity of convex optimization with limited memory. In Conference on Learning Theory, pages 3202--3210. PMLR, 2019

    2019

  98. [106]

    Deltagrad: Rapid retraining of machine learning models

    Yinjun Wu, Edgar Dobriban, and Susan Davidson. Deltagrad: Rapid retraining of machine learning models. In International Conference on Machine Learning (ICML), 2020

    2020

  99. [107]

    u hle, Andrew Paverd, Olga Ohrimenko, Boris K \

    Santiago Zanella-B \'e guelin, Lukas Wutschitz, Shruti Tople, Victor R \"u hle, Andrew Paverd, Olga Ohrimenko, Boris K \"o pf, and Marc Brockschmidt. Analyzing information leakage of updates to natural language models. In CCS, pages 363--375, 2020

    2020

  100. [108]

    Rethinking influence functions of neural networks in the over-parameterized regime

    Rui Zhang and Shihua Zhang. Rethinking influence functions of neural networks in the over-parameterized regime. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021

    2021

  101. [109]

    Negative preference optimization: From catastrophic collapse to effective unlearning

    Ruiqi Zhang, Licong Lin, Yu Bai, and Song Mei. Negative preference optimization: From catastrophic collapse to effective unlearning. arXiv preprint arXiv:2404.05868, 2024

    2024 arXiv

Pith tools

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