Randomness and permutations in coordinate descent methods

We consider coordinate descent (CD) methods with exact line search on convex quadratic problems. Our main focus is to study the performance of the CD method that use random permutations in each epoch and compare it to the performance of the CD methods that use deterministic orders and random samplin...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2020-06, Vol.181 (2), p.349-376
Main Authors: Gürbüzbalaban, Mert, Ozdaglar, Asuman, Vanli, Nuri Denizcan, Wright, Stephen J.
Format: Article
Language:English
Subjects:
Algorithms
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Descent
Full Length Paper
Hessian matrices
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematical programming
Mathematics
Mathematics and Statistics
Mathematics of Computing
Methods
Numerical Analysis
Optimization
Performance enhancement
Permutations
Random sampling
Theoretical
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider coordinate descent (CD) methods with exact line search on convex quadratic problems. Our main focus is to study the performance of the CD method that use random permutations in each epoch and compare it to the performance of the CD methods that use deterministic orders and random sampling with replacement. We focus on a class of convex quadratic problems with a diagonally dominant Hessian matrix, for which we show that using random permutations instead of random with-replacement sampling improves the performance of the CD method in the worst-case. Furthermore, we prove that as the Hessian matrix becomes more diagonally dominant, the performance improvement attained by using random permutations increases. We also show that for this problem class, using any fixed deterministic order yields a superior performance than using random permutations. We present detailed theoretical analyses with respect to three different convergence criteria that are used in the literature and support our theoretical results with numerical experiments.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-019-01438-4