Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders
This work addresses a bottleneck in stochastic optimization for machine learning practitioners by enhancing theoretical guarantees for practical sampling methods, though it is incremental as it builds on existing variance reduction techniques.
The paper tackles the problem of improving convergence rates for variance reduction methods under without-replacement sampling orders in composite finite-sum minimization, developing Prox-DFinito which achieves state-of-the-art rates matching full-batch gradient descent and, in highly data-heterogeneous scenarios, attains a sample-size-independent convergence rate that matches uniform-iid-sampling with variance reduction.
When applying a stochastic algorithm, one must choose an order to draw samples. The practical choices are without-replacement sampling orders, which are empirically faster and more cache-friendly than uniform-iid-sampling but often have inferior theoretical guarantees. Without-replacement sampling is well understood only for SGD without variance reduction. In this paper, we will improve the convergence analysis and rates of variance reduction under without-replacement sampling orders for composite finite-sum minimization. Our results are in two-folds. First, we develop a damped variant of Finito called Prox-DFinito and establish its convergence rates with random reshuffling, cyclic sampling, and shuffling-once, under both convex and strongly convex scenarios. These rates match full-batch gradient descent and are state-of-the-art compared to the existing results for without-replacement sampling with variance-reduction. Second, our analysis can gauge how the cyclic order will influence the rate of cyclic sampling and, thus, allows us to derive the optimal fixed ordering. In the highly data-heterogeneous scenario, Prox-DFinito with optimal cyclic sampling can attain a sample-size-independent convergence rate, which, to our knowledge, is the first result that can match with uniform-iid-sampling with variance reduction. We also propose a practical method to discover the optimal cyclic ordering numerically.