# Estimation with Norm Regularization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 May 2015.

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

- [Restricted Strong Convexity of Deep Learning Models with Smooth Activations](https://mlsanity.com/paper/2209.15106/) (2022)
- [Matrix Completion with Model-free Weighting](https://mlsanity.com/paper/2106.05850/) (2021)
- [System Identification via Nuclear Norm Regularization](https://mlsanity.com/paper/2203.16673/) (2022)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [Smart predict-then-robustly-optimize](https://mlsanity.com/paper/2607.21773/) (2026)
- [Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails](https://mlsanity.com/paper/2609.03504/) (2026)

## Abstract (arXiv)

Analysis of non-asymptotic estimation error and structured statistical recovery based on norm regularized regression, such as Lasso, needs to consider four aspects: the norm, the loss function, the design matrix, and the noise model. This paper presents generalizations of such estimation error analysis on all four aspects compared to the existing literature. We characterize the restricted error set where the estimation error vector lies, establish relations between error sets for the constrained and regularized problems, and present an estimation error bound applicable to any norm. Precise characterizations of the bound is presented for isotropic as well as anisotropic subGaussian design matrices, subGaussian noise models, and convex loss functions, including least squares and generalized linear models. Generic chaining and associated results play an important role in the analysis. A key result from the analysis is that the sample complexity of all such estimators depends on the Gaussian width of a spherical cap corresponding to the restricted error set. Further, once the number of samples n crosses the required sample complexity, the estimation error decreases as fracc√n, where c depends on the Gaussian width of the unit norm ball.