PaperlayerView exact revision on arXiv

Source-linked AI summary

GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training

Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, Abir De, Rishabh Iyer

arXiv:2103.00123v2cs.LG

TL;DR

Large-scale deep learning incurs substantial computational and environmental costs, motivating subset selection that preserves accuracy. GRAD-MATCH matches weighted subset gradients to training or validation gradients using OMP, and experiments report the best speedup–accuracy trade-off among evaluated approaches. The method is supported by convergence and approximation analyses, though its guarantees rely on bounded-parameter and gradient assumptions.

  • Problem

    Training on massive datasets is computationally, financially, energetically, and environmentally costly, raising whether much smaller subsets can preserve test accuracy.

  • Method

    GRAD-MATCH selects weighted data points or mini-batches by minimizing mismatch between subset gradients and training or validation-set gradients, using OMP.

  • Results

    GRAD-MATCH achieves the best speedup–accuracy trade-off in the reported experiments and outperforms several recent data-selection methods.

  • Takeaways & Limitations

    The experiments report substantial speedups and energy savings while retaining accuracy close to full training on several datasets.

  • Takeaways & Limitations

    The convergence analysis assumes bounded model parameters and bounded gradients, and its weak-submodularity guarantee uses a gradient-norm bound.

Abstract

from arXiv · show

The great success of modern machine learning models on large datasets is contingent on extensive computational resources with high financial and environmental costs. One way to address this is by extracting subsets that generalize on par with the full data. In this work, we propose a general framework, GRAD-MATCH, which finds subsets that closely match the gradient of the training or validation set. We find such subsets effectively using an orthogonal matching pursuit algorithm. We show rigorous theoretical and convergence guarantees of the proposed algorithm and, through our extensive experiments on real-world datasets, show the effectiveness of our proposed framework. We show that GRAD-MATCH significantly and consistently outperforms several recent data-selection algorithms and achieves the best accuracy-efficiency trade-off. GRAD-MATCH is available as a part of the CORDS toolkit: \url{https://github.com/decile-team/cords}.

1. Introduction

The paper targets the computational, financial, energy, and carbon costs of training on massive datasets by asking whether much smaller subsets can preserve test accuracy. GRAD-MATCH matches training or validation gradients and is reported to improve the accuracy–efficiency trade-off.

  • Motivation: Subset selection seeks to train models on much smaller datasets with negligible loss in test accuracy.This targets the computational and resource costs associated with massive training datasets.
  • Motivation: Smaller training subsets can reduce hardware requirements, end-to-end turnaround time, energy consumption, and CO2 emissions.The paper links these benefits to avoiding full-dataset training across repeated experiments.
  • Approach: GRAD-MATCH minimizes an error measuring how closely a weighted subset matches full-training or validation-set gradients.Its design is motivated by convergence analysis for adaptive data-selection strategies.
  • Approach: An orthogonal matching pursuit greedy algorithm solves the gradient-matching objective, with implementation techniques intended to speed selection.The objective is connected to weakly submodular maximization.
  • Empirical findings: On ImageNet, CIFAR-10, and CIFAR-100, a 30% subset gives around 3× efficiency improvement with an accuracy drop close to 1%.The paper also reports larger speedups for smaller subsets and matching full-data accuracy after extended training with 30% of the data.
  • Empirical findings: GRAD-MATCH is presented as achieving a better accuracy–training-time trade-off than CRAIG, GLISTER, random subsets, and full training with early stopping.The comparison covers several state-of-the-art data-selection approaches and a full-training baseline.

2. GRAD-MATCH through the lens of adaptive data subset selection

The paper analyzes adaptive subset selection through the gradient error introduced when weighted subsets replace full training or validation data. It uses this analysis to motivate GRAD-MATCH and derive convergence guarantees.

  • Adaptive subset selection: Adaptive data selection updates model parameters using weighted gradients from selected subsets that may change as training proceeds.Selection need not occur every epoch; subsets and weights can be reused between selection intervals.
  • Adaptive subset selection: The framework supports matching either the full training loss gradient or the validation loss gradient.The validation target is relevant when the training data is biased, such as under class imbalance.
  • Convergence analysis: The convergence analysis applies to adaptive data-selection algorithms for Lipschitz continuous, Lipschitz smooth, and strongly convex losses.The theorem is stated for bounded model parameters and gradient-related assumptions.
  • Convergence analysis: The convergence bounds include an error term measuring the mismatch between the selected weighted subset and the target loss gradient.The analysis therefore suggests selecting subsets with small gradient error at each iteration.
  • GRAD-MATCH motivation: GRAD-MATCH directly minimizes this gradient error, linking the adaptive-selection convergence analysis to its subset-selection objective.The paper states that minimizing this error is likely to reduce loss at each iteration.

3. The GRAD-MATCH Algorithm

GRAD-MATCH selects weighted data points or mini-batches whose gradients approximate training or validation gradients. It regularizes the matching objective and uses weak-submodularity-based greedy optimization with theoretical guarantees.

  • Algorithm: GRAD-MATCH selects subsets every R epochs and applies weighted mini-batch SGD on the previously selected subset between selections.The validation flag determines whether matching targets validation or training gradients.
  • Objective: The regularized objective adds a squared l2 penalty on weights to discourage assigning large weights to individual data instances or mini-batches.The weights and subset are optimized jointly during data selection.
  • Mini-batch variant: GRAD-MATCHPB matches weighted mini-batch gradients to full training or validation gradients instead of selecting individual data points.Selecting mini-batches reduces OMP selection rounds by a factor of B and yields a reported B× speedup.
  • Optimization: The subset objective can be converted into maximizing Fλ(X), which the paper shows is weakly submodular.This structure supports greedy approximation guarantees under a cardinality constraint.
  • Optimization: OMP and greedy selection can return bounded-cardinality subsets or approximately minimum-sized subsets satisfying a target error tolerance.The stopping criterion is Eλ(X) ≤ ϵ.
  • Guarantees: If OMP achieves Eλ(X^t) ≤ ϵ, GRAD-MATCH inherits convergence bounds with an additional Dϵ term, including O(1/T) behavior for smooth or strongly convex losses.The paper gives explicit bounds for Lipschitz-continuous and smooth cases.
  • Connections: GRAD-MATCH is reported to outperform CRAIG and GLISTER across multiple deep-learning datasets.The paper attributes weaker CRAIG bounds to optimizing an upper bound of the gradient error, which may require larger subsets for the same error.

4. Speeding up GRAD-MATCH

The paper introduces practical approximations and scheduling choices to make gradient matching scalable. These include gradient compression, class-wise selection, warm starts, and less frequent selection.

  • Gradient approximations: Last-layer gradients reduce the dimensionality of gradient matching for modern neural networks.The paper uses this approximation because high-dimensional gradients slow OMP.
  • Gradient approximations: Per-class and per-gradient approximations reduce the memory needed to store gradients for large datasets.GRAD-MATCHPB does not require these approximations because its ground set consists of mini-batches.
  • Warm starts: Warm-start variants run full training for initial epochs before switching to subset training.The number of full-training epochs is chosen relative to the subset-training fraction κ.
  • Warm starts: Full training during the first few epochs is reported to produce better warm-start models and much better convergence.A large warm-start duration approaches full training with early stopping because less data selection remains.
  • Selection scheduling: Data selection every R epochs and per-batch variants are used as additional speedups.The experiments set R = 20 while also studying the effect of this choice.

5. Experiments

Experiments evaluate GRAD-MATCH across datasets, architectures, subset sizes, imbalance levels, and efficiency measures. The variants generally provide strong accuracy-efficiency trade-offs, including faster convergence and energy savings versus baselines and full training.

  • Speedups and energy gains compared to full training: 7x, 4.2x and 3x speedup and energy gains were achieved on CIFAR-10 with 10%, 20% and 30% subsets, with accuracy drops of 2.8%, 1.5% and 0.9%, respectively.These results are reported for GRAD-MATCHPB-WARM relative to full training.
  • Comparison to other baselines: GRAD-MATCH variants outperformed random selection, FULL-EARLYSTOP, CRAIG variants, and GLISTER variants across the reported comparisons.GLISTER and CRAIG could not run on ImageNet because of memory requirements and running time; only selected variants scaled to ImageNet.
  • Convergence and running time: GRAD-MATCHPB-WARM achieved similar performance to full training while being 2.5x faster on a 30% CIFAR-100 subset after 30 to 50 additional epochs.The extended convergence experiment trades some efficiency for comparable accuracy.
  • Convergence and running time: GRAD-MATCHPB-WARM outperformed smaller MobileNet-V1 and MobileNet-V2 models on CIFAR-10 in both test accuracy and speedup.The comparison used ResNet-18 for GRAD-MATCHPB-WARM and MobileNet models as smaller-model proxies.
  • Data selection with class imbalance: GRAD-MATCH and its variants outperformed baselines in class-imbalance settings except the 30% MNIST case, while GRAD-MATCH-WARM exceeded full training in some imbalanced settings.For imbalance experiments, gradient matching used a clean validation loss because the training data were biased.

6. Conclusions

The paper introduces GRAD-MATCH as a gradient-matching framework and establishes theoretical guarantees for adaptive subset selection under several loss-function conditions. Its bounds relate optimization performance to the subset’s gradient-matching error.

  • 6. Conclusions: GRAD-MATCH minimizes an error measuring how closely a weighted subset matches full-training or validation-set gradients.The framework is analyzed through convergence rates, approximation bounds, and connections to weak submodularity.
  • 6. Conclusions: The analysis covers adaptive data selection algorithms defined by weights and subsets and run with full gradient descent under stated convexity, smoothness, and bounded-gradient assumptions.Different cases use Lipschitz continuity, Lipschitz smoothness, convexity, or strong convexity.
  • 6. Conclusions: Under Lipschitz-smooth training loss with bounded instance losses and α = 1/L_T, the minimum optimization gap is bounded by a term involving D^2L_T + 2β_T.This is one of the stated convergence cases for adaptive data selection.
  • 6. Conclusions: Under Lipschitz continuity and strong convexity, setting α_t = 2/[µ(1+t)] yields a bound involving σ_T^2 and the gradient-matching error.The bound also contains the iteration-dependent factor 2D_t/[T(T + 1)].

B.2. Convergence Analysis with Stochastic Gradient Descent

The stochastic-gradient analysis gives convergence bounds for adaptive subset selection when the objective is training or validation loss. The bounds explicitly depend on gradient-matching error and stated smoothness, convexity, and bounded-gradient assumptions.

  • B.2. Convergence Analysis with Stochastic Gradient Descent: Adaptive data selection with SGD has convergence bounds for either training or validation loss when parameter norms and gradients are bounded.The theorem considers subsets and weights selected over iterations t = 1, ..., T with learning rate α.
  • B.2. Convergence Analysis with Stochastic Gradient Descent: For Lipschitz-continuous training loss and strongly convex objective, α_t = 2/[µ(1+t)] yields an expected minimum-loss convergence bound.The stated result uses the expected minimum over iterations.
  • B.2. Convergence Analysis with Stochastic Gradient Descent: The stochastic convergence analysis defines Err(w_t, X_t, L, L_T, θ_t) as the difference between weighted subset and target loss gradients.This error connects the selected subset to the optimization bound.
  • B.2. Convergence Analysis with Stochastic Gradient Descent: The proof treats subset sampling as a random choice from the selected subset and uses normalized weights to control the weighted gradient.The analysis takes expectations over stochastic-gradient updates and sample choices.

B.3. Conditions for adaptive data selection algorithms to reduce the objective value at every iteration

The paper identifies conditions under which adaptive data selection reduces the objective at every iteration. These conditions require aligned subset and target gradients together with an appropriate learning-rate schedule.

  • Conditions for adaptive data selection algorithms to reduce the objective value at every iteration: The adaptive subset strategy reduces the objective at every iteration when the subset gradient has nonnegative inner product with the target gradient and the learning rate is sufficiently small.The theorem states L(θ_{t+1}) ≤ L(θ_t) under this alignment and learning-rate condition.
  • Conditions for adaptive data selection algorithms to reduce the objective value at every iteration: Minimizing the gradient-matching error is expected to help satisfy the gradient-alignment condition when the learning rate is selected appropriately.The paper connects the sufficient condition to the objective optimized by data-selection methods.
  • Conditions for adaptive data selection algorithms to reduce the objective value at every iteration: The objective L may denote either training loss or validation loss, and the analysis assumes a validation set when validation loss is used.The subset selected by GRAD-MATCH is denoted S and its training loss by L_T(θ, S).
  • Conditions for adaptive data selection algorithms to reduce the objective value at every iteration: The gradient-matching objective has a weak-submodularity guarantee under a bounded-gradient condition, with γ ≥ λ/(λ + k∇^2_max).The result follows from eigenvalue bounds on the regularized objective.

B.5. Proof of Theorem 3

The theorem establishes convergence guarantees for greedy and OMP subset selection when Fλ is γ-weakly submodular. The proof bounds the selected subset size needed to achieve error at most ϵ.

  • Theorem assumptions: Both greedy selection and OMP achieve subsets satisfying the stopping criterion Eλ(X) ≤ ϵ under the theorem’s weak-submodularity and gradient-bound assumptions.The theorem assumes Fλ(X) is γ-weakly submodular and max_i ||∇θL_i^T(θ^t)||_2 < ∇max.
  • Greedy case: The greedy proof stops when Fλ(X) ≥ Lmax − ϵ and compares the resulting subset size with the optimal subset X∗.The proof treats the procedure as a submodular set-cover problem and uses the upper bound Fλ(X) ≤ Lmax.
  • Greedy case: The resulting bound is Fλ(X∗) − Fλ(X) ≤ (1 − γ/|X∗|)|X|Lmax.This follows from the recursive greedy-gain argument and the bounds Fλ(∅) ≥ 0 and Fλ(X∗) ≤ Lmax.
  • Greedy case: Choosing |X| ≤ |X∗|/γ log(Lmax/ϵ) ensures the greedy approximation error is at most ϵ.The proof selects a subset size satisfying the displayed error bound, which implies Fλ(X∗) − Fλ(X) ≤ ϵ.
  • OMP case: The OMP proof obtains an analogous recursion, replacing the relevant factor with the ratio of strong concavity to smoothness parameters.This ratio is the same bound used to establish weak submodularity for Fλ.

B.6. Convergence result for GRAD-MATCH using the OMP algorithm

This section gives OMP-based convergence results under a per-iteration gradient-approximation condition and relates the optimization to surrogate subset objectives. It also describes the experimental settings used to evaluate the method.

  • Convergence result: OMP-based data selection has a convergence result when every subset X^t satisfies Eλ(X^t) ≤ ϵ.The result is stated for subsets selected across iterations t = 1, …, T.
  • Convergence result: Under Lipschitz continuity and strong convexity, the stated learning rate α_t = 2/[µ(1+t)] yields min_t L(θ^t) − L(θ∗) ≤ 2σ_T^2/[µ(1+T)] + Dϵ.The bound is given for the strongly convex case with Lipschitz-continuous loss parameter σ_T.
  • Convergence result: The proof uses Eλ(X^t) = E(X^t,w_t) + λ||w_t||^2 ≤ ϵ to infer Err(w_t,X^t,L,L_T,θ^t) ≤ ϵ, then invokes the general convergence theorem.The nonnegative regularization term makes the gradient-matching error no larger than Eλ.
  • Surrogate objectives: The surrogate objective ˆE(X) upper-bounds the full-gradient estimation error E(X).This supports optimizing the surrogate as a way to control gradient approximation error.
  • Surrogate objectives: The corresponding facility-location maximization problem is cardinality-constrained submodular maximization with a greedy 1 − 1/e approximation.The facility-location function is identified as the one used in CRAIG, and ˆF(X) is a lower bound of F(X).
  • Experimental settings: Experiments use MNIST, CIFAR10, SVHN, CIFAR100, and ImageNet, with LeNet for MNIST and ResNet18 for the other datasets.Training uses SGD with initial learning rate 0.01, momentum 0.9, and weight decay 5e-4; ImageNet uses 350 epochs.

C.4. Data Selection Results:

Across the reported datasets, GRAD-MATCH variants generally achieve higher test accuracy with lower training time than the compared selection strategies. The per-batch warm-start variant is also reported as the most energy-efficient.

  • Accuracy and training time: GRAD-MATCH and its variants consistently outperform the baselines with higher test accuracy and lower training times.The comparisons include random subsets, FULL-EARLYSTOP, CRAIG, CRAIGPB, and GLISTER.
  • Accuracy and training time: GRAD-MATCHPB-WARM achieves the best reported accuracy–training-time trade-off among the compared strategies.The paper reports this pattern across CIFAR10, CIFAR100, and SVHN, while also discussing ImageNet scalability.
  • Scalability: GLISTER and CRAIG cannot run on ImageNet because of large memory requirements and running time.GRAD-MATCH, GRAD-MATCHPB, and CRAIGPB are reported as the variants that scale to ImageNet.
  • Energy consumption: GRAD-MATCHPB-WARM is the most energy-efficient strategy among those evaluated on CIFAR10 and CIFAR100.The energy results are reported for different subset sizes and measured in KWH.
  • Energy consumption: PerBatch variants CRAIGPB and GRADMATCHPB have better energy efficiency than GRAD-MATCH and CRAIG.This comparison is stated in the energy-consumption results.

C.5. Standard deviation and statistical significance results:

GRAD-MATCHPB-WARM shows the lowest variability among the evaluated subset-selection strategies, while smaller subsets generally produce larger standard deviations. Pairwise testing reports significant outperformance over other baselines at p < 0.01.

  • GRAD-MATCHPB-WARM has the least standard deviation among the compared subset-selection strategies.The comparison covers CIFAR10, CIFAR100, and MNIST over five training runs.
  • Smaller subsets produce larger standard deviations across the evaluated selection strategies.
  • GRAD-MATCHPB-WARM significantly outperforms other baselines at p < 0.01 in pairwise one-tailed Wilcoxon signed-rank tests.The tests compare every pair of strategies across all datasets.

C.6. Other Results:

Additional analyses link GRAD-MATCH’s performance to gradient approximation, redundancy, and variant design. Across comparisons, PerBatch and other GRAD-MATCH variants provide strong accuracy-efficiency results, while some alternatives show weaknesses on very small subsets.

  • Gradient Errors: GRAD-MATCHPB achieves the smallest average gradient error on MNIST, followed closely by CRAIGPB.PerBatch variants have lower gradient error than their non-PerBatch counterparts.
  • Gradient Errors: GLISTER has substantially larger gradient error at a 1% subset, partially explaining its poor performance at very small subset percentages.
  • Redundant Points: Redundant-point results indicate that similar performance to full training can be achieved with a much smaller informative MNIST subset.Redundant points are data points never used for training.
  • Comparison between variants of GRAD-MATCH: The PerClass variant is not scalable, while PerClassPerGradient achieves comparable accuracy much faster and PerBatch performs best in accuracy and training efficiency.PerClass can take longer than full-data training for 30% CIFAR10 and CIFAR100 subsets.
  • Comparison with additional subset selection methods: GRAD-MATCH outperforms Facility Location, Entropy, and Forgetting Events on CIFAR10 and CIFAR100 while using a lower-complexity, faster ResNet-18 model.The compared results use numbers reported from experiments with ResNet-164, which is roughly 4× slower than ResNet-18.
Loading 2103.00123v2…