An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
arXiv:2106.02720
Abstract
We present and analyze an algorithm for optimizing smooth and convex or strongly convex objectives using minibatch stochastic gradient estimates. The algorithm is optimal with respect to its dependence on both the minibatch size and minimum expected loss simultaneously. This improves over the optimal method of Lan (2012), which is insensitive to the minimum expected loss; over the optimistic acceleration of Cotter et al. (2011), which has suboptimal dependence on the minibatch size; and over the algorithm of Liu and Belkin (2018), which is limited to least squares problems and is also similarly suboptimal with respect to the minibatch size. Applied to interpolation learning, the improvement over Cotter et al. and Liu and Belkin translates to a linear, rather than square-root, parallelization speedup.
arXiv comment24 pages
References in corpus (15)
- Reconciling modern machine learning practice and the bias-variance trade-off
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- Understanding deep learning requires rethinking generalization
- A Convergence Theory for Deep Learning via Over-Parameterization
- Optimal Distributed Online Prediction using Mini-Batches
- On Lazy Training in Differentiable Programming
- Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
- Better Mini-Batch Algorithms via Accelerated Gradient Methods
- The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
- Benign overfitting in ridge regression
- Unified Optimal Analysis of the (Stochastic) Gradient Method
- Optimal Black-Box Reductions Between Optimization Objectives
- Accelerating SGD with momentum for over-parameterized learning
- Minibatch vs Local SGD for Heterogeneous Distributed Learning
- Optimistic Rates for Learning with a Smooth Loss