Robust Estimation of a Sparse Linear Model: Provable Guarantees with Non-convexity

Deepak Maurya, Adarsh Barik, Jean Honorio
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:523-531, 2026.

Abstract

In this paper, we address the problem of sparse regression vector estimation in the presence of corrupted samples, with a particular focus on accurately identifying the support. Traditional methods, such as the Least Absolute Shrinkage and Selection Operator (LASSO), often fail in such scenarios, exhibiting inconsistency. To tackle this challenge, we propose a combinatorial, non-convex, and robust variant of LASSO framework, designed to enhance estimation accuracy under corruption. Our approach is supported by theoretical guarantees, which establish its reliability and robustness. Our method also handles corruption from heavy-tailed distributions, with only a few bounded moments. We validate our theoretical results through extensive experiments, comparing the performance of our method against the LASSO and its other robust variants. These comparisons highlight the efficacy of our framework, demonstrating its practical applicability in sparse regression tasks involving corrupted data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-maurya26a, title = { Robust Estimation of a Sparse Linear Model: Provable Guarantees with Non-convexity }, author = {Maurya, Deepak and Barik, Adarsh and Honorio, Jean}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {523--531}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/maurya26a/maurya26a.pdf}, url = {https://proceedings.mlr.press/v300/maurya26a.html}, abstract = { In this paper, we address the problem of sparse regression vector estimation in the presence of corrupted samples, with a particular focus on accurately identifying the support. Traditional methods, such as the Least Absolute Shrinkage and Selection Operator (LASSO), often fail in such scenarios, exhibiting inconsistency. To tackle this challenge, we propose a combinatorial, non-convex, and robust variant of LASSO framework, designed to enhance estimation accuracy under corruption. Our approach is supported by theoretical guarantees, which establish its reliability and robustness. Our method also handles corruption from heavy-tailed distributions, with only a few bounded moments. We validate our theoretical results through extensive experiments, comparing the performance of our method against the LASSO and its other robust variants. These comparisons highlight the efficacy of our framework, demonstrating its practical applicability in sparse regression tasks involving corrupted data. } }
Endnote
%0 Conference Paper %T Robust Estimation of a Sparse Linear Model: Provable Guarantees with Non-convexity %A Deepak Maurya %A Adarsh Barik %A Jean Honorio %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-maurya26a %I PMLR %P 523--531 %U https://proceedings.mlr.press/v300/maurya26a.html %V 300 %X In this paper, we address the problem of sparse regression vector estimation in the presence of corrupted samples, with a particular focus on accurately identifying the support. Traditional methods, such as the Least Absolute Shrinkage and Selection Operator (LASSO), often fail in such scenarios, exhibiting inconsistency. To tackle this challenge, we propose a combinatorial, non-convex, and robust variant of LASSO framework, designed to enhance estimation accuracy under corruption. Our approach is supported by theoretical guarantees, which establish its reliability and robustness. Our method also handles corruption from heavy-tailed distributions, with only a few bounded moments. We validate our theoretical results through extensive experiments, comparing the performance of our method against the LASSO and its other robust variants. These comparisons highlight the efficacy of our framework, demonstrating its practical applicability in sparse regression tasks involving corrupted data.
APA
Maurya, D., Barik, A. & Honorio, J.. (2026). Robust Estimation of a Sparse Linear Model: Provable Guarantees with Non-convexity . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:523-531 Available from https://proceedings.mlr.press/v300/maurya26a.html.

Related Material