Fast Local Search for Sparse Linear Regression with Tight Approximation Guarantees

Finding the best fit with at most $k$ features in sparse linear regression is computationally challenging, while existing local search methods often rely on strong curvature conditions or repeatedly scan all features when searching for an exchange. We propose Subsampled Ridge-Exchange Local Search (SRE-LS), which uses ridge-based support exchanges and balanced candidate sampling while maintaining a support of size $k$. We prove that SRE-LS achieves an $O(1/\rho )$ approximation with probability at least $1-\delta$ in $O((nd+n{k}^2)\log (1/\delta ))$ time, where $\rho$ is a response orthogonal regularity parameter. We also establish a matching $\Omega (1/\rho )$ worst-case inapproximability bound for randomized polynomial-time algorithms, unless $\mathrm{NP}\subseteq \mathrm{BPP}$, showing that the dependence on $\rho$ is tight. Experiments on synthetic and real-world datasets show that SRE-LS achieves regression loss comparable to existing local-search methods while requiring less running time.