Lifting high-dimensional nonlinear models with Gaussian regressors

2017/12/11 by Thrampoulidis, Christos, Rawat, Ankit Singh
#FOS: Computer and information sciences #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1712.03638

Abstract

We study the problem of recovering a structured signal x₀ from high-dimensional data y_i=f(a_i^Tx₀) for some nonlinear (and potentially unknown) link function f, when the regressors a_i are iid Gaussian. Brillinger (1982) showed that ordinary least-squares estimates x₀ up to a constant of proportionality μ_ℓ, which depends on f. Recently, Plan & Vershynin (2015) extended this result to the high-dimensional setting deriving sharp error bounds for the generalized Lasso. Unfortunately, both least-squares and the Lasso fail to recover x₀ when μ_ℓ=0. For example, this includes all even link functions. We resolve this issue by proposing and analyzing an alternative convex recovery method. In a nutshell, our method treats such link functions as if they were linear in a lifted space of higher-dimension. Interestingly, our error analysis captures the effect of both the nonlinearity and the problem's geometry in a few simple summary parameters.

Related

• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• The generalized Lasso with non-linear observations
• The Generalized Lasso with Nonlinear Observations and Generative Priors
• The Squared-Error of Generalized LASSO: A Precise Analysis
• On Single Index Models beyond Gaussian Data