High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition

arXiv1701.04455MaRDI QIDQ6282007FDOQ6282007

Publication date: 16 January 2017

Abstract: We consider a sparse linear regression model Y=X�eta^{*}+W where X has a Gaussian entries, W is the noise vector with mean zero Gaussian entries, and �eta^{*} is a binary vector with support size (sparsity) k. Using a novel conditional second moment method we obtain a tight up to a multiplicative constant approximation of the optimal squared error min_{�eta}|Y-X�eta|_{2}, where the minimization is over all k-sparse binary vectors �eta. The approximation reveals interesting structural properties of the underlying regression problem. In particular, a) We establish that n^*=2klog p/log (2k/sigma^{2}+1) is a phase transition point with the following "all-or-nothing" property. When n exceeds n^{*}, (2k)^{-1}|�eta_{2}-�eta^*|_0approx 0, and when n is below n^{*}, (2k)^{-1}|�eta_{2}-�eta^*|_0approx 1, where �eta_2 is the optimal solution achieving the smallest squared error. With this we prove that n^{*} is the asymptotic threshold for recovering �eta^* information theoretically. b) We compute the squared error for an intermediate problem min_{�eta}|Y-X�eta|_{2} where minimization is restricted to vectors �eta with |�eta-�eta^{*}|_0=2k zeta, for zetain [0,1]. We show that a lower bound part Gamma(zeta) of the estimate, which corresponds to the estimate based on the first moment method, undergoes a phase transition at three different thresholds, namely n_{ ext{inf,1}}=sigma^2log p, which is information theoretic bound for recovering �eta^* when k=1 and sigma is large, then at n^{*} and finally at n_{ ext{LASSO/CS}}. c) We establish a certain Overlap Gap Property (OGP) on the space of all binary vectors �eta when nle cklog p for sufficiently small constant c. We conjecture that OGP is the source of algorithmic hardness of solving the minimization problem min_{�eta}|Y-X�eta|_{2} in the regime n<n_{ ext{LASSO/CS}}.

This page was built for publication: High-Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6282007)