Optimization Online


Random permutations fix a worst case for cyclic coordinate descent

Ching-pei Lee (ching-pei***at***cs.wisc.edu)
Stephen J. Wright (swright***at***cs.wisc.edu)

Abstract: Variants of the coordinate descent approach for minimizing a nonlinear function are distinguished in part by the order in which coordinates are considered for relaxation. Three common orderings are cyclic (CCD), in which we cycle through the components of $x$ in order; randomized (RCD), in which the component to update is selected randomly and independently at each iteration; and random-permutations cyclic (RPCD), which differs from CCD only in that a random permutation is applied to the variables at the start of each cycle. Known convergence guarantees are weaker for CCD and RPCD than for RCD, though in most practical cases, computational performance is similar among all these variants. There is a certain family of quadratic functions for which CCD is significantly slower than for RCD; a recent paper of Sun and Ye has explored the poor behavior of CCD on this family. The RPCD approach performs well on this family, and this paper explains this good behavior with a tight analysis.

Keywords: Coordinate descent, randomization, permutations

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: IMA Journal on Numerical Analysis. To appear. First version: July 2016. Revision: November 2017. Second revision: March 2018.

Download: [PDF]

Entry Submitted: 07/28/2016
Entry Accepted: 07/28/2016
Entry Last Modified: 06/02/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society