PaperlayerView exact revision on arXiv

Source-linked AI summary

Making AI Forget You: Data Deletion in Machine Learning

Antonio Ginart, Melody Y. Guan, Gregory Valiant, James Zou

arXiv:1907.05012v2cs.LGstat.ML

TL;DR

When data can no longer be used, removing it from a trained model by retraining from scratch may be computationally impractical. This paper formalizes efficient data deletion and proposes two k-means deletion algorithms, reporting over 100× average speedup in amortized runtime across six datasets versus canonical Lloyd’s algorithm seeded by k-means++ [53, 5].

  • Problem

    Removing an individual’s data from a trained model by retraining on the remaining data can be computationally impractical.

    Source: §1 · p. 2

  • Method

    The paper formalizes exact data deletion and deletion efficiency in an online setting, then proposes two deletion-efficient algorithms for k-means clustering.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    Over 100× average speedup in amortized runtime across six datasets versus canonical Lloyd’s algorithm seeded by k-means++ [53, 5] is reported for the proposed methods.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper synthesizes four engineering principles for designing deletion-efficient learning systems.

    Source: §1 · p. 2

    The paper focuses on exact deletion and defers approximate deletion to future work.

    Source: §3 · p. 3

Abstract

from arXiv · show

Intense recent discussions have focused on how to provide individuals with control over when their data can and cannot be used --- the EU's Right To Be Forgotten regulation is an example of this effort. In this paper we initiate a framework studying what to do when it is no longer permissible to deploy models derivative from specific user data. In particular, we formulate the problem of efficiently deleting individual data points from trained machine learning models. For many standard ML models, the only way to completely remove an individual's data is to retrain the whole model from scratch on the remaining data, which is often not computationally practical. We investigate algorithmic principles that enable efficient data deletion in ML. For the specific setting of k-means clustering, we propose two provably efficient deletion algorithms which achieve an average of over 100X improvement in deletion efficiency across 6 datasets, while producing clusters of comparable statistical quality to a canonical k-means++ baseline.

1 Introduction

The paper frames efficient data deletion as a machine-learning data-management problem motivated by withdrawal rights and costly retraining, then develops a framework and studies k-means deletion algorithms.

1 Introduction

  • UK Biobank participant withdrawals, GDPR and Right to Be Forgotten obligations, and model-inversion attacks motivate controlling continued use of models trained on deleted data.The introduction notes that continued use of AI systems trained on deleted data could be considered illegal under certain interpretations.Source: §1 · p. 1
  • Deletion should make an updated model independent of sample i and as if trained on the remaining n−1 points, avoiding the often-intractable cost of retraining from scratch.The paper formalizes efficient data deletion for machine learning models.Source: §1 · p. 2
  • Efficient deletion could also speed up leave-one-out cross-validation, support user data marketplaces, or help identify valuable datapoints [37].Source: §1 · p. 2
  • Across six datasets, two k-means deletion methods achieved over 100× average amortized-runtime speedup versus Lloyd’s algorithm seeded by k-means++ [53, 5], with comparable clustering quality on three metrics.The methods achieve optimal deletion efficiency in certain regimes.Source: §1 · p. 2
  • The paper defines deletion-efficient learning for possibly stochastic models, poses deletion as an online problem, and derives optimal deletion efficiency from a lower bound on amortized computation time.The introduction notes that deletion efficiency had not been studied generally and that stochastic-learning deletion lacked a definition.Source: §1 · p. 2
  • The authors synthesize four engineering principles from their theory and experiments for designing deletion-efficient learning systems.They also describe the principles as an algorithmic toolbox.Source: §1 · p. 2

2 Related Works

Efficient deletion updates are known for several canonical learning algorithms. Data deletion and privacy are related but distinct: deletion is constrained by computation, while privacy raises statistical challenges.

Deterministic Deletion Updates

  • Efficient deletion updates cover linear models, some lazy-learning methods, recursive SVMs, and co-occurrence collaborative filtering.Examples of lazy-learning methods include Nadaraya-Watson kernel regressions and nearest-neighbors methods.Source: §2 · p. 2

Data Deletion and Data Privacy

  • Efficient deletion and privacy are distinct: deletion's challenge is computational, whereas privacy raises statistical challenges even without computational limits.Retraining from scratch supports naive deletion without requiring privacy guarantees; conversely, an operation that outputs the entire dataset could support deletion but would not be private.Source: §2 · p. 2

3 Problem Formulation

The section formalizes deletion as producing a model indistinguishable in distribution from retraining without the deleted point, then frames deletion efficiency as an online computational problem. It also presents design principles for algorithms that support efficient deletion.

3 Problem Formulation

  • A deletion operation must produce a model distributed identically to the learning algorithm’s output when trained on the dataset without the specified point.The operation takes the dataset, its trained model, and the point’s index as input.Source: §3 · p. 3
  • The paper focuses on exact deletion, while approximate deletion relaxes the requirement to a bound on the distance or divergence between output distributions.The authors defer a full discussion of approximate deletion, including its connection to differential privacy, to future work.Source: §3 · p. 3

A Computational Challenge

  • Because retraining on the remaining dataset is always a deletion option, the challenge is to make deletion computationally efficient, potentially sublinear in dataset size or original training time.The formulation also asks how metadata memory constraints affect deletion efficiency.Source: A Computational Challenge · p. 3
  • The online formulation processes a stream of m≤n distinct deletion indices one at a time and seeks to minimize amortized computation while outputting the model after each deletion.The authors propose amortized runtime as a measure of deletion efficiency.Source: A Computational Challenge · p. 3
  • The amortized runtime has a lower bound of Ω(n/m) for sequential learning algorithms, assuming each algorithm processes every datapoint and deletion can otherwise take constant time.The passage gives this bound for n datapoints and m deletion requests.Source: A Computational Challenge · p. 3
  • The paper calls algorithms meeting the lower bound deletion efficient, notes tight bounds remain open for several paradigms, and studies k-means as a case achieving efficiency without sacrificing statistical performance.The named open cases include ridge regression, decision trees, and stochastic optimization.Source: A Computational Challenge · p. 3

3.1 General Principles for Deletion Efficient Machine Learning Systems

  • The four proposed principles include linearity for post-processing away a point’s influence and quantization to enable fast average-case deletions when small deletion counts leave the model unchanged.Quantization is most effective when the number of parameters is small relative to the dataset; linearity is most effective where feature spaces reveal linear relationships.Source: §3.1 · pp. 3–4
  • Laziness delays computation until inference, simplifying deletion, while modularity confines computation or model dependence to dataset partitions so only affected modules need recomputation.Laziness suits settings with fewer constraints on inference time and memory than on training or deletion; modularity is most effective when data dimension is small relative to dataset size.Source: §3.1 · p. 4

4 Deletion Efficient Clustering

The section studies efficient deletion from k-means models, treating the output centroids as the model and proposing two algorithms with theoretical runtime and statistical guarantees.

4.1 Quantized k-Means

  • Q-k-means quantizes centroids at each iteration, memoizes state for deletion, and retrains from scratch only when deletion changes a quantized centroid or removes an initial centroid.The quantization maps points to a randomly shifted uniform ϵ-lattice; if recomputation is unnecessary, linearity lets the algorithm update metadata to reflect the deletion without recomputing centroids.Source: §4.1 · pp. 4–5
  • Q-k-means supports m deletions in expected time O(m^2 d^{5/2}/ϵ), with probability over quantization and k-means++ initialization.The bound is worst-case over normalized datasets; quantization makes centroids stable to many small deletion perturbations, so most deletions need no centroid recomputation.Source: §4.1 · p. 5
  • Q-k-means has expected loss at most (8logk+16)L*+ϵ, matching the k-means++ upper bound up to an additive ϵ.The corollary applies to Q-k-means loss on a problem instance of size n.Source: §4.1 · p. 5

4.2 Divide-and-Conquer k-Means

  • DC-k-means uses tree width w as a trade-off knob, with empirical statistical performance tending to decrease as w increases.At w=1, DC-k-means reduces to canonical Lloyd’s algorithm.Source: §4.2 · p. 6
  • DC-k-means partitions data among leaves, solves k-means subproblems, and merges centroids up a tree; depth-1 trees support m deletions in expected O(m max{n^ρ,n^{1−ρ}}d) time.A deletion requires recomputing only the affected leaf’s subproblem and the path from that leaf to the root; the runtime bound assumes w=Θ(n^ρ), 0<ρ<1, with probability over dataset partitioning.Source: §4.2 · p. 6

4.3 Amortized Runtime Complexity in Online Deletion Setting

  • Q-k-means is α-deletion efficient in expectation when ϵ=Θ(n^−β) and α≤1−β; depth-1 DC-k-means is α-deletion efficient when α<1−max{1−ρ,ρ}.For DC-k-means, the condition assumes w=Θ(n^ρ), with 0<ρ<1; α-deletion efficiency means amortized runtime O(n^{1−α}).Source: §4.3 · p. 7

5 Experiments

In the simulated online deletion benchmark, Q-k-means and DC-k-means achieve orders-of-magnitude speedups, while the three methods have competitive statistical clustering performance. The speedup patterns differ by dataset dimensionality, and statistical performance remains virtually unchanged over 1,000 deletions.

5 Experiments

  • The benchmark uses a uniformly random, without-replacement stream of 1,000 deletions; the canonical k-means baseline retrains from scratch for each request.Each algorithm trains once on the full dataset and produces an intermediate model after each deletion.Source: §5 · p. 7

5.1 Statistical Performance Metrics

  • Clustering quality is evaluated using k-means optimization loss, silhouette coefficient, and normalized mutual information (NMI).Silhouette uses spatial information without labels, while NMI measures agreement with ground-truth labels up to permutation; higher values indicate better results for both metrics.Source: §5.1 · p. 7

5.2 Summary of Results

  • Q-k-means offers greater speedups at lower dimension relative to sample size, whereas DC-k-means is more consistent across dimensionalities.MNIST and Covtype have the highest d/n ratios and are the datasets where Q-k-means offers the least speedup; DC-k-means speedup increases with n for fixed d.Source: §5.2 · pp. 8–9
  • Both proposed algorithms achieve orders-of-magnitude speedups over retraining, while all three methods have competitive statistical clustering performance.Table 4 reports amortized training-plus-deletion runtime; Tables 1–3 report clustering quality.Source: §5 · p. 7, Table 4 · p. 8, §5.2 · p. 8
  • Across the 1,000-request benchmark, statistical performance remains virtually unchanged, and Q-k-means deletion efficiency has higher variance.The authors attribute Q-k-means variance to centroid-stabilization randomness having greater impact than dataset-partition randomness; 1,000 deletions are less than 10% of each dataset.Source: §5.2 · p. 9

6 Discussion

The discussion presents four design principles for deletion-efficient learning and considers how to extend them beyond clustering to supervised methods. It sketches possible deletion mechanisms for regression, trees, forests, and neural-network training, with conditions and limitations for some approaches.

6 Discussion

  • The paper proposes four design principles as pillars for deletion-efficient learning and discusses applying them beyond clustering to supervised methods.The discussion notes that existing deletion-efficient supervised methods mainly cover linear models, support vector machines, and non-parametric regressions.Source: §6 · p. 9

Segmented Regression

  • Combining Q-k-means with cluster-specific linear least-squares models could support segmented regression, with deletions enabling a simple update if clusters remain stable.Segmented linear regression is described as a relaxation of canonical regression models.Source: §6 · p. 9

Kernel Regression

  • Random Fourier feature kernel regression could support efficient large-scale deletion because only its data-independent feature-space linear layer requires updating.Random Fourier feature methods have also shown affinity for quantization [91].Source: §6 · p. 9

Decision Trees and Random Forests

  • Quantized or randomized split criteria may enable efficient deletion in decision trees, while bagging gives random forests a natural route to modularity.Source: §6 · p. 9

Deep Neural Networks and Stochastic Gradient Descent

  • Neural-network quantization and pruning robustness [46] [25] [52] may enable stable quantized SGD updates, but scaling requires larger batches and fewer gradient steps.Approximate deletion may also overcome shortcomings of exact deletion for large neural models.Source: §6 · p. 9

7 Conclusion · A Supplementary Materials

The paper develops a notion of deletion efficiency and provably deletion-efficient unsupervised clustering algorithms, while identifying principles that may extend to other learning paradigms. It notes that the work relies on simplifying assumptions and points to more complex deletion settings as future work.

7 Conclusion

  • The paper develops a notion of deletion efficiency for large-scale learning systems and proposes provably deletion-efficient unsupervised clustering algorithms.Source: §7 · p. 9
  • The authors identify potential algorithmic principles that may enable deletion efficiency for other learning algorithms and paradigms.Source: §7 · p. 9
  • The work assumes a system with only one model and one database.Source: §7 · p. 9
  • It also assumes that each user-based deletion request corresponds to a single data point.Source: §7 · p. 9
  • Future work should address deletion efficiency across many models and databases and complex user-to-data relationships.Source: §7 · p. 9

A Supplementary Materials

  • The supplementary materials provide material that may repeat the main text and include technical minutiae too detailed for the main body.Source: A Supplementary Materials · p. 15

A.1 Online Data Deletion … C Mathematical Details

The appendices define average-case, robust, and approximate deletion, then give algorithmic details for Q-k-means and divide-and-conquer k-means, along with mathematical notation for the proofs.

A.1 Online Data Deletion

  • A deletion operation must match retraining in distribution when the deleted index is independent of the learned model; robust deletion extends this requirement to adversarially chosen indices.The appendices note that adversarial requests can violate DC-k-means deletion correctness, while Q-k-means deletion remains robust but can be made inefficient by repeatedly deleting an initial centroid.Source: §A.1 · pp. 15–16
  • For m=Θ(n^α), k-means algorithms reach the ideal lower bound for sufficiently small α, while average-case online deletion samples indices uniformly and without replacement.An algorithm is α-deletion efficient when its amortized runtime is O(n^(1−α)); adversarial deletion sequences and memory constraints are left for future study.Source: §A.1 · p. 16

A.2 Approximate Data Deletion; A.2.1 Approximate Deletion and Differential Privacy

  • Approximate deletion permits a bounded distributional discrepancy from retraining; differential privacy is a possible route, but streaming deletions raise unresolved leakage and noise concerns.The passage cautions that privacy may reveal dataset size or deletion counts through group size, and that group privacy can require substantially more noise.Source: §A.2 · p. 16, §A.2.1 · p. 17

B Algorithmic Details; B.1 Quantized k-Means

  • Q-k-means combines k-means++ initialization with quantization, memoization, balance correction, and early termination; deletion retrains if an initial centroid was selected or quantization stability fails.Its deletion procedure otherwise verifies centroid stability and updates the stored state and dataset.Source: B Algorithmic Details · p. 17, §B.1 · pp. 17–18

B.1.1 γ-Balanced Clusters

  • Q-k-means corrects small clusters by averaging current and previous centroids to reduce instability; γ=0.2 is suggested unless data are severely imbalanced.For severely imbalanced datasets, the appendix says DC-k-means may be preferable.Source: §B.1.1 · p. 18

B.1.2 Quantizing with an ϵ-Lattice

  • Q-k-means quantizes centroids by rounding to the nearest vertex of a uniform ϵ-lattice and applying an independent uniform random phase shift in each dimension.Source: §B.1.2 · pp. 18–19

B.2 Divide-and-Conquer k-Means; B.3 Initialization for k-Means

  • Divide-and-conquer deletion recomputes subproblems only along the deleted point’s leaf-to-root path; both proposed algorithms use k-means++ initialization.Source: §B.2 · p. 19, §B.3 · p. 19

C Mathematical Details

  • The mathematical appendix establishes notation for proofs, including shorthand for retrained models and deletion operations.Source: C Mathematical Details · p. 19

C.1 Proof of Theorem 4.1 · C.2 Proofs of Corollaries and Propositions

The proof establishes an expected-time bound for Q-k-means deletions using stability of the quantized clustering output and a memo-based check that triggers retraining when needed. It also specifies the assumptions used for the theorem and the asymptotic regime considered for the corollary proofs.

C.1 Proof of Theorem 4.1

  • Q-k-means supports m deletions in expected time O(m^2 d^(5/2)/ϵ).The proof accounts for sequentially processing the deletion requests while scaling the analysis primarily with m, ϵ, and n.Source: §C.1 · p. 21
  • Theorem 4.1 assumes data scaled onto the unit hypercube; it also holds with an assumed constant-factor radial bound instead.The proof is organized into Lemmas C.1 through C.3.Source: §C.1 · p. 20
  • With shared initial centroids and quantization maps, Q-k-means returns the same centroids on D and D−∆ for deletions disjoint from the initialization, with the lemma’s stated probability.Lemma C.3 states this stability for any ∆⊂D with |∆|≤m; its probability bound is with respect to quantization randomness.Source: §C.1 · p. 20
  • A runtime memo checks whether a deletion changes the algorithm’s output; if it does, the algorithm retrains from scratch, otherwise it reuses the output.Retraining takes O(nkTd), while verifying the memo at deletion time takes O(kTd).Source: §C.1 · p. 21
  • The deletion mechanism’s correctness argument conditions on the deleted point not being a k-means++ initialization and couples the iid random phase sequences for the original and deleted datasets.The proof uses the equality in distribution of the initializations under that conditioning and verifies output stability using the training-time memo.Source: §C.1 · p. 21

C.2 Proofs of Corollaries and Propositions

  • For the online asymptotic analysis, the corollary proofs set ϵ=Θ(n^-β) and w=Θ(n^ρ), with β,ρ∈(0,1).The analysis focuses on the asymptotic effects of n, m, ϵ, and w, treating other variables as constants.Source: §C.2 · p. 21

C.2.1 Proof of Corollory 4.1.1 · C.2.2 Proof of Proposition 4.2

The proofs bound Q-k-means expected loss using the k-means++ guarantee and establish DC-k-means deletion-time and correctness guarantees under a fixed-leaf-count design.

C.2.1 Proof of Corollory 4.1.1

  • Using Arthur and Vassilvitskii’s k-means++ guarantee, Corollary 4.1.1 bounds Q-k-means expected loss by (8lnk+16)L* + ϵ.The cited k-means++ guarantee bounds expected loss by (8lnk+16)L*; the corollary adds ϵ.Source: §C.2.1 · p. 22

C.2.2 Proof of Proposition 4.2

  • DC-k-means supports m deletions in expected time O(mnmax(ρ,1−ρ)d) with a depth-1, w-ary tree and w=Θ(nρ), for ρ∈(0,1).The proposition’s probability qualification is over the randomness in dataset partitioning.Source: §C.2.2 · p. 22
  • Correctness requires that removing datapoint i yields the same distribution as applying the algorithm to D−i; independent leaf assignment preserves the remaining points’ distribution.The number of leaves must not change when a point is deleted.Source: §C.2.2 · p. 22
  • Rounding the intended n^ρ leaves to the nearest power of 2 keeps their count within a factor of 2, but a rounding change can require retraining from scratch.In the fractional-power regime, such retraining can occur only a constant number of times, leaving amortized or average-case asymptotic time unchanged.Source: §C.2.2 · p. 22
  • The runtime analysis models each deletion as sampled uniformly without replacement and uses J to represent the subproblem size seen by a randomly selected datapoint.J is defined as n times the empirical fraction of datapoints assigned to a leaf, where the empirical distribution comes from n samples over n^ρ elements.Source: §C.2.2 · pp. 22–23
  • The runtime bound separates leaf and root deletion costs, with expected total time at most O(mkTd)E(J)+O(mn^ρk^2Td).The first term accounts for total deletion time at the leaves and the second for total deletion time at the root.Source: §C.2.2 · p. 23

C.2.3 Proof of Corollary 4.2.1

The proof analyzes Q-k-means deletion efficiency under polynomial rates for the error parameter and dataset size, and states an efficiency condition on α and β.

C.2.3 Proof of Corollary 4.2.1

  • With ϵ=Θ(n^-β) for 0<β<1, the corollary states that Q-k-means is deletion efficient in expectation if α≤1−β.Source: §C.2.3 · p. 23
  • Under ϵ=Θ(n^-β) and m=Θ(n^α), the proof gives amortized time O(n^(1−α)+n^(α+β)) and concludes efficiency when 1−α>α+β.The proof derives the time scaling by applying these rates to the expected deletion time from Theorem 4.1, adding training time, and amortizing.Source: §C.2.3 · p. 23

C.2.4 Proof of Corollary 4.2.2 … D.3 Supplementary Experiments

The corollary gives an asymptotic condition under which DC-k-means is deletion efficient; the supplementary material specifies experimental procedures, implementation choices, parameter heuristics, and additional experiments.

C.2.4 Proof of Corollary 4.2.2

  • With w=Θ(n^ρ), DC-k-means is deletion efficient in expectation for a depth-1 w-ary tree when α≤1−max(ρ,1−ρ).The proof uses deletion runtime O(n^max(ρ,1−ρ)) and training time O(n), with m=Θ(n^α).Source: §C.2.4 · p. 23

D.1 Experimental Protocol

  • The online benchmark compares k-means++ with Lloyd’s algorithm, Q-k-means, and DC-k-means across six datasets using amortized wall-clock time.Each method is tested in five replicates; after full-data training, models satisfy 1,000 uniformly random deletion requests, with total time divided by 1,000.Source: §D.1 · pp. 23–24

D.1.1 Implementation Framework

  • All three methods use the same in-house Lloyd-iteration optimization routine, based on Numpy.The implementation is available at the URL given in the paper.Source: §D.1.1 · p. 24

D.1.2 Heuristic Parameter Selection

  • For Q-k-means, the heuristic sets ϵ=2⌊−log10(n/(kd^1.5))−3⌉ and γ=0.2; for DC-k-means, it sets w to n^0.3 rounded to a power of two.Both methods use 10 iterations; the Q-k-means heuristic balances centroid stability against quantization noise, while DC-k-means width balances subproblem size and count.Source: §D.1.2 · p. 24

D.1.3 Clustering Performance Metrics

  • Clustering quality is measured by silhouette coefficient and normalized mutual information, with silhouette computed on a random 10,000-point subsample per instance.The evaluations use Scikit-Learn routines [65].Source: §D.1.3 · p. 24

D.1.4 Scaling

  • All datasets except MNIST are min-max scaled to the unit hypercube, but scaling is unnecessary and the theory also applies to unscaled data with an additional constant factor.If deletions change min-max scaling, retraining when an extremal point is deleted has negligible empirical and asymptotic runtime impact.Source: §D.1.4 · pp. 24–25

D.2 Datasets

  • The six datasets are Celltypes, Postures, Covtype, Botnet, MNIST, and a synthetic Gaussian mixture.Celltypes, Postures, Covtype, Botnet [56], and MNIST are described alongside their sample sizes and features; the Gaussian dataset has five 25-dimensional clusters and 100,000 samples.Source: §D.2 · p. 25

D.3 Supplementary Experiments; D Implementation and Experimental Details

  • The supplementary experiments examine Q-k-means centroid stability and how ϵ and w affect clustering quality and online deletion efficiency.The appendix also elaborates on implementation details and the main-body experimental protocol.Source: D Implementation and Experimental… · p. 23, §D.3 · p. 25

D.3.1 Re-training During Deletion Stream for Q-k-means … E.3 Hyperparameter Tuning

The appendix examines Q-k-means retraining stability and how quantization granularity and tree width affect loss and deletion runtimes. Its discussion frames deletion efficiency against statistical performance, and notes concerns about overparameterization and hyperparameter tuning.

D.3.1 Re-training During Deletion Stream for Q-k-means

  • For higher effective dimensionality relative to sample size, as with MNIST, Q-k-means retraining proceeds at a roughly constant slope through deletions, indicating limited centroid stability.The experiment plots average retrains from scratch needed to satisfy deletion requests throughout the stream.Source: §D.3.1 · pp. 25–26, Figure 2 · p. 25

D.3.2 Effects of Quantization Granularity and Tree Width on Optimization Loss

  • Across six datasets, Q-k-means performance rapidly deteriorates as ϵ→1, consistent with the theoretical analysis.The comparison uses k-means optimization loss normalized to the baseline and restricts trees to depth 1.Source: Figure 3 · p. 26, §D.3.2 · p. 26
  • As tree width increases, performance generally decreases, but not always monotonically; on some datasets, random-seed variance appears to dominate width’s effect.The relationship between width and loss is difficult to analyze theoretically.Source: Figure 4 · p. 26, §D.3.2 · p. 27

D.3.3 Effects of Quantization Granularity and Tree Width on Deletion Efficiency

  • On Covtype, Q-k-means runtimes increase monotonically as ϵ→0, while DC-k-means runtimes are minimized at an optimal tree width of approximately 32–64 leaves.The experiment sweeps ϵ and w for both methods.Source: Figure 5 · p. 27, Figure 6 · p. 27, §D.3.3 · p. 27

E Extended Discussion

  • The extended discussion covers relevant ideas that could not fit in the paper’s main body.It includes the deletion-efficiency/statistical-performance trade-off, overparameterization, and hyperparameter tuning.Source: E Extended Discussion · p. 27

E.1 Deletion Efficiency vs. Statistical Performance

  • Complex, stochastic processing can improve statistical learning but make deletion inefficient or require retraining, while simpler, structured processing supports efficient deletion but may weaken statistical performance.The paper frames this as the central design trade-off for deletion-efficient learning systems.Source: §E.1 · p. 27

E.2 Overparametrization, Dimensionality Reduction and Quantization

  • Quantization may perform poorly with overparameterized models; metric-preserving dimensionality reduction techniques could potentially help in some situations.Source: §E.2 · p. 27

E.3 Hyperparameter Tuning

  • When hyperparameter tuning falls within deletion’s scope, tuning on data unlikely to be deleted soon or using data-independent heuristics may be prudent.The paper describes tuning as a conundrum for deletion-efficient learning.Source: §E.3 · p. 28

Related papers

Loading 1907.05012v2…