acceptodds
Under review as a conference paper at ICLR 2027

Fast Local Search for Sparse Linear Regression with Tight Approximation Guarantees

Abstract

Finding the best fit with at most 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 . We prove that SRE-LS achieves an approximation with probability at least in time, where is a response orthogonal regularity parameter. We also establish a matching worst-case inapproximability bound for randomized polynomial-time algorithms, unless , showing that the dependence on 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.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Sparse Linear Regresion, Local Search, Tight Approximation

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_AWpwOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This work considers the sparse linear regression problem from the perspective of random local search based in subsampling. A majority of the manuscript is to establish some theoretical tight bound to prove that it achieves an approximation with high probability and reasonable computational cost.

Critical strengths

The problem is well defined. The proposed method considers the worst-case scenario, comparing how far the proposed algorithm’s solution can be in the worst case? The manuscript also examines the computational complexity. The theoretical analysis accommodates the situation of dependence of the current support on earlier sampled data. The conditional lower bound can help explain the worst-case order of the approximation factor.

Critical weaknesses

The novelty on methodology is limited. The theoretical contribution is also marginal since the manuscript does not consider the commonly-studied situation with p >> n, and both p and n go to infinity.

The practical advantage is not fully established. The practical information supplied by the residual bound is unclear.

The comparisons with recent sparse ridge methods are missing.

The performance of the proposed method is not appealing.

The numerical setting is mainly for n >p, which is not for high-dimensional data.

Questions for authors

I have major concerns listed above in the critical weakness. In addition, there are major questions as follows:

  1. The experimental algorithm uses a ridge penalty of 0.05, whereas the proof uses 1. The paper does not explain how this change affects the exchange score or residual guarantee.

  2. The numerical experiments are toy examples. All responses are generated, but from the real data.

  3. In Table 2, it is not clear what metric is the loss? Do authors consider the prediction loss? The proposed method does not have a better performance on loss.

  4. How is the penalty of 0.05 incorporated into the exchange score and deletion update, and what version of Theorem 3.6 applies to the evaluated algorithm?

  5. It is better to compare with the established sparse ridge methods under the same feature budget and evaluation objective.

Reviewer_DP2uOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies best-subset regression: given a design AA with columns of norm at most one and a response bb, find a support of exactly kk columns whose least-squares residual is close to f⋆=min⁡∥x∥0≤k∥Ax−b∥2f^\star=\min_{\|x\|_0\le k}\|Ax-b\|_2. The proposed algorithm, SRE-LS, is a randomized single-swap local search. It uses the ridge energy E(S)=min⁡w∥USw−b∥2+∥w∥2E(S)=\min_w\|U_Sw-b\|^2+\|w\|^2, where UU is the column-normalized design.

The main guarantee (Theorem 3.6) is f(A,b,S^)≤14ρf⋆f(A,b,\widehat S)\le \frac{14}{\rho} f^\star with probability 1−δ1-\delta, in time O((nd+nk2)log⁡(1/δ))O((nd+nk^2)\log(1/\delta)). Lemma 3.3 seems to be critical for Theorem 3.6. Experiments on synthetic and real-world datasets are performed.

Critical strengths
  • Efficient support exchanges with rigorous analysis: exactly kk selected columns, allowance for dependent columns, and only O(d)O(d) candidate evaluations over kk rounds.
  • A complementary worst-case lower bound: a rational, polynomial-bit construction establishing the limitation of uniform o(1/ρ)o(1/\rho) approximation.
Critical weaknesses
  • Yes, the authors claim to have an algorithm with improved runtime (at least theoretically) but what is the use the proposed algorithm if the theoretical bounds in Theorem 3.6 are weak (as per my understanding). Can the bounds in Theorem 3.6 be used for something like support recovery in high-dimensional setting?
  • I ask this because in the first paragraph of the introduction section, the authors motivate using "In modern high-dimensional settings, the number of features can substantially exceed the number of observations, which often poses challenges for statistical estimation and variable selection".
  • The speed advantage over the closest baselines depends strongly on the dataset and sparsity level. Please clarify the regime in which SRE-LS offers a useful computational advantage.
  • Given the statistical-estimation and variable-selection motivation, please compare empirically with a standard Lasso implementation, optionally followed by least-squares refitting. Explain how regularization and feature budgets are matched, and distinguish the statistical assumptions and conclusions from those of Wainwright (2009).

Wainwright MJ. Sharp thresholds for High-Dimensional and noisy sparsity recovery using $\ell _ {1} $-Constrained Quadratic Programming (Lasso). IEEE transactions on information theory. 2009 Apr 21;55(5):2183-202.

  • In the abstract, ρ\rho is defined as response orthogonal regularity parameter but in the experiments section it is defined as correlation.

  • Since the claim is about the improvement in the runtime, the authors should also report the hyperparameters of the baseline which are citical for comparison. For example, the variable T discussed in Table 1.

  • In line 423, the authors mention 10k10k sample rounds for experiments. But in Line 225, as per my understanding the algorithm is ran for only k rounds. Did I misunderstand something?

  • The theoretical and empirical comparisons omit important greedy alternatives. For example, can the authors justify why the following papers not used in Table 1 or 2:

  1. Andrew R. Barron, Albert Cohen, Wolfgang Dahmen, Ronald A. DeVore "Approximation and learning by greedy algorithms," The Annals of Statistics, Ann. Statist. 36(1), 64-94, (February 2008)
  2. Das A, Kempe D. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection.
  3. Elenberg ER, Khanna R, Dimakis AG, Negahban S. Restricted strong convexity implies weak submodularity. The Annals of Statistics. 2018 Dec 1;46(6B):3539-68.
  4. Mirzasoleiman B, Badanidiyuru A, Karbasi A, Vondrák J, Krause A. Lazier than lazy greedy. InProceedings of the AAAI Conference on Artificial Intelligence 2015 Feb 18 (Vol. 29, No. 1).
  5. Khanna R, Elenberg E, Dimakis A, Negahban S, Ghosh J. Scalable greedy feature selection via weak submodularity. InArtificial Intelligence and Statistics 2017 Apr 10 (pp. 1560-1568). PMLR.

Minor:

  • In line 313, authors refer to theorem 3.2 which does not exist in the paper. I guess it refers to Lemma 3.2.
  • In Theorem 3.6, ϵ\epsilon is introduced but never used.
Questions for authors
  • In Line 432, authors mention SRE-LS uses \lambda = 0.05. Where is λ\lambda defined in the paper? I wasn't able to find it?
  • As per Table 2, there is very small or negligible improvement in the runtime for MNIST and the loss function value is higher. For RCV1 dataset, the proposed method is not doing better in terms of the reported loss function value and runtime.
  • Can the authors also compare their theoretical bounds in Lemma 3.3 to Theorem 2.3 of the following paper:

Andrew R. Barron, Albert Cohen, Wolfgang Dahmen, Ronald A. DeVore "Approximation and learning by greedy algorithms," The Annals of Statistics, Ann. Statist. 36(1), 64-94, (February 2008)

If I am not wrong, bounds with better constants already exist.

Reviewer_WTqdOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies sparse linear regression, minimizing ∥Ax−b∥22\|Ax-b\|_2^2 subject to xx being kk-sparse. The authors introduce a parameter called response-orthogonal regularity ρ\rho, defined as the minimum singular value of normalized, linearly independent feature subsets of size at most kk, after projection onto the subspace orthogonal to bb. They propose a randomized local-search algorithm using ridge-based feature exchanges and candidate subsampling, achieving an O(1/ρ)O(1/\rho) approximation to the optimal residual in O(nd+nk2)O(nd+nk^2) time with constant probability. They also establish a matching Ω(1/ρ)\Omega(1/\rho) computational hardness bound and experimentally demonstrate comparable regression loss with faster runtimes on several datasets.

Critical strengths

S1 — Matching approximation lower bound

The paper establishes an Ω(1/ρ)\Omega(1/\rho) inapproximability result for randomized polynomial-time algorithms (unless NP⊆BPP\mathrm{NP}\subseteq\mathrm{BPP}), matching the dependence on ρ\rho in their upper bound. This provides a tight characterization of the worst-case approximation factor in terms of the proposed parameter.

S2 — Efficient local-search algorithm

The proposed algorithm achieves an O(1/ρ)O(1/\rho) approximation in O(nd+nk2)O(nd+nk^2) time with constant probability, maintaining exactly kk selected features. Its randomized candidate-sampling technique reduces the total number of candidate evaluations to O(d)O(d) over kk iterations. The experiments demonstrate speedups over existing local-search methods on larger instances while achieving comparable regression loss.

Critical weaknesses

W1 — Limited usefulness of the approximation guarantee

The approximation guarantee can be vacuous even for moderately large sparsity levels. In particular, using Lemma 3.5 and the column normalization, one can show that the stated 14/ρ14/\rho approximation bound is no better than the trivial residual bound ∥b∥2\|b\|_2 for k≤195k\le195. Several experiments, including the main synthetic experiment, use k=20k=20. Although the authors also evaluate larger values of kk, they do not establish whether the approximation bound is nonvacuous on these instances. This raises questions about the practical significance of the theoretical guarantee.

W2 — Interpretability and usefulness of the parameter ρ\rho

The proposed parameter ρ\rho is somewhat counterintuitive as a measure of sparse regression difficulty. While a small ρ\rho can correspond to a nearly exact sparse fit, it can also arise from nearly linearly dependent columns that are irrelevant to predicting bb. Indeed, the hardness construction in Appendix B.2 produces small ρ\rho in both YES and NO instances, including instances where the optimal residual remains bounded away from zero. Thus, although the dependence on 1/ρ1/\rho is theoretically tight, it is unclear whether this parameter captures meaningful difficulty in natural sparse regression problems.

Questions for authors

Q1 — Usefulness of the approximation guarantee

Can the authors identify natural classes of instances where the 14/ρ14/\rho approximation guarantee is nonvacuous? In particular, for k≤195k\le195, the bound is no better than the trivial residual bound ∥b∥2\|b\|_2. It would also be useful to understand whether the guarantee is meaningful on the experimental datasets, and how the authors view ρ\rho as a measure of problem difficulty given its sensitivity to nearly dependent, potentially irrelevant columns.

Q2 — Novelty relative to existing greedy algorithms

Classical approximation guarantees for Orthogonal Matching Pursuit (e.g., Barron et al., 2008), combined with Lemma 3.5, appear to imply an O(1/ρ)O(1/\rho) approximation guarantee as well. Can the authors clarify how their theoretical result compares to this existing guarantee?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.