Analyzing Random Permutations for Cyclic Coordinate Descent

Published: 2017/06/01, Updated: 2020/01/13

Unconstrained Optimization coordinate descent, gauss-seidel, permutations, randomization Short URL: https://optimization-online.org/?p=14599

We consider coordinate descent methods on convex quadratic problems, in which exact line searches are performed at each iteration. (This algorithm is identical to Gauss-Seidel on the equivalent symmetric positive definite linear system.) We describe a class of convex quadratic problems for which the random-permutations version of cyclic coordinate descent (RPCD) outperforms the standard cyclic coordinate descent (CCD) approach, yielding convergence behavior similar to the fully-random variant (RCD). A convergence analysis is developed to explain the empirical observations.

Analyzing Random Permutations for Cyclic Coordinate Descent

Citation

Article