Analyzing Random Permutations for Cyclic Coordinate Descent

2017/06/03 by Wright, Stephen J., Lee, Ching-Pei · 2 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1706.00908

Abstract

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.

Cited by

• Randomized coordinate gradient descent almost surely escapes strict saddle points
• On the Worst-Case Analysis of Cyclic Block Coordinate Descent type Algorithms

Related

• Randomness and Permutations in Coordinate Descent Methods
• Random Permutations Fix a Worst Case for Cyclic Coordinate Descent
• Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
• Convergence rate analysis of randomized and cyclic coordinate descent for convex optimization through semidefinite programming
• Worst-case Complexity of Cyclic Coordinate Descent: O(n²) Gap with Randomized Version