Exponential screening and optimal rates of sparse estimation

DOI10.1214/10-AOS854zbMATH Open1215.62043arXiv1003.2654MaRDI QIDQ548534FDOQ548534

Authors: Philippe Rigollet, Alexandre B. Tsybakov 

Publication date: 29 June 2011

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: In high-dimensional linear regression, the goal pursued here is to estimate an unknown regression function using linear combinations of a suitable set of covariates. One of the key assumptions for the success of any statistical procedure in this setup is to assume that the linear combination is sparse in some sense, for example, that it involves only few covariates. We consider a general, non necessarily linear, regression with Gaussian noise and study a related question that is to find a linear combination of approximating functions, which is at the same time sparse and has small mean squared error (MSE). We introduce a new estimation procedure, called Exponential Screening that shows remarkable adaptation properties. It adapts to the linear combination that optimally balances MSE and sparsity, whether the latter is measured in terms of the number of non-zero entries in the combination ($el{l}_0$ norm) or in terms of the global weight of the combination ($el{l}_1$ norm). The power of this adaptation result is illustrated by showing that Exponential Screening solves optimally and simultaneously all the problems of aggregation in Gaussian regression that have been discussed in the literature. Moreover, we show that the performance of the Exponential Screening estimator cannot be improved in a minimax sense, even if the optimal sparsity is known in advance. The theoretical and numerical superiority of Exponential Screening compared to state-of-the-art sparse procedures is also discussed.

Full work available at URL: https://arxiv.org/abs/1003.2654

Recommendations

• Sparse estimation by exponential weighting
• PAC-Bayesian bounds for sparse regression estimation with exponential weights
• Estimation and variable selection with exponential weights
• Aggregation and minimax optimality in high-dimensional estimation
• Nearly optimal minimax estimator for high-dimensional sparse linear regression

zbMATH Keywords

lassoaggregationBICadaptationhigh-dimensional regressionsparsityminimax ratessparsity oracle inequalities

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Nonparametric regression and quantile regression (62G08) Asymptotic properties of nonparametric inference (62G20) Linear regression; mixed models (62J05) Estimation in multivariate analysis (62H12) Minimax procedures in statistical decision theory (62C20)

Cites Work

• The elements of statistical learning. Data mining, inference, and prediction
• Nearly unbiased variable selection under minimax concave penalty
• Ideal spatial adaptation by wavelet shrinkage
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• On the conditions used to prove oracle results for the Lasso
• Simultaneous analysis of Lasso and Dantzig selector
• High-dimensional generalized linear models and the lasso
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Universal approximation bounds for superpositions of a sigmoidal function
• Title not available (Why is that?)
• Title not available (Why is that?)
• Learning Theory and Kernel Machines
• Sparsity oracle inequalities for the Lasso
• Adapting to unknown sparsity by controlling the false discovery rate
• Title not available (Why is that?)
• Introduction to nonparametric estimation
• The sparsity and bias of the LASSO selection in high-dimensional linear regression
• Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
• Minimax risk over \(l_ p\)-balls for \(l_ q\)-error
• The risk inflation criterion for multiple regression
• Title not available (Why is that?)
• Mixing least-squares estimators when the variance is unknown
• A simple proof of the restricted isometry property for random matrices
• Aggregation for Gaussian regression
• Information Theory and Mixing Least-Squares Regressions
• Adaptive estimation of the intensity of inhomogeneous Poisson processes via concentration inequalities
• The Dantzig selector and sparsity oracle inequalities
• Some sharp performance bounds for least squares regression with \(L_1\) regularization
• PAC-Bayesian bounds for sparse regression estimation with exponential weights
• Exponential screening and optimal rates of sparse estimation
• The restricted isometry property and its implications for compressed sensing
• Sparsity in penalized empirical risk minimization
• Sparse regression learning by aggregation and Langevin Monte-Carlo
• Mirror averaging with sparsity priors
• Aggregation by Exponential Weighting and Sharp Oracle Inequalities
• Generalized mirror averaging and \(D\)-convex aggregation
• Minimax multiple shrinkage estimation
• Combining Minimax Shrinkage Estimators

Cited In (69)

• Targeting underrepresented populations in precision medicine: a federated transfer learning approach
• Statistical inference for data-adaptive doubly robust estimators with survival outcomes
• Structured, sparse aggregation
• Model-averaged \(\ell_1\) regularization using Markov chain Monte Carlo model composition
• Simple proof of the risk bound for denoising by exponential weights for asymmetric noise distributions
• Theory of adaptive estimation
• Covariate-adaptive randomization with variable selection in clinical trials
• Estimation and Inference for High-Dimensional Generalized Linear Models with Knowledge Transfer
• Aggregation of affine estimators
• On cross-validated Lasso in high dimensions
• Sharp oracle inequalities for aggregation of affine estimators
• Robust Bayes estimation using the density power divergence
• Restricted strong convexity implies weak submodularity
• Covariate assisted screening and estimation
• The smooth-Lasso and other \(\ell _{1}+\ell _{2}\)-penalized methods
• An \(\ell_1\)-oracle inequality for the Lasso in multivariate finite mixture of multivariate Gaussian regression models
• Localized Gaussian width of \(M\)-convex hulls with applications to Lasso and convex aggregation
• Combining a relaxed EM algorithm with Occam's razor for Bayesian variable selection in high-dimensional regression
• Exponential screening and optimal rates of sparse estimation
• Optimal Kullback-Leibler aggregation in mixture density estimation by maximum likelihood
• On the prediction loss of the Lasso in the partially labeled setting
• Structured matrix estimation and completion
• Optimal learning with \textit{Q}-aggregation
• Adaptive density estimation on bounded domains
• Oracle inequalities for sparse additive quantile regression in reproducing kernel Hilbert space
• Oracle inequalities for high-dimensional prediction
• Slope meets Lasso: improved oracle bounds and optimality
• On Robustness of Principal Component Regression
• Exponential weights in multivariate regression and a low-rankness favoring prior
• Bayesian linear regression with sparse priors
• Model selection in regression under structural constraints
• Estimation and variable selection with exponential weights
• Sharp oracle inequalities for low-complexity priors
• Prediction and estimation consistency of sparse multi-class penalized optimal scoring
• Regularization and the small-ball method. II: Complexity dependent error rates
• Entropic optimal transport is maximum-likelihood deconvolution
• Solution of linear ill-posed problems by model selection and aggregation
• Aggregated hold out for sparse linear regression with a robust loss function
• Optimal bounds for aggregation of affine estimators
• Sparse PCA: optimal rates and adaptive estimation
• Mirror averaging with sparsity priors
• Adaptive estimation over anisotropic functional classes via oracle approach
• Minimax risks for sparse regressions: ultra-high dimensional phenomenons
• Prediction error bounds for linear regression with the TREX
• Block-based refitting in \(\ell_{12}\) sparse regularization
• A new perspective on least squares under convex constraint
• PAC-Bayesian bounds for sparse regression estimation with exponential weights
• Statistical inference in compound functional models
• Sparse covariance matrix estimation in high-dimensional deconvolution
• Oracle inequalities for local and global empirical risk minimizers
• Upper bounds and aggregation in bipartite ranking
• A general framework for Bayes structured linear models
• Estimation of matrices with row sparsity
• Inference without compatibility: using exponential weighting for inference on a parameter of a linear model
• The Lasso as an \(\ell _{1}\)-ball model selection procedure
• On the exponentially weighted aggregate with the Laplace prior
• Empirical risk minimization is optimal for the convex aggregation problem
• MAP model selection in Gaussian regression
• Kullback-Leibler aggregation and misspecified generalized linear models
• Comment on ``Hypothesis testing by convex optimization
• Deviation optimal learning using greedy \(Q\)-aggregation
• Oracle inequalities for high dimensional vector autoregressions
• Estimation of high-dimensional low-rank matrices
• CLEAR: covariant least-square refitting with applications to image restoration
• Isotonic regression meets Lasso
• Sparse estimation by exponential weighting
• Oracle inequalities and optimal inference under group sparsity
• Transfer Learning in Large-Scale Gaussian Graphical Models with False Discovery Rate Control
• High-dimensional regression with unknown variance

Uses Software

• CRAN
• Plus
• ElemStatLearn
• l1_ls

This page was built for publication: Exponential screening and optimal rates of sparse estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q548534)