Generic Error Bounds for the Generalized Lasso with Sub-Exponential Data

Abstract

This work performs a non-asymptotic analysis of the generalized Lasso under the assumption of sub-exponential data. Our main results continue recent research on the benchmark case of (sub-)Gaussian sample distributions and thereby explore what conclusions are still valid when going beyond. While many statistical features remain unaffected (e.g., consistency and error decay rates), the key difference becomes manifested in how the complexity of the hypothesis set is measured. It turns out that the estimation error can be controlled by means of two complexity parameters that arise naturally from a generic-chaining-based proof strategy. The output model can be non-realizable, while the only requirement for the input vector is a generic concentration inequality of Bernstein-type, which can be implemented for a variety of sub-exponential distributions. This abstract approach allows us to reproduce, unify, and extend previously known guarantees for the generalized Lasso. In particular, we present applications to semi-parametric output models and phase retrieval via the lifted Lasso. Moreover, our findings are discussed in the context of sparse recovery and high-dimensional estimation problems.

arXiv commentThe current version of the manuscript has been accepted to the Journal "Sampling Theory, Signal Processing, and Data Analysis"

References in corpus (23)

• Rejoinder to "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• The Convex Geometry of Linear Inverse Problems
• The solution path of the generalized lasso
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• Concentration inequalities for polynomials in $\alpha$-sub-exponential random variables
• Sparse Nonlinear Regression: Parameter Estimation and Asymptotic Inference
• High-Dimensional Estimation of Structured Signals from Non-Linear Observations with General Convex Loss Functions
• Bounds on tail probabilities for quadratic forms in dependent sub-gaussian random variables
• On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models
• Structured Recovery with Heavy-tailed Measurements: A Thresholding Procedure and Optimal Rates
• Recovering Structured Data From Superimposed Non-Linear Measurements
• Lifting high-dimensional nonlinear models with Gaussian regressors
• The Mismatch Principle: The Generalized Lasso Under Large Model Uncertainties
• Restricted Eigenvalue from Stable Rank with Applications to Sparse Linear Regression

Cited by in corpus (4)

• A Unified Approach to Uniform Signal Recovery From Non-Linear Observations
• Sparsified Simultaneous Confidence Intervals for High-Dimensional Linear Models
• A New Perspective on Debiasing Linear Regressions
• The Restricted Isometry of ReLU Networks: Generalization through Norm Concentration