Variance-Reduced Stochastic Learning under Random Reshuffling

Abstract

Several useful variance-reduced stochastic gradient algorithms, such as SVRG, SAGA, Finito, and SAG, have been proposed to minimize empirical risks with linear convergence properties to the exact minimizer. The existing convergence results assume uniform data sampling with replacement. However, it has been observed in related works that random reshuffling can deliver superior performance over uniform sampling and, yet, no formal proofs or guarantees of exact convergence exist for variance-reduced algorithms under random reshuffling. This paper makes two contributions. First, it resolves this open issue and provides the first theoretical guarantee of linear convergence under random reshuffling for SAGA; the argument is also adaptable to other variance-reduced algorithms. Second, under random reshuffling, the paper proposes a new amortized variance-reduced gradient (AVRG) algorithm with constant storage requirements compared to SAGA and with balanced gradient computations compared to SVRG. AVRG is also shown analytically to converge linearly.

References in corpus (5)

• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
• Finito: A Faster, Permutable Incremental Gradient Method for Big Data Problems
• Variance-Reduced Stochastic Learning by Networked Agents under Random Reshuffling

Cited by in corpus (5)

• Stochastic Learning under Random Reshuffling with Constant Step-sizes
• An introduction to decentralized stochastic optimization with gradient tracking
• Gradient tracking and variance reduction for decentralized optimization and machine learning
• A general framework for decentralized optimization with first-order methods
• SMG: A Shuffling Gradient-Based Method with Momentum