Provable Guarantees For Robust Feature Selection in Sparse Linear Models in High-Dimensions

Deepak Maurya, Adarsh Barik, Jean Honorio
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:4381-4426, 2026.

Abstract

We study feature selection (support recovery) in sparse linear models, including linear and logistic regression, under a strong adversarial contamination model where an adversary can arbitrarily corrupt a constant fraction of samples in the high-dimensional regime. Most of the existing methods target one or two aspects of this interesting problem: (1) achieving robustness against \emph{strong} adversaries, (2) handling adversarial corruption in \emph{both} features and labels, and (3) performing feature selection in \emph{high dimensions}. Our approach tackles all three issues simultaneously. We propose a trimmed maximum likelihood estimator with $\ell_1$-regularization, leading to a non-convex relaxation of an NP-hard combinatorial optimization problem. We prove that any locally optimal solution to this non-convex problem achieves \emph{near-minimax} optimal statistical rates, up to logarithmic factors. Critically, our method recovers the true support in a computationally efficient manner despite the intractability of the exact formulation. The resulting sample complexity scales only logarithmically with the ambient dimension, making it well-suited for high-dimensional settings. Furthermore, our framework accommodates heavy-tailed noise distributions under mild moment assumptions, requiring only that the fourth moment be bounded. We also validate our theoretical findings empirically.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-maurya26a, title = {Provable Guarantees For Robust Feature Selection in Sparse Linear Models in High-Dimensions}, author = {Maurya, Deepak and Barik, Adarsh and Honorio, Jean}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {4381--4426}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/maurya26a/maurya26a.pdf}, url = {https://proceedings.mlr.press/v337/maurya26a.html}, abstract = {We study feature selection (support recovery) in sparse linear models, including linear and logistic regression, under a strong adversarial contamination model where an adversary can arbitrarily corrupt a constant fraction of samples in the high-dimensional regime. Most of the existing methods target one or two aspects of this interesting problem: (1) achieving robustness against \emph{strong} adversaries, (2) handling adversarial corruption in \emph{both} features and labels, and (3) performing feature selection in \emph{high dimensions}. Our approach tackles all three issues simultaneously. We propose a trimmed maximum likelihood estimator with $\ell_1$-regularization, leading to a non-convex relaxation of an NP-hard combinatorial optimization problem. We prove that any locally optimal solution to this non-convex problem achieves \emph{near-minimax} optimal statistical rates, up to logarithmic factors. Critically, our method recovers the true support in a computationally efficient manner despite the intractability of the exact formulation. The resulting sample complexity scales only logarithmically with the ambient dimension, making it well-suited for high-dimensional settings. Furthermore, our framework accommodates heavy-tailed noise distributions under mild moment assumptions, requiring only that the fourth moment be bounded. We also validate our theoretical findings empirically.} }
Endnote
%0 Conference Paper %T Provable Guarantees For Robust Feature Selection in Sparse Linear Models in High-Dimensions %A Deepak Maurya %A Adarsh Barik %A Jean Honorio %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-maurya26a %I PMLR %P 4381--4426 %U https://proceedings.mlr.press/v337/maurya26a.html %V 337 %X We study feature selection (support recovery) in sparse linear models, including linear and logistic regression, under a strong adversarial contamination model where an adversary can arbitrarily corrupt a constant fraction of samples in the high-dimensional regime. Most of the existing methods target one or two aspects of this interesting problem: (1) achieving robustness against \emph{strong} adversaries, (2) handling adversarial corruption in \emph{both} features and labels, and (3) performing feature selection in \emph{high dimensions}. Our approach tackles all three issues simultaneously. We propose a trimmed maximum likelihood estimator with $\ell_1$-regularization, leading to a non-convex relaxation of an NP-hard combinatorial optimization problem. We prove that any locally optimal solution to this non-convex problem achieves \emph{near-minimax} optimal statistical rates, up to logarithmic factors. Critically, our method recovers the true support in a computationally efficient manner despite the intractability of the exact formulation. The resulting sample complexity scales only logarithmically with the ambient dimension, making it well-suited for high-dimensional settings. Furthermore, our framework accommodates heavy-tailed noise distributions under mild moment assumptions, requiring only that the fourth moment be bounded. We also validate our theoretical findings empirically.
APA
Maurya, D., Barik, A. & Honorio, J.. (2026). Provable Guarantees For Robust Feature Selection in Sparse Linear Models in High-Dimensions. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:4381-4426 Available from https://proceedings.mlr.press/v337/maurya26a.html.

Related Material