Structured Recovery with Heavy-tailed Measurements: A Thresholding Procedure and Optimal Rates

Abstract

This paper introduces a general regularized thresholded least-square procedure estimating a structured signal ${\theta }_{\ast }\in {\mathbb{R}}^d$ from the following observations: $y_i=f(⟨{\mathbf{x}}_i,{\theta }_{\ast }⟩,{\xi }_i),i\in \{1,2,\cdots ,N\}$, with i.i.d. heavy-tailed measurements $\{({\mathbf{x}}_i,y_i){\}}_{i=1}^N$. A general framework analyzing the thresholding procedure is proposed, which boils down to computing three critical radiuses of the bounding balls of the estimator. Then, we demonstrate these critical radiuses can be tightly bounded in the following two scenarios: (1) The link function $f(\cdot )$ is linear, i.e. $y=⟨\mathbf{x},{\theta }_{\ast }⟩+\xi$, with ${\theta }_{\ast }$ being a sparse vector and $\{{\mathbf{x}}_i{\}}_{i=1}^N$ being general heavy-tailed random measurements with bounded $(20+\epsilon )$-moments. (2) The function $f(\cdot )$ is arbitrary unknown (possibly discontinuous) and $\{{\mathbf{x}}_i{\}}_{i=1}^N$ are heavy-tailed elliptical random vectors with bounded $(4+\epsilon )$-moments. In both scenarios, we show under these rather minimal bounded moment assumptions, such a procedure and corresponding analysis lead to optimal sample and error bounds with high probability in terms of the structural properties of ${\theta }_{\ast }$.

arXiv comment43 pages, 1 figure

References in corpus (8)

• Simultaneous analysis of Lasso and Dantzig selector
• The lower tail of random quadratic forms, with applications to ordinary least squares and restricted eigenvalue properties
• High-dimensional estimation with geometric constraints
• A Shrinkage Principle for Heavy-Tailed Data: High-Dimensional Robust Low-Rank Matrix Recovery
• Optimal linear estimation under unknown nonlinear transform
• Structured signal recovery from non-linear and heavy-tailed measurements
• On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models
• Non-Gaussian Observations in Nonlinear Compressed Sensing via Stein Discrepancies

Cited by in corpus (5)

• The Generalized Lasso with Nonlinear Observations and Generative Priors
• Generic Error Bounds for the Generalized Lasso with Sub-Exponential Data
• High Dimensional M-Estimation with Missing Outcomes: A Semi-Parametric Framework
• Surrogate Aided Unsupervised Recovery of Sparse Signals in Single Index Models for Binary Outcomes
• II. High Dimensional Estimation under Weak Moment Assumptions: Structured Recovery and Matrix Estimation