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

We consider a sparse linear regression model Y=X\\beta^{*}+W where X has a\nGaussian entries, W is the noise vector with mean zero Gaussian entries, and\n\\beta^{*} is a binary vector with support size (sparsity) k. Using a novel\nconditional second moment method we obtain a tight up to a multiplicative\nconstant approximation of the optimal squared error\n\\min_{\\beta}\\|Y-X\\beta\\|_{2}, where the minimization is over all k-sparse\nbinary vectors \\beta. The approximation reveals interesting structural\nproperties of the underlying regression problem. In particular, a) We establish\nthat n^*=2k\\log p/\\log (2k/\\sigma^{2}+1) is a phase transition point with the\nfollowing "all-or-nothing" property. When n exceeds n^{*},\n(2k)^{-1}\\|\\beta_{2}-\\beta^*\\|_0\\approx 0, and when n is below n^{*},\n(2k)^{-1}\\|\\beta_{2}-\\beta^*\\|_0\\approx 1, where \\beta_2 is the optimal\nsolution achieving the smallest squared error. With this we prove that n^{*} is\nthe asymptotic threshold for recovering \\beta^* information theoretically. b)\nWe compute the squared error for an intermediate problem\n\\min_{\\beta}\\|Y-X\\beta\\|_{2} where minimization is restricted to vectors \\beta\nwith \\|\\beta-\\beta^{*}\\|_0=2k \\zeta, for \\zeta\\in [0,1]. We show that a lower\nbound part \\Gamma(\\zeta) of the estimate, which corresponds to the estimate\nbased on the first moment method, undergoes a phase transition at three\ndifferent thresholds, namely n_{\\text{inf,1}}=\\sigma^2\\log p, which is\ninformation theoretic bound for recovering \\beta^* when k=1 and \\sigma is\nlarge, then at n^{*} and finally at n_{\\text{LASSO/CS}}. c) We establish a\ncertain Overlap Gap Property (OGP) on the space of all binary vectors \\beta\nwhen n\\le ck\\log p for sufficiently small constant c. We conjecture that OGP is\nthe source of algorithmic hardness of solving the minimization problem\n\\min_{\\beta}\\|Y-X\\beta\\|_{2} in the regime n<n_{\\text{LASSO/CS}}.\n