Optimal linear estimation under unknown nonlinear transform

Abstract

Linear regression studies the problem of estimating a model parameter ${\beta }^{\ast }\in {\mathbb{R}}^p$, from $n$ observations $\{(y_i,{\mathbf{x}}_i){\}}_{i=1}^n$ from linear model $y_i=⟨{\mathbf{x}}_i,{\beta }^{\ast }⟩+{\epsilon }_i$. We consider a significant generalization in which the relationship between $⟨{\mathbf{x}}_i,{\beta }^{\ast }⟩$ and $y_i$ is noisy, quantized to a single bit, potentially nonlinear, noninvertible, as well as unknown. This model is known as the single-index model in statistics, and, among other things, it represents a significant generalization of one-bit compressed sensing. We propose a novel spectral-based estimation procedure and show that we can recover ${\beta }^{\ast }$ in settings (i.e., classes of link function $f$) where previous algorithms fail. In general, our algorithm requires only very mild restrictions on the (unknown) functional relationship between $y_i$ and $⟨{\mathbf{x}}_i,{\beta }^{\ast }⟩$. We also consider the high dimensional setting where ${\beta }^{\ast }$ is sparse ,and introduce a two-stage nonconvex framework that addresses estimation challenges in high dimensional regimes where $p\gg n$. For a broad class of link functions between $⟨{\mathbf{x}}_i,{\beta }^{\ast }⟩$ and $y_i$, we establish minimax lower bounds that demonstrate the optimality of our estimators in both the classical and high dimensional regimes.

25 pages, 3 figures

References in corpus (9)

• Generalized power method for sparse principal component analysis
• Sparse principal component analysis and iterative thresholding
• Sparse PCA: Optimal rates and adaptive estimation
• Optimal Solutions for Sparse Principal Component Analysis
• Truncated Power Method for Sparse Eigenvalue Problems
• Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
• High-dimensional estimation with geometric constraints
• Sparse single-index model
• Robust Logistic Regression using Shift Parameters (Long Version)

Cited by in corpus (8)

• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations
• Structured signal recovery from non-linear and heavy-tailed measurements
• Learning Nonlinear Mixtures: Identifiability and Algorithm
• Structured Recovery with Heavy-tailed Measurements: A Thresholding Procedure and Optimal Rates
• Lifting high-dimensional nonlinear models with Gaussian regressors
• Misspecified Nonconvex Statistical Optimization for Phase Retrieval
• A Provable Smoothing Approach for High Dimensional Generalized Regression with Applications in Genomics