Sparse multinomial logistic regression: fast algorithms and generalization bounds

TLDR

Sparse classifier learning methods, which use weighted sums of basis functions with sparsity‑promoting priors, are state‑of‑the‑art supervised learning techniques that control model capacity by minimizing the number of basis functions, thereby improving generalization. The paper introduces a true multiclass multinomial logistic regression formulation, fast exact algorithms via bound‑optimization and component‑wise updates, and nontrivial generalization bounds for sparse classifiers. We formulate sparse multiclass classification as multinomial logistic regression and use bound‑optimization with component‑wise updates to obtain fast exact algorithms that scale with sample size and dimensionality, and we derive generalization bounds for the binary case. These first exact multinomial logistic regression algorithms with sparsity priors achieve high accuracy, sparsity, and efficiency on standard benchmark data sets.

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.