Timezone: »

 
Poster
Statistical-Computational Tradeoff in Single Index Models
Lingxiao Wang · Zhuoran Yang · Zhaoran Wang

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #240
in Theory -- Information Theory »
We study the statistical-computational tradeoffs in a high dimensional single index model $Y=f(X^\top\beta^*) +\epsilon$, where $f$ is unknown, $X$ is a Gaussian vector and $\beta^*$ is $s$-sparse with unit norm. When $\cov(Y,X^\top\beta^*)\neq 0$, \cite{plan2016generalized} shows that the direction and support of $\beta^*$ can be recovered using a generalized version of Lasso. In this paper, we investigate the case when this critical assumption fails to hold, where the problem becomes considerably harder. Using the statistical query model to characterize the computational cost of an algorithm, we show that when $\cov(Y,X^\top\beta^*)=0$ and $\cov(Y,(X^\top\beta^*)^2)>0$, no computationally tractable algorithms can achieve the information-theoretic limit of the minimax risk. This implies that one must pay an extra computational cost for the nonlinearity involved in the model.
Keywords: Sparsity and Compressed Sensing · Algorithms
[ Paper]  [ Poster] 

Author Information

Lingxiao Wang (Northwestern University)
Zhuoran Yang (Princeton University)
Zhaoran Wang (Northwestern University)

More from the Same Authors