SMG: A Shuffling Gradient-Based Method with Momentum
arXiv:2011.11884
Abstract
We combine two advanced ideas widely used in optimization for machine learning: shuffling strategy and momentum technique to develop a novel shuffling gradient-based method with momentum, coined Shuffling Momentum Gradient (SMG), for non-convex finite-sum optimization problems. While our method is inspired by momentum techniques, its update is fundamentally different from existing momentum-based methods. We establish state-of-the-art convergence rates of SMG for any shuffling strategy using either constant or diminishing learning rate under standard assumptions (i.e.-smoothness and bounded variance). When the shuffling strategy is fixed, we develop another new algorithm that is similar to existing momentum methods, and prove the same convergence rates for this algorithm under the -smoothness and bounded gradient assumptions. We demonstrate our algorithms via numerical simulations on standard datasets and compare them with existing shuffling methods. Our tests have shown encouraging performance of the new algorithms.
arXiv commentThe 38th International Conference on Machine Learning (ICML 2021)
References in corpus (14)
- PyTorch: An Imperative Style, High-Performance Deep Learning Library
- Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
- An overview of gradient descent optimization algorithms
- SGDR: Stochastic Gradient Descent with Warm Restarts
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
- Random Reshuffling: Simple Analysis with Vast Improvements
- A Unified Convergence Analysis for Shuffling-Type Gradient Methods
- Incremental Methods for Weakly Convex Optimization
- Variance-Reduced Stochastic Learning under Random Reshuffling
- A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
- SGD with shuffling: optimal rates without component convexity and large epoch requirements
- Closing the convergence gap of SGD without replacement
- SGD without Replacement: Sharper Rates for General Smooth Convex Functions