Stochastic Methods for l1-regularized Loss Minimization

By Shai Shalev-Shwartz, Shalev-ShwartzShai, TewariAmbuj, Ambuj Tewari. 2011

146 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

Citations in the corpus

Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “This can be generalized to objectives with (non-)diﬀerentiable regularizers [BKBG11, ST11].”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “For example, for randomized coordinate descent (as part of glmnet ), Lu and Xiao (2013, Theorem 1) gives a O (1 /t ) approximation quality for any separable regularizer, including L 1 and elastic net; see also Tappenden et al. (2015) and Shalev-Shwartz and Tewari (2011).”
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´arik & Tak´aˇc (2012c); Necoara et al. (2012); Tappenden et al. (2013b); Shalev-Shwartz & Zhang (2013b); Lu & Xiao (2013).”
Mini-Batch Primal and Dual Methods for SVMs (2013, background): “…by considering the dual problem (2) as an ℓ1-regularized, box-constrained quadratic problem, it is possible to obtain guarantees on the dual suboptimality, D(α∗) − D(α(t)), after a finite number of SDCA iterations (Shalev-Shwartz & Tewari, 2011; Nesterov, 2012; Richtárik & Takáč, 2013).”
Coordinate descent algorithms (2015, methodology): “A result similar to (27) is proved by Shalev-Schwartz and Tewari [51] for certain types of `1-regularized problems.)”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, methodology): “If φ is (1 /γ ) -smooth with respect to a norm · P , then its dual function φ ∗ is γ -strongly convex with respect to its dual norm · D , where and the dual norm is deﬁned as Throughout this paper, we will denote · as · 2 for simplicity.”
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function (2011, methodology): “While they seem to have never belonged to the mainstream focus of the optimization community, a renewed interest in CD methods wa sparked recently by their successful application in several areas—training support vector machines in machine learning [5], [3], [18], [28], [29], optimization [9], [23],”
Parallel Coordinate Descent for L1-Regularized Loss Minimization (2011, methodology): “2, theory (Shalev-Shwartz & Tewari, 2009) and extensive empirical results (Yuan et al., 2010) have shown that variants of Shooting are particularly competitive for high-dimensional data.”
Accelerated, Parallel, and Proximal Coordinate Descent (2013, methodology): “4 Training linear support vector machines Our last experiment is the dual of Support Vector Machine problem [18].”
Parallel coordinate descent methods for big data optimization (2012, methodology): “Stochastic/randomized CDMs, that is, methods where the coordinate to be updated is chosen randomly, were rst analyzed for quadratic objectives [17, 2], later independently generalized to L1-regularized problems [16] and smooth block-structured problems [7], and nally uni ed and re ned in [12, 13].”
Optimal Algorithms for Online Convex Optimization with Multi-Point Bandit Feedback. (2010, background): “Zinkevich (2003) presents a strategy based on gradient descent that guarantees a regret of O( √ T ) when the set K is compact and the loss functions are Lipschitz continuous.”
On the Convergence of Block Coordinate Descent Type Methods (2013, methodology): “It was shown in [19] that the number of iterations required to obtain an expected ε-accurate solution is O(1/ε).”
Faster Coordinate Descent via Adaptive Importance Sampling (2017, methodology): “Basic coordinate descent methods sample an active coordinate set for optimization uniformly at random, cf. , Stochastic Dual Coordinate As-cent (SDCA) [Shalev-Shwartz and Zhang, 2013] and other variants [Friedman et al., 2007, 2010, Shalev-Shwartz and Tewari, 2011].”
Parallel Coordinate Descent Newton Method for Efficient $\ell_1$-Regularized Minimization (2013, methodology): “1 into an equivalent problem with a twice-diﬀerentiable regularizer following Shalev-Shwartz and Tewari (2009).”
Accelerated Gradient Methods for Stochastic Optimization and Online Learning (2009, background): “Examples include Pegasos [1], SGD-QN [2], FOLOS [3], and stochastic coordinate descent (SCD) [4].”
Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization (2009, background): “, 2009; Bredies and Lorenz, 2008; Beck and Teboulle, 2009) and the online setting (e.g., Langford et al., 2009; Duchi and Singer, 2009; Shalev-Shwartz and Tewari, 2009).”