Nearly optimal minimax estimator for high-dimensional sparse linear regression

DOI10.1214/13-AOS1141zbMATH Open1360.62391arXiv1206.6536MaRDI QIDQ385791FDOQ385791

Authors: Li Zhang 

Publication date: 11 December 2013

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

Abstract: We present estimators for a well studied statistical estimation problem: the estimation for the linear regression model with soft sparsity constraints ($el{l}_q$ constraint with $0<qleq1$) in the high-dimensional setting. We first present a family of estimators, called the projected nearest neighbor estimator and show, by using results from Convex Geometry, that such estimator is within a logarithmic factor of the optimal for any design matrix. Then by utilizing a semi-definite programming relaxation technique developed in [SIAM J. Comput. 36 (2007) 1764-1776], we obtain an approximation algorithm for computing the minimax risk for any such estimation task and also a polynomial time nearly optimal estimator for the important case of $el{l}_1$ sparsity constraint. Such results were only known before for special cases, despite decades of studies on this problem. We also extend the method to the adaptive case when the parameter radius is unknown.

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

Recommendations

• Minimax \(\ell_q\) risk in \(\ell_p\) balls
• Minimax risks for sparse regressions: ultra-high dimensional phenomenons
• SLOPE is adaptive to unknown sparsity and asymptotically minimax
• Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators
• Adaptive Minimax Estimation over Sparse $\ell_q$-Hulls

zbMATH Keywords

linear regressioncompressed sensingminimax estimationnearest neighbor estimatoroptimal minimax estimatororthogonal projection estimatorprojected nearest neighbor estimatorsparsity constraint

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Linear regression; mixed models (62J05) Minimax procedures in statistical decision theory (62C20)

Cites Work

• Nearly unbiased variable selection under minimax concave penalty
• The Adaptive Lasso and Its Oracle Properties
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Title not available (Why is that?)
• Simultaneous analysis of Lasso and Dantzig selector
• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Title not available (Why is that?)
• Introduction to nonparametric estimation
• Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
• Risk bounds for model selection via penalization
• Minimax risk over \(l_ p\)-balls for \(l_ q\)-error
• Nonconcave penalized likelihood with a diverging number of parameters.
• Decoding by Linear Programming
• Model selection for regression on a fixed design
• Approximation and learning by greedy algorithms
• Compressed sensing
• Asymptotically Minimax Adaptive Estimation. I: Upper Bounds. Optimally Adaptive Estimates
• Rate minimaxity of the Lasso and Dantzig selector for the \(l_{q}\) loss in \(l_{r}\) balls
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Generic Chaining
• Sparse Recovery With Orthogonal Matching Pursuit Under RIP
• Optimal filtering of square-integrable signals in Gaussian noise
• Orthogonal Matching Pursuit for Sparse Signal Recovery With Noise
• Gelfand numbers of operators with values in a Hilbert space
• Model selection for Gaussian regression with random design
• Smoothed analysis of algorithms
• The LASSO Risk for Gaussian Matrices
• How well can we estimate a sparse vector?
• Title not available (Why is that?)
• Shifting Inequality and Recovery of Sparse Signals
• Minimax risk over hyperrectangles, and implications
• The Noise-Sensitivity Phase Transition in Compressed Sensing
• An alternative point of view on Lepski's method
• Approximating the Radii of Point Sets
• Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
• Title not available (Why is that?)
• Adaptive estimation with soft thresholding penalties
• Title not available (Why is that?)

Cited In (12)

• Kolmogorov \(n\)-widths of function classes induced by a non-degenerate differential operator: a convex duality approach
• New approach to Bayesian high-dimensional linear regression
• Adaptive Minimax Estimation over Sparse $\ell_q$-Hulls
• Exponential screening and optimal rates of sparse estimation
• Estimation of linear projections of non-sparse coefficients in high-dimensional regression
• Non-negative least squares for high-dimensional linear models: consistency and sparse recovery without regularization
• Minimax risks for sparse regressions: ultra-high dimensional phenomenons
• An improved private mechanism for small databases
• Sparse estimation via lower-order penalty optimization methods in high-dimensional linear regression
• Minimax \(\ell_q\) risk in \(\ell_p\) balls
• Consistent tuning parameter selection in high dimensional sparse linear regression
• Optimal prediction for sparse linear models? Lower bounds for coordinate-separable M-estimators

This page was built for publication: Nearly optimal minimax estimator for high-dimensional sparse linear regression

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