# The Squared-Error of Generalized LASSO: A Precise Analysis

arXiv: https://arxiv.org/abs/1311.0830 · HTML: https://mlsanity.com/paper/1311.0830/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Nov 2013.

## Built on by (most cited first, 15 of 15)

- [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021)
- [Label-Imbalanced and Group-Sensitive Classification under Overparameterization](https://mlsanity.com/paper/2103.01550/) (2021)
- [Local convexity of the TAP free energy and AMP convergence for Z2-synchronization](https://mlsanity.com/paper/2106.11428/) (2021)
- [Homophily modulates double descent generalization in graph convolution networks](https://mlsanity.com/paper/2212.13069/) (2022)
- [High-dimensional learning of narrow neural networks](https://mlsanity.com/paper/2409.13904/) (2024)
- [Optimal Regularization for a Data Source](https://mlsanity.com/paper/2212.13597/) (2022)
- [Certified Data Removal Under High-dimensional Settings](https://mlsanity.com/paper/2505.07640/) (2025)
- [Beyond Independent Measurements: General Compressed Sensing with GNN Application](https://mlsanity.com/paper/2111.00327/) (2021)
- [Exclusive Group Lasso for Structured Variable Selection](https://mlsanity.com/paper/2108.10284/) (2021)
- [Decentralized Statistical Inference with Unrolled Graph Neural Networks](https://mlsanity.com/paper/2104.01555/) (2021)
- [Flat Minima in Linear Estimation and an Extended Gauss Markov Theorem](https://mlsanity.com/paper/2311.11093/) (2023)
- [Optimal Implicit Bias in Linear Regression](https://mlsanity.com/paper/2506.17187/) (2025)
- [Phase Transitions in Recovery of Structured Signals from Corrupted Measurements](https://mlsanity.com/paper/2101.00599/) (2021)
- [Low Complexity Regularized Phase Retrieval](https://mlsanity.com/paper/2407.16413/) (2024)
- [Risk reversal for least squares estimators under nested convex constraints](https://mlsanity.com/paper/2601.16041/) (2026)

## Abstract (arXiv)

We consider the problem of estimating an unknown signal x0 from noisy linear observations y = Ax0 + z∈ Rm. In many practical instances, x0 has a certain structure that can be captured by a structure inducing convex function f(·). For example, ℓ1 norm can be used to encourage a sparse solution. To estimate x0 with the aid of f(·), we consider the well-known LASSO method and provide sharp characterization of its performance. We assume the entries of the measurement matrix A and the noise vector z have zero-mean normal distributions with variances 1 and σ2 respectively. For the LASSO estimator x^*, we attempt to calculate the Normalized Square Error (NSE) defined as frac|x^*-x0|22σ2 as a function of the noise level σ, the number of observations m and the structure of the signal. We show that, the structure of the signal x0 and choice of the function f(·) enter the error formulae through the summary parameters D(cone) and D(λ), which are defined as the Gaussian squared-distances to the subdifferential cone and to the λ-scaled subdifferential, respectively. The first LASSO estimator assumes a-priori knowledge of f(x0) and is given by argminx|y-Ax|2~subject to~f(x)≤ f(x0). We prove that its worst case NSE is achieved when σrightarrow 0 and concentrates around fracD(cone)m-D(cone). Secondly, we consider argminx|y-Ax|2+λ f(x), for some λ≥ 0. This time the NSE formula depends on the choice of λ and is given by fracD(λ)m-D(λ). We then establish a mapping between this and the third estimator argminxfrac12|y-Ax|22+ λ f(x). Finally, for a number of important structured signal classes, we translate our abstract formulae to closed-form upper bounds on the NSE.