A dual coordinate descent method for large-scale linear SVM

By Cho-Jui Hsieh, Kai-Wei Chang, Chih-Jen Lin, S. Sathiya Keerthi, S. Sundararajan. 2008

1,036 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical Learning Theory, Signal Processing

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 Statistical Learning Theory

In Signal Processing

Citations in the corpus

Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “In the degenerate binary SVM case, our block-coordinate Frank-Wolfe algorithm is actually equivalent to the method of Hsieh et al. (2008), where because each datapoint has a unique dual variable, exact coordinate optimization can be accomplished by the line-search step of our algorithm.”
Distributed Coordinate Descent Method for Learning with Big Data (2013, methodology): “Methods of this type, in various settings, were studied by several authors, including Hsieh et al. (2008); Shalev-Shwartz & Tewari (2009); Nesterov (2012); Richtárik & Takáč (2012c); Necoara et al.”
Stochastic dual coordinate ascent methods for regularized loss (2012, positive): “[3] recently argued that SDCA outperform the SGD approach in some regimes.”
Communication-Efficient Distributed Dual Coordinate Ascent (2014, methodology): “MJ acknowledges support by the Simons Institute for the Theory of Computing.”
Mini-Batch Primal and Dual Methods for SVMs (2013, methodology): “In the context of SVMs, approaches of this form include primal stochastic gradient descent (SGD) methods (e.g., Pegasos, Shalev-Shwartz et al. 2011, NORMA, Zhang 2004) and dual stochastic coordinate ascent (Hsieh et al., 2008).”
Semi-Stochastic Gradient Descent Methods (2013, methodology): “Algorithm Complexity/Work Nesterov’s algorithm O ( √ κn log(1/ε)) EMGD O ( (n+ κ2) log(1/ε) ) SAG (n ≥ 8κ) O (n log(1/ε)) SDCA O ((n+ κ) log(1/ε)) SVRG O ((n+ κ) log(1/ε)) S2GD O ((n+ κ) log(1/ε)) 7.”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, methodology): “Stochastic optimization has been extensively studied in the machine learning community [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13].”
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function (2011, background): “While they seem to have never belonged to the mainstream focus of the optimization community, a renewed interest in CD methods was sparked recently by their successful application in several areas—training support vector machines in machine learning [5,3,18,28,29], optimization [9,23,21,31,17,13,25]”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, background): “Application of a coordinate descent method to the dual formulation of (2.1) is generally referred to as Stochastic Dual Coordinate Ascent (SDCA) [78].”
A Parallel SGD method with Strong Convergence (2013, methodology): “such as stochastic gradient descent (SGD) and its variation s [1, 2, 3] and dual coordinate ascent [4] are much faster than batch gradient-based methods for reach ing weights with sufficient training optimality needed for attaining steady state generalizati on performance.”
A Comparison of Optimization Methods and Software for Large-scale L1-regularized Linear Classification (2010, background): “Hsieh et al. (2008) showed that for L2-regularized linear classification, maintaining the gradient for selecting only one variable at a time is not costeffective.”
Faster Coordinate Descent via Adaptive Importance Sampling (2017, methodology): “Indeed, due to their space and computational eﬃciency as well as their ease of implementation, these methods are the state-of-the-art for a wide selection of standard machine learning and signal processing applications [Fu, 1998, Hsieh et al., 2008, Wright, 2015].”
Iteration complexity of feasible descent methods for convex optimization (2014, methodology): “Hsieh et al. (2008) pointed out that ‖Ei‖ = 0 implies the optimal α∗i is C, which can be obtained at the first iteration and is never changed.”
LIBLINEAR: A Library for Large Linear Classification (2008, background): “A theoretical proof of this kind of results is in Theorem 3 of Keerthi and Lin (2003).”
Coordinate descent with arbitrary sampling I: algorithms and complexity† (2014, neutral): “We provide a complexity analysis of ALPHA, from which we deduce as a direct corollary complexity bounds for its many variants, all matching or improving best known bounds.”
Bundle Methods for Regularized Risk Minimization (2010, methodology): “LIBLINEAR solves the dual problem of linear SVM using a coordinate descent method (Hsieh et al., 2008).”
Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection (2015, background): “1 The family of functions h1 includes core machinelearning problems such as least squares, logistic regression, lasso, and SVMs (when solved in dual form) [Hsieh et al., 2008].”
SGD-QN: Careful Quasi-Newton Stochastic Gradient Descent (2009, methodology): “It certainly does not work in the case of traditional SVMs because the hinge loss has zero curvature almost everywhere.”