Understanding Limitation of Two Symmetrized Orders by Worst-case Complexity

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.

arXiv comment31 pages, 9 tables

References in corpus (14)

• Why Random Reshuffling Beats Stochastic Gradient Descent
• A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization
• A Convergent 3-Block Semi-Proximal Alternating Direction Method of Multipliers for Conic Programming with $4$-Type of Constraints
• Randomized Dual Coordinate Ascent with Arbitrary Sampling
• PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent
• Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences
• Worst-case Complexity of Cyclic Coordinate Descent: $O(n^2)$ Gap with Randomized Version
• On the Sublinear Convergence Rate of Multi-Block ADMM
• Improved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex Problems
• On the Efficiency of Random Permutation for ADMM and Coordinate Descent
• On the Global Linear Convergence of the ADMM with Multi-Block Variables
• Iteration Complexity Analysis of Multi-Block ADMM for a Family of Convex Minimization without Strong Convexity
• Extended ADMM and BCD for Nonseparable Convex Minimization Models with Quadratic Coupling Terms: Convergence Analysis and Insights
• Explicit diagonalization of an anti-triangular Cesaró matrix