Best Subset Selection in Linear Regression: Fixed-Design Error Bounds and Insights for Random Designs

Abstract

We study exact support recovery by best subset selection in linear regression under a fixed design. For a known support size $s$ and ambient dimension $d$, we derive a non-asymptotic upper bound on the probability that best subset selection fails to recover the true support. The bound is expressed through a deterministic subset-separability parameter, which measures how well the true support can be distinguished from competing supports after projection. The result holds for all sample sizes $n$ exceeding a certain sufficient threshold which we state explicitly in terms of the signal-to-noise ratio, the subset separability of the realized design, and a logarithmic factor of order $\ln s + \ln(d - s)$. In contrast to random-design analyses, no full log-combinatorial term over the candidate support class appears. We discuss how such terms may reappear when the design is random and the separability parameter must be controlled uniformly over many competing subsets. The fixed-design formulation and the proof strategy also indicate settings in which the effective complexity of best subset selection may be reduced, for instance, under structured designs or restricted candidate subset classes.