Group Sparse Additive Machine

Hong Chen, Xiaoqian Wang, Cheng Deng, Heng HuangNeurIPS 2017 · OpenReview

Introduction

In high-dimensional data analysis, researchers often face a trade-off between the "black-box" high performance of complex deep learning models and the interpretability of linear models. Additive models offer a compelling middle ground: they represent a function as a sum of component functions (e.g., $f(x) = \sum f_j(x_j)$), inheriting the flexibility of nonlinear models and the interpretability of linear ones.

However, two major gaps have persisted in this domain. First, most existing group-sparse additive models were designed for least-squares regression, leaving a void for robust classification algorithms. Second, standard sparse models (like the Lasso) select individual variables but often ignore the fact that variables in real-world data—such as genes or sensor arrays—frequently act in functional groups.

To address these challenges, researchers have introduced the Group Sparse Additive Machine (GroupSAM), a novel classification framework that combines the flexibility of nonlinear additive models with the power of group-based variable selection.

Methodology

GroupSAM operates in Reproducing Kernel Hilbert Spaces (RKHS) and utilizes structured sparsity to achieve state-of-the-art classification accuracy. It is built on a coefficient-based regularized framework with several key technical innovations:

Comparison of GroupSAM with existing additive and sparse models.
  • Data-Dependent Hypothesis Spaces: Unlike traditional methods that use fixed splines, GroupSAM searches for component functions in kernel-based spaces that adapt to the training data. This provides greater flexibility for nonlinear prediction and requires fewer tuning parameters.
  • Structured Sparsity ($\ell_{2,1}$-norm): The model employs a group-sparse penalty. This "all-or-nothing" approach for groups of variables allows the model to perform variable selection at the group level, effectively filtering out non-informative feature sets.
  • Hinge Loss Integration: To adapt additive models for classification, the authors utilize the hinge loss (the backbone of Support Vector Machines), making the model robust for binary classification tasks.
  • Optimization: The resulting objective function is solved efficiently using an accelerated proximal gradient descent algorithm, which handles the non-smooth nature of the sparsity penalty and the hinge loss.

Key Insights and Theoretical Guarantees

Beyond empirical success, the authors provide a rigorous proof of the generalization error bound. They demonstrate that GroupSAM can achieve a fast convergence rate of $O(n^{-1})$ under mild conditions, which is a significant theoretical milestone for this class of models.

Furthermore, GroupSAM simultaneously learns and selects: it doesn't just classify; it identifies which groups of features are driving the classification. This makes it a powerful tool for feature engineering and scientific discovery.

Experimental Results

The authors evaluated GroupSAM using both controlled synthetic environments and real-world challenges (seven diverse datasets from the UCI Machine Learning Repository, including Ecoli, Breast Cancer, and Balance Scale).

Classification accuracy on synthetic datasets across varying noise levels. GroupSAM consistently outperforms baselines, achieving perfect accuracy in high-dimensional settings.
  • Superior Accuracy on Synthetic Data: GroupSAM consistently outperformed standard SVMs, L1-regularized SVMs, and previous sparse additive models (SAM). In a high-dimensional 300-group test, GroupSAM achieved a perfect 1.000 accuracy, while other methods struggled significantly (some dropping as low as 0.275).
  • Benchmark Performance: On the 7 UCI datasets, GroupSAM achieved the highest average classification accuracy in 6 out of 7 cases, showing particular strength in datasets like Ecoli (0.839 vs. 0.815 for SVM) and Balance Scale (0.893 vs. 0.864 for SVM).
  • Feature Identification: In synthetic tests, GroupSAM correctly identified the exact "ground truth" feature groups used to generate the data, proving its effectiveness as a variable selection tool.

Limitations and Future Work

While the authors established a strong upper bound for the generalization error, providing a matching lower bound to prove the "optimality" of the rate is left for future research. Additionally, the current model uses standard hinge loss; future iterations could incorporate quantile regression or other robust loss functions to handle datasets with significant outliers or heavy-tailed noise. Finally, the current model assumes group structures are known a priori or created via replication. Exploring how to automatically discover optimal group structures during training remains an exciting open direction.

Summary updated

Abstract

A family of learning algorithms generated from additive models have attracted much attention recently for their flexibility and interpretability in high dimensional data analysis. Among them, learning models with grouped variables have shown competitive performance for prediction and variable selection. However, the previous works mainly focus on the least squares regression problem, not the classification task. Thus, it is desired to design the new additive classification model with variable selection capability for many real-world applications which focus on high-dimensional data classification. To address this challenging problem, in this paper, we investigate the classification with group sparse additive models in reproducing kernel Hilbert spaces. A novel classification method, called as \emph{group sparse additive machine} (GroupSAM), is proposed to explore and utilize the structure information among the input variables. Generalization error bound is derived and proved by integrating the sample error analysis with empirical covering numbers and the hypothesis error estimate with the stepping stone technique. Our new bound shows that GroupSAM can achieve a satisfactory learning rate with polynomial decay. Experimental results on synthetic data and seven benchmark datasets consistently show the effectiveness of our new approach.
BibTeX
@inproceedings{chen2017group,
  author = {Hong Chen and Xiaoqian Wang and Cheng Deng and Heng Huang},
  title = {{Group Sparse Additive Machine}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=BkbmSP-O-r},
}
Figure