On the Convergence of Block Coordinate Descent Type Methods

By Amir Beck, Luba Tetruashvili. 2013

683 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

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

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

An asynchronous parallel stochastic coordinate descent algorithm (2013, methodology): “Global linear (sublinear) convergence rate for strongly (weakly) convex optimization was proved in [Beck and Tetruashvili, 2013].”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, background): “7 provides similar convergence rates as another recent analysis [4], which makes slightly different assumptions on the function f .”
Dykstra's Algorithm, ADMM, and Coordinate Descent: Connections, Insights, and Extensions (2017, background): “For example, Beck and Tetruashvili (2013); Li et al. (2016) establish finite-time linear convergence rates for coordinate descent, but require strong convexity of the entire objective. Remark 3 (Active set identification). The asymptotics developed in Iusem and De Pierro (1990); Deutsch and Hundal (”
Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties (2014, methodology): “Our discussion there included non-stochastic, cyclic coordinate descent methods [38, 23, 41, 5, 39, 40], synchronous parallel methods that distribute the work of function and gradient evaluation [15, 24, 17, 7, 11, 1, 10, 35], and asynchronous parallel stochastic gradient methods (including the rand”
On the complexity analysis of randomized block-coordinate descent methods (2013, methodology): “The global and local convergence of the cyclic BCD method have been well studied in the literature (see, for example, [8,21]), and its global convergence rate (non-asymptotic) has also been established recently under various assumptions [1,3,17].”
Proximal alternating linearized minimization for nonconvex and nonsmooth problems (2013, background): “Very recently, in [10], global rate of convergence results have been derived for block coordinate gradient projection algorithm for convex and smooth constrained minimization problems.”
Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection (2015, methodology): “While this is faster than known rates for cyclic coordinate selection [Beck and Tetruashvili, 2013] and holds deterministically rather than in expectation, this rate is the same as the randomized rate given in (5).”
Graph Learning From Data Under Laplacian and Structural Constraints (2016, methodology): “For Problems 2 and 3, Algorithms 1 and 2 implement a variation of the general projected block-coordinate descent method, whose convergence to the optimal solution is shown in [55].”
Iteration complexity of feasible descent methods for convex optimization (2014, background): “A similar rate of linear convergence appears in Beck and Tetruashvili (2013). They assumed f is σmin strongly convex and the optimization problem is unconstrained.”
PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent (2015, background): “In terms of theoretical analysis, the convergence of (cyclic) coordinate descent has been studied for a long time (Luo & Tseng, 1992; Bertsekas, 1999), and the global linear convergence is presented recently under certain condition (Saha & Tewari, 2013; Wang & Lin, 2014).”
On the Convergence of Alternating Minimization for Convex Programming with Applications to Iteratively Reweighted Least Squares and Decomposition Schemes (2015, background): “The only result available on the rate of convergence of the method under general convexity assumptions (and not strong convexity) is the result in [4] showing a sublinear rate of convergence, and that the multiplicative constant depends on the minimum of the block Lipschitz constants.”
Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms (2014, methodology): “1) is to use a block-coordinate descent method, which minimizes f(x) with respect to a block of variables at each iteration; a simpler approach forms a local quadratic model of f(x) at each iteration and essentially solves a projection subproblem over some block [26, 29, 3].”
Let's Make Block Coordinate Descent Go Fast: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence (2017, background): “E Functions Bound Iterates under Strong-Convexity Defining F (x) as F (x) = f(x) + g(x) in the “smooth plus separable non-smooth” setting of (27), existing works on cyclic [2] and greedy selection [61] of ik within proximal coordinate descent methods imply that F (x)− F (x∗) ≤ ρ[F (x)− F (x∗)], (40)”
Deep Unsupervised Similarity Learning Using Partially Ordered Sets (2017, background): “The convergence of block coordinate-descent methods has been largely discussed obtaining guarantees of convergence to a stationary point [30, 4].”
Parallel Random Coordinate Descent Method for Composite Minimization: Convergence Analysis and Error Bounds (2016, background): “For cyclic coordinate search, estimates on the rate of convergence were given recently in [1, 5], while they were given for the greedy coordinate search in [28].”