A coordinate gradient descent method for nonsmooth separable minimization

By Paul Tseng, Sangwoon Yun. 2008

845 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

Sparse Partially Linear Additive Models (2014, methodology): “Besides, Lemma 1 in [37] suggests ∇L(β) d + dkHkdk + h(β + d) − h(β) ≤ 0.”
An asynchronous parallel stochastic coordinate descent algorithm (2013, background): “…of expected diﬀerences in successive primal iterates: where ¯ x j +1 is the hypothesized full update obtained by applying the single-component update to every component of x j , that is, In the unconstrained case Ω = R n , the ratio (17) reduces to which is evidently related to (4), but not…”
Optimization with Sparsity-Inducing Penalties (2011, methodology): “Specifically, the BCD scheme of [119] solves at each iteration a problem of the form:”
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.”
A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization (2012, neutral): “Furthermore, this idea can be used to simplify the computation and to guarantee the convergence of the original BCD algorithm with the Gauss-Seidel update rule (e.g. [31], [12], [32]).”
An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems (2009, neutral): “If P is separable, the minimum point S τ (G) can be found in closed form, which is an advantage of algorithms using (12) to update the current point (i.e., α k = 1 for all k) or compute a direction for large-scale optimization problems [24] [44] [46] [47].”
Parallel Selective Algorithms for Nonconvex Big Data Optimization (2014, neutral): “Roughly speaking these works can be divided in two groups, namely: solution methods for convexobjective functions [8], [11], [13], [23], [27], [35], [36] andnonconvex ones [9], [10], [12], [21], [37], [39], [40].”
Approximation accuracy, gradient methods, and error bound for structured convex optimization (2010, methodology): “, Jk ∪ · · · ∪ Jk+K covers all subsets of J for some constant K ≥ 0 [32,89,107,141,147] or Jk is chosen in a Gauss-Southwell manner to satisfy k ≤ ω all k ,”
Calculus of the Exponent of Kurdyka–Łojasiewicz Inequality and Its Applications to Linear Convergence of First-Order Methods (2016, methodology): “…with an open domain, so that for any ¯ y in the boundary of the domain, one has liminf y → ¯ y l ( y ) ≥ l (¯ y ) = ∞ . whenever x ∈ dom f i for some κ > 0, thanks to [41, Lemma 6], 9 and that for these x , it is easy to show that dist( x, Arg min f i ) ≤ dist(( x, P i ( x )) , Arg min g i ) .”
Heterogeneous feature machines for visual recognition (2009, methodology): “However, since the regularization term can be separated into smaller components due to the group structure, Tseng and Yun [31]suggested to carry out the optimization procedure in a group-wise way.”
On the Linear Convergence of the Proximal Gradient Method for Trace Norm Regularization (2013, methodology): “Prior to this work, Lipschitzian error bounds for composite function minimization are available for cases where the non–smooth part either has a polyhedral epigraph (such as the l1–norm) [23] or is the (sparse) group LASSO regularization [22, 25].”
A Stochastic Quasi-Newton Method for Large-Scale Optimization (2014, methodology): “To establish a reference benchmark with a well known algorithm, we used the particular implementation of one of the coordinate descent (CD) methods in [24], as described in [14].”
Distributed Block Coordinate Descent for Minimizing Partially Separable Functions (2014, methodology): “For classical references in the optimization literature on non-randomized variants we refer to the work of Tseng [14, 39, 38, 37].”
Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection (2015, background): “In Section 6, we discuss selection rules that incorporate the L i to achieve faster rates whenever the L i are distinct, but ﬁrst we consider the eﬀect of exact coordinate optimization on the choice of the L i k .”
Regression shrinkage and selection via the lasso: a retrospective (2011, neutral): “A key work is Tseng (2001), and also Tseng and Yun (2009) is crucial for extending the computation to for example group lasso problems for the non-Gaussian, generalized linear model case (Meier et al., 2008).”