Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization

By Paul Tseng. 2001

2,267 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, 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 Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

In Optimization & Training

Citations in the corpus

Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, background): “Alternating optimization converges to a local optimum under mild technical conditions, see (Tseng, 2001; Tseng and Yun, 2009; Razaviyayn et al., 2013).”
Additive models with trend filtering (2017, methodology): “5 in van de Geer [1990] (see also van de Geer [2000]). Lemma 14. Let , i = 1, . . . , n be uniformly sub-Gaussian random variables having variance proxy σ(2) > 0. Let J be a seminorm satisfying Assumption C3, and let ρ > 0 be arbitrary. Then there exist constants c1, c2, n0 > 0, depending only on σ,”
Fused Lasso Additive Model (2014, methodology): “Here we develop a much faster algorithm using block coordinate descent to solve (5) [Tseng, 2001].”
An asynchronous parallel stochastic coordinate descent algorithm (2013, neutral): “Among cyclic coordinate descent algorithms, Tseng (2001) proved the convergence of a block coordinate descent method for nondifferentiable functions with certain conditions.”
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.”
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function (2011, background): “While theasymptotic convergence rates of some variants of CD methods are well understood [9], [23], [21], [31],iteration complexityresults are very rare.”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, background): “essentially cyclic [40], randomized [41] or parallel) and solve the subproblem inexactly.”
Multi-Stage Multi-Task Feature Learning (2012, positive): “(8) is the block coordinate descent (Grippo and Sciandrone, 2000; Tseng, 2001) summarized below: • Fix W = Ŵ (ℓ): v̂(ℓ) = argmin v { l(Ŵ (ℓ)) + λvTh(Ŵ (ℓ))− λg⋆(v) } = argmin v { vTh(Ŵ (ℓ))− g⋆(v) } .”
A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization (2012, neutral): “Convergence of the BCD method typically requires the uniqueness of the minimizer at each step or the quasi-convexity of the objective function (see [30] and the references therein).”
An efficient algorithm for a class of fused lasso problems (2010, methodology): “Convergence results have been established, when the non-differentiable part is separable [33, 34]; and CD was applied for solving Lasso in [8].”
An Exact Penalty Method for Binary Optimization Based on MPEC Formulation (2017, methodology): “In each iteration, we minimize over x and v alternatingly (Tseng, 2001; Bolte, Sabach, and Teboulle, 2014), while fixing the parameter ρ.”
An introduction to continuous optimization for imaging (2016, background): “In the context of this chapter, see in particular Beck and Tetruashvili (2013); see also Tseng (2001), Tseng and Yun (2009), Beck (2015), Chouzenoux, Pesquet and Repetti (2016) and Nesterov (2012).”
Recursive regularization for large-scale classification with hierarchical and graphical dependencies (2013, neutral): “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].”
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].”
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, background): “When f is nonsmooth, the original BCD can get stuck at a non-stationary point [2, Page 94], but not if the nonsmooth part is separable (see [17,31,49, 50,60,41,40,61,62] for results on different forms of f and different variants of BCD).”