TY - JOUR

T1 - On the efficiency of random permutation for ADMM and coordinate descent

AU - Sun, Ruoyu

AU - Luo, Zhi Quan

AU - Ye, Yinyu

N1 - Funding Information:
Funding: This research is supported by the leading talents of Guangdong Province program [Grant 00201501]; the Development and Reform Commission of Shenzhen Municipality; Air Force Office of Scientific Research [Grant FA9550-12-1-0396]; National Science Foundation of China [Grant 61731018]; and the National Science Foundation [Grant CCF 1755847].

PY - 2020/2

Y1 - 2020/2

N2 - 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 (RPADMM) 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.

AB - 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 (RPADMM) 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.

KW - ADMM

KW - Convergence

KW - Coordinate descent

KW - Matrix AM-GM inequality

KW - Random permutation

KW - Spectral radius

UR - http://www.scopus.com/inward/record.url?scp=85085130210&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85085130210&partnerID=8YFLogxK

U2 - 10.1287/MOOR.2019.0990

DO - 10.1287/MOOR.2019.0990

M3 - Article

AN - SCOPUS:85085130210

VL - 45

SP - 233

EP - 271

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

SN - 0364-765X

IS - 1

ER -