Linear Recursive Feature Machines provably recover low-rank matrices

A fundamental problem in machine learning is to understand how neuralnetworks make accurate predictions, while seemingly bypassing the curse ofdimensionality. A possible explanation is that common training algorithms forneural networks implicitly perform dimensionality reduction - a process calledfeature learning. Recent work posited that the effects of feature learning canbe elicited from a classical statistical estimator called the average gradientouter product (AGOP). The authors proposed Recursive Feature Machines (RFMs) asan algorithm that explicitly performs feature learning by alternating between(1) reweighting the feature vectors by the AGOP and (2) learning the predictionfunction in the transformed space. In this work, we develop the firsttheoretical guarantees for how RFM performs dimensionality reduction byfocusing on the class of overparametrized problems arising in sparse linearregression and low-rank matrix recovery. Specifically, we show that RFMrestricted to linear models (lin-RFM) generalizes the well-studied IterativelyReweighted Least Squares (IRLS) algorithm. Our results shed light on theconnection between feature learning in neural networks and classical sparserecovery algorithms. In addition, we provide an implementation of lin-RFM thatscales to matrices with millions of missing entries. Our implementation isfaster than the standard IRLS algorithm as it is SVD-free. It also outperformsdeep linear networks for sparse linear regression and low-rank matrixcompletion.