A new perspective on least squares under convex constraint

Abstract

Consider the problem of estimating the mean of a Gaussian random vector when the mean vector is assumed to be in a given convex set. The most natural solution is to take the Euclidean projection of the data vector on to this convex set; in other words, performing "least squares under a convex constraint." Many problems in modern statistics and statistical signal processing theory are special cases of this general situation. Examples include the lasso and other high-dimensional regression techniques, function estimation problems, matrix estimation and completion, shape-restricted regression, constrained denoising, linear inverse problems, etc. This paper presents three general results about this problem, namely, (a) an exact computation of the main term in the estimation error by relating it to expected maxima of Gaussian processes (existing results only give upper bounds), (b) a theorem showing that the least squares estimator is always admissible up to a universal constant in any problem of the above kind and (c) a counterexample showing that least squares estimator may not always be minimax rate-optimal. The result from part (a) is then used to compute the error of the least squares estimator in two examples of contemporary interest.

Published in at http://dx.doi.org/10.1214/14-AOS1254 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (9)

• On the "degrees of freedom" of the lasso
• Lasso-type recovery of sparse representations for high-dimensional data
• High-dimensional generalized linear models and the lasso
• Sparsity oracle inequalities for the Lasso
• On risk bounds in isotonic and other shape restricted regression problems
• The Dantzig selector and sparsity oracle inequalities
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• New Null Space Results and Recovery Thresholds for Matrix Rank Minimization
• The achievable performance of convex demixing

Cited by in corpus (37)

• Unknown sparsity in compressed sensing: Denoising and inference
• High-dimensional estimation with geometric constraints
• Sensitivity of ${\ell }_1$ minimization to parameter choice
• Multivariate convex regression: global risk bounds and adaptation
• Prediction error of cross-validated Lasso
• Minimal penalties and the slope heuristics: a survey
• Geometric Inference for General High-Dimensional Linear Inverse Problems
• On matrix estimation under monotonicity constraints
• Adaptive Risk Bounds in Univariate Total Variation Denoising and Trend Filtering
• Estimation in high dimensions: a geometric perspective
• On the Sensitivity of the Lasso to the Number of Predictor Variables
• Multivariate extensions of isotonic regression and total variation denoising via entire monotonicity and Hardy-Krause variation
• Nonparametric Shape-restricted Regression
• Convex Regression in Multidimensions: Suboptimality of Least Squares Estimators
• Slope heuristics and V-Fold model selection in heteroscedastic regression using strongly localized bases
• Bayesian fractional posteriors
• Robustness of shape-restricted regression estimators: an envelope perspective
• Optimistic lower bounds for convex regularized least-squares
• Convergence rates of least squares regression estimators with heavy-tailed errors
• A note on the approximate admissibility of regularized estimators in the Gaussian sequence model
• A Geometric View on Constrained M-Estimators
• High dimensional regression and matrix estimation without tuning parameters
• Nonparametric, tuning-free estimation of S-shaped functions
• The geometry of hypothesis testing over convex cones: Generalized likelihood tests and minimax radii
• Stratified incomplete local simplex tests for curvature of nonparametric multiple regression
• On Suboptimality of Least Squares with Application to Estimation of Convex Bodies
• A concentration inequality for the excess risk in least-squares regression with random design and heteroscedastic noise
• High-Dimensional Semiparametric Selection Models: Estimation Theory with an Application to the Retail Gasoline Market
• Model Repair: Robust Recovery of Over-Parameterized Statistical Models
• Improved Prediction and Network Estimation Using the Monotone Single Index Multi-variate Autoregressive Model
• Some facts about the optimality of the LSE in the Gaussian sequence model with convex constraint
• Maximum Regularized Likelihood Estimators: A General Prediction Theory and Applications
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• Estimating Piecewise Monotone Signals
• Convergence rates for estimating multivariate scale mixtures of uniform densities
• On the Minimal Error of Empirical Risk Minimization
• On $\epsilon$-Admissibility in High Dimension and Nonparametrics