Adam with Bandit Sampling for Deep Learning

Abstract

Adam is a widely used optimization method for training deep learning models. It computes individual adaptive learning rates for different parameters. In this paper, we propose a generalization of Adam, called Adambs, that allows us to also adapt to different training examples based on their importance in the model's convergence. To achieve this, we maintain a distribution over all examples, selecting a mini-batch in each iteration by sampling according to this distribution, which we update using a multi-armed bandit algorithm. This ensures that examples that are more beneficial to the model training are sampled with higher probabilities. We theoretically show that Adambs improves the convergence rate of Adam---$O(\sqrt{\frac{\log n}{T}})$ instead of $O(\sqrt{\frac{n}{T}})$ in some cases. Experiments on various models and datasets demonstrate Adambs's fast convergence in practice.

arXiv commentAccepted to NeurIPS 2020 as spotlight presentation

References in corpus (8)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• ADADELTA: An Adaptive Learning Rate Method
• On the Convergence of Adam and Beyond
• On The Power of Curriculum Learning in Training Deep Networks
• Not All Samples Are Created Equal: Deep Learning with Importance Sampling
• Variance Reduction in SGD by Distributed Importance Sampling
• Stochastic Dual Coordinate Ascent with Adaptive Probabilities
• Coordinate Descent with Bandit Sampling

Cited by in corpus (1)

• 1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed