On the efficiency of random permutation for ADMM and coordinate descent

Ruoyu Sun, Zhi Quan Luo, Yinyu Ye

Research output: Contribution to journalArticlepeer-review

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 (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.

Original languageEnglish (US)
Pages (from-to)233-271
Number of pages39
JournalMathematics of Operations Research
Volume45
Issue number1
DOIs
StatePublished - Feb 2020

Keywords

  • ADMM
  • Convergence
  • Coordinate descent
  • Matrix AM-GM inequality
  • Random permutation
  • Spectral radius

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'On the efficiency of random permutation for ADMM and coordinate descent'. Together they form a unique fingerprint.

Cite this