Sparse Multinomial Logistic Regression via Approximate Message Passing.

Evan Byrne, Philip Schniter

Introduction

Modern data analysis in fields such as genomics and text mining often encounters the "curse of dimensionality," where the number of features ($N$) vastly exceeds the number of available training samples ($M$). In these high-dimensional settings, standard Multinomial Logistic Regression (MLR) models are prone to overfitting unless sparsity is strictly enforced. The paper "Sparse Multinomial Logistic Regression via Approximate Message Passing" introduces a high-performance framework designed to tackle these challenges by leveraging Approximate Message Passing (AMP) techniques.

The Challenge: High-Dimensionality and Sparsity

In multi-class classification, MLR is the standard tool. However, when $N \gg M$, researchers must assume that only a small subset of features is truly relevant. While existing solvers like GLMNET or SBMLR utilize $\ell_1$ regularization (Lasso) to promote sparsity, they often rely on computationally expensive cross-validation to tune hyperparameters. Furthermore, as the number of classes ($D$) grows, the computational burden of these solvers scales poorly. The authors address this by adapting the Hybrid Generalized Approximate Message Passing (HyGAMP) framework to the MLR problem.

The HyGAMP Framework

The core contribution of the paper is the application of HyGAMP to handle "non-separable" likelihood functions, such as the softmax function used in MLR. Unlike binary logistic regression where likelihoods are separable, multi-class problems involve competing classes that couple variables together. HyGAMP is uniquely capable of decoupling these interactions.

The authors propose two primary variants:

  1. SPA-HyGAMP (Sum-Product): Optimized to minimize the test error rate.
  2. MSA-HyGAMP (Min-Sum): Designed for Maximum A Posteriori (MAP) estimation.

Technical Innovations: SHyGAMP and Gaussian Mixtures

To make the framework practical for massive datasets, the authors introduced SHyGAMP (Simplified HyGAMP). Standard HyGAMP requires inverting $D \times D$ matrices for every feature and sample, which is computationally prohibitive. SHyGAMP streamlines this by employing diagonal covariance matrices and scalar variance approximations.

A significant technical breakthrough is the use of a Gaussian Mixture (GM) model to approximate the complex softmax integral. The authors demonstrated that the logistic function can be closely approximated by a mixture of just two Gaussians, turning a difficult integral into a fast, closed-form calculation.

Runtime comparison of different approximation methods as the number of classes $D$ increases.

As illustrated in Figure 2, the GM approach provides order-of-magnitude speedups over numerical integration and importance sampling as the number of classes increases. Importantly, this efficiency does not sacrifice accuracy. Figure 3 shows that the GM approximation maintains a Mean Squared Error (MSE) nearly identical to exact numerical methods, while other approximations, such as Taylor series expansions, can diverge significantly as variance increases.

MSE performance of approximation methods across varying noise levels.

Automated Tuning and Scalability

Beyond speed, SHyGAMP eliminates the need for manual hyperparameter tuning. It utilizes Expectation-Maximization (EM) for the SPA version and a novel approach based on Stein’s Unbiased Risk Estimate (SURE) for the MSA version. This allows the algorithm to automatically adjust its "sparsity knob" during the iteration process, matching the performance of exhaustive grid searches without the associated time penalty.

Empirical results on datasets like RCV1 (text classification) and MNIST (handwritten digits) confirm these advantages. On the RCV1 dataset, SHyGAMP converged more than ten times faster than SBMLR and GLMNET. Furthermore, while competitors showed quadratic runtime growth relative to the number of samples, SHyGAMP’s runtime increased linearly, making it highly suitable for "Big Data" applications.

Conclusion

By combining the decoupling power of AMP with efficient Gaussian Mixture approximations and automated SURE-tuning, the authors have provided a robust framework for sparse multinomial logistic regression. While the algorithm performs best on i.i.d. Gaussian feature matrices, its success on real-world benchmarks suggests it is a powerful alternative to traditional solvers in high-dimensional, multi-class settings. Future work may extend this framework to handle structured sparsity and non-Gaussian feature distributions more robustly.

Summary updated

Abstract

For the problem of multi-class linear classification and feature selection, we propose approximate message passing approaches to sparse multinomial logistic regression (MLR). First, we propose two algorithms based on the Hybrid Generalized Approximate Message Passing (HyGAMP) framework: one finds the maximum a posteriori (MAP) linear classifier and the other finds an approximation of the test-error-rate minimizing linear classifier. Then we design computationally simplified variants of these two algorithms. Next, we detail methods to tune the hyperparameters of their assumed statistical models using Stein's unbiased risk estimate (SURE) and expectation-maximization (EM), respectively. Finally, using both synthetic and real-world datasets, we demonstrate improved error-rate and runtime performance relative to existing state-of-the-art approaches to sparse MLR.
BibTeX
@article{byrne2016sparse,
  author = {Evan Byrne and Philip Schniter},
  title = {{Sparse Multinomial Logistic Regression via Approximate Message Passing.}},
  journal = {IEEE Trans. Signal Process.},
  year = {2016},
  url = {https://openreview.net/forum?id=vNiypqoqOzDR},
}
Figure