The DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Efficient projections onto the l1-ball for learning in high dimensions
Abstract
We describe efficient algorithms for projecting a vector onto the ℓ1-ball. We present two methods for projection. The first performs exact projection in O(n) expected time, where n is the dimension of the space. The second works on vectors k of whose elements are perturbed outside the ℓ1-ball, projecting in O(k log(n)) time. This setting is especially useful for online learning in sparse feature spaces such as text categorization applications. We demonstrate the merits and effectiveness of our algorithms in numerous batch and online learning tasks. We show that variants of stochastic gradient projection methods augmented with our efficient projection procedures outperform interior point methods, which are considered state-of-the-art optimization techniques. We also show that in online settings gradient updates with ℓ1 projections outperform the exponentiated gradient algorithm while obtaining models with high degrees of sparsity. 1.
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
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
Donoho, D. L. (2004) · Cited by 16,703
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
RCV1: A New Benchmark Collection for Text Categorization Research
Lewis, D., Yang, Y., Rose, T. G., & Li, F. (2004) · Goldsmiths (University of London) · doi:10.5555/1005332.1005345 · Cited by 2,503
Donoho, D. L. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20132 · Cited by 2,490
An Interior-Point Method for Large-Scale -Regularized Least Squares
Kim, S.-J., Koh, K., Lustig, M., Boyd, S., & Gorinevsky, D. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910971 · Cited by 2,083
Data Structures and Network Algorithms
Tarjan, R. E. (1983) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970265 · Cited by 2,057
Training linear SVMs in linear time
Joachims, T. (2006) · Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1150402.1150429 · Cited by 1,920
Pathwise coordinate optimization
Friedman, J., Hastie, T., Höfling, H., & Tibshirani, R. (2007) · The Annals of Applied Statistics · doi:10.1214/07-aoas131 · Cited by 1,895
Parlar, M. (2000) · Interactive Operations Research with Maple · doi:10.1007/978-1-4612-1356-7_5 · Cited by 1,741
(2003) · Cited by 1,733
Feature selection, L 1 vs. L 2 regularization, and rotational invariance
Ng, A. Y. (2004) · Twenty-first international conference on Machine learning - ICML '04 · doi:10.1145/1015330.1015435 · Cited by 1,572
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-citationMirror 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
On the Learnability and Design of Output Codes for Multiclass Problems
Crammer, K., & Singer, Y. (2002) · Machine Learning · doi:10.1023/a:1013637720281 · Cited by 650
Self-citationAn Interior-Point Method for Large-Scale '1-Regularized Logistic Regression
Koh, K., Kim, S.-J., & Boyd, S. (2007) · Cited by 579
Two-Metric Projection Methods for Constrained Optimization
Gafni, E. M., & Bertsekas, D. P. (1984) · SIAM Journal on Control and Optimization · doi:10.1137/0322061 · Cited by 234
On the Learnability and Design of Output Codes for Multiclass Problems
Boros, E. (2002) · Machine Learning · Cited by 125
An Interior-Point Method for Large-Scale '1-Regularized Logistic Regression
Koh, K., Kim, S.-J., & Boyd, S. (2007) · Cited by 115
Efficient Learning of Label Ranking by Soft Projections onto Polyhedra
Shalev‐Shwartz, S., & Singer, Y. (2006) · Cited by 80
Self-citationA new family of online algorithms for category ranking
Crammer, K., & Singer, Y. (2002) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/564400.564404 · Cited by 38
Self-citation
Cited by
(2010) · Cited by 8,261
Parikh, N., & Boyd, S. (2014) · Foundations and Trends® in Optimization · doi:10.1561/2400000003 · Cited by 4,102
Online Learning for Matrix Factorization and Sparse Coding
Mairal, J., Bach, F., Ponce, J., & Sapiro, G. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0908.0050 · Cited by 2,258
Sparse Reconstruction by Separable Approximation
Wright, S. J., Nowak, R. D., & Figueiredo, M. A. T. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2016892 · Cited by 1,854
Tensor Decomposition for Signal Processing and Machine Learning
Sidiropoulos, N. D., De Lathauwer, L., Fu, X., Huang, K., Papalexakis, E. E., & Faloutsos, C. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2690524 · Cited by 1,617
Metadata
- Authors
- Duchi, J., Shalev-Shwartz, S., Singer, Y., & Chandra, T.
- Venue
- Proceedings of the 25th international conference on Machine learning - ICML '08
- Publisher
- ACM Press
- Published
- 2008
- Pages
- 272-279
- OpenAlex
- W1978259121
- Cited by
- 1,184
- References
- 24
- FWCI
- 26.80
- 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.