The Sample Complexity of One Reweighted Least-Squares Step

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 $a=X^{†}y$ and uses weights $|a_i{|}^q$. For a noiseless Gaussian design with $n$ features and a fixed $k$-sparse target with equal magnitudes, ${\left[n{\left(k\log (n/\delta )\right)}^q\right]}^{1/(q+1)}$ samples suffice for fixed relative error, and a high-probability lower bound matches the powers of $n$ and $k$. Yet $a$ already ranks the support correctly with order $k\log n$ samples. Between these scales, which differ by a factor polynomial in $n$, 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 $n$. 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.