On the convergence of the coordinate descent method for convex differentiable minimization

By Zhi-Quan Tom Luo, Paul Tseng. 1992

The coordinate descent method enjoys a long history in convex differentiable minimization. Surprisingly, very little is known about the convergence of the iterates generated by this method. Convergence typically requires restrictive assumptions such as that the cost function has bounded level sets and is in some sense strictly convex. In a recent work, Luo and Tseng showed that the iterates are convergent for the symmetric monotone linear complementarity problem, for which the cost function is convex quadratic, but not necessarily strictly convex, and does not necessarily have bounded level sets. In this paper, we extend these results to problems for which the cost function is the composition of an affine mapping with a strictly convex function which is twice differentiable in its effective domain. In addition, we show that the convergence is at least linear. As a consequence of this result, we obtain, for the first time, that the dual iterates generated by a number of existing methods for matrix balancing and entropy optimization are linearly convergent.

Subfields: Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, background): “Luo & Tseng (1992) has proven a local linear convergence rate for the strongly convex case.”
Minimizing finite sums with the stochastic average gradient (2013, background): “Further, even in cases where μ = λ, the convergence rate of SAG might be much faster if the iterates stay in local region with a higher 7Local linear convergence rates of deterministic coordinate descent methods had been established much earlier [Luo and Tseng, 1992].”
An asynchronous parallel stochastic coordinate descent algorithm (2013, neutral): “If L i , L max , and L res are deﬁned in the block sense, as follows: where E i is the projection from the i th block to R n and | i | denotes the number of components in block i , our analysis can be extended appropriately.”
Coordinate descent algorithms (2015, background): “6] included a comprehensive discussion of “univariate relaxation,” and such optimization specialists as Luo and Tseng [30,31], Tseng [55], and Bertsekas and Tsitsiklis [5] made important contributions to understanding the convergence properties of these methods in the 1980s and 1990s.”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, methodology): “Stochastic optimization has been extensively studied in the machine learning community [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].”
On the linear convergence of the alternating direction method of multipliers (2012, methodology): “By using this bound, it can be shown that a number of ascent methods, including coordinate ascent methods and a gradient projection method, converge at least linearly when applied to solve the dual problem (see [33,34]; also see [2,11,28] for related analysis).”
Recursive regularization for large-scale classification with hierarchical and graphical dependencies (2013, background): “Note that the convergence of the above optimization method can be derived by viewing the procedure as a block co-ordinate descent scheme on a convex function where the blocks corresponds to parameters at each node of the hierarchy [23], [30].”
Multi-Class Deep Boosting (2014, background): “The theorem can in fact be extended to the case where instead of the best direction, the derivative for the direction selected at each round is within a constant threshold of the best [Luo and Tseng, 1992].”
PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent (2015, background): “Coordinate descent is a classical optimization technique that has been studied for a long time (Bertsekas, 1999; Luo & Tseng, 1992).”
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems (2013, background): “Various update schemes have been considered, such as cyclic coordinate update and the best coordinate update, however these schemes are either hard to estimate [20] or difficult to be implemented efficiently.”
Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions (2017, background): “(Of course, for solving linear systems, coordinate descent reduces to Gauss-Seidel iterations, which dates back to the 1800s.) Some key papers analyzing the convergence of coordinate descent methods are Tseng and Bertsekas (1987); Tseng (1990); Luo and Tseng (1992, 1993); Tseng (2001).”
A Globally Convergent Algorithm for Nonconvex Optimization Based on Block Coordinate Update (2014, methodology): “The convergence rate of BCM was established under the strong convexity assumption [33] for the multi-block case and under the general convexity assumption [7] for the two-block case.”
Error bounds and convergence analysis of feasible descent methods: a general approach (1993, methodology): “This brings together previously scattered results [ 36-38 , 56] and serves to highlight the connections between them (see section 2). Second, we propose a general class of feasible descent methods, based on the iteration (1.3), that unifies the methods mentioned above.”