A fundamental problem in machine learning is to understand how neural
networks make accurate predictions, while seemingly bypassing the curse of
dimensionality. A possible explanation is that common training algorithms for
neural networks implicitly perform dimensionality reduction - a process called
feature learning. Recent work posited that the effects of feature learning can
be elicited from a classical statistical estimator called the average gradient
outer product (AGOP). The authors proposed Recursive Feature Machines (RFMs) as
an algorithm that explicitly performs feature learning by alternating between
(1) reweighting the feature vectors by the AGOP and (2) learning the prediction
function in the transformed space. In this work, we develop the first
theoretical guarantees for how RFM performs dimensionality reduction by
focusing on the class of overparametrized problems arising in sparse linear
regression and low-rank matrix recovery. Specifically, we show that RFM
restricted to linear models (lin-RFM) generalizes the well-studied Iteratively
Reweighted Least Squares (IRLS) algorithm. Our results shed light on the
connection between feature learning in neural networks and classical sparse
recovery algorithms. In addition, we provide an implementation of lin-RFM that
scales to matrices with millions of missing entries. Our implementation is
faster than the standard IRLS algorithm as it is SVD-free. It also outperforms
deep linear networks for sparse linear regression and low-rank matrix
completion.

神经网络在绕过维度灾难的同时能够准确预测的基础是对特征学习的隐式维度缩减过程的理解，本文提出了递归特征机（RFM）作为一种能够显式地执行特征学习的算法，并且在稀疏线性回归等问题中展示了其维度缩减能力和优于标准算法的性能。

线性递归特征机器可证明恢复低秩矩阵

Linear Recursive Feature Machines provably recover low-rank matrices

In this technical report, we explore the behavior of Recursive Feature
Machines (RFMs), a type of novel kernel machine that recursively learns
features via the average gradient outer product, through a series of
experiments on regression datasets. When successively adding random noise
features to a dataset, we observe intriguing patterns in the Mean Squared Error
(MSE) curves with the test MSE exhibiting a decrease-increase-decrease pattern.
This behavior is consistent across different dataset sizes, noise parameters,
and target functions. Interestingly, the observed MSE curves show similarities
to the "double descent" phenomenon observed in deep neural networks, hinting at
new connection between RFMs and neural network behavior. This report lays the
groundwork for future research into this peculiar behavior.

本研究通过对回归数据集的一系列实验研究，探讨了一种新型核机器 —— 递归特征机的行为，发现与神经网络行为类似的双下降现象表现，揭示了 RFMs 和神经网络行为之间的新联系，为未来的研究打下了基础。