Abstract
This paper introduces Logistic Group Orthogonal Matching Pursuit (Logit-GOMP), a greedy feature selection algorithm designed for high-dimensional logistic regression with grouped variables. By leveraging gradients as pseudo-residuals, Logit-GOMP provides a computationally efficient alternative to $l_1$-regularization methods like the Group Lasso. We provide non-asymptotic theoretical guarantees for prediction accuracy and exact variable recovery. Empirical evaluations on synthetic and real-world bioinformatics datasets demonstrate that Logit-GOMP achieves superior sparsity and higher $F_1$ scores for feature selection compared to state-of-the-art methods.
Introduction
In modern machine learning, datasets often feature a high number of variables relative to the sample size, necessitating sparse modeling to prevent overfitting. Furthermore, variables frequently possess an inherent group structure—such as one-hot encoded categorical features or gene clusters. While the Group Lasso is a standard approach for group sparsity in logistic regression, greedy methods like Orthogonal Matching Pursuit (OMP) have historically been limited to linear regression. Logit-GOMP bridges this gap, extending greedy selection to the classification domain with rigorous theoretical backing.
The Logit-GOMP Algorithm
Logit-GOMP is an iterative forward selection procedure. Unlike linear OMP, which uses standard residuals, Logit-GOMP utilizes the gradient of the logistic loss function as a "pseudo-residual." In each iteration, the algorithm identifies the feature group that maximizes the projection onto this gradient vector. After adding the group to the active set, coefficients are re-estimated via standard logistic regression on the selected features. This approach allows the intuitive geometric selection of OMP to be applied to non-linear classification tasks.
Theoretical Foundations
A key contribution of this work is the derivation of non-asymptotic bounds for empirical risk and the formulation of geometric "exact recovery" conditions. These conditions define the mathematical criteria under which the algorithm is guaranteed to select only the correct feature groups. Because of the logistic link function, these conditions are highly non-linear, mapping out a specific geometric sub-space the residuals must fall into to ensure success.
Experimental Results
The performance of Logit-GOMP was evaluated against several baselines, including Logistic Group Lasso and standard Logistic Lasso, across multiple simulated scenarios and the MEMset Donor bioinformatics dataset.
In simulations involving categorical variables and complex interactions, Logit-GOMP consistently outperformed the Group Lasso in terms of selection accuracy. As shown in the table below, Logit-GOMP achieved significantly higher $F_1$ scores, particularly in identifying relevant variable groups. For instance, in Experiment 1, Logit-GOMP reached an $F_1$ score of 0.896 compared to 0.494 for the Logistic Group Lasso.
On the real-world MEMset DNA dataset, Logit-GOMP matched the predictive performance of the Group Lasso (correlation coefficient of ~0.659) while selecting a much smaller, more interpretable set of feature groups. This parsimony is a significant advantage in domains like bioinformatics where model interpretability is as critical as predictive power.
Conclusion and Future Work
Logit-GOMP offers a powerful and theoretically grounded alternative to $l_1$-regularized methods for grouped feature selection in logistic regression. By producing sparser models with higher selection precision, it addresses the over-selection tendencies often seen in the Group Lasso. Future research will focus on extending these guarantees to stochastic settings and proving performance bounds for other Generalized Linear Models (GLMs) such as Poisson or multinomial regression.
Summary updated