On the Efficiency of Random Permutation for ADMM and Coordinate Descent

Ruoyu Sun (), Zhi-Quan Luo () and Yinyu Ye ()
Additional contact information
Ruoyu Sun: Department of Industrial and Enterprise Systems Engineering and Coordinated Science Laboratory, University of Illinois Urbana–Champaign, Champaign, Illinois 61801;
Zhi-Quan Luo: Chinese University of Hong Kong, 518172 Shenzhen, China; Shenzhen Research Institute of Big Data, 518172 Shenzhen, China;
Yinyu Ye: Department of Management Science and Engineering, Stanford University, Palo Alto, California 94305

Mathematics of Operations Research, 2020, vol. 45, issue 1, 233–271

Abstract: Random permutation is observed to be powerful for optimization algorithms: for multiblock ADMM (alternating direction method of multipliers), whereas the classical cyclic version diverges, the randomly permuted version converges in practice; for BCD (block coordinate descent), the randomly permuted version is typically faster than other versions. In this paper we provide strong theoretical evidence that random permutation has positive effects on ADMM and BCD, by analyzing randomly permuted ADMM (RP-ADMM) for solving linear systems of equations, and randomly permuted BCD (RP-BCD) for solving unconstrained quadratic problems. First, we prove that RP-ADMM converges in expectation for solving systems of linear equations. The key technical result is that the spectrum of the expected update matrix of RP-BCD lies in (−1/3, 1), instead of the typical range (−1, 1). Second, we establish expected convergence rates of RP-ADMM for solving linear systems and RP-BCD for solving unconstrained quadratic problems. This expected rate of RP-BCD is O ( n ) times better than the worst-case rate of cyclic BCD, thus establishing a gap of at least O ( n ) between RP-BCD and cyclic BCD. To analyze RP-BCD, we propose a conjecture of a new matrix algebraic mean-geometric mean inequality and prove a weaker version of it.

Keywords: random permutation; ADMM; coordinate descent; convergence; matrix AM-GM inequality; spectral radius (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2019.0990 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:45:y:2020:i:1:p:233-271

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().