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

Retraining models after small dataset changes is expensive because it can require recomputing the entire optimization path. DeltaGrad uses cached training information to rapidly update SGD-trained models, and the paper reports theoretical and empirical support, including speed-ups up to 6.5x with negligible accuracy loss. Its scope is constrained by overheads in approximate L-BFGS computation and explicit gradient evaluation, and by future-work needs for smaller mini-batches and more complicated models without strong convexity and smoothness guarantees.

  • Problem

    Retraining models from scratch after small data additions or deletions can have complexity comparable to the original training process, despite similar models being expected on similar datasets.

  • Method

    DeltaGrad rapidly retrains empirical-risk-minimization models trained with SGD after small data changes by using information cached during the original training phase.

  • Results

    The paper reports theoretical and empirical support for DeltaGrad, with speed-ups up to 6.5x and negligible accuracy loss on several medium-scale problems.

  • Takeaways & Limitations

    DeltaGrad supports rapid model retraining for data addition, deletion, and continuous updating, with applications including privacy, robustness, debiasing, and statistical inference.

  • Takeaways & Limitations

    The method incurs non-negligible L-BFGS and explicit-gradient overheads, while handling smaller SGD mini-batches and more complicated models without strong convexity and smoothness guarantees remains future work.

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 targets the costly retraining required when training data changes slightly, using cached training information to rapidly update models. The paper presents theoretical and empirical support for its accuracy and speed, including applications to privacy, robustness, debiasing, and statistical inference.

  • Applications: Efficient retraining supports privacy and robustness-related deletion, bias correction through leave-one-out datasets, uncertainty quantification, interpretability, and model debugging.The paper also connects repeated retraining to deletion diagnostics and influential-data analysis.
  • Motivation: Small dataset changes can require retraining models from scratch, with complexity comparable to the original training process.This issue arises because SGD-based retraining recomputes the entire optimization path.
  • Related work: Prior approaches were limited to specialized problems or required randomization that changed standard training algorithms.The paper positions DeltaGrad as addressing both limitations for general SGD-trained models.
  • Proposed approach: DeltaGrad rapidly retrains empirical-risk-minimization models trained with SGD after small additions or deletions, using information cached during training.Its design differentiates the optimization path with respect to the data and does not require additional randomization.
  • Results: 6.5x speed-ups are reported with negligible accuracy loss on several medium-scale problems, including two-layer neural networks.The paper provides both theoretical and empirical support for DeltaGrad’s effectiveness.
  • Contributions: The contributions include theoretical accuracy results for GD and SGD, empirical speed and accuracy results for addition, removal, and continuous updates, and applications across several ML tasks.The listed applications include privacy, robustness, debiasing, and statistical inference.

2. Algorithms

DeltaGrad updates a model after removing or adding a small number of samples by combining cached optimization information with approximate gradient and Hessian computations. Under stated assumptions, its iterates approximate the correctly retrained iterates at a rate better than the baseline r/n, while reducing per-step computation.

  • Setup: After training on n samples, the algorithm targets the minimizer after removing r samples where r ≪ n, and also supports adding r samples.The naive alternative directly runs gradient descent on the remaining samples.
  • Proposed DeltaGrad Algorithm: DeltaGrad uses a leave-r-out gradient formula to update the model instead of recomputing the full optimization path.The update approximates the changed-data gradient using the original training trajectory.
  • Proposed DeltaGrad Algorithm: Cached model parameters and gradients from full-data training provide the historical information used during incremental retraining.The algorithm input includes the cached parameters, corresponding gradients, removed-sample indices, and update hyperparameters.
  • Proposed DeltaGrad Algorithm: L-BFGS approximates Hessian-vector products from historical parameter and gradient updates, with full gradients computed during burn-in and periodically thereafter.Between full-gradient computations, DeltaGrad maintains a history of updates and applies an efficient quasi-Newton update.
  • Convergence rate for strongly convex objectives: Under strong convexity, smoothness, bounded gradients, Lipschitz Hessians, small r/n, and strong independence of updates, DeltaGrad approximates correctly retrained iterates with error o(r/n).The strong-independence condition requires the minimum singular value of normalized weight updates to remain bounded away from zero.
  • Complexity: The method explicitly evaluates gradients for the r removed or added samples while approximating the remaining gradient contribution from cached information.The approximate-gradient step has complexity 6rf(p) + O(m^3) + 6mp + p.
  • Complexity: When approximate-computation overhead is small and the burn-in period is short, speed-ups of a factor T0 are expected.The analysis attributes the approximate step’s cost to L-BFGS overhead and explicit gradients over changed samples.

3. Extension to SGD

DeltaGrad extends rapid retraining to mini-batch stochastic gradient descent by updating parameters using the remaining data and historical observations. Its approximation is accurate under conditions involving mini-batch size and the removed-data fraction.

  • Extension to SGD: DeltaGrad adapts retraining to mini-batch stochastic gradient descent when training data are removed from individual mini-batches.The update accounts for the subset removed from each mini-batch and can handle iterations where all samples in a mini-batch are removed.
  • Extension to SGD: The algorithm uses historical observations of parameter and gradient differences to update the model incrementally.These observations support the approximation of Hessian-vector products during retraining.
  • Convergence rate: With probability at least the theorem’s stated probability, DeltaGrad’s result wI,St approximates the correct iteration values wU,St at the stated rate.The supplied theorem passage introduces the guarantee, while the following passages characterize its accuracy conditions.
  • Convergence rate: When B is large and r/n is small, DeltaGrad accurately approximates the correct iteration values.Here B denotes mini-batch size, while p and T denote the number of model parameters and SGD iterations, respectively.

4. Experiments

Experiments evaluate DeltaGrad for batch and online additions/deletions across logistic-regression datasets and a two-layer MNIST network. DeltaGrad substantially reduces update time while closely matching BaseL in parameter distance and prediction accuracy, though GPU and L-BFGS overhead limit realized speed-ups.

  • Experimental setup: Experiments cover four datasets—MNIST, covtype, HIGGS, and RCV1—with regularized logistic regression, plus a two-layer neural network on MNIST.The neural network uses 300 hidden ReLU neurons and a DeltaGrad variant adapted for settings without strong convexity guarantees.
  • Batch addition/deletion: Batch addition and deletion tests vary the changed-sample rate from 0 to 1% and compare BaseL and DeltaGrad using runtime, parameter distance, and prediction accuracy.The experiments include both distance to the correctly retrained parameters and distance to the full-data model.
  • Batch addition/deletion: Up to 6.5x speed-ups are achieved over BaseL, with gains of 2.6x on MNIST, 2x on covtype, 1.6x on HIGGS, and 6.5x on RCV1.Running time is reported as nearly constant across delete and add rates in the tested small-change regime.
  • Batch addition/deletion: The parameter distance between DeltaGrad and correct retraining remains below 0.0001 for changes of up to 1% of samples and is at least one order of magnitude below the full-model baseline distance.Near-zero change rates produce distances around 10^-6, or 10^-8 for RCV1.
  • Batch addition/deletion: BaseL and DeltaGrad generally have effectively identical prediction accuracy, including cases where their confidence intervals overlap despite differing predictions.The comparison reports results at 0.005% and 1% add/delete rates because of space limitations.
  • Online addition/deletion: With 100 sequential online additions or deletions, DeltaGrad is 2.5x faster on MNIST, 2x on covtype, 1.8x on HIGGS, and 6.5x on RCV1, with essentially no prediction-performance difference.The discussion attributes incomplete realization of theoretical speed-ups partly to approximate L-BFGS matrix multiplications and GPU data-transfer and kernel-launch overheads.

5. Applications

DeltaGrad supports applications that repeatedly retrain models after deleting, adding, or excluding data, including production updates, robust learning, bias correction, predictive inference, and sample-importance analysis.

  • Privacy-related deletion: The paper frames data deletion as relevant to privacy and describes approximate deletion as a route to private deletion using added Laplace noise.The cited definition formalizes deletion operations that map a dataset, model, and removed-sample index to an updated model.
  • Continuous model updating: DeltaGrad updates production models after newly acquired data arrive, or after data changes by first removing original data and then adding replacements.The paper identifies continuous model updating as a direct application.
  • Robust statistical learning: Robust learning can fit a preliminary model, prune identified outliers, and refit the model using DeltaGrad to accelerate retraining.The paper connects this workflow to statistically efficient robust-learning methods for certain problems.
  • Scope boundary: A key scope boundary is future support for smaller SGD mini-batches and more complicated models without strong convexity and smoothness guarantees.The authors identify these extensions as important future work.
  • Bias correction and data valuation: DeltaGrad can recompute estimators for every leave-one-out dataset, accelerating jackknife bias correction and training-sample importance evaluation.The jackknife removes each training point in turn, while leave-one-out comparisons assess changes in model parameters.
  • Uncertainty quantification: Conformal-prediction techniques can use DeltaGrad to accelerate retraining models on subsets of data for uncertainty quantification and predictive inference.Cross-conformal prediction is given as an example involving models trained while excluding each of K subsets.

6. Conclusion

The paper concludes that DeltaGrad enables fast retraining after small dataset changes, with theoretical accuracy guarantees and empirical speed and accuracy results across standard datasets. It also identifies applications in continuous updates and related data-deletion workflows.

  • Deterministic gradient descent: The deterministic-GD analysis identifies Theorem 7 as DeltaGrad’s main result for that setting.The cited passage points to Section A.2.8 for the proof.
  • Stochastic gradient descent: The SGD analysis uses convergence assumptions and Bernstein inequalities to control stochastic-gradient behavior.The supplied passages state the assumptions and introduce scalar and matrix Bernstein inequalities for the analysis.

A.2. Results for deterministic gradient descent

This section develops the deterministic-gradient-descent analysis of DeltaGrad using cached parameter and gradient differences with Quasi-Newton approximations. It presents the update machinery used to obtain the method’s main GD result.

  • Main result: The deterministic-GD analysis identifies Theorem 7 as the main result for DeltaGrad.The theorem is proved in Section A.2.8.
  • Quasi-Newton updates: DeltaGrad forms Quasi-Hessian updates from parameter gaps and gradient gaps accumulated during optimization.The indices track corresponding parameter and gradient differences across iterations.
  • Update procedure: The algorithm applies equation (S11) to prior updates within its incremental retraining procedure.The supplied passage explicitly states this use of equation (S11).
  • L-BFGS implementation: The L-BFGS overview takes sequences of parameter differences, gradient differences, a vector, and a history size as input.It outputs approximate results of H(w_m)v at the final point.
  • Quasi-Hessian construction: The implementation computes a diagonal matrix, a lower-triangular submatrix, and a Cholesky factorization for the Quasi-Hessian construction.These operations are listed as steps in the supplied algorithmic description.

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

The analysis establishes that the Quasi-Hessian matrices used by DeltaGrad are well-conditioned, with bounds controlled by problem parameters and the limited history size.

  • Well-conditioned Quasi-Hessians: The Quasi-Hessian matrices computed by L-BFGS are well-conditioned.This is stated directly as a result of the analysis.
  • Bounds: Lemma 6 gives positive lower and upper bounds for the Quasi-Hessians through constants K1 and K2 depending on problem parameters.The bounds apply for any iteration, vector, and retained history index k.
  • Lower bound: The lower bound is kept away from zero under the experimental conditions described in the proof.The supplied text explicitly states that the lower bound will not approach zero.
  • Proof ingredients: Positive definiteness and norm inequalities support the Quasi-Hessian bounds used in the conditioning argument.The proof invokes positive definiteness and the Cauchy-Schwarz inequality for the Quasi-Hessian.
  • Upper bound: The upper bound follows from z^T B_jk+1 z ≤ (k + 1)L∥z∥2 and the bounded history size m.The analysis sets K2 := (m + 1)L.

A.2.3. PROOF PRELIMINARIES

The proof preliminaries establish bounds for DeltaGrad’s iterate and quasi-Hessian approximations, supporting its convergence-rate guarantees under stated assumptions.

  • Quasi-Hessian construction: The analysis uses cached parameter and gradient differences to approximate Hessian-vector products through a quasi-Newton construction.The secant equation characterizes the Quasi-Newton update, while historical vectors supply the approximation inputs.
  • Proof strategy: The proof bounds quasi-Hessian errors using Lipschitz Hessians, bounded gradients, contraction of GD iterates, and induction over intermediate indices.The contraction result gives d_jk,jq ≤ (1 − µη)^jk d_0,jq−jk under the stated conditions.
  • Iterate bounds: Theorem 4 bounds the distance between full-data iterates and iterates on the leave-r-out dataset.The bound is used as a preliminary estimate in the convergence analysis.
  • Iterate bounds: Theorem 6 bounds the distance between full-data iterates and incrementally updated iterates across all iterations.This preliminary estimate supports later approximation bounds.
  • Main convergence bounds: DeltaGrad’s main result bounds the distance between its iterates wI_t and the correct updated iterates wU_t at a stated convergence rate.The result is presented as Theorem 7 for all iterations.

B.1. Privacy related data deletion

This section formalizes approximate data deletion and explains how DeltaGrad can support privacy-related deletion using randomized outputs and SGD extensions.

  • Deletion definitions: Approximate data deletion compares model outputs after removing a training sample with outputs from an approximate update algorithm.The paper defines deletion through inequalities over datasets and measurable output subsets.
  • Deletion definitions: The paper defines ε-approximate deletion as a stricter version of an earlier approximate-deletion notion.This definition is introduced for an update algorithm R_A and learning algorithm A.
  • Privacy mechanism: Gradient descent can satisfy the approximate-deletion definition when randomness is added to BaseL and DeltaGrad outputs.The paper gives the Laplace mechanism as one way to add the necessary randomness.
  • Privacy mechanism: The randomized DeltaGrad construction preserves ε-approximate deletion when the added noise is calibrated using an upper bound on the distance between updated outputs.The relevant bound concerns ∥wU* − wI*∥.
  • SGD extension: The SGD version replaces full-data gradients and Hessians with mini-batch counterparts in Algorithm 1.The corresponding quantities are wS_t, wU,S_t, wI,S_t, G_B,S, B_S, and H_S.
  • Online updates: The online deletion/addition version updates history information whenever a new deletion or addition request arrives.The section’s analysis covers gradient descent with online deletion, while similar scenarios are left for future work.

C.2.1. CONVERGENCE RATE ANALYSIS FOR ONLINE GRADIENT DESCENT VERSION OF DELTAGRAD

The online gradient-descent analysis extends DeltaGrad across sequential deletion requests by tracking accumulated iterate, gradient, and Hessian-approximation errors.

  • Online deletion setup: At each deletion request, BaseL retrains from scratch while DeltaGrad reuses the previous updated state and cached information.The cumulative number of removed samples remains assumed much smaller than the original dataset size.
  • Online DeltaGrad: The online algorithm uses cached parameters and gradients, periodic exact evaluations, and L-BFGS history to approximate Hessian-vector products.The history consists of parameter and gradient differences from selected prior iterations.
  • Iterate bounds: Theorem 14 bounds the change between BaseL iterates for consecutive single-point deletion requests.The bound depends on strong convexity and the bound on individual gradients.
  • Error analysis: The analysis propagates bounds on iterate differences, gradient approximation errors, and quasi-Hessian accuracy recursively across deletion requests.The derivation uses assumptions including bounded gradients, Hessian Lipschitzness, and quasi-Hessian conditioning.

Main results

The main results establish convergence bounds for online DeltaGrad and describe extensions for non-strongly convex or non-smooth objectives through local checks and restricted history construction.

  • Online deletion: Theorem 18 bounds online DeltaGrad’s iterates relative to full-data iterates across deletion requests and iterations.The bound is stated under a preceding assumption controlling successive updated iterates.
  • Online deletion: Theorem 19 gives the convergence rate of DeltaGrad for online deletion at the rth deletion request.It compares the algorithm’s result wI_t^(r) with the correct iteration values wU_t^(r).
  • Proof components: The online analysis uses error bounds for quasi-Hessian approximation, integrated Hessian differences, and the distance between correct and incrementally updated iterates.These components are combined recursively in the proof.
  • General models: For non-strongly convex objectives, DeltaGrad assumes convexity in local regions and constructs its history arrays using parameters and gradients from those regions.This extends the approach beyond the strongly convex setting under a local-convexity condition.
  • General models: For local non-smoothness, the method checks whether the estimated gradient drift exceeds a threshold based on L(w_t − wI_t).In the reported experiments, L is configured as 1.

D.1. Experiments with large deletion rate

DeltaGrad remains faster than BaseL as deletion rates increase to 20%, while maintaining close agreement in updated model parameters and predictions.

  • The large-deletion experiment varies deletion rates up to 20% on MNIST while keeping the learning rate and mini-batch size fixed.
  • Figure S1 compares running time and distance as the deletion rate changes, using DeltaGrad with T0 = 5 and j0 = 10 against BaseL.
  • At a 20% deletion rate, DeltaGrad is 1.67x faster than BaseL, taking 1.53s versus 2.27s.The resulting parameter error is on the order of 10^-3, compared with 10^-1 between BaseL and the full-data model.
  • At the largest deletion rate, DeltaGrad and BaseL achieve nearly identical prediction performance: 87.460 ± 0.0011% and 87.458 ± 0.0012%, respectively.

D.2. Influence of hyper-parameters on performance

DeltaGrad’s performance depends on mini-batch size, T0, and j0: larger batches improve speed, while smaller tuning values often provide favorable speed–error trade-offs.

  • Mini-batch size: Larger mini-batch sizes increase DeltaGrad’s speed gains, while GPU data-transfer and kernel-launch overheads make small batches less efficient.
  • j0: Figure S3 evaluates running time and distance across mini-batch sizes while fixing T0 = 5 and varying j0 between 5, 10, and 50.
  • Mini-batch size: With T0 = 5, increasing mini-batch size reduces the distance between the DeltaGrad and BaseL parameters, consistent with the stated theoretical bound.
  • T0: Increasing T0 only slightly decreases running time for a fixed mini-batch size and can prevent the parameter distance from decreasing with larger batches.For T0 = 10 or T0 = 20, the bound’s T0-dependent component can dominate.
  • j0: Increasing j0 adds burn-in iterations and running time without significantly reducing the distance between DeltaGrad and BaseL.The experiments therefore indicate that smaller values such as j0 = 5 or j0 = 10 can provide more speed-up.
  • Hyper-parameter recommendations: For regularized logistic regression, T0 = 5 and j0 = 5–20 provide favorable trade-offs between running time and error.For more complex 2-layer DNNs, higher j0 and smaller T0 are necessary.

D.4. Experiments on large ML models

Experiments extend DeltaGrad to large-model settings and robust-learning outlier evaluation, showing speed advantages with small computational or prediction differences.

  • Large ML models: On CIFAR-10 with a pre-trained ResNet152 feature transformation and a trained final layer, DeltaGrad is evaluated against BaseL for deletion rates up to 1%.
  • Large ML models: For the ResNet152 experiment, DeltaGrad has error up to 4 × 10^-3 versus the baseline error up to 2 × 10^-2.
  • Robust learning: On RCV1 with up to 10% randomly generated outliers, DeltaGrad is at least 2.18x faster than BaseL while sacrificing no more than 5 × 10^-3 computational accuracy.
  • Robust learning: The outlier experiment measures the effect of outliers through the difference between model parameters before and after deleting them.
Loading 2006.14755v2…