Stochastic methods for l1 regularized loss minimization

By Shai Shalev-Shwartz, Ambuj Tewari. 2009

396 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Statistics and Probability, Optimization & Training

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 Statistics and Probability

In Optimization & Training

Citations in the corpus

Data Encoding for Byzantine-Resilient Distributed Optimization (2019, background): “This can be generalized to objectives with (non-)differentiable regularizers [16], [39].”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, methodology): “Mini-batch CD (for lasso) and SDCA (for SVM) aim to improve mini-batch SGD by employing coordinate descent, which has theoretical and practical justifications (Shalev-Shwartz and Tewari, 2011; Takáč et al., 2015; Fercoq and Richtárik, 2015; Tappenden et al., 2015; Takáč et al., 2013).”
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); Richtárik & Takáč (2012c); Necoara et al. (2012); Tappenden et al. (2013b); Shalev-Shwartz & Zhang (2013b); Lu & Xiao (2013).”
Stochastic dual coordinate ascent methods for regularized loss (2012, neutral): “sis shows a convergence rate of O(n2 log(1= D)) in order to achieve D-sub-optimality on the dual while our analysis shows a convergence of O((n+ 1=)log(1=)) to achieve duality gap. In addition, [12], and later [9] have analyzed randomized versions of coordinate descent for unconstrained and constra”
Coordinate descent algorithms (2015, background): “A result similar to (27) is proved by Shalev-Schwartz and Tewari [50] for certain types of 1-regularized problems.”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, background): “Examples include Tikhonov and elastic net regularization, Lasso, sparse logistic regression, and support vector machines [1]–[5].”
Optimization with Sparsity-Inducing Penalties (2011, methodology): “these methods suggest that they behave in a similar way to proximal methods [104, 125].”
Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function (2011, methodology): “Table 3 Comparison ofCDapproaches forminimizing composite functions (forwhich iteration complexity results are provided) Algorithm Lipschitz constant(s) Ψ Block Choice of coordinate Work per 1 iteration Yun and Tseng [22] L(∇ f ) Separable Yes Greedy Expensive Saha and Tewari [17] L(∇ f ) ‖ · ‖1 No ”
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): “For this problem, one can recover the primal solution [22] and thus we can compare the decrease in the duality gap; summarized”
Online Learning: A Comprehensive Survey (2018, methodology): “the number of non-zero elements in classier. Because of these similarities, they share some common strategies such as truncation and projection. 3.5.6 Others Two stochastic methods were proposed in (Shalev-Shwartz and Tewari, 2011) for ‘ 1-regularized loss minimization. The Stochastic Coordinate Des”
Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization (2013, background): “For such objectives, online techniques based on stochastic approximations have proven to be particularly efficient, and have drawn a lot of attraction in machine learning, statistics, and optimization [3–6, 9–12,14, 16, 17, 19, 22, 24–26,30].”
L1-Regularized Distributed Optimization: A Communication-Efficient Primal-Dual Framework (2015, background): “Mini-batch CD Mini-batch CD aims to improve mini-batch SGD by employing coordinate descent, which has encouraging theoretical and practical backings [25, 9, 28].”
Approximate Steepest Coordinate Descent (2017, methodology): “For instance in (Shalev-Shwartz & Zhang, 2013; Friedman et al., 2007; 2010; Shalev-Shwartz & Tewari, 2011) uniform sampling (UCD) is used, whereas other papers propose adaptive sampling strategies that change over time (Papa et al., 2015; Csiba et al., 2015; Osokin et al., 2016; Perekrestenko et…”