Estimation with Norm Regularization

Abstract

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 $\frac{c}{\sqrt{n}}$, where $c$ depends on the Gaussian width of the unit norm ball.

Fixed technical issues. Generalized some results

Cited by in corpus (16)

• Robust Wasserstein Profile Inference and Applications to Machine Learning
• Estimating Structured Vector Autoregressive Model
• Generalized Dantzig Selector: Application to the k-support norm
• Broadcasted Nonparametric Tensor Regression
• Structured signal recovery from non-linear and heavy-tailed measurements
• Non-parametric Quantile Regression via the K-NN Fused Lasso
• Generalized Direct Change Estimation in Ising Model Structure
• Unified View of Matrix Completion under General Structural Constraints
• CP Degeneracy in Tensor Regression
• Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis
• Regularization-Induced Bias and Consistency in Recursive Least Squares
• Structured Matrix Recovery via the Generalized Dantzig Selector
• Alternating Estimation for Structured High-Dimensional Multi-Response Models
• A proximal dual semismooth Newton method for computing zero-norm penalized QR estimator
• II. High Dimensional Estimation under Weak Moment Assumptions: Structured Recovery and Matrix Estimation
• Learning Sparse Structural Changes in High-dimensional Markov Networks: A Review on Methodologies and Theories