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

arXiv: https://arxiv.org/abs/1701.04455 · HTML: https://mlsanity.com/paper/1701.04455/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jan 2017.

## Built on by (most cited first, 12 of 12)

- [Lattice-Based Methods Surpass Sum-of-Squares in Clustering](https://mlsanity.com/paper/2112.03898/) (2021)
- [Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert](https://mlsanity.com/paper/2308.09474/) (2023)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Performance of Bayesian linear regression in a model with mismatch](https://mlsanity.com/paper/2107.06936/) (2021)
- [Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs](https://mlsanity.com/paper/2203.02824/) (2022)
- [On the Efficiency of ERM in Feature Learning](https://mlsanity.com/paper/2411.12029/) (2024)
- [Exact Recovery of Sparse Binary Vectors from Generalized Linear Measurements](https://mlsanity.com/paper/2502.16008/) (2025)
- [Separating Oblivious and Adaptive Models of Variable Selection](https://mlsanity.com/paper/2602.16568/) (2026)
- [Best Subset Selection with Efficient Primal-Dual Algorithm](https://mlsanity.com/paper/2207.02058/) (2022)
- [Penalised regression with multiple sources of prior effects](https://mlsanity.com/paper/2212.08581/) (2022)
- [Dynamic Incremental Optimization for Best Subset Selection](https://mlsanity.com/paper/2402.02322/) (2024)
- [Choosing the Right Regularizer for Applied ML: Simulation Benchmarks of Popular Scikit-learn Regularization Frameworks](https://mlsanity.com/paper/2604.03541/) (2026)

## Abstract (arXiv)

We consider a sparse linear regression model Y=Xβ*+W where X has a Gaussian entries, W is the noise vector with mean zero Gaussian entries, and β* 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β|Y-Xβ|2, where the minimization is over all k-sparse binary vectors β. The approximation reveals interesting structural properties of the underlying regression problem. In particular, a) We establish that n^*=2klog p/log (2k/σ2+1) is a phase transition point with the following "all-or-nothing" property. When n exceeds n*, (2k)-1|β2-β^*|0≈ 0, and when n is below n*, (2k)-1|β2-β^*|0≈ 1, where β2 is the optimal solution achieving the smallest squared error. With this we prove that n* is the asymptotic threshold for recovering β^* information theoretically. b) We compute the squared error for an intermediate problem minβ|Y-Xβ|2 where minimization is restricted to vectors β with |β-β*|0=2k zeta, for zeta∈ [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 ninf,1=σ2log p, which is information theoretic bound for recovering β^* when k=1 and σ is large, then at n* and finally at nLASSO/CS. c) We establish a certain Overlap Gap Property (OGP) on the space of all binary vectors β when n≤ cklog p for sufficiently small constant c. We conjecture that OGP is the source of algorithmic hardness of solving the minimization problem minβ|Y-Xβ|2 in the regime n<nLASSO/CS.