PaperlayerView exact revision on arXiv

Source-linked AI summary

GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning

Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, Rishabh Iyer

arXiv:2012.10630v4cs.LGcs.AI

TL;DR

GLISTER addresses the gap between efficient and robust learning when training data are expensive, noisy, or imbalanced. It formulates validation-guided subset selection as a bi-level problem and develops online and active-learning variants. Across tasks, the framework improves efficiency, accuracy, and robustness, with computational trade-offs and limitations in subset-selection cost.

  • Problem

    Existing work largely focuses on efficiency or robustness separately, despite the need to reduce training costs while handling noisy and imbalanced data.

  • Method

    GLISTER selects training subsets by maximizing held-out validation log-likelihood, with GLISTER-ONLINE performing iterative selection alongside parameter updates and GLISTER-ACTIVE extending the approach to batch active learning.

  • Results

    Across a wide range of tasks, GLISTER variants improve state-of-the-art efficiency, accuracy, and robustness, including more than 10% gains over other baselines in a noisy DNA setting.

  • Takeaways & Limitations

    Validation-guided subset selection provides a common framework for efficient training, robust learning under noise and imbalance, and batch-active learning.

  • Takeaways & Limitations

    For large datasets, subset selection can exceed training complexity, while shallow or two-layer models can incur orders-of-magnitude higher selection time than full training.

Abstract

from arXiv · show

Large scale machine learning and deep models are extremely data-hungry. Unfortunately, obtaining large amounts of labeled data is expensive, and training state-of-the-art models (with hyperparameter tuning) requires significant computing resources and time. Secondly, real-world data is noisy and imbalanced. As a result, several recent papers try to make the training process more efficient and robust. However, most existing work either focuses on robustness or efficiency, but not both. In this work, we introduce Glister, a GeneraLIzation based data Subset selecTion for Efficient and Robust learning framework. We formulate Glister as a mixed discrete-continuous bi-level optimization problem to select a subset of the training data, which maximizes the log-likelihood on a held-out validation set. Next, we propose an iterative online algorithm Glister-Online, which performs data selection iteratively along with the parameter updates and can be applied to any loss-based learning algorithm. We then show that for a rich class of loss functions including cross-entropy, hinge-loss, squared-loss, and logistic-loss, the inner discrete data selection is an instance of (weakly) submodular optimization, and we analyze conditions for which Glister-Online reduces the validation loss and converges. Finally, we propose Glister-Active, an extension to batch active learning, and we empirically demonstrate the performance of Glister on a wide range of tasks including, (a) data selection to reduce training time, (b) robust learning under label noise and imbalance settings, and (c) batch-active learning with several deep and shallow models. We show that our framework improves upon state of the art both in efficiency and accuracy (in cases (a) and (c)) and is more efficient compared to other state-of-the-art robust learning algorithms in case (b).

Introduction

GLISTER addresses the under-explored combination of efficient and robust learning by selecting training subsets according to held-out validation performance. It extends subset-selection analysis beyond simple classifiers and connects the formulation to submodular optimization under stated assumptions.

  • Motivation: Training modern models incurs substantial compute and engineering costs from extensive tuning and architecture search.These costs motivate more efficient data use.
  • Motivation: GLISTER targets effective subsets that reduce training time, lower labeling cost, and mitigate noisy labels and class imbalance without sacrificing accuracy.These are the paper’s three stated goals.
  • Research gap: Prior work generally addressed efficiency or robustness separately, leaving their combination relatively under-explored.Efficiency methods often optimize training-set proxies, while robustness methods can impose substantial additional cost.
  • Problem formulation: GLISTER selects a subset S of training data U by minimizing validation loss on a held-out set V, or equivalently maximizing validation log-likelihood.The formulation uses separate training and validation losses for subset selection and parameter learning.
  • Relation to prior work: The framework extends prior training-set-based subset selection by using validation performance and considering models beyond nearest neighbor and naive Bayes.The cited prior formulation is recovered when validation loss is replaced with training loss.
  • Submodular analysis: For naive Bayes and nearest-neighbor classifiers, the selection problem becomes submodular maximization under a fixed-cardinality constraint.The equivalence relies on an assumption that class-label distributions in the selected subset and full training set match.

GLISTER-ONLINE Framework

GLISTER-ONLINE jointly selects training subsets and updates model parameters, using periodic approximations to optimize validation performance efficiently. Its selection problem is generally NP-hard but admits submodular or weakly submodular formulations for several important losses, with conditions guaranteeing validation-loss reduction and convergence.

  • Framework: GLISTER-ONLINE performs data selection jointly with parameter learning, selecting subsets periodically while updating model parameters.The algorithm selects every L epochs and otherwise reuses the previous subset while training on it.
  • Framework: The outer objective selects a training subset whose trained model achieves high validation log-likelihood, while the inner objective maximizes training log-likelihood on that subset.The resulting formulation is a nested bi-level optimization problem requiring approximations for general loss functions.
  • Optimization: Equation (4) is NP-hard in general, but becomes cardinality-constrained submodular or weakly submodular maximization for several loss functions.The guarantees cover negative logistic, squared, hinge, perceptron, and cross-entropy losses.
  • Optimization: Lazy or stochastic greedy methods provide 1−1/e approximation guarantees for monotone cases, while randomized greedy provides a 1/e guarantee for negative squared loss.These guarantees follow from the corresponding submodular formulations.
  • Efficiency: Stochastic-greedy selection has complexity O(nmFT/L log 1/ϵ + kTB), which can exceed full-training complexity for large datasets.The paper introduces last-layer and Taylor approximations to reduce selection cost, including O([km + n log 1/ϵ]fT/L + kTB) for stochastic greedy with Taylor approximation.
  • Theory: Under aligned training and validation gradients, smoothness, bounded gradients, and a suitable learning rate, GLISTER-ONLINE monotonically decreases validation loss and can converge in O(1/ϵ2) epochs.The convergence statement assumes the alignment condition holds for all encountered subsets.

GLISTER-ACTIVE Framework

GLISTER-ACTIVE extends GLISTER to adaptive mini-batch active learning by selecting unlabeled examples over multiple labeling rounds. It uses hypothesized labels and updates selection based on previously labeled points and model changes.

  • Active learning: GLISTER-ACTIVE selects batches of B unlabeled instances for labeling across T adaptive rounds.Selections in later rounds are affected by previously selected points as the model is updated.
  • Active learning: The method uses hypothesized labels from the current model during greedy Taylor optimization because true labels are unavailable.This design is described as similar to existing approaches such as BADGE and FASS.
  • Active learning: GLISTER-ACTIVE differs from GLISTER-ONLINE by selecting only from unlabeled instances and adding selected batches to the labeled set.Its goal is to choose informative points that help the model form an appropriate decision boundary.

Experimental Results

Experiments evaluate GLISTER-ONLINE and GLISTER-ACTIVE across efficiency, imbalance, noise, and active-learning settings using shallow and deep models. GLISTER generally outperforms competing data-selection and robustness baselines.

  • Experimental setup: Experiments test GLISTER-ONLINE and GLISTER-ACTIVE on real-world datasets with shallow and deep models.Datasets include DNA, SVMGuide, Digits, Letter, USPS, MNIST, and CIFAR-10.
  • Data selection for efficient learning: GLISTER and its variants significantly outperform CRAIG and Random across evaluated subset sizes in MNIST and CIFAR-10 efficiency experiments.Subset sizes are 10%, 30%, and 50%; CRAIG was selected every 20 epochs for comparability, with an additional every-epoch MNIST baseline.
  • Class imbalance: R-GLISTER improves performance by around 7% over other baselines on CIFAR-10 under class imbalance at 30% and 50% subset sizes.The comparison includes baselines with prior knowledge of imbalance and validation-set information.
  • Noisy labels: GLISTER and its variants outperform other baselines by more than 10% in the noisy DNA setting, even surpassing full training.The paper attributes this to data selection filtering noise in the smaller dataset.

Conclusion

GLISTER combines validation-likelihood-based subset selection with online and active-learning variants. Across diverse tasks, the framework reports improvements and associated trade-offs in efficiency, accuracy, and robustness.

  • Framework: GLISTER formulates efficient training as mixed discrete-continuous bi-level optimization guided by held-out validation likelihood for robustness.GLISTER-ONLINE performs iterative data selection, while GLISTER-ACTIVE extends the framework to batch active learning.
  • Conclusion: Across a wide range of tasks, GLISTER variants improve upon the state of the art in efficiency, accuracy, and robustness, with associated trade-offs.

Proof of NP-Hardness (Lemma 2)

The paper proves that GLISTER’s subset-selection step can be NP-hard by constructing an instance equivalent to the Set-Cover Problem under specific model, data, and loss assumptions.

  • Reduction setup: The subset-selection optimization maximizes validation log-likelihood after a parameter update using a training subset of bounded cardinality.The objective is Gθ(S) = LLV(θ + α∇θLLT(θ,S), V).
  • Reduction construction: The validation data are constructed from weighted set-cover vectors, with all validation labels fixed to 1 and a shifted negative hinge-loss form.The vector components are obtained from the set-cover instance.
  • Reduction assumptions: The hardness construction assumes a linear model, zero initial parameters, one-hot training gradients, and equal numbers of training points and features.These assumptions encode the combinatorial structure needed for the reduction.
  • Hardness conclusion: The resulting optimization instance is a Set-Cover Problem, which is NP-hard.Therefore, there exist log-likelihood functions and datasets for which GLISTER’s data-selection step is NP-hard.

Proof of Submodularity of the Data Selection in GLISTER-ONLINE (Theorem 1)

Theorem 1 characterizes GLISTER-ONLINE’s subset-selection objective through submodularity properties that depend on the validation loss. Logistic, squared, hinge, and perceptron losses yield submodular cases, while cross-entropy yields weak or approximate submodularity under bounded data norms.

  • Theorem 1 scope: Negative logistic, squared, hinge, and perceptron validation losses produce cardinality-constrained submodular maximization instances.The theorem states these cases are non-monotone submodular in general, while specific lemmas establish monotone forms for logistic and hinge/perceptron losses.
  • Negative logistic loss: Under negative logistic loss, the subset objective is a cardinality-constrained monotone submodular maximization problem.A proxy objective preserves the optimizer under the cardinality constraint, allowing greedy optimization.
  • Negative squared loss: Under negative squared loss, the objective is submodular but non-monotone, so an equality cardinality constraint is required.The proxy transformation shifts pairwise terms to ensure nonnegative contributions while preserving optimization under fixed subset size.
  • Negative hinge and perceptron losses: Under negative hinge or perceptron loss, the objective is cardinality-constrained monotone submodular maximization.The proof uses a concave-over-modular proxy whose optimizer matches the original objective under the cardinality constraint.
  • Negative cross-entropy loss: Negative cross-entropy loss is not submodular, but the objective is β-approximate submodular with β = 1/(2R^2 + 1) when training and validation norms are bounded by R.Greedy selection achieves a 1 − e^-β approximation factor under the stated cardinality constraint.
  • Negative cross-entropy loss: The cross-entropy proof combines a positive modular term with a β-submodular term to establish approximate submodularity.The argument uses bounded training and validation data norms.

Convergence of GLISTER-ONLINE and Reduction in Objective Value

GLISTER-ONLINE is analyzed under gradient-alignment and smoothness conditions that guarantee nonincreasing validation loss and convergence. When validation and training data have similar distributions, the alignment condition is approximately satisfied and convergence occurs in O(1/T) steps.

  • Validation loss decreases monotonically when training and validation gradients have nonnegative inner product, with bounded gradients and a suitable learning rate.The theorem assumes Lipschitz-smooth validation loss and gradient bounds σT and σV.
  • The selected subset must produce a training-loss gradient aligned with the validation-loss gradient at every training epoch.GLISTER-ONLINE selects subsets by maximizing the gradient dot product in its Taylor-series approximation.
  • The convergence analysis uses Lipschitz-smooth losses, bounded gradients, a bounded parameter distance, and a learning rate tied to R and σT.The proof introduces θl, θ∗, δmin, and the angle Θl between validation and subset-training gradients.
  • GLISTER-ONLINE converges in O(1/T) steps when validation and training data come from similar distributions and cos(Θl) is approximately 1.Similar distributions imply near-aligned training and validation gradients in the stated convergence discussion.

Derivation of Closed Form Expressions for Special Cases

The appendix derives validation- and training-based subset objectives for Naive Bayes, nearest neighbors, and linear regression. Under balance, cardinality, or cluster-preservation assumptions, these objectives reduce to submodular optimization problems with structured constraints.

  • Discrete Naive Bayes: Naive Bayes training log-likelihood becomes a difference of submodular functions, with balancing and fixed-size constraints making selected terms constant.The resulting feature-based form uses a concave function, specifically log, applied to modular feature counts.
  • Discrete Naive Bayes: Discrete Naive Bayes validation log-likelihood reduces to optimizing a feature-based function under class-balanced subset constraints.The reduction assumes |S ∩ Vy| = k|Vy|/|V| and uses a partition matroid constraint.
  • Discrete Naive Bayes: The Naive Bayes and nearest-neighbor reductions require subset distributions to match validation or training class proportions.These assumptions are intended to support generalization from the selected subset to the validation set.
  • Nearest Neighbors: Nearest-neighbor validation log-likelihood reduces to facility location under class-balanced subset constraints.The objective sums each validation point’s maximum similarity to a selected training point with the same label.
  • Nearest Neighbors: Linear regression subset selection is approximated by clustering training data, preserving cluster proportions, and optimizing a transformed proxy objective.The transformation shifts similarities by their minimum so the graph-cut-like component is nonnegative.
  • Nearest Neighbors: The transformed linear-regression proxy is a non-monotone submodular function under cardinality and cluster constraints.The proxy is equivalent to the original objective under cardinality equality constraints.

Additional Details on GreedyDSS

GreedyDSS builds the selected subset incrementally through per-example proxy gains and repeated constrained maximization. After each round, selected points are removed and model parameters are updated before the next round.

  • GreedyDSS initializes an empty subset and repeatedly evaluates candidate examples using a first-order parameter update and a proxy gain.The proxy combines Gθe(e|Sk) with a regularization term λR(e|Sk).
  • Each round selects a subset of size k/r by maximizing the proxy over the remaining training data.The selected batch is added to S and removed from U.
  • After selection, the algorithm updates model parameters, increments the round counter, and returns the accumulated subset.The procedure repeats until t reaches r.

Additional Details on GLISTER-ACTIVE

GLISTER-ACTIVE performs mini-batch adaptive active learning by selecting batches of unlabeled examples for labeling across multiple rounds. Selection favors points expected to reduce validation loss, while training continues from the previously updated model.

  • GLISTER-ACTIVE selects B unlabeled samples for labeling in each of T rounds according to their expected validation-loss reduction.The method uses model-generated hypothesized labels and GreedyDSS with budget k set to B.
  • The model is not retrained from scratch after each round; training continues as newly selected samples are labeled and incorporated.Experiments assume access to a very small labeled validation set.

Dataset Description

The experiments draw on datasets from LIBSVM, sklearn.datasets, and the UCI repository, with validation and test splits constructed for datasets lacking explicit partitions. The paper also reports dataset descriptions and computational-complexity comparisons for GLISTER approximations.

  • Dataset Sources: The real-world datasets were sourced from LIBSVM, sklearn.datasets, and the UCI machine learning repository.The listed datasets include dna, svmguide1, letter, ijcnn1, connect-4, usps, a9a, Census Income, Covertype, and sklearn-digits.
  • Dataset Overview: Table 1 provides a brief description of the datasets used in the experiments.
  • Dataset Splits: Datasets without explicit validation and test sets use 10% and 20% of training samples for validation and testing, respectively.Census Income sizes exclude instances with missing values.
  • Complexity Overview: Table 2 compares time complexities for GLISTER approximations under Naive Greedy and Stochastic Greedy selection.

Experimental Settings

Experiments evaluate shallow and deep models under controlled training, imbalance, and label-noise settings. Algorithm parameters govern subset size, selection frequency, validation-loss recomputation, regularization, and active-learning rounds.

  • Model Training: Experiments use shallow and deep models, including a two-layer network, LeNet-like MNIST models, and ResNet-18 for CIFAR-10.The shallow network has 100 hidden nodes; training lasts 100 epochs for MNIST, 150 for CIFAR-10, and 200 for other datasets.
  • Robustness Settings: Class imbalance removes 90% of instances from 30% of classes, while noisy experiments flip labels at a 30% noise ratio.
  • Algorithm Parameters: The subset size k determines how many points train the model.
  • Algorithm Parameters: Subset selection occurs every L epochs, with L set to 20 except in experiments varying L.
  • Algorithm Parameters: Validation loss is recomputed r times through complete forward passes, with r approximately 0.03k to balance test accuracy and training time.
  • Algorithm Parameters: Regularization uses λ = 0.9 for Rand-Reg GLISTER-ONLINE and λ = 100 for Fac Loc Reg GLISTER-ONLINE.
  • Active Learning Parameters: In active learning, B controls labels obtained per round, R is set to 10 rounds, and T is set to 200 training epochs per round.

Additional Experiments

Additional experiments evaluate GLISTER across efficient training, class imbalance, noisy labels, active learning, convergence trade-offs, and synthetic data-selection behavior. The results generally report competitive or improved performance, while exposing computational trade-offs controlled by L and r.

  • Efficient Learning: With 10%, 30%, and 50% subsets, GLISTER-ONLINE significantly outperforms baselines and often approaches full-training performance on additional datasets.
  • Robust Learning: In class-imbalance experiments, GLISTER-ONLINE significantly outperforms baselines and often exceeds full training.
  • Noisy Labels: With an 80% noise ratio, GLISTER-ONLINE outperforms baselines and achieves accuracy comparable to training on data without noise.
  • Active Learning: GLISTER-ACTIVE performs comparably to BADGE and FASS on normal datasets and often outperforms baselines under class imbalance.
  • Convergence with varying L: Lower L values produce faster convergence but higher computational time, with some datasets showing faster convergence at L = 50 than L = 20.
  • Convergence with varying r: Low r values make GLISTER-ONLINE unstable, while larger r improves stability but increases computational time; r = 10 converges faster than r = 20 on most datasets.
  • Synthetic Selection Behavior: Synthetic experiments show GLISTER-ONLINE selects points near decision boundaries, whereas CRAIG, KNNSubmod, and Random select representative training points.
  • Covariate Shift: Under shifted validation distributions, GLISTER-ONLINE is evaluated using training data, shifted validation data, validation loss, and test loss.
Loading 2012.10630v4…