The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Stochastic methods for l 1 regularized loss minimization
Abstract
We describe and analyze two stochastic methods for l1 regularized loss minimization problems, such as the Lasso. The first method updates the weight of a single feature at each iteration while the second method updates the entire weight vector but only uses a single training example at each iteration. In both methods, the choice of feature/example is uniformly at random. Our theoretical runtime analysis suggests that the stochastic methods should outperform state-of-the-art deterministic approaches, including their deterministic counterparts, when the size of the problem is large. We demonstrate the advantage of stochastic methods by experimenting with synthetic and natural data sets.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482
An Introduction to Support Vector Machines and Other Kernel-based Learning Methods
Cristianini, N., & Shawe-Taylor, J. (2000) · doi:10.1017/cbo9780511801389 · Cited by 13,855
Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004) · The Annals of Statistics · doi:10.1214/009053604000000067 · Cited by 9,357
An Introduction to Support Vector Machines
Cristianini, N., & Shawe-Taylor, J. S. (2000) · ePrints Soton (University of Southampton) · Cited by 4,115
An algorithm for quadratic programming
Frank, M., & Wolfe, P. (1956) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800030109 · Cited by 3,030
Pegasos: primal estimated sub-gradient solver for SVM
Shalev-Shwartz, S., Singer, Y., Srebro, N., & Cotter, A. (2011) · Mathematical Programming · doi:10.1007/s10107-010-0420-4 · Cited by 1,477
Self-citationProblem complexity and method efficiency in optimization
(1984) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(84)90101-0 · Cited by 1,329
Predicting the clinical status of human breast cancer by using gene expression profiles
West, M., Blanchette, C., Dressman, H., Huang, E., Ishida, S., Spang, R., Zuzan, H., Olson, J. A., Marks, J. R., & Nevins, J. R. (2001) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.201162998 · Cited by 1,318
Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
Nesterov, Y. (2012) · SIAM Journal on Optimization · doi:10.1137/100802001 · Cited by 1,187
Efficient projections onto the l1-ball for learning in high dimensions
Duchi, J., Shalev-Shwartz, S., Singer, Y., & Chandra, T. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390191 · Cited by 1,184
Self-citationThe Tradeoffs of Large-Scale Learning
Bottou, L., & Bousquet, O. (2011) · Optimization for Machine Learning · doi:10.7551/mitpress/8996.003.0015 · Cited by 1,128
Mirror descent and nonlinear projected subgradient methods for convex optimization
Beck, A., & Teboulle, M. (2003) · Operations Research Letters · doi:10.1016/s0167-6377(02)00231-6 · Cited by 1,060
Pegasos: Primal Estimated sub-GrAdient SOlver for SVM
Shalev-Shwartz, S., Singer, Y., & Srebro, N. (2007) · Proceedings of the 24th international conference on Machine learning · doi:10.1145/1273496.1273598 · Cited by 973
Self-citationExponentiated Gradient versus Gradient Descent for Linear Predictors
Kivinen, J., & Warmuth, M. K. (1997) · Information and Computation · doi:10.1006/inco.1996.2612 · Cited by 864
Large-Scale Bayesian Logistic Regression for Text Categorization
Genkin, A., Lewis, D. D., & Madigan, D. (2007) · Technometrics · doi:10.1198/004017007000000245 · Cited by 808
Coordinate descent algorithms for lasso penalized regressionPreprint
Wu, T. T., & Lange, K. L. (2008) · Cited by 735
Dual Averaging Method for Regularized Stochastic Learning and Online Optimization
Xiao, L. (2009) · Cited by 574
Coordinate descent algorithms for lasso penalized regression
Wu, T. T., & Lange, K. (2008) · The Annals of Applied Statistics · doi:10.1214/07-aoas147 · Cited by 563
An Interior-Point Method for Large-Scale '1-Regularized Logistic Regression
Koh, K., Kim, S.-J., & Boyd, S. (2007) · Cited by 549
On the convergence of the coordinate descent method for convex differentiable minimization
Luo, Z. Q., & Tseng, P. (1992) · Journal of Optimization Theory and Applications · doi:10.1007/bf00939948 · Cited by 502
Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm
Littlestone, N. (1988) · Machine Learning · doi:10.1007/bf00116827 · Cited by 497
An optimal method for stochastic composite optimization
Lan, G. (2012) · Mathematical Programming · doi:10.1007/s10107-010-0434-y · Cited by 427 · cited 5×
“Finally, we would like to point out that while the stochastic coordinate descent method is parameter free, the success of SMIDAS and of the method of Langford et al. (2009), depends on a careful tuning of a learning rate parameter.”
InfluentialOnline Learning: Theory, Algorithms, and Applications
Shalev‐Shwartz, S. (2007) · Cited by 418
Self-citationText Categorization Based on Regularized Linear Classification Methods
Zhang, T., & Oles, F. J. (2001) · Information Retrieval · doi:10.1023/a:1011441423217 · Cited by 379
Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
Clarkson, K. L. (2010) · ACM Transactions on Algorithms · doi:10.1145/1824777.1824783 · Cited by 379
SVM optimization: inverse dependence on training set size
Shalev-Shwartz, S., & Srebro, N. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390273 · Cited by 240
Self-citationAn Interior-Point Method for Large-Scale l1-Regularized Logistic Regression
KohKwangmoo, KimSeung-Jean, & BoydStephen (2007) · Journal of Machine Learning Research · doi:10.5555/1314498.1314550 · Cited by 231
Composite objective mirror descent
Duchi, J. C., Shalev‐Shwartz, S., Singer, Y., & Tewari, A. (2010) · Cited by 221
Self-citationSparse Online Learning via Truncated Gradient
Langford, J. C., Li, L., & Zhang, T. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0806.4686 · Cited by 184
Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints
Shalev‐Shwartz, S., Srebro, N., & Zhang, T. (2010) · SIAM Journal on Optimization · doi:10.1137/090759574 · Cited by 152
Self-citationOn‐line learning for very large data sets
Bottou, L., & LeCun, Y. (2005) · Applied Stochastic Models in Business and Industry · doi:10.1002/asmb.538 · Cited by 149
The Robustness of the p-Norm Algorithms
Gentile, C. (2003) · Machine Learning · doi:10.1023/a:1026319107706 · Cited by 145
Block-Coordinate Gradient Descent Method for Linearly Constrained Nonsmooth Separable Optimization
Tseng, P., & Yun, S. (2008) · Journal of Optimization Theory and Applications · doi:10.1007/s10957-008-9458-3 · Cited by 144
Sequential greedy approximation for certain convex optimization problems
Zhang, T. (2003) · IEEE Transactions on Information Theory · doi:10.1109/tit.2002.808136 · Cited by 136
General Convergence Results for Linear Discriminant Updates
Grove, A. J., Littlestone, N., & Schuurmans, D. (2001) · Machine Learning · doi:10.1023/a:1010844028087 · Cited by 118
An Interior-Point Method for Large-Scale '1-Regularized Logistic Regression
Koh, K., Kim, S.-J., & Boyd, S. (2007) · Cited by 115
Cited by
Wright, S. J. (2015) · Mathematical Programming · doi:10.1007/s10107-015-0892-3 · Cited by 1,438
Optimization with Sparsity-Inducing Penalties
Bach, F., Jenatton, R., Mairal, J., & Obozinski, G. (2025) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000015 · Cited by 730
Richtárik, P., & Takáč, M. (2014) · Mathematical Programming · doi:10.1007/s10107-012-0614-z · Cited by 654
Optimization with Sparsity-Inducing Penalties
Bach, F. (2011) · now publishers, Inc. eBooks · doi:10.1561/9781601985118 · Cited by 608
On the Convergence of Block Coordinate Descent Type Methods
Beck, A., & Tetruashvili, L. (2013) · SIAM Journal on Optimization · doi:10.1137/120887679 · Cited by 572
Metadata
- Authors
- Shalev-Shwartz, S., & Tewari, A.
- Venue
- Proceedings of the 26th Annual International Conference on Machine Learning
- Publisher
- ACM
- Published
- 2009-06-14
- Pages
- 929-936
- OpenAlex
- W1969048569
- Cited by
- 298
- References
- 36
- FWCI
- 10.11
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.