On the Comparison between Cyclic Sampling and Random Reshuffling.

摘要: When applying a stochastic/incremental algorithm, one must choose the order to draw samples. Among most popular approaches are cyclic sampling and random reshuffling, which empirically faster more cache-friendly than uniform-iid-sampling. Cyclic draws samples in fixed, order, is less robust reshuffling periodically. Indeed, existing works have established worst case convergence rates for sampling, generally worse that of reshuffling. In this paper, however, we found certain can be much discover it at low cost! Studying comparing different orders typically require new analytic techniques. introduce norm, defined based on measure distance solution. Applying technique proximal Finito/MISO algorithm allows us identify optimal fixed ordering, beat by factor up log(n)/n terms best-known upper bounds. We also propose strategy ordering numerically. The state-of-the-art compared previous works.