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

Abstract: In this work, 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.

Link: https://openreview.net/forum?id=0bNcXCLrYA

Bio: Deepak Maurya is a Ph.D. candidate in Computer Science at Purdue University, advised by Prof. Jean Honorio and Prof. Petros Drineas. His current research focuses on designing practical polynomial-time algorithms for robust high-dimensional estimation that achieve dimension-independent statistical guarantees under adversarial data corruption. Prior to his PhD, Deepak completed his M.S. in Computer Science under the guidance of Prof. Balaraman Ravindran from IIT Madras. His MS thesis was focused on hypergraph partitioning and hyperedge prediction using spectral properties of tensors. Prior to M.S., Deepak completed his B.Tech and M.Tech (dual degree) in Electrical Engineering from IIT Madras. His final year M.Tech project was  focused on proposing Dynamic Iterative PCA algorithm for system identification. This project led to five conference and three journal publications and a Best Student Paper Award. Deepak has also co-organized five editions of the Graphs and more Complex Structures For Learning and Reasoning (GCLR) workshop at AAAI conference from 2021-2026.