- 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
- 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.
- 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.
- The paper overstates the gap between the sample scales for screening and estimation. It claims that the two differ by a factor polynomial in , but this statement does not hold throughout the permitted parameter range. The ratio of the estimation lower-bound scale to the screening scale is
Questions for authors
Please see the weaknesses.
3 comments
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 and , using as a feasible interpolant and applying Xu et al.’s target-coordinate identity gives . Since with high probability, this yields a constant-error lower bound for with a sufficiently small constant . 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 , 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 on the fitted target coefficient, which certifies error bounded away from zero up to order 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 whp which then certifies the same conclusion up to order n^{1/3}. So, the interpolation estimates clearly differ between the two designs.
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 k, 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 μ and keff are of order k. 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), up to logfactors, for fixed accuracy, fixed q>0, and bounded coefficient ratio, within their stated dimensional ranges. This quantifies the gain over minimum norm's order-n sample scale in sparse regimes and its dependence on k and q.
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)/logn, which gives logn in your example. The polynomial case will be fixed to state that it only holds for fixed q and k≤n1−η with fixed η>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.