Lifting high-dimensional non-linear models with Gaussian regressors

Christos Thrampoulidis, Ankit Singh Rawat
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:3206-3215, 2019.

Abstract

We study the problem of recovering a structured signal x0 from high-dimensional data yi=f(aTix0) for some nonlinear (and potentially unknown) link function f, when the regressors ai are iid Gaussian. Brillinger (1982) showed that ordinary least-squares estimates x0 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 x0 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-thrampoulidis19a, title = {Lifting high-dimensional non-linear models with Gaussian regressors}, author = {Thrampoulidis, Christos and Rawat, Ankit Singh}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {3206--3215}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/thrampoulidis19a/thrampoulidis19a.pdf}, url = {https://proceedings.mlr.press/v89/thrampoulidis19a.html}, abstract = {We study the problem of recovering a structured signal $\mathbf{x}_0$ from high-dimensional data $\mathbf{y}_i=f(\mathbf{a}_i^T\mathbf{x}_0)$ for some nonlinear (and potentially unknown) link function $f$, when the regressors $\mathbf{a}_i$ are iid Gaussian. Brillinger (1982) showed that ordinary least-squares estimates $\mathbf{x}_0$ up to a constant of proportionality $\mu_\ell$, 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 $\mathbf{x}_0$ when $\mu_\ell=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.} }
Endnote
%0 Conference Paper %T Lifting high-dimensional non-linear models with Gaussian regressors %A Christos Thrampoulidis %A Ankit Singh Rawat %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-thrampoulidis19a %I PMLR %P 3206--3215 %U https://proceedings.mlr.press/v89/thrampoulidis19a.html %V 89 %X We study the problem of recovering a structured signal $\mathbf{x}_0$ from high-dimensional data $\mathbf{y}_i=f(\mathbf{a}_i^T\mathbf{x}_0)$ for some nonlinear (and potentially unknown) link function $f$, when the regressors $\mathbf{a}_i$ are iid Gaussian. Brillinger (1982) showed that ordinary least-squares estimates $\mathbf{x}_0$ up to a constant of proportionality $\mu_\ell$, 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 $\mathbf{x}_0$ when $\mu_\ell=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.
APA
Thrampoulidis, C. & Rawat, A.S.. (2019). Lifting high-dimensional non-linear models with Gaussian regressors. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:3206-3215 Available from https://proceedings.mlr.press/v89/thrampoulidis19a.html.

Related Material