Abstract
While variance-reduction methods like SVRG and SAGA have revolutionized stochastic optimization by providing linear convergence rates, their theoretical guarantees typically rely on the assumption of sampling with replacement. In practice, however, practitioners almost exclusively use Random Reshuffling (RR)—sampling without replacement—which often yields superior empirical performance despite lacking rigorous theoretical backing. This paper bridges this gap by proving the linear convergence of SAGA under RR. Furthermore, it introduces the Amortized Variance-Reduced Gradient (AVRG) algorithm, which achieves the memory efficiency of SVRG and the computational balance of SAGA, making it highly suitable for large-scale and decentralized learning environments.
Introduction: The Gap Between Theory and Practice
In large-scale machine learning, we minimize empirical risk by averaging loss across massive datasets. While Stochastic Gradient Descent (SGD) is ubiquitous, its convergence is hindered by the variance of individual sample gradients. Variance-reduction techniques, such as SVRG and SAGA, mitigate this noise to achieve faster, linear convergence.
However, a significant discrepancy exists: mathematical proofs for these algorithms usually assume data is sampled uniformly with replacement. In contrast, real-world implementations utilize Random Reshuffling (RR), where the dataset is shuffled and processed once per epoch (sampling without replacement). RR is empirically faster but theoretically challenging because samples within an epoch are no longer independent, leading to biased gradient estimators.
Algorithmic Contributions
The paper provides two major technical advancements to reconcile these differences.
Linear Convergence of SAGA under RR
The authors rigorously demonstrate that SAGA maintains linear convergence even when data is reshuffled every epoch. They show that although the gradient estimator becomes biased under RR, this bias is "asymptotically vanishing"—it decreases as the algorithm approaches the optimal solution, allowing for stable convergence.
The AVRG Algorithm
To address the practical limitations of existing methods, the authors propose Amortized Variance-Reduced Gradient (AVRG). Existing methods often face a trade-off between memory and computational balance:
- SAGA requires $O(N)$ storage, which is prohibitive for very large datasets.
- SVRG has "unbalanced" computation, requiring a full-gradient pass at the start of each epoch that can lead to hardware idling in parallel systems.
AVRG "amortizes" the full gradient calculation by updating the average gradient incrementally during the inner loop. This design ensures constant $O(1)$ storage and balanced computation across iterations.
Empirical Evaluation
The authors evaluated the proposed theories and the AVRG algorithm using four standard binary classification benchmarks: Covtype, MNIST (0 vs 1), RCV1, and CIFAR-10 (airplane vs automobile).
Key Results
The experimental results confirm the theoretical findings:
- RR Superiority: SAGA with Random Reshuffling consistently outperforms SAGA with uniform sampling, likely because RR ensures every data point contributes to the gradient history exactly once per epoch.
- AVRG Efficiency: AVRG matches the convergence performance of SAGA and SVRG while maintaining a significantly lower memory footprint and a smoother computational profile.
Discussion and Future Work
A key insight from this work is that unbiasedness is not a strict requirement for convergence; asymptotic unbiasedness is sufficient. While the theoretical bounds provided are conservative compared to empirical observations, they offer a solid foundation for understanding why RR works so well in practice.
Future research directions include extending this analysis to non-smooth or non-convex loss functions, which are prevalent in deep learning, and further exploring AVRG's advantages in fully decentralized, peer-to-peer learning environments where centralized full-gradient computations are impossible.
Summary updated