Iteration complexity of feasible descent methods for convex optimization

By Po-Wei Wang, Chih-Jen Lin. 2014

153 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Industrial and Manufacturing Engineering, Mathematical Optimization

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 Computer Vision and Pattern Recognition

In Industrial and Manufacturing Engineering

In Mathematical Optimization

Citations in the corpus

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.”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, background): “…for problems like the hinge-loss support vector machine that could be applied, e.g., by us-ing error bound conditions (Necoara and Nedelcu, 2014; Wang and Lin, 2014), weak strong convexity conditions (Ma et al., 2015c; Necoara, 2015) or by considering Polyak-Łojasiewicz conditions (Karimi et…”
An asynchronous parallel stochastic coordinate descent algorithm (2013, methodology): “Local and global linear convergence were established under additional assumptions, by Luo and Tseng [1992] and Wang and Lin [2013], respectively.”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, methodology): “In the case of FCFW, we do not need to consider away steps: by the quality of the approximate correction in Algorithm 4 (as speciﬁed in Line 4), we know that at the beginning of a new iteration, the away gap g A t ≤ (cid:15) .”
Distributed block-diagonal approximation methods for regularized empirical risk minimization (2017, methodology): “This method has been proven to be efﬁcient in the single-core setting empirically; theoretically, it is guaranteed to converge globally linearly (Wang and Lin 2014) and can outperform other variants of coordinate descent on some cases (Lee and Wright 2019b; Wright and Lee 2017).”
PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent (2015, background): “Parallel Stochastic Coordinate Descent.”
An efficient distributed learning algorithm based on effective local functional approximations (2013, background): “The glrc result in Wang and Lin (2013) is only applicable to descent methods that are “close” (see equations (7) and (8) in Wang and Lin (2013)) to the gradient descent method.”
Frank-Wolfe with Subsampling Oracle (2018, background): “This type of function is commonly know as a ˜ µ -generally strongly convex function (Beck & Tetruashvili, 2013; Wang & Lin, 2014) or (Lacoste-Julien & Jaggi, 2015) (see “Away curvature and geometric strong convexity” in Appendix B for deﬁnition).”
A Functional Approximation Based Distributed Learning Algorithm (2013, methodology): “The glrc result in Wang & Lin [23] is only applicable to descent methods that are“close”(see equations (7) and (8) in [23]) to the gradient descent method.”
Linear Convergence of Randomized Feasible Descent Methods Under the Weak Strong Convexity Assumption (2016, methodology): “These coefficients are very similar, but FDM Wang and Lin (2014) covers only cyclic coordinate descent and not a randomized coordinate descent method (which is covered by Theorem 12).”
Distributed dual gradient methods and error bound conditions (2014, methodology): “Our approach for proving a certain error bound property is in a way similar to the one in [7,26].”
Linear convergence of first order methods for non-strongly convex optimization (2015, methodology): “Older papers that derive functional classes satisfying a local/generalized error bound type condition using the Hoffman bound are e.g. [9–11].”
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”
Linearly convergent away-step conditional gradient for non-strongly convex functions (2015, background): “Deﬁnition 2.1 ( Linear Oracle ) Given a set X , an operator O X : R n → X is called a linearoracle for X ,ifforeach c ∈ R n itreturnsavector p ∈ X suchthat (cid:4) c , p (cid:5) ≤ (cid:4) c , x for any x ∈ X , i.e., p is a minimizer of the linear function (cid:4) c , x (cid:5) over X .”
A Dual Augmented Block Minimization Framework for Learning with Limited Memory (2015, background): “…it suffices for the fast convergence of proximal-point update (11) to solve subproblem (14) for only a single pass of all blocks of variables αB1 ,..., αBK , and limit the number of iterations the designated solver spends on each subproblem (7), (14) to be no more than some parameter Tmax.”
Incremental learning for ν-Support Vector Regression (2015, background): “ˇ R t ∗ , ˇ R ∗ t The row and the column of a matrix ˇ R corresponding to the sample ( x t , y t , z t ) , respectively.”