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

This work performs a non-asymptotic analysis of the general ized Lasso under the assumption of sub-exponential data. Our main results continue recent researc h on the benchmark case of (sub-)Gaussian sample distributions and thereby explore what conclusions are sti ll valid when going beyond. While many statistical features of the generalized Lasso remain unaffected (e.g., consistency), the key difference becomes manifested in the way how the complexity of the hypothesis set is measured. It t urns out that the estimation error can be controlled by means of two complexity parameters that arise naturally fro m 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 g uarantees for the generalized Lasso. In particular, we present applications to semi-parametric output models a nd phase retrieval via the lifted Lasso. Moreover, our findings are discussed in the context of sparse recovery and h igh-dimensional estimation problems.