A framework to characterize performance of LASSO algorithms
read the original abstract
In this paper we consider solving \emph{noisy} under-determined systems of linear equations with sparse solutions. A noiseless equivalent attracted enormous attention in recent years, above all, due to work of \cite{CRT,CanRomTao06,DonohoPol} where it was shown in a statistical and large dimensional context that a sparse unknown vector (of sparsity proportional to the length of the vector) can be recovered from an under-determined system via a simple polynomial $\ell_1$-optimization algorithm. \cite{CanRomTao06} further established that even when the equations are \emph{noisy}, one can, through an SOCP noisy equivalent of $\ell_1$, obtain an approximate solution that is (in an $\ell_2$-norm sense) no further than a constant times the noise from the sparse unknown vector. In our recent works \cite{StojnicCSetam09,StojnicUpper10}, we created a powerful mechanism that helped us characterize exactly the performance of $\ell_1$ optimization in the noiseless case (as shown in \cite{StojnicEquiv10} and as it must be if the axioms of mathematics are well set, the results of \cite{StojnicCSetam09,StojnicUpper10} are in an absolute agreement with the corresponding exact ones from \cite{DonohoPol}). In this paper we design a mechanism, as powerful as those from \cite{StojnicCSetam09,StojnicUpper10}, that can handle the analysis of a LASSO type of algorithm (and many others) that can be (or typically are) used for "solving" noisy under-determined systems. Using the mechanism we then, in a statistical context, compute the exact worst-case $\ell_2$ norm distance between the unknown sparse vector and the approximate one obtained through such a LASSO. The obtained results match the corresponding exact ones obtained in \cite{BayMon10,DonMalMon10}. Moreover, as a by-product of our analysis framework we recognize existence of an SOCP type of algorithm that achieves the same performance.
This paper has not been read by Pith yet.
Forward citations
Cited by 5 Pith papers
-
When Stronger Triggers Backfire: A High-Dimensional Theory of Backdoor Attacks
In the proportional high-dimensional regime, stronger backdoor training triggers improve clean accuracy and make attack success non-monotonic for regularized GLMs on Gaussian mixtures, with closed-form proofs for squa...
-
High-Dimensional Private Linear Regression with Optimal Rates
DP-GD achieves minimax optimal non-asymptotic risk O(γ + γ²/ρ²) for well-conditioned high-dimensional data and power-law scaling for ill-conditioned power-law spectra, with the exponent depending on the privacy parameter ρ.
-
Characterization of Gaussian Universality Breakdown in High-Dimensional Empirical Risk Minimization
In high-dimensional convex ERM with non-Gaussian data, the projection of the estimator onto a test covariate asymptotically follows the convolution of a generally non-Gaussian term with an independent centered Gaussia...
-
Few-shot Multi-Task Learning of Linear Invariant Features with Meta Subspace Pursuit
Meta Subspace Pursuit learns the invariant low-rank subspace in multi-task linear models with provable algorithmic and statistical guarantees and outperforms baselines like ANIL in experiments.
-
High-Dimensional Statistics: Reflections on Progress and Open Problems
A survey synthesizing representative advances, common themes, and open problems in high-dimensional statistics while pointing to key entry-point works.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.