Block-Coordinate Gradient Descent Method for Linearly Constrained Nonsmooth Separable Optimization

By Paul Tseng, Sangwoon Yun. 2009

172 citations recorded by the source corpus.

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

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, methodology): “We ﬁrst show that our algorithm can be seen as an instance of proximal coordinate descent (PCD) (Tseng and Yun, 2009; Richt´arik and Tak´ac, 2014) on a slightly modiﬁed objective function.”
Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, background): “But these problems have also been shown to satisfy proximal variants of the EB condition [Tseng, 2010, Necoara and Clipici, 2016], and thus by the equivalence in Appendix G we have that any L1-regularized least squares problem satisﬁes the proximal-PL inequality.”
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function (2011, background): “Yun & Tseng [22] L(∇ f ) separable Yes greedy expensive”
Approximation accuracy, gradient methods, and error bound for structured convex optimization (2010, background): “Under the EB condition, asymptotic linear and even superlinear convergence can be established for various methods, including interior point, gradient projection, proximal minimization, coordinate minimization, and coordinate gradient methods—even if X̄ is unbounded; see [13,51,81,82,140,147,145,146]”
Iteration complexity of feasible descent methods for convex optimization (2014, methodology): “If f(x) is strongly convex and X is a polyhedral set, a global error bound has been established by Pang (1987, Theorem 3.1).”
A Review of Feature Reduction Techniques in Neuroimaging (2013, methodology): “The LASSO function is solved using an optimization procedure such as the coordinate descent algorithm as explored elsewhere (Friedman et al. 2010; Tseng and Yun 2009).”
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).”
Hessian-CoCoA : a general parallel and distributed framework for non-strongly convex regularizers (2017, methodology): “9) as operative framework, (block) coordinate gradient descent method, as described in the paper [10], comes from a combination of proximal Newton-type method and coordinate descent: indeed, it is based on a local quadratic approximation of the smooth component f , plus the original r, and the basic”
On the complexity analysis of randomized block-coordinate descent methods (2013, methodology): “Block-coordinate descent (BCD) methods and their variants have been successfully applied to solve various large-scale optimization problems (see, for example, [22, 4, 18, 19, 20, 21, 9, 23]).”
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].”
Trace Norm Regularization: Reformulations, Algorithms, and Multi-Task Learning (2010, methodology): “ǫ ) iterations; see [ 52, Theorem 5.1 ]. Like the DCG method, the work per iteration for the above DGP method is O(mr2)”
Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback. (2010, background): “In the full information case, stochastic coordinate descent approaches usually have a convergence rate slower by a factor of d compared to gradient descent, which offsets the computational gains (Shalev- Shwartz & Tewari, 2009; Tseng & Yun, 2009).”