PaperlayerView exact revision on arXiv

Source-linked AI summary

DeltaGrad: Rapid retraining of machine learning models

Yinjun Wu, Edgar Dobriban, Susan B. Davidson

arXiv:2006.14755v2cs.LGstat.ML

TL;DR

For small dataset changes, retraining can require recomputing the full optimization path at a cost comparable to original training. DeltaGrad uses information cached during training for rapid retraining; experiments report speed-ups up to 6.5x with negligible accuracy loss.

  • Problem

    For small dataset additions or deletions, retraining can require recomputing the full optimization path at a cost comparable to original training.

    Source: §1 · p. 1

  • Method

    DeltaGrad rapidly retrains models after slight training-dataset changes using information cached during training.

    Source: §1 · p. 1

  • Results

    Up to 6.5x speed-ups with negligible accuracy loss were observed on several medium-scale standard-dataset problems, including two-layer neural networks.

    Source: §1 · p. 2

  • Takeaways & Limitations

    DeltaGrad is presented as an approach for updating production models with newly acquired data and for handling data changes by removing the original data and then adding the changed data.

    Source: §5.2 · p. 8

    Theoretical speed-ups are not fully achieved because L-BFGS computation and explicit-gradient overhead remain non-negligible.

    Source: §4.2.2 · p. 7

Abstract

from arXiv · show

Machine learning models are not static and may need to be retrained on slightly changed datasets, for instance, with the addition or deletion of a set of data points. This has many applications, including privacy, robustness, bias reduction, and uncertainty quantifcation. However, it is expensive to retrain models from scratch. To address this problem, we propose the DeltaGrad algorithm for rapid retraining machine learning models based on information cached during the training phase. We provide both theoretical and empirical support for the effectiveness of DeltaGrad, and show that it compares favorably to the state of the art.

1. Introduction

DeltaGrad uses information cached during training to rapidly retrain SGD-based models after small dataset changes, addressing the cost of retraining from scratch. The paper reports theoretical and empirical support for its accuracy and speed, with applications including privacy, robustness, debiasing, and statistical inference.

1. Introduction

  • Retraining from scratch after small dataset changes can require recomputing the full optimization path, despite uses in privacy, robustness, bias reduction, and uncertainty quantification.Examples include removing data for privacy and robustness, leave-one-out retraining for jackknife bias correction, and subset retraining for conformal prediction.Source: §1 · p. 1

1.1. Related work

  • Prior retraining approaches are limited to specialized problems or require algorithm-changing randomization, while Hessian-based deletion can handle only one sample and is unsuitable for many large-scale applications.The introduction cites k-means and logistic regression as specialized cases and notes the single-sample limitation of Koh & Liang (2017).Source: §1 · p. 1, §1.1 · p. 2

1. Introduction

  • DeltaGrad uses cached training information to differentiate the optimization path and retrain general empirical-risk-minimization models trained with SGD, without additional randomization.The method targets small dataset changes, such as adding or deleting samples.Source: §1 · p. 1, §1.1 · p. 2
  • Up to 6.5x speed-ups with negligible accuracy loss were reported across medium-scale problems, including two-layer neural networks.Figure 1 also illustrates faster runtime than training from scratch and accuracy for logistic regression on RCV1 as data are added or deleted.Source: Figure 1 · p. 1, §1 · p. 2

1.1. Related work

  • The paper proves that DeltaGrad approximates the true optimization path at a fast rate for strongly convex objectives and reports smaller-order error than the fraction of points removed for both GD and SGD.Its empirical results cover addition, removal, and continuous updates, and the paper describes applications in privacy, robustness, debiasing, and statistical inference.Source: §1 · p. 2, §1.1 · p. 2

2. Algorithms

DeltaGrad targets efficient retraining after removing a small set of training samples, and also applies when samples are added. It reuses information cached during original training to approximate updates, with convergence and complexity analyses under stated conditions.

2.1. Setup

  • When r≪n samples are removed, the goal is to update the model to the minimizer on the remaining data; the method also applies to adding r samples.The naive solution reruns gradient descent over the remaining training samples.Source: §2.1 · p. 3

2.2. Proposed DeltaGrad Algorithm

  • DeltaGrad uses cached parameters and gradients with a leave-r-out gradient formula, then approximates Hessian-vector products using L-BFGS after burn-in, computing full gradients every T0 iterations.Between full-gradient iterations, it maintains historical parameter and gradient differences for the L-BFGS update.Source: §2.2 · pp. 3–4

2.3. Convergence rate for strongly convex objectives

  • The convergence analysis assumes strongly convex, smooth losses, bounded gradients, Lipschitz Hessians, and strongly independent weight updates.The paper reports a normalized-update minimum singular value around 0.2 on MNIST with default hyperparameters.Source: §2.3 · p. 4

2.3.1. RESULTS

  • For sufficiently large t, Theorem 1 bounds DeltaGrad iterates against retrained iterates and reports a better convergence rate than the expected baseline error of order r/n.The comparison is between DeltaGrad’s approximation and the full-model parameter baseline; the supplied passage does not expose the theorem’s bound formula.Source: §2.3.1 · p. 4

2.4. Complexity analysis

  • At approximate-gradient steps, DeltaGrad costs 6rf(p)+O(m^3)+6mp+p versus 6(n-r)f(p) for explicit gradients when r≪n; speedups of factor T0 are expected when j0≪T.The speedup expectation assumes n is large enough that approximation overhead is much smaller than explicit computation.Source: §2.4 · p. 5

3. Extension to SGD

DeltaGrad extends retraining to mini-batch SGD by accounting for removed examples and using historical observations. For strongly convex objectives, the paper gives an approximation-rate guarantee and says accuracy holds when the batch size is large and the removed fraction is small.

3. Extension to SGD

  • For mini-batch SGD, DeltaGrad adjusts updates for removed examples, leaves parameters unchanged when B−ΔB_t=0, and relies on historical observations.The update also uses a periodic or early-iteration condition.Source: §3 · p. 5

3.1. Convergence rate for strongly convex objectives

  • Theorem 2 gives a high-probability approximation-rate guarantee for strongly convex objectives, with accurate iteration approximations when B is large and r/n is small.The supplied passages do not include the probability threshold or the rate expression.Source: §3.1 · p. 5

4. Experiments

Across batch and online additions or deletions, DeltaGrad substantially speeds model updates while closely tracking retraining outputs and preserving prediction performance in the reported experiments.

4.1. Experimental setup.

  • Experiments tested batch and sequential edits using regularized logistic regression on four datasets and a two-layer MNIST network, measuring update time, parameter distances, and test performance.For DNNs, the method was adjusted to evaluate gradients explicitly outside regions where convexity was assumed locally.Source: §4.1 · pp. 5–6

4.2.1. BATCH ADDITION/DELETION.

  • For batch edits, the distance between DeltaGrad’s and BaseL’s updated parameters stayed below 0.0001 at rates up to 1%, and was at least tenfold smaller than the retraining-to-full-data distance.Near zero edit rates, the distance was 10^-6 (10^-8 for RCV1).Source: §4.2.1 · p. 6
  • On MNIST’s two-layer network, the modified DeltaGrad variant achieved about 1.4x speedup over BaseL while maintaining a relatively small parameter difference.The network lacks strong-convexity guarantees; the authors leave extending the analysis beyond strong convexity for future work.Source: §4.2.1 · pp. 6–7
  • For any given delete or add rate, DeltaGrad achieved speedups over BaseL of up to 2.6x on MNIST, 2x on covtype, 1.6x on HIGGS, and 6.5x on RCV1.Running time of BaseL and DeltaGrad was almost constant regardless of delete or add rate.Source: §4.2.1 · p. 6
  • Batch-edit predictions from BaseL and DeltaGrad were effectively the same in most cases; where results differed, their confidence intervals overlapped.The reported comparisons cover the 0.005% and 1% add/delete rates.Source: §4.2.1 · p. 6, Table 1 · p. 7

4.2.2. ONLINE ADDITION/DELETION.

  • The authors attribute unrealized theoretical speedups partly to L-BFGS matrix-operation overhead and costs of transferring data to the GPU and launching kernels for explicit gradients.They suggest future work on better utilizing GPU computation.Source: §4.2.2 · pp. 7–8
  • For 100 sequential additions or deletions, DeltaGrad was 2.5x, 2x, 1.8x, and 6.5x faster than BaseL on MNIST, covtype, HIGGS, and RCV1, respectively.The paper reports essentially no prediction-performance difference between the methods.Source: §4.2.2 · p. 7, Figure 4 · p. 8, Table 2 · p. 8

5. Applications

DeltaGrad is presented as useful for data deletion, continuous updating, robustness, data valuation, bias reduction, and uncertainty quantification. The applications rely on rapidly retraining models after changes to training data or across data subsets.

5.1. Privacy related data deletion

  • DeltaGrad can support private data deletion by using approximate deletion (Ginart et al., 2019) and adding Laplace noise to obtain an ϵ-approximate deletion.The stated noise is independent Laplace (δ/ϵ) noise added to each coordinate of the algorithm’s output.Source: §5.1 · p. 8

5.2. Continous model updating

  • DeltaGrad can update production models with newly acquired data and handle data changes by removing the original data, then adding the changed data.The authors describe this as a direct application of DeltaGrad.Source: §5.2 · p. 8

5.3. Robustness

  • DeltaGrad can speed robust learning that identifies outliers with a preliminary model, prunes them, and refits the model.The passage notes that methods using this approach are statistically efficient for certain problems.Source: §5.3 · p. 8

5.4. Data valuation

  • DeltaGrad can speed leave-one-out evaluation of how deleting a training sample changes model parameters, a common approach to assessing sample importance (Ghorbani & Zou, 2019).The authors identify support for smaller SGD mini-batches and models without strong convexity and smoothness guarantees as future work.Source: §5.4 · pp. 8–9

5.5. Bias reduction

  • DeltaGrad can recompute an estimator on every training subset of size n − 1, enabling jackknife bias correction, including for logistic regression when n is not much larger than p (Sur & Cand`es, 2018).The jackknife estimates bias from the estimator computed after removing each individual data point.Source: §5.5 · p. 9

5.6. Uncertainty quantification / Predictive inference

  • DeltaGrad applies to cross-conformal prediction, where models are retrained on subsets and larger K can yield shorter prediction intervals.The passage states that the resulting set has level β = 1 − 2α − 2K/n and coverage P(y_{n+1} ∈ C(x_{n+1})) ≥ β over sample randomness.Source: §5.6 · p. 9

6. Conclusion … A.1.3. CLASSICAL RESULTS FOR RANDOM VARIABLES

DeltaGrad uses information from training to retrain after slight dataset changes by differentiating the optimization path with a Quasi-Newton method. The conclusion says it is provably more accurate than retraining from scratch and reports empirical advantages on medium-scale public datasets.

6. Conclusion

  • DeltaGrad is reported to be more accurate than retraining from scratch, with empirical advantages demonstrated on medium-scale public datasets.The conclusion identifies potential applications in machine-learning systems for data deletion and addition.Source: §6 · p. 9

Appendix for DeltaGrad: Rapid retraining of machine learning models; A. Mathematical details

A.1.1. CLASSICAL RESULTS ON GD CONVERGENCE, SGD CONVERGENCE

  • For strongly convex objectives, the cited classical GD result gives exponential convergence with a fixed step size, and a companion lemma bounds contraction-operator eigenvalues.The eigenvalue bound is stated under gradient descent’s fixed-step convergence conditions.Source: §A.1.1 · p. 14
  • The SGD convergence result assumes stochastic gradient estimates correlated with the true gradient and bounded as specified, and gives a rate under a fixed-step-size condition.For unbiased estimates, the appendix relates the variance term to minibatch size and states a sufficient step-size condition.Source: §A.1.1 · pp. 14–15

A.1.2. NOTATIONS FOR DELTAGRAD WITH SGD

  • The SGD notation distinguishes full-data, explicitly retrained, and incrementally retrained parameters, assuming shared minibatch randomness and unbiased gradient estimates.The update rules are defined using the mini-batch and removed samples.Source: §A.1.2 · p. 15

A.1.3. CLASSICAL RESULTS FOR RANDOM VARIABLES

  • For SGD analysis, the appendix invokes scalar and matrix Bernstein inequalities for independent, zero-mean, bounded random variables or matrices (Oliveira, 2009; Tropp, 2012; 2016).The matrix inequality defines a deterministic variance surrogate.Source: §A.1.3 · pp. 15–16

A.2. Results for deterministic gradient descent · A.2.1. QUASI-NEWTON

For deterministic gradient descent, the paper identifies Theorem 7 as DeltaGrad’s main result; the quasi-Newton subsection describes its update and L-BFGS approximation procedure.

A.2. Results for deterministic gradient descent

  • The main result for DeltaGrad with gradient descent is Theorem 7, proved in Section A.2.8.Source: §A.2 · p. 16

A.2.1. QUASI-NEWTON

  • The Quasi-Hessian update follows equations 1.2 and 1.3 from Byrd et al. (1994), while the method also uses their formulas 3.5 and 2.25 with different notation.Source: §A.2.1 · p. 16
  • Quasi-Hessians B_jk are indexed to match parameter and gradient gaps; their indices depend on iteration t and refresh by removing the oldest entry and adding T0 each period.Source: §A.2.1 · p. 16
  • DeltaGrad applies equation (S11) to prior updates.Source: §A.2.1 · p. 16
  • Algorithm 2 takes parameter-difference and gradient-difference sequences, a vector, and history size m, and outputs an approximate Hessian-vector result at w_m.Source: §A.2.1 · pp. 16–17
  • The L-BFGS procedure forms the diagonal matrix D and lower-triangular submatrix L from ΔW^TΔG.Source: §A.2.1 · p. 17
  • It then computes a Cholesky factorization of σΔW^TΔW + LDL^T to obtain JJ^T.Source: §A.2.1 · p. 17

A.2.2. PROOF THAT QUASI-HESSIANS ARE WELL-CONDITIONED

The L-BFGS Quasi-Hessian matrices are well-conditioned: their eigenvalues admit positive lower and finite upper bounds determined by problem parameters and the bounded memory size.

A.2.2. PROOF THAT QUASI-HESSIANS ARE WELL-CONDITIONED

  • Lemma 6 establishes that the L-BFGS Quasi-Hessian matrices are well-conditioned, with positive constants K1 and K2 depending on problem parameters.The bounds apply for any t, vector z, and k in {0, 1, ..., m}.Source: §A.2.2 · p. 17
  • The lower bound does not approach zero under the stated experimental conditions, with m described as small and set to 2.The supplied proof passages do not include the explicit lower-bound expression.Source: §A.2.2 · p. 18
  • The upper bound is z^T B_jk z ≤ (k + 1)L∥z∥^2, which is at most K2∥z∥^2 for K2 = (m + 1)L.The derivation applies recursively and uses bounded m.Source: §A.2.2 · p. 18

A.2.3. PROOF PRELIMINARIES … B. Details on applications

This section develops the proof bounds and conditions underlying DeltaGrad, covering quasi-Hessian approximation, recursive and update errors, and probabilistic control of stochastic-gradient iterates. It relates incrementally updated iterates to the correct or full-data iterates and states convergence-rate and high-probability results across training iterations.

A.2.3. PROOF PRELIMINARIES

  • Under a preliminary iterate-error estimate, the proof bounds quasi-Hessian error relative to the mean Hessian and shows gradient-descent iterate gaps contract geometrically.Theorem 3 bounds secant-approximation error for intermediate quasi-Hessians; Corollary 1 and Lemma 8 support the Hessian-approximation and contraction arguments.Source: §A.2.3 · pp. 19, 21, 22

A.2.5. PROOF OF THEOREM 4

  • Theorem 4 bounds the distance between full-data iterates and iterates trained on the leave-r-out dataset.Its proof begins by establishing contraction for gradient updates and iteratively bounding the difference.Source: §A.2.4 · p. 23, §A.2.5 · p. 24

A.2.6. PROOF OF THEOREM 5

  • Theorem 5 bounds the distance between full-data and incrementally updated iterates when the quasi-Hessian error satisfies its stated condition.The proof derives a recurrent bound across quasi-Hessian update intervals and uses exact-gradient iterations as reset points.Source: §A.2.4 · p. 23, §A.2.6 · p. 25

A.2.7. PROOF OF THEOREM 6

  • Theorem 6 extends the incremental-versus-full iterate bound to all iterations by choosing j0 and T0 so the required Hessian-error condition holds throughout.The analysis says this condition holds for sufficiently small r/n; the experiments used m = 2 and T0 = 5.Source: §A.2.4 · p. 23, §A.2.7 · p. 26

A.2.4. MAIN RECURSIONS

  • Theorem 7 states that DeltaGrad’s iterates approximate the correct leave-r-out iterates at a convergence rate for all iterations.The theorem is presented as the main result of the recursion analysis.Source: §A.2.4 · p. 23

A.2.7. PROOF OF THEOREM 6

  • Theorem 6’s proof extends the iterate-error bound across successive T0-length intervals by alternating Corollary 1 and Theorem 5, with gradients evaluated explicitly at interval boundaries.For the initial interval, it uses stored updates, gradients, and quasi-Hessian matrices from the preceding m iterations.Source: §A.2.7 · pp. 27–28

A.2.8. PROOF OF THEOREM 7

  • The analysis separates the usual gradient-descent contraction component from error terms caused by using a quasi-Hessian, not having a quadratic objective, and updating with iterate wI rather than correct wU.Source: §A.2.8 · p. 29

A.3.1. QUASI-NEWTON

  • The SGD quasi-Newton variant modifies the earlier equations to use training-history updates and gradients, with positive constants K1 and K2 bounding quasi-Hessian eigenvalues.Its construction relies on the SGD training history and a bound derived by the same argument as Lemma 6.Source: §A.3.1 · p. 32

A.3.2. PROOF PRELIMINARIES

  • The SGD preliminaries bound the gradient discrepancy uniformly over iterations with high probability, and the associated Ψ1 term tends to zero as minibatch size grows.The discrepancy bound uses the gradient-norm assumption and Hoeffding’s inequality.Source: §A.3.2 · pp. 32–33
  • The SGD preliminaries also state a high-probability bound for minibatch Hessian sums and an error theorem for the mean Hessian and secant equation under an iterate-discrepancy condition.The Hessian bound is derived using matrix Bernstein; the error theorem uses the quasi-Hessian eigenvalue bounds and Hessian smoothness assumptions.Source: §A.3.2 · pp. 33–35

A.3.3. MAIN RECURSIONS

  • Theorem 10 bounds the distance between iterates on the full and leave-r-out datasets.Its stated bound holds across iterations under a probability condition.Source: §A.3.3 · p. 39
  • Theorem 11 bounds the difference between full-data iterates and incrementally updated iterates.The theorem gives bounds for the specified iterations and states that the resulting inequality holds for all iterations.Source: §A.3.3 · pp. 39–40
  • Theorem 12 bounds the distance between full-data and incrementally updated iterates for all iterations, with probability higher than 1 − T × (Ψ1 + Ψ2 + Ψ3).The bound applies when jm < t < jm + T0 − 1.Source: §A.3.3 · p. 40
  • Theorem 13 states that, with probability higher than 1 − T × (Ψ1 + Ψ2 + Ψ3), Algorithm 1’s iterates approximate the correct SGD iterates at a stated rate.The supplied passages do not give the rate expression in readable form.Source: §A.3.3 · p. 40

A.3.4. PROOF OF THEOREM 10

  • Theorem 10’s proof applies the update rules, Cauchy’s mean-value theorem, and Lemmas 3 and 9, then recurses to obtain its bound.The resulting bound holds for all iterations up to t with probability higher than 1 − t · Ψ1.Source: §A.3.4 · pp. 40–41

A.3.5. PROOF OF THEOREM 11

  • Theorem 11’s proof substitutes the subsampled iterates and quantities into the earlier argument, bounds the update difference, and applies the resulting inequality recursively.The proof uses the bound on ∥HS∥ between iterations.Source: §A.3.5 · p. 41

A.3.6. PROOF OF THEOREM 12

  • For every k ≤ t, the probability that Ω2(k) holds, conditioned on Ω1(k) and Ω3(k) holding together for every k ≤ t, is 1.When t ≤ j0, wI,St = wU,St.Source: §A.3.6 · pp. 42–43
  • Theorem 12’s proof bounds the probability of a joint-event failure using union bounds, Theorem 8, Formula (S53), and Lemma 9.The excerpt concludes that this finishes the proof and then applies the same argument across T iterations.Source: §A.3.6 · pp. 44–45

A.3.7. PROOF OF THEOREM 13

  • Theorem 13 adapts Theorem 6’s proof by replacing its variables and relying on Theorem 11 and Corollary 2; its excerpt derives high-probability inequalities for iterate differences.The stated probability is higher than 1 − T(Ψ2 + Ψ3 + Ψ1); the proof also invokes large mini-batch conditions and an asymptotic argument as t and y tend to infinity.Source: §A.3.7 · pp. 45–46

B.1. Privacy related data deletion … C.2. Extension of DeltaGrad for online deletion/addition

The supplementary material defines privacy-related data deletion and reports that randomized DeltaGrad can satisfy an approximate-deletion guarantee. It also outlines extensions for stochastic and online updates, with online analysis limited to gradient-descent deletion.

B.1. Privacy related data deletion

  • Definition 1 describes δ-deletion by comparing model behavior on the full dataset D and the dataset D−i after removing sample i.The approximate update algorithm RA updates the model after that sample is removed.Source: §B.1 · p. 46
  • Definition 3 gives a stricter approximate-deletion notion than Ginart et al. (2019), quantified over datasets and measurable subsets of H.The supplied passage introduces the definition, but its inequality is not included.Source: §B.1 · p. 47
  • Randomized DeltaGrad preserves ε-approximate deletion when suitable randomness is added to its output.The passage also describes smaller output noise, but its parameter conditions are incomplete in the supplied text.Source: §B.1 · p. 47

C. Supplementary algorithm details

  • The supplementary algorithm section frames extensions beyond deterministic batch gradient descent to stochastic updates, online deletion/addition, and non-strongly-convex, nonsmooth objectives.The supplied passages give implementation details only for stochastic gradient descent and online deletion/addition.Source: C. Supplementary algorithm details · p. 48

C.1. Extension of DeltaGrad for stochastic gradient descent

  • The SGD version of DeltaGrad replaces full-batch gradients and related quantities with their mini-batch counterparts.It uses the mini-batch average gradient GB,S in place of the full-sample average gradient ∇F.Source: §C.1 · p. 48

C.2. Extension of DeltaGrad for online deletion/addition

  • For online deletion/addition, DeltaGrad updates its history information after each request, assuming one sample is added or deleted at a time.The online version is presented as Algorithm 3, with differences from Algorithm 1 highlighted.Source: §C.2 · p. 48
  • The error-bound analysis covers gradient descent with online deletion; stochastic-gradient online addition and similar scenarios are left for future work.The passage notes that maintaining history after each request requires additional error-bound analysis.Source: §C.2 · p. 48

C.2.1. CONVERGENCE RATE ANALYSIS FOR ONLINE GRADIENT DESCENT VERSION OF DELTAGRAD · Additional notes on setup, preliminaries

The online deletion analysis assumes the removed set is small relative to the dataset and derives bounds on iterate changes, quasi-Hessian accuracy, and gradient approximation error across deletion requests.

Additional notes on setup, preliminaries

  • The setup assumes the total number of removed samples is far smaller than the dataset size and indexes deletions sequentially.At request k, the removed set contains the first k deleted samples.Source: Additional notes on setup, preliminaries · p. 48
  • Periodic explicit gradient evaluations ensure the quasi-Hessian eigenvalue bound from Lemma 6 holds across deletion requests.DeltaGrad evaluates gradients during warmup and at periodic iterations; its intervening gradients may be approximate.Source: Additional notes on setup, preliminaries · pp. 49–50
  • Theorem 14 bounds the change in BaseL iterates when one datapoint is deleted, under strong convexity and bounded individual gradients.BaseL retrains from scratch on the remaining samples for each request.Source: Additional notes on setup, preliminaries · p. 50
  • Across deletion requests, the maximum distance between iterates is bounded using the initial distance and per-request iterate changes.The stated bound is independent of the deletion-request index k.Source: Additional notes on setup, preliminaries · pp. 50–51
  • Corollary 3 bounds quasi-Hessian approximation error within a period, assuming bounded iterate changes and using Hessian regularity and independence conditions.The bound depends on the maximal gap between full-data GD iterates in the specified interval.Source: Additional notes on setup, preliminaries · p. 52
  • For iterations within the stated period, Lemmas 12 and 13 bound individual-gradient norms and the error between true and approximate gradients.The analysis applies recursively across deletion requests and derives a tighter approximation-error bound as t tends to infinity.Source: Additional notes on setup, preliminaries · pp. 52–55

Main results … D. Supplementary experiments

For online deletions, DeltaGrad is shown to approximate the correct iterates at a stated convergence rate, with intermediate theorems bounding the gap from full-data updates. The supplementary extension describes adaptations for non-strongly convex, non-smooth objectives, while the supplementary-experiments passage gives no experiment-specific findings.

Main results

  • Theorems 16–18 establish bounds between full-data and incrementally updated iterates, extending from selected iterations to all iterations and deletion requests.The supplied theorem passages state these bounds but omit their formulas.Source: Main results · pp. 55–56
  • Theorem 19 states that, at each online deletion request, DeltaGrad’s iterates approximate the correct iterates at a convergence rate.The supplied passage does not include the rate’s formula.Source: Main results · p. 56

The proof of Theorem 16

  • The proof of Theorem 16 compares the update rules across consecutive deletion requests and recursively bounds the iterate difference across iterations.The derivation uses a Cauchy mean-value step and matrix-norm bounds.Source: The proof of Theorem 16 · pp. 56–58

The proof of Theorem 19

  • The proof of Theorem 19 bounds the update discrepancy using the quasi-Hessian error and an iterate-difference bound that requires no additional assumptions.It also bounds the difference of integrated Hessians.Source: The proof of Theorem 19 · p. 60

C.3. Extension of DeltaGrad for non-strongly convex, non-smooth objective functions

  • For non-strongly convex objectives, the extension constructs its update arrays using parameters and gradients only from regions where local convexity holds.The paper presents this as an extension beyond the strong-convexity condition needed by the original L-BFGS algorithm.Source: §C.3 · p. 60
  • For local non-smoothness, the method checks whether the estimated-gradient discrepancy exceeds L times the parameter discrepancy, using L = 1 in experiments.If the check fails, the algorithm uses an exact gradient-descent update, as indicated in the supplied algorithm passages.Source: §C.3 · p. 61

D. Supplementary experiments

  • The supplementary-experiments section introduces experiments omitted from the paper for space, but the supplied passage reports no experiment results.Source: D. Supplementary experiments · p. 61

D.1. Experiments with large deletion rate

On MNIST, DeltaGrad remains faster than BaseL with deletion rates up to 20%, while the resulting models have small parameter differences and nearly identical prediction performance.

D.1. Experiments with large deletion rate

  • The experiment varies MNIST deletion rates from 0 to 20%, using DeltaGrad with T0 = 5 and j0 = 10 while keeping other hyperparameters unchanged from Section 18.The comparison is between DeltaGrad and BaseL.Source: §D.1 · p. 61
  • At 20% deletion, DeltaGrad is 1.67x faster than BaseL (2.27s VS 1.53s).The error bound between their resulting model parameters is on the order of 10^-3, versus 10^-1 between wU∗ and w∗. Prediction performance is 87.460 ± 0.0011% and 87.458 ± 0.0012%, respectively.Source: Figure S1 · p. 62, §D.1 · p. 62

D.2. Influence of hyper-parameters on performance · D.3. Comparison against the state-of-the-art work

DeltaGrad’s hyper-parameter trade-offs depend on batch size, T0, j0, and model complexity. Against PrIU, it is faster and uses less memory in the reported comparisons, while supporting sample additions that PrIU does not.

D.2. Influence of hyper-parameters on performance

  • For logistic regression, larger mini-batches increase DeltaGrad’s speed-up but require longer running time, while the distance between wU and wI becomes smaller as batch size grows.GPU data-copy and kernel-launch overhead can be significant relative to the smaller computational overhead for smaller batches.Source: §D.2 · pp. 62–63, Figure S3 · p. 63

D.3. Comparison against the state-of-the-art work

  • DeltaGrad is always faster than PrIU on MNIST and covtype, with more significant speed-ups on MNIST.Figure S4 reports running time and distance across deletion rates; the paper attributes PrIU’s slower runtime to its O(rp) per-iteration complexity.Source: Figure S4 · p. 63, §D.3 · p. 64

D.2. Influence of hyper-parameters on performance

  • With T0 = 10 or T0 = 20, the distance between wI,S and wU,S does not decrease with larger batches, whereas T0 = 5 gives comparable speed-ups without sacrificing closeness.The paper explains that a bound component can dominate for the larger T0 choices; increasing T0 only slightly decreases running time.Source: §D.2 · p. 63
  • Increasing j0 incurs more running time through longer burn-in iterations without significantly reducing the distance between wI,S and wU,S, so smaller values such as 5 or 10 can speed retraining.Source: §D.2 · pp. 63–64
  • For regularized logistic regression, T0 = 5 and j0 = 5–20 provide favorable running-time and error trade-offs; two-layer DNNs instead need smaller T0 values of 1 or 2 and higher j0.For DNNs, j0 may be as high as half the total iteration count; experiments on adding training samples showed similar trends.Source: §D.2 · p. 64

D.3. Comparison against the state-of-the-art work

  • DeltaGrad supports adding samples, unlike PrIU, which targets linear and regularized logistic regression and handles deletions only; the comparison used MNIST and covtype with matched settings and varying deletion rates.The paper identifies PrIU as the closest work and compares it with DeltaGrad using T0 = 5, j0 = 10, mini-batch size 16384, and the same learning and regularization rates.Source: §D.3 · p. 64
  • PrIU uses much more DRAM than DeltaGrad—up to 10x on MNIST—because it collects full-dataset information with quadratic dependence on model parameters.The authors conclude that DeltaGrad has smaller time and space overhead, suggesting potential for realistic large-scale scenarios.Source: Table 1 · p. 64, §D.3 · p. 64

D.4. Experiments on large ML models · D.5. Applications of DeltaGrad to robust learning

DeltaGrad accelerates retraining in both tested settings: a pre-trained ResNet152 on CIFAR-10 and RCV1 robust learning with outliers. The reported speedups come with small error or computational-accuracy bounds.

D.4. Experiments on large ML models

  • The large-model experiment uses pre-trained ResNet152 parameters with all but the top layer frozen, making last-layer training equivalent to logistic regression.The frozen layers transform each training sample before the training phase.Source: §D.4 · p. 64
  • The CIFAR-10 experiment uses 60,000 32×32 color images and mini-batch SGD with batch size 10,000, learning rate 0.05, and L2 regularization 0.0001.Deletion rates vary from 0 to 1%; DeltaGrad uses T0 = 5 and j0 = 20.Source: §D.4 · p. 64

D.4. Experiments on large ML models; D.5. Applications of DeltaGrad to robust learning

  • On CIFAR-10, DeltaGrad provides up to 3x speedup over BaseL at a 0.005% deletion rate; on RCV1 with up to 10% outliers, it is at least 2.18x faster.On RCV1, this speedup sacrifices no more than 5 × 10−3 computational accuracy.Source: §D.4 · p. 64, §D.5 · p. 65

D.4. Experiments on large ML models

  • The ResNet152 experiment reports an error bound up to 4 × 10−3, compared with a baseline error bound up to 2 × 10−2.The authors expect the approach to apply in many cases because reusing sophisticated pre-trained models is common in practice.Source: §D.4 · p. 65

D.5. Applications of DeltaGrad to robust learning

  • The robust-learning application evaluates outlier effects as the difference between model parameters before and after deleting outliers.The paper cites Yu & Yao (2017) for this representation of outlier effects.Source: §D.5 · p. 65
  • For RCV1, the experiment trains on data containing randomly generated outliers, removes them, and updates the model on the remaining samples with DeltaGrad or BaseL.The outlier fraction, defined as the number of outliers divided by training-set size, varies from 1% to 10%.Source: §D.5 · p. 65

Related papers

Loading 2006.14755v2…