Randomness and permutations in coordinate descent methods

Mathematical Programming, 181, pp. 349–376, 2020.

Publisher (DOI)

Does the order in which coordinate descent visits the coordinates matter? For a family of quadratic problems the paper gives exact convergence rates for the random-permutations order and shows it can beat both the fixed cyclic order and independent random sampling, while the cyclic order can beat random sampling on others — the picture is more subtle than the worst-case bounds suggest.

The playground Why random reshuffling beats SGD lets you try the ideas of this paper in the browser.

The research note Why random reshuffling beats SGD explains the paper informally.

Incremental methods & data ordering

• Why random reshuffling beats stochastic gradient descent (Math. Program., 2021)
• Convergence rate of incremental gradient and incremental Newton methods (SIAM J. Optim., 2019)
• Global convergence rate of proximal incremental aggregated gradient methods (SIAM J. Optim., 2018)
• Surpassing gradient descent provably: a cyclic incremental method with linear convergence rate (SIAM J. Optim., 2018)
• A double incremental aggregated gradient method with linear convergence rate for large-scale optimization (ICASSP, 2017)