The DOI matches its Crossref record; 48 of the 48 references it cites were found in a registry or an index.
Sparse multinomial logistic regression: fast algorithms and generalization bounds
Abstract
Recently developed methods for learning sparse classifiers are among the state-of-the-art in supervised learning. These methods learn classifiers that incorporate weighted sums of basis functions with sparsity-promoting priors encouraging the weight estimates to be either significantly large or exactly zero. From a learning-theoretic perspective, these methods control the capacity of the learned classifier by minimizing the number of basis functions used, resulting in better generalization. This paper presents three contributions related to learning sparse classifiers. First, we introduce a true multiclass formulation based on multinomial logistic regression. Second, by combining a bound optimization approach with a component-wise update procedure, we derive fast exact algorithms for learning sparse multiclass classifiers that scale favorably in both the number of training samples and the feature dimensionality, making them applicable even to large data sets in high-dimensional feature spaces. To the best of our knowledge, these are the first algorithms to perform exact multinomial logistic regression with a sparsity-promoting prior. Third, we show how nontrivial generalization bounds can be derived for our classifier in the binary case. Experimental results on standard benchmark data sets attest to the accuracy, sparsity, and efficiency of the proposed methods.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Maximum Likelihood from Incomplete Data Via the EM Algorithm
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01600.x · Cited by 50,444
The Nature of Statistical Learning Theory
Vapnik, V. N. (1995) · doi:10.1007/978-1-4757-2440-0 · Cited by 39,138
Wu, Y. (1999) · Technometrics · doi:10.1080/00401706.1999.10485951 · Cited by 27,221
A Wavelet Tour of Signal Processing
(1999) · Elsevier eBooks · doi:10.1016/b978-0-12-466606-1.x5000-4 · Cited by 16,227
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
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827596304010 · Cited by 6,845
Emergence of simple-cell receptive field properties by learning a sparse code for natural images
Olshausen, B. A., & Field, D. J. (1996) · Nature · doi:10.1038/381607a0 · Cited by 5,694
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (2001) · SIAM Review · doi:10.1137/s003614450037906x · Cited by 5,085
Maximum likelihood estimation from incomplete data via the EM algorithm
Dempster, A. P. (1977) · Journal of the Royal Statistical Society Series A (Statistics in Society) · Cited by 4,543
Bayesian Learning for Neural Networks
Neal, R. M. (1996) · Lecture Notes in Statistics · doi:10.1007/978-1-4612-0745-0 · Cited by 4,276
An Introduction to Support Vector Machines
Cristianini, N., & Shawe-Taylor, J. S. (2000) · ePrints Soton (University of Southampton) · Cited by 4,115
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
Donoho, D. L., & Elad, M. (2003) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0437847100 · Cited by 2,898
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results
Bartlett, P. L., & Mendelson, S. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44581-1_15 · Cited by 1,949
(2000) · CrossRef Listing of Deleted DOIs · doi:10.1162/15324430152748236 · Cited by 1,819
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
Learning Overcomplete Representations
Lewicki, M. S., & Sejnowski, T. J. (2000) · Neural Computation · doi:10.1162/089976600300015826 · Cited by 1,129
Optimization Transfer Using Surrogate Objective Functions
Lange, K., Hunter, D. R., & Yang, I. (2000) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.2000.10474858 · Cited by 808
Fast Marginal Likelihood Maximisation for Sparse Bayesian Models
Tipping, M. E., & Faul, A. (2003) · Cited by 775
Bayesian classification with Gaussian processes
Williams, C. K. I., & Barber, D. (1998) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.735807 · Cited by 766
Sparse On-Line Gaussian Processes
Csató, L., & Opper, M. (2002) · Neural Computation · doi:10.1162/089976602317250933 · Cited by 749
Use of the zero norm with linear models and kernel methods
Weston, J., Elisseeff, A., Schölkopf, B., & Tipping, M. (2003) · MPG.PuRe (Max Planck Society) · doi:10.5555/944919.944982 · Cited by 688
Maximum Likelihood Estimation from Incomplete Data
Hartley, H. O. (1958) · Biometrics · doi:10.2307/2527783 · Cited by 602
Multinomial logistic regression algorithm
B�hning, D. (1992) · Annals of the Institute of Statistical Mathematics · doi:10.1007/bf00048682 · Cited by 547
Learning Kernel Classifiers: Theory and Algorithms
Herbrich, R. (2001) · The MIT Press eBooks · doi:10.7551/mitpress/4170.001.0001 · Cited by 547
Adaptive sparseness for supervised learning
Figueiredo, M. A. T. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1227989 · Cited by 536
Self-citationFast Sparse Gaussian Process Methods: The Informative Vector Machine
Herbrich, R., Lawrence, N. D., & Seeger, M. (2002) · neural information processing systems · Cited by 488
McAllester, D. A. (1998) · Proceedings of the eleventh annual conference on Computational learning theory · doi:10.1145/279943.279989 · Cited by 464
Kernel Logistic Regression and the Import Vector Machine
Zhu, J., & Hastie, T. (2005) · Journal of Computational and Graphical Statistics · doi:10.1198/106186005x25619 · Cited by 425
Text Categorization Based on Regularized Linear Classification Methods
Zhang, T., & Oles, F. J. (2001) · Information Retrieval · doi:10.1023/a:1011441423217 · Cited by 379
Bayesian Regularization and Pruning Using a Laplace Prior
Williams, P. M. (1995) · Neural Computation · doi:10.1162/neco.1995.7.1.117 · Cited by 377
A comparison of numerical optimizers for logistic regression
Minka, T. P. (2004) · Cited by 235
PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification
Seeger, M. (2003) · Journal of Machine Learning Research · doi:10.1162/153244303765208386 · Cited by 229
Monotonicity of quadratic-approximation algorithms
Böhning, D., & Lindsay, B. G. (1988) · Annals of the Institute of Statistical Mathematics · doi:10.1007/bf00049423 · Cited by 170
Fast Sparse Gaussian Process Methods: The Informative Vector Machine
Lawrence, N. D., Seeger, M., & Herbrich, R. (2003) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 165
McAllester, D. A. (1999) · Machine Learning · doi:10.1023/a:1007618624809 · Cited by 162
A Bayesian approach to joint feature selection and classifier design
Krishnapuram, B., Harternink, A. J., Carin, L., & Figueiredo, M. A. T. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.55 · Cited by 159
Self-citationLange, K. L. (2004) · Springer texts in statistics · doi:10.1007/978-1-4757-4182-7 · Cited by 143
Predictive automatic relevance determination by expectation propagation
Qi, Y. (., Minka, T. P., Picard, R. W., & Ghahramani, Z. (2004) · Twenty-first international conference on Machine learning - ICML '04 · doi:10.1145/1015330.1015418 · Cited by 110
Generalization error bounds for Bayesian mixture algorithms
Meir, R., & Zhang, T. (2003) · Cited by 107
Adaptive overrelaxed bound optimization methods
Salakhutdinov, R., & Roweis, S. T. (2003) · Cited by 82
Bayesian learning of sparse classifiers
Figueiredo, M. A. T., & Jain, A. K. (2005) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2001.990453 · Cited by 65
Self-citationFriedman, J. H., Hastie, T. J., Rosset, S., Tibshirani, R. J., & Zhu, J. (2003) · Cited by 46
Graepel, T., Herbrich, R., & Williamson, R. C. (2000) · Cited by 45
Joint classifier and feature optimization for cancer diagnosis using gene expression data
Krishnapuram, B., Carin, L., & Hartemink, A. J. (2003) · doi:10.1145/640075.640097 · Cited by 22
Self-citationMicrochoice Bounds and Self Bounding Learning Algorithms
Langford, J. C., & Blum, A. L. (2003) · Machine Learning · doi:10.1023/a:1022806918936 · Cited by 16
Valiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
Sparse Representation for Computer Vision and Pattern Recognition
Wright, J., Ma, Y., Mairal, J., Sapiro, G., Huang, T. S., & Yan, S. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2010.2044470 · Cited by 1,847
Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning
Sun, Y., Babu, P., & Palomar, D. P. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2601299 · Cited by 1,820
The Group Lasso for Logistic Regression
Meier, L., Van De Geer, S., & Bühlmann, P. (2008) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2007.00627.x · Cited by 1,674
Fisher Kernels on Visual Vocabularies for Image Categorization
Perronnin, F., & Dance, C. (2007) · 2007 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2007.383266 · Cited by 1,641
Text Classification Algorithms: A Survey
Kowsari, K., Jafari Meimandi, K., Heidarysafa, M., Mendu, S., Barnes, L., & Brown, D. (2019) · Information · doi:10.3390/info10040150 · Cited by 1,312
Metadata
- Authors
- Krishnapuram, B., Carin, L., Figueiredo, M. A. T., & Hartemink, A. J.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2005-06
- Volume
- 27
- Issue
- 6
- Pages
- 957-968
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W2150579376
- Cited by
- 877
- References
- 48
- FWCI
- 24.03
- Type
- journal article
- 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.