Optimization Online


Understanding Limitation of Two Symmetrized Orders by Worst-case Complexity

Peijun Xiao(peijunx2***at***illinois.edu)
Zhisheng Xiao(zxiao***at***uchicago.edu)
Ruoyu Sun(ruoyus***at***illinois.edu)

Abstract: It was recently found that the standard version of multi-block cyclic ADMM diverges. Interestingly, Gaussian Back Substitution ADMM (GBS-ADMM) and symmetric Gauss-Seidel ADMM (sGS-ADMM) do not have the divergence issue. Therefore, it seems that symmetrization can improve the performance of the classical cyclic order. In another recent work, cyclic CD (Coordinate Descent) was shown to be O(n^2) times slower than randomized versions in the worst-case. A natural question arises: can the symmetrized orders achieve a faster convergence rate than the cyclic order, or even getting close to randomized versions? In this paper, we give a negative answer to this question. We show that both Gaussian Back Substitution and symmetric Gauss-Seidel order suffer from the same slow convergence issue as the cyclic order in the worst case. In particular, we prove that for unconstrained problems, they can be O(n^2) times slower than R-CD. For linearly constrained problems with quadratic objective, we empirically show the convergence speed of GBS-ADMM and sGS-ADMM can be roughly O(n^2) times slower than randomly permuted ADMM.

Keywords: Convex optimization, coordinate descent, alternating direction method of multipliers, worst-case efficiency estimates

Category 1: Convex and Nonsmooth Optimization

Category 2: Complementarity and Variational Inequalities

Category 3: Nonlinear Optimization


Download: [PDF]

Entry Submitted: 11/04/2019
Entry Accepted: 11/04/2019
Entry Last Modified: 11/04/2019

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