acceptodds
Under review as a conference paper at ICLR 2027

The Sample Complexity of One Reweighted Least-Squares Step

Abstract

Recursive feature machines learn features by repeatedly refitting a predictor and reweighting its inputs. Their linear version generalizes iteratively reweighted least squares, which also underlies FOCUSS: each step fits the data by weighted least squares and reweights each coordinate by a power of its fitted value. Existing analyses describe the limit of this iteration, draw fresh data for every step, or hold only asymptotically; with fewer samples than features, the finite-sample cost of a step that reuses the data has been open. We bound it for the first step, which starts from the minimum-norm estimate and uses weights . For a noiseless Gaussian design with features and a fixed -sparse target with equal magnitudes, samples suffice for fixed relative error, and a high-probability lower bound matches the powers of and . Yet already ranks the support correctly with order samples. Between these scales, which differ by a factor polynomial in , one step finds the relevant coordinates but does not use them: the many inactive coordinates, each with a small weight, together fit the observations at a lower weighted cost than the target. The gap persists for every ridge penalty and weight floor and closes when the power grows logarithmically in . We extend the lower bound to unequal magnitudes and prove consistency under Gaussian noise with an oracle penalty. Experiments on the same simulated trials measure the gap and its cause, and show that a second step removes it.

Primary area:
learning theory
Keywords:
Learning theory, least squares

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_RJuQOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

For recursive feature machines (RFMs), this paper studies a single reweighting step under a restricted setting involving an independent Gaussian design, a linear target, diagonal coordinate reweighting, and minimum-norm initialization. It provides an estimate of the sample size required to achieve a given relative error, together with a high-probability lower bound. The paper also explains why a single reweighting step can identify the relevant coordinates but fail to use them effectively: although each inactive coordinate receives a small weight, the inactive coordinates collectively can fit the observations at a lower weighted cost than the true target.

Critical strengths

None

Critical weaknesses
  1. The practical significance of this work is limited. The paper’s core theoretical analysis is restricted to an independent Gaussian design, linear targets, diagonal coordinate reweighting, minimum-norm initialization, and a single update, while the main matching bounds further rely on equal-magnitude sparse signals. Together, these assumptions narrow the scope to a highly specialized one-step estimator. The results therefore have limited relevance to understanding Recursive Feature Machines, which repeatedly update features and refit the predictor. In particular, the paper’s own experiments (Table 3, Appendix D.3) show that a second update can substantially mitigate the failure of the first, yet the theory does not explain this improvement. Furthermore, the paper provides a counterexample showing that, even when the covariance matrix has a bounded condition number, the probability of successful screening by the initial estimate can tend to zero (Proposition 15, Appendix C). This further limits the applicability of the theoretical results.
  2. Even within this highly restricted setting, the paper’s contribution remains limited. Its central explanation is that a large number of irrelevant features, each assigned a small weight, can collectively interpolate the training data at a low weighted cost, thereby hindering effective recovery. This mechanism has already appeared in "Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and a Tight Univariate Rate" [1], which also provides an identity for the weight of the target coordinate. The paper has realized this paper and mentions it in the paper. Thus, the paper’s use of it as a failure mechanism offers limited novelty.
  3. The paper overstates the gap between the sample scales for screening and estimation. It claims that the two differ by a factor polynomial in nn, but this statement does not hold throughout the permitted parameter range. The ratio of the estimation lower-bound scale to the screening scale is
=\frac{(n/k)^{1/(q+1)}}{\log n}.$$ For example, taking $q=1$ and $k= n/(\log n)^4$, the screening scale is $n/(\log n)^3$, while the estimation lower-bound scale is $n/(\log n)^2$, so the two differ by only a factor of $\log n$. [1] Xu, Huibo, et al. "Feature Priming in Online Linear Regression: Sparse-Regret Lower Bounds and Tight Coordinatewise Rates." arXiv preprint arXiv:2608.17573
Questions for authors

Please see the weaknesses.

3 comments

We thank the reviewer for the detailed comments. As far as we can see, the concerns can be phrased as : 1) the practical consequences are somewhat weak and 2) the theoretical aspects are related to Xu et. al and 3) errata re : the relative bound ratios.

1. Practicality. As we make clear in section 2, we identify the estimator with the first updates of sparse lin-RFM, FOCUSS, and unsmoothed IRLS under the stated initialization/powers. We give concrete guidance on regularization and reweighting : e.g. corollary 7 states that in the lower-bound regime, tuning ridge or a weight floor cannot repair first-step errors even with data-based selection of parameters. Similarly, we show that with known kk, hard selection and refitting recover exactly once screening succeeds (Theorem 1) as well as showing that a logarithmically growing power reaches the screening sample scale in one update, with a numerical-conditioning cost (Corollary 4). We also distinguish tuning initial weights vs learning weights through another update - e.g. Prop 2 relates new weight ratios to the error, and this is measured in Appendix D.3 with second-step gains in Table 3.

Further, these assumptions do cover an established lin-RFM benchmark: noiseless Gaussian features with active coefficients in [0.5, 1] (please see the original paper, Section 4). And matching exponents will hold whenever the largest-to-smallest active magnitude ratio is bounded, since both μ\mu and keffk_{\rm eff} are of order kk. Noiseless interpolating guarantees also transfer to the independent spherical rows by row normalization. Proposition 15 identifies why a covariance condition-number bound is by itself insufficient for screening, and section 5 tests validation-tuned fits with noise/approximately sparse targets, alongside non-Gaussian cases. To sum up, we believe our practical guidance does exist, and is grounded in the previous literature, therefore it is not correct to state that the practical relevance of the paper is overly narrow (further, for a theoretically-driven result, the practical facet should be considered in the context of the paper's area and focus).

2. Theoretical contribution beyond Xu et al. We agree that this paper is relevant and this is why we cite it. Xu et al. establish the nuisance-interpolation mechanism and target-coordinate identity. But, their theorems address adversarial online regret which is a different case. We study the obstruction case as it occurs with high probability under Gaussian sampling and how many samples suffice to overcome it - specifically, Theorems 3/5 locate the scale (nkq)1/(q+1)(nk^q)^{1/(q+1)}, up to logfactors, for fixed accuracy, fixed q>0q>0, and bounded coefficient ratio, within their stated dimensional ranges. This quantifies the gain over minimum norm's order-nn sample scale in sparse regimes and its dependence on kk and qq.

And, we have corollary 8 which gives that exact screening and hard recovery coexist with soft-refit relative error at least 0.6 on the same observations, whp. The study of a different use case alongside these statistical thresholds and the joint screening/error provide the distinction to the works of Xu et. al. The Gaussian lower bound requires simultaneous singular-value control over all large inactive blocks because fitted weights determine their selection.

To be clear, we agree that Xu et al. deserve credit for their analysis of this mechanism in a different scenario. We already cite them and we will revise the paper to make the crediting more explicit alongside the citation.

3. Correction to the gap description. We thank you for catching this. At fixed confidence, the general scale ratio is (n/k)1/(q+1)/log⁡n(n/k)^{1/(q+1)}/\log n, which gives log⁡n\log n in your example. The polynomial case will be fixed to state that it only holds for fixed qq and k≤n1−ηk \leq n^{1-\eta} with fixed η>0\eta>0. We will correct this throughout the paper. Please note that, however, that theorems 3/5 and corollary 8 already state their parametric conditions so their statements and proofs remain unchanged.

Thanks again for your review and we hope this addresses all your concerns.

Thank you for your response and for agreeing to correct the statement. As the authors point out, Xu et al. study adversarial online regret. Given the same dataset, the two refitting estimators coincide for the powers covered by both papers. Xu et al. already showed that many weakly weighted inactive features can jointly interpolate the data at low cost, suppressing the fitted coefficient on the true coordinate. In the Gaussian case with �0��0� and �1��1�, using �2��2� as a feasible interpolant and applying Xu et al.’s target-coordinate identity gives �3��3�. Since �4��4� with high probability, this yields a constant-error lower bound for �5��5� with a sufficiently small constant �6��6�. The uniform singular-value control emphasized in the rebuttal justifies the construction of an interpolant supported entirely on inactive features. The lower-bound scale in this special case follows directly from Xu et al.’s argument. For sparse RFM, Table 3 shows that at �7��7�, the median error falls from 0.732 after the first update to 0.026 after the second. The cited Proposition 2 bounds the error given the new weights. Even with the observed weights, it gives an upper bound below 1 in only 1 of 40 trials. The theory leaves open when the first refit produces weights that lead to such an improvement. Given that the theoretical contribution concerns a single update under restrictive assumptions, it offers limited insight into the iterative behavior of sparse RFM. I therefore maintain my original score.

That argument works for the special case k=q=1. However, as we have made clear, our paper studies general sparsity k and every fixed power q>0. Let's be specific and take k=1,q=2. With m observations, Xu et al.'s Hadamard construction gives a bound of m4n−1\frac{m^4}{n-1} on the fitted target coefficient, which certifies error bounded away from zero up to order n1/4n^{1/4} on that design. In the Gaussian case, combining the same identity with the interpolation estimate in our proof of Theorem 5 gives a bound of C m3n−1\frac{m^3}{n-1} whp which then certifies the same conclusion up to order n^{1/3}. So, the interpolation estimates clearly differ between the two designs.

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

This paper works on the first step reweighted least-squares step started from the minimum-norm estimate. Accordingly, this paper investigates how many observations are required for one step of a reweighted least-squares algorithm to accurately recover a sparse linear model? It first proves the initial minimum-norm estimator can correctly identify the k features with approximately klog⁡nk\log n observations. However, it then shows one soft reweighting step needs roughly [n(klog⁡n)q]1/(q+1)[n(k\log n)^q]^{1/(q+1)} samples to use them, because thousands of weakly weighted irrelevant features can jointly mimic the signal. The empirical results measure the gap and show that the extension a second step closes it.

Critical strengths
  1. This paper is motivated by a well-posed question that what a feature-learning step extracts from finite data and derives solid theoretical results to answer it. Empirical results are also provided to verify the theorem and extend theoretical results to two step settings.
Critical weaknesses
  1. Most of the principal statistical guarantees assume that the design matrix has independent standard Gaussian entries. This work should discussion more about which properties of the Gaussian distribution are essential to the proofs and which might extend to other distributions.

  2. The regularization parameter in Theorem 10 depends on the unknown quantities βmin\beta_{min} and σ\sigma, so the guaranteed estimator cannot be computed in practice. Although it evaluates validation-tuned penalties empirically, the paper would benefit from a more thorough discussion of this practical procedure and of how closely it tracks the oracle choice.

Questions for authors

Can the positive sample-complexity guarantees in Theorems 1 and 3 be extended beyond independent Gaussian designs ?

1 comment

We thank the reviewer for the positive review and specific questions.

Beyond Gaussian designs. In the noise-free setting, we have both fits as the low-space projector P=X†XP=X^\dagger X: with the initial fit being a=Pβ⋆a=P\beta^\star, and the refit minimizing its weighted norm subject to Pβ=Pβ⋆P\beta=P\beta^\star. So Theorems 1 and 3 hold unchanged for any full-row-rank design with a uniformly random row space, including independent rows uniform on a sphere. This will be added to the paper. General correlated designs need some extra assumptions, please check Prop 15.

Practical regularization. In Appendix D.5 we select among 22 penalties using 256 independent validation observations, additional to the training sample. With n=2048n=2048, k=8k=8, and σ=0.15\sigma=0.15, validation-selected q=2q=2 has median relative errors 0.141, 0.046, and 0.018 for m=256,512,1024m=256,512,1024 while the oracle formula gives 0.138, 0.043, and 0.016 (Tables 18 and 17). This partially answers your point via separate trials and weight setups and we have comparable errors in these settings. We agree that validation-based guarantees may not always be met in practice and this focuses on answering the empirical question, this will be made explicit.

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

The paper studies the sampling complexity of iterative reweighted least squares algorithms for the first step of the algorithms i.e. for algorithms that start with a=X†ya=X^{\dagger}y and reweigh coefficients as ∣ai∣q|a_i|^q for any qq, specifically q=(1/2,1,2)q=(1/2,1,2) where the support of the solution is kk. For getting a fixed relative error, the paper achieves upper and lower bounds on the number of samples required explicitly dependent on the power qq. This analysis is done with assumption of a Gaussian design matrix and no noise. However, some extension is also done in the noisy setting with oracle regularization assumption. Some experimental validation to the theory is provided using synthetic data.

Critical strengths

The work is interesting from a theoretical perspective and appears sound. It would be of considerable interest to the relevant community.

Critical weaknesses
  1. The scope of the analysis appears restricted to me i.e. most of the main results assume gaussian design matrix and no noise while the noisy case requires and oracle regularization assumption.

  2. The writing is too dense. The structure of the papers is theorems, corollaries, propositions appearing back-to-back without many discussions on the insights of the results.

Questions for authors

none but a suggestion:

Please structure the paper for better readability and add some discussion and insights with technical statements.

2 comments

Thanks for the positive review and suggestions on readability. We will reorganize the main text around the screening-estimation separation and the upper/lower bounds. Results will be explained more per result instead of coming one after the other and we'll move extra technical statements to the appendix. We will also add the noiseless extension scenario for the spherical designs case via row-space invariance. We'll also clarify the relationship between the noisy result and the oracle setup.

Thank you for the rebuttal. Based on the answers and other reviews, I feel the paper requires some work for a clear accept. Currently I will keep my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.