Timezone: »

An Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders
Xinmeng Huang · Kun Yuan · Xianghui Mao · Wotao Yin

Tue Dec 07 04:30 PM -- 06:00 PM (PST) @

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 generally 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.

Author Information

Xinmeng Huang (University of Pennsylvania)
Kun Yuan (Alibaba Group)
Xianghui Mao (Tsinghua University, Tsinghua University)
Wotao Yin (Alibaba US, DAMO Academy)

More from the Same Authors