Understanding Limitation of Two Symmetrized Orders by Worst-case Complexity
Preprint
Abstract
Update order is one of the major design choices of block decomposition algorithms. There are at least two classes of deterministic update orders: nonsymmetric (e.g. cyclic order) and symmetric (e.g. Gaussian back substitution or symmetric Gauss-Seidel). Recently, Coordinate Descent (CD) with cyclic order 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 faster convergence rates than the cyclic order, or even getting close to the randomized versions? In this paper, we give a negative answer to this question. We show that both Gaussian back substitution (GBS) and symmetric Gauss-Seidel (sGS) suffer from the same slow convergence issue as the cyclic order in the worst case. In particular, we prove that for unconstrained problems, both GBS-CD and sGS-CD can be $O(n^2)$ times slower than R-CD. Despite unconstrained problems, we also empirically study linearly constrained problems with quadratic objective: we empirically demonstrate that the convergence speed of GBS-ADMM and sGS-ADMM can be roughly $O(n^2)$ times slower than randomly permuted ADMM.
Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Worst-case complexity of cyclic coordinate descent: $O(n^2)$ gap with randomized versionMathematical Programming, 2019
- Parallel Multi-Block ADMM with o(1 / k) ConvergenceJournal of Scientific Computing, 2016
- On the linear convergence of the alternating direction method of multipliersMathematical Programming, 2016
- Iteration Complexity Analysis of Multi-block ADMM for a Family of Convex Minimization Without Strong ConvexityJournal of Scientific Computing, 2016
- On the Proximal Jacobian Decomposition of ALM for Multiple-Block Separable Convex Minimization Problems and Its Relationship to ADMMJournal of Scientific Computing, 2015
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensionsMathematical Programming, 2014
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergentMathematical Programming, 2014
- Efficient random coordinate descent algorithms for large-scale structured nonconvex optimizationJournal of Global Optimization, 2014
- A Note on the Alternating Direction Method of MultipliersJournal of Optimization Theory and Applications, 2012
- Triangular truncation and finding the norm of a Hadamard multiplierLinear Algebra and its Applications, 1992