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

摘要

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 strong adversaries, (2) handling adversarial corruption in both features and labels, and (3) performing feature selection in high dimensions. Our approach tackles all three issues simultaneously. We propose a trimmed maximum likelihood estimator with ℓ_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 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.