Submodular Batch Selection for Training Deep Neural Networks

K. J. Joseph, Vamshi Teja R, Krishnakant Singh, Vineeth N. Balasubramanian

TL;DR

This paper introduces a novel method for selecting mini-batches of data during deep neural network training. By framing batch selection as a submodular optimization problem, the authors ensure that each mini-batch is both informative and diverse, leading to improved model generalization compared to standard Stochastic Gradient Descent (SGD) and other sampling techniques.

What Problem Does This Paper Address?

Training deep neural networks typically relies on mini-batch Stochastic Gradient Descent (SGD). The process of selecting these mini-batches, however, is usually done by randomly sampling data points. This random selection might not be optimal, as it could lead to redundant or uninformative samples within a batch, potentially hindering the model's ability to generalize well to unseen data. The paper addresses the challenge of intelligently selecting mini-batches that maximize both the informativeness of individual samples and the diversity of the entire batch, aiming to improve the generalization performance of deep learning models.

Methods

The core of the paper's contribution lies in formulating mini-batch selection as a cardinality-constrained monotone submodular function maximization problem. Submodular functions exhibit a "diminishing returns" property, meaning the benefit of adding an element to a set decreases as the set grows. This property is leveraged to ensure diversity.

The authors propose a composite objective function, $F(S)$, which combines four scores:

  • Uncertainty Score ($U(x_i)$): Measures how "confused" the model is by a data point, indicating its informativeness. This is calculated using the entropy of the model's predictions.
  • Redundancy Score ($R(x_i)$): Encourages diversity by penalizing samples that are too close to each other in the feature space. This is achieved by using a distance metric (e.g., Euclidean) to find the minimum distance to other samples in the potential batch.
  • Mean Closeness Score ($MC(x_i)$): Helps avoid selecting outliers by favoring samples closer to the mean of the dataset.
  • Feature Match Score ($FM(x_i)$): Enforces diversity across different feature dimensions.

This submodular objective function is then solved using an efficient greedy algorithm, which is guaranteed to find a solution that is at least (1 - 1/e) (approximately 0.63) of the optimal solution. To handle the high sampling rates required for SGD, they propose a scalable, divide-and-conquer approach inspired by distributed submodular maximization and a "Lazier than Lazy Greedy" (LtLG) algorithm.

Datasets

The paper evaluates its proposed method on the following standard image classification datasets:

  • SVHN (Street View House Numbers)
  • CIFAR-10
  • CIFAR-100

The network architectures used were ResNet 20 for SVHN and CIFAR-10, and ResNet 32 for CIFAR-100.

Key Insights and Ideas

  • Submodularity for Data Selection: The paper demonstrates that the principles of submodularity, often used in areas like document summarization or sensor placement, can be effectively applied to the problem of selecting informative and diverse mini-batches for deep learning.
  • Balancing Informativeness and Diversity: The proposed objective function successfully balances the need for samples that challenge the model (informativeness) with the need for samples that cover different aspects of the data distribution (diversity).
  • Improved Generalization: The core insight is that intelligent batch selection, rather than random sampling, can lead to models that generalize better to unseen data, as evidenced by lower test errors and losses.
  • Robustness to Hyperparameters: The method shows consistent performance across different learning rates, batch sizes, and distance metrics, indicating its robustness.

Key Results

  • The proposed Submodular Mini-Batch Data Loader (SMDL) consistently outperforms standard SGD and a loss-based sampling baseline in terms of test accuracy and test loss across all tested datasets (SVHN, CIFAR-10, CIFAR-100).
  • For example, on SVHN, SMDL achieved a final accuracy of 95.46%, compared to 93.60% for loss-based sampling and 92.44% for SGD.
  • The paper also shows that SMDL leads to less overfitting: training error is higher for SMDL compared to SGD and loss-based sampling, while test error is significantly lower. This indicates that SMDL trains models that are better at generalizing.
  • Ablation studies confirm that each component of the submodular objective function contributes to the overall performance, and that Euclidean distance is a suitable metric for diversity.

Limitations and Future Work

  • Computational Cost: While the proposed method is scalable, it is noted that SMDL takes significantly more time per epoch than standard SGD (e.g., 937 seconds for SMDL vs. 373 seconds for SGD on SVHN). However, it is still faster than loss-based sampling.
  • Future Work: The authors suggest extending the submodular objective to allow the model to decide not only which data points to select but also the optimal number of data points for training. They also aim to develop more efficient strategies to further speed up the proposed method.

Summary updated

Abstract

Mini-batch gradient descent based methods are the de facto algorithms for training neural network architectures today.We introduce a mini-batch selection strategy based on submodular function maximization. Our novel submodular formulation captures the informativeness of each sample and diversity of the whole subset. We design an efficient, greedy algorithm which can give high-quality solutions to this NP-hard combinatorial optimization problem. Our extensive experiments on standard datasets show that the deep models trained using the proposed batch selection strategy provide better generalization than Stochastic Gradient Descent as well as a popular baseline sampling strategy across different learning rates, batch sizes, and distance metrics.
BibTeX
@inproceedings{joseph2019submodular,
  author = {K. J. Joseph and Vamshi Teja R and Krishnakant Singh and Vineeth N. Balasubramanian},
  title = {{Submodular Batch Selection for Training Deep Neural Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=4KEUvfEHP25},
}
Figure