A Unified Convergence Analysis for Shuffling-Type Gradient Methods

Abstract

In this paper, we propose a unified convergence analysis for a class of generic shuffling-type gradient methods for solving finite-sum optimization problems. Our analysis works with any sampling without replacement strategy and covers many known variants such as randomized reshuffling, deterministic or randomized single permutation, and cyclic and incremental gradient schemes. We focus on two different settings: strongly convex and nonconvex problems, but also discuss the non-strongly convex case. Our main contribution consists of new non-asymptotic and asymptotic convergence rates for a wide class of shuffling-type gradient methods in both nonconvex and convex settings. We also study uniformly randomized shuffling variants with different learning rates and model assumptions. While our rate in the nonconvex case is new and significantly improved over existing works under standard assumptions, the rate on the strongly convex one matches the existing best-known rates prior to this paper up to a constant factor without imposing a bounded gradient condition. Finally, we empirically illustrate our theoretical results via two numerical examples: nonconvex logistic regression and neural network training examples. As byproducts, our results suggest some appropriate choices for diminishing learning rates in certain shuffling variants.

Journal of Machine Learning Research, 2021

References in corpus (8)

• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Random Reshuffling: Simple Analysis with Vast Improvements
• Momentum-Based Variance Reduction in Non-Convex SGD
• Incremental Methods for Weakly Convex Optimization
• Closing the convergence gap of SGD without replacement
• SGD without Replacement: Sharper Rates for General Smooth Convex Functions
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization

Cited by in corpus (13)

• Random Reshuffling: Simple Analysis with Vast Improvements
• SGD with shuffling: optimal rates without component convexity and large epoch requirements
• Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
• Incremental Without Replacement Sampling in Nonconvex Optimization
• Adaptive Gradient Methods Can Be Provably Faster than SGD after Finite Epochs
• SMG: A Shuffling Gradient-Based Method with Momentum
• Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems
• Random Reshuffling with Variance Reduction: New Analysis and Better Rates
• Random-reshuffled SARAH does not need a full gradient computations
• Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Permutation-Based SGD: Is Random Optimal?
• Optimal Rates for Random Order Online Optimization