Exact Dynamics and Finite-Sample Trajectory Recovery of Linear Recursive Feature Machines

1. Introduction

• The paper situates its questions within AGOP-based feature learning and prior linear-RFM work connecting the model to IRLS in the noiseless interpolating setting.It asks for exact finite-time dynamics, finite-sample trajectory recovery, and convergence characterization.Source: §1 · pp. 1–2
• The study targets whether finite-sample errors remain controlled throughout repeated feature updates, since each update reuses the same dataset.The analysis considers noisy targets generated by a low-rank teacher matrix.Source: §1 · p. 2
• The first population update identifies the task-dependent subspace exactly; later updates preserve it and reweight its directions through an explicit spectral recursion.The recursion converges linearly after a finite burn-in period to the optimal point.Source: §1 · p. 2
• Under isotropic sub-Gaussian inputs and bounded teacher rank, empirical representation and predictor paths stay uniformly close to population paths with high probability.For fixed dimension and confidence, the discrepancy decreases at the usual n^-1/2 rate without accumulating across iterations despite data reuse.Source: §1 · p. 2
• Regularized lin-RFM specializes matrix IRLS to noisy multivariate regression, extending its prior connection to the interpolating setting.The paper does not claim a novel algorithm; it combines exact finite-time dynamics, uniform statistical control, and sample-complexity recovery rates.Source: §1 · pp. 2–3

2. Regularized lin-RFM

• The model factors the predictor as F = AB, where B determines the linear features and A is the output layer.With invertible B, the factorization does not enlarge the class of end-to-end linear predictors.Source: §2 · pp. 3–4
• The representation changes the penalty assigned to input directions, emphasizing task-sensitive directions and down-weighting irrelevant ones.The end-to-end predictor remains linear in the original input.Source: §2 · p. 4
• Starting from the identity representation, each iteration fits the output layer on the current representation and then updates the representation using the resulting predictor.The regression step is ridge-regularized, with λ and ϵ as positive parameters.Source: §2 · p. 4

8 end

• The full trajectory depends only on sufficient statistics that can be accumulated in one pass, so sample matrices need not be stored.For sparse inputs and one-hot responses, moment updates cost O(k^2) and O(k); the state occupies O(d^2 + pd) memory, though dense linear algebra still depends on feature dimension.Source: §8 · p. 4
• Regularized lin-RFM is a reparameterization of fixed-smoothing, Schatten-one matrix IRLS specialized to multivariate regression.The smoothed trace-norm penalty favors low-rank predictors, and the predictor update coincides under the stated identification.Source: §8 · p. 5
• The feature matrix and IRLS penalty weight encode complementary views of the same update: larger feature weights mean less penalty on those directions in the next regression.In the IRLS interpretation, the weight adaptively reweights the quadratic regularizer.Source: §8 · pp. 5–6
• The fixed-data correspondence identifies the objective and limiting point, but not the finite-time path or how sampling error affects it.The paper's contribution is to characterize the exact population trajectory and show uniform empirical tracking when the same sample is reused.Source: §8 · p. 6

3. Optimization endpoint and implicit bias

• The fixed-data endpoint is characterized independently of the teacher model or data distribution.The displayed convergence result concerns fixed X and Y with λ, ϵ > 0.Source: §3 · p. 6
• For fixed inputs and responses with positive λ and ϵ, the predictor converges to the unique minimizer of the smoothed trace-norm objective.The learned representation converges correspondingly; the argument uses boundedness, stationarity of accumulation points, and strict convexity.Source: §3 · p. 6
• Identifying the endpoint does not characterize the finite-time path, its convergence speed, or the effect of sampling error on the trajectory.The paper assigns those questions to its population-path and uniform empirical-tracking analyses.Source: §3 · p. 6
• The endpoint recovers the noisy-regression analogue of prior IRLS-1 and linear-RFM analysis; in the noiseless perfectly fit case, the stated condition reduces toward constrained nuclear-norm minimization as ϵ decreases to zero.Related implicit bias to the nuclear norm has also been recovered in analyses of linear neural networks and matrix factorization.Source: §3 · p. 7

• The analysis assumes square outputs, isotropic inputs, a bounded-rank teacher, and finite noise second moment.Source: §4 · p. 7
• The population feature matrix remains diagonal in the teacher basis, with each iteration reweighting directions through the scalar b_t recursion.Source: §4 · pp. 7–8
• The scalar recursion is a multiplicative half-quadratic majorization–minimization algorithm under the specialization of Nikolova and Ng (2005).Source: §4 · p. 8
• For every µ, b_t(µ) converges to a unique fixed point, and the reduced-map Jacobian is diagonal with a spectral radius characterizing local contraction.Source: §4 · pp. 8–9

• Reusing the same empirical moments could amplify estimation error, while empirical updates can also move feature directions outside the teacher basis.Source: §5 · p. 9
• The proof bounds moment-estimation error and trajectory-error propagation separately, using eventual contraction to keep the full empirical path close.Source: §5 · p. 9
• The sample guarantee assumes bounded teacher rank and norm, independent isotropic sub-Gaussian inputs, and independent mean-zero noise with covariance σ^2Id.Source: §5 · p. 10
• With n ≳ d samples, the empirical representation and predictor track their population trajectories uniformly at the n^-1/2 rate, without error growth across reused-data iterations.Source: §5 · pp. 9–10
• The teacher-estimation bound combines a sampling term with population iteration error and regularization bias.Source: §5 · p. 10

Experimental setup

• The OpenWebText and HLCA tasks each use 20,000 word or gene coordinates and roughly 10^9 input–prediction pairs, but their covariates are neither independent nor isotropic.OpenWebText predicts a center word from surrounding words; HLCA predicts a held-out expressed gene from a cell’s TF–IDF-weighted expression vector.Source: §6 · p. 11

Runtime

• Streaming the sufficient statistics Sn and En avoids storing the full sample matrices, and subsequent RFM updates have costs independent of the number of training pairs.The passage notes that Table 1 summarizes runtime costs but supplies no values.Source: §6 · p. 11, Table 1 · p. 11

Feature measurement

• The stable rank is computed on the feature matrix after subtracting the smoothing floor, so it measures spectral concentration above that baseline.Because the smoothing floor keeps every eigenvalue at least ϵ^1/4, the learned matrices are not exactly low rank.Source: §6 · p. 11

Results

• OpenWebText features develop pronounced spectral weights and changed word neighborhoods after the first update, while later updates continue reshaping them.The t = 0 neighborhoods provide an unstructured baseline; the observed discrepancy against a larger-sample reference decreases approximately as n^-1/2.Source: §6 · p. 11

Scope

• Because the real-data covariates are sparse and anisotropic, the observed experiments are not direct tests of the theoretical assumptions.The larger-sample reference trajectory is itself finite-sample, not the exact population path.Source: §6 · pp. 11–12

Scope and contribution

• The results characterize learned representations along the way, with empirical representation and predictor paths uniformly close to the exact population trajectory under the stated setting.The discussion frames this as a tractable linear setting for connecting feature learning with statistical stability.Source: §7 · pp. 12–13

Non-isotropic covariance

• For general positive-definite Σ, Σ and E⊤E need not commute, so the representation may rotate and the explicit population-rate and uniform-tracking guarantees do not directly extend.Synthetic experiments suggest eventual geometric convergence rates depend on the covariance spectrum; spectra with equal condition numbers can still yield different rates.Source: §7 · p. 12

Nonlinear predictors

• With nonlinear activations, the population dynamics do not automatically reduce to the scalar recursion, and empirical trajectories are generally not determined by the two fixed moments Sn and En.The discussion identifies characterizing and uniformly controlling such trajectories under repeated reuse of the same finite sample as an open question.Source: §7 · p. 12

Architectural extensions

• The discussion asks whether trajectory-level analysis can extend to convolutional, deep, and tree-structured RFMs when the same finite sample is reused across iterations.The proposed extensions concern finite-time population dynamics and uniform control of empirical paths.Source: §7 · p. 12

Convergence experiments

• Figure 3 evaluates predictor discrepancy against sample size, convergence toward a 500-iteration endpoint, and estimated contraction rates across covariance spectra.Its experiments indicate that equal condition numbers can yield different convergence rates.Source: §7 · pp. 12, 15, Figure 3 · p. 15

Disclosure

• AI tools assisted with manuscript editing and exposition, including mathematical arguments, related work, and numerical-experiment checks.The authors say they reviewed and revised all AI-assisted material and take responsibility for the paper’s correctness and content.Source: AI Disclosure · p. 16

Appendix A. Proofs for uniform finite-sample stability

• When √r ∆n is sufficiently small, the proof controls the metric trajectory error uniformly by C∆n and derives feature and predictor bounds.Here r is the teacher rank and ∆n is the moment error; the deterministic theorem allows r to vary up to d.Source: Appendix A · pp. 21–22

A.1. Metric maps, trapping, and one-step perturbation

• The proof traps both metric trajectories in a common spectral region, compares updates at a shared input, and uses moment perturbation and Taylor-remainder bounds to control trajectory error.After finite burn-in, local amplification contracts, enabling induction on the trajectory error.Source: §A.1 · pp. 22–23

A.2. Teacher-adapted block norm

• A teacher-eigenspace block norm handles empirical perturbations without requiring empirical and population trajectory matrices to commute.The norm is adapted to the teacher’s signal and null subspaces.Source: §A.2 · p. 24

A.3. Elementary derivative of the population map

• The population-map derivative has an entrywise formula in the teacher basis; it annihilates null–null perturbations and has signal–null coefficients constant across null columns.The coefficient is Kij(H) = λ(µi si + µj sj)/((hi + λ)(hj + λ)(ti + tj)).Source: §A.3 · p. 26
• At the population fixed point, the derivative contraction is bounded by λ/(λ + √ϵ) < 1 for every teacher spectrum, yielding eventual contraction after finite burn-in.For any ρ between this bound and 1, a finite Tρ makes the derivative contract by at most ρ thereafter.Source: §A.3 · p. 27

A.4. Quadratic remainder

• A block Taylor bound controls the square-root remainder around a teacher-basis block-diagonal base point, even when the perturbation itself is not block diagonal.The base matrix and its perturbed version are both bounded below by ϵId.Source: §A.4 · p. 28
• Under a local perturbation condition, the square-root increment is bounded and the population update has a local quadratic remainder.The square-root bound uses a positive spectral floor ϵ; the local-remainder constants depend on ME, λ, and ϵ.Source: §A.4 · pp. 29–30

A.5. Finite-burn-in perturbation argument

• After a finite burn-in, the tracking recursion contracts with rate ρ and bounds the tracking error by a constant multiple of δ.The recursion assumes κ_t ≤ L before T_ρ and κ_t ≤ ρ thereafter; its bound combines the finite and contractive phases.Source: §A.5 · pp. 32–33
• The proof converts block-norm tracking into operator-norm control for metrics and predictors, then takes a supremum over t to conclude Theorem 5.The two metrics are bounded below by mId, enabling square-root comparison; the predictor comparison uses the stated Lipschitz bound for s(H).Source: §A.5 · pp. 33–34

A.6. Sub-Gaussian concentration

• Theorem 7 reduces the sample-complexity problem to bounding Δn, the combined errors in empirical covariance and cross-moments.A common concentration argument controls both terms.Source: §A.6 · p. 34
• With probability at least 1 − η, the empirical moments satisfy the concentration bounds of Lemma 18 under Corollary 6’s assumptions.The proof applies covariance concentration to independent augmented vectors, then extracts covariance and cross-moment blocks; the noiseless case uses covariance concentration directly on the inputs.Source: §A.6 · pp. 34–35
• For bounded teacher rank, n ≳ d + log(1/η) suffices for uniform empirical-to-population trajectory tracking at the n^-1/2 rate.The argument first ensures the rank-explicit estimate applies, then absorbs bounded rank into the constants.Source: §A.6 · pp. 35–36
• The concentration event concerns only empirical moments, so deterministic trajectory control applies at every iteration without a union bound over iteration times.The moments are reused throughout the recursion.Source: §A.6 · p. 36

B.1. Computational complexity of regularized lin-RFM on text data

• For sparse inputs, sufficient-statistic construction costs O(nk2), each update costs O(d3), and total complexity is O(Td3) + O(nk2).Streaming avoids forming the full sample matrices; memory is O(d2). In HuffPost’s 42-class setting, a compact SVD makes the feature-update step cheaper, while dense solves still dominate.Source: §B.1 · p. 36

B.2. Learned nearest neighbor embeddings

• The learned PSD feature matrix induces top-k spectral embeddings, whose coordinate neighborhoods are ranked by cosine similarity; t = 0 is only an unstructured baseline.The initialization has equal eigenvalues, so it has no distinguished top-k eigenspace.Source: §B.2 · pp. 36–37

B.3. Anisotropic covariance families.

• The four anisotropic covariance families share the same trace and condition number but distribute variance differently across directions.The construction normalizes trace to d without changing the prescribed condition number.Source: §B.3 · p. 37

Appendix C. Sample complexity of dynamics plots

• Sample-complexity plots compare finite-sample feature trajectories with a large-sample reference, reporting the median over trials and a 10–90 percentile band.The finite-sample sampling procedure varies by dataset.Source: Appendix C · p. 37

C.1. OpenWebText

• OpenWebText uses normalized context-word inputs to predict the one-hot center word, with nested prefixes drawn from a 10^9-example reference stream.The 20,000-word experiment streamed sufficient statistics in 2.01 hours and ran 10 RFM iterations in 1.5 minutes on an A100 GPU.Source: §C.1 · pp. 38–39

C.2. Integrated Human Lung Cell Atlas (HLCA)

• HLCA formed leave-one-gene-out prediction tasks from normalized expression vectors and streamed 1.003 × 10^9 pairs in 8.51 hours on a compute node using 16 CPU cores.Runtime exceeded OpenWebText’s because each cell averaged 1,933 nonzero vocabulary genes, yielding roughly 3.7 million sparse outer-product entries per cell.Source: §C.2 · pp. 39–40

C.3. TinyStories

• TinyStories feature recovery aligns with Theorem 5’s results despite the experiment lying beyond the theorem’s assumptions.The task predicts a center word from surrounding bag-of-words context.Source: §C.3 · p. 41

C.4. HuffPost News

• Subsequent lin-RFM iterations reduce HuffPost test MSE relative to the initial ridge predictor on an 80/20 split of 167,621 training and 41,906 test articles.The article text is represented by TF-IDF features and the target is its one-hot category.Source: §C.4 · p. 41, Figure 6 · p. 44
• Figure 7’s left panel tracks stable rank at checkpoints A, B, and C, while the HuffPost experiments also show nearest-neighbor embeddings and feature tracking.The embeddings and feature-recovery experiment use all 209,527 articles.Source: §C.4 · p. 41, Figure 7 · p. 44, Figure 8 · p. 45
• −0.493 is the empirical log-log slope of HuffPost’s trajectory error, close to n^-1/2 despite sparse, anisotropic inputs outside Theorem 5’s assumptions.The trajectory discrepancy is measured against the full-data reference over the evaluated iterations.Source: §C.4 · p. 45

D.1.1. HLCA; D.1.2. OPENWEBTEXT

• The HLCA table reports top-five gene neighbors at t = 1 and t = 5 with cosine similarities; the OpenWebText table lists top-five word neighbors for queries selected by t = 1 versus t = 5 Jaccard dissimilarity.Source: Table 2 · p. 45, Table 3 · p. 47