Efficient Data-Dependent Random Projection for Least Square Regressions
Jacob Sturges, Luyuan Yang, Shayan Shafaei, Chao Lan · 2025
This paper presents a new data-dependent random projection method D2RP for least square regressions, which maps data into the row space of a randomly mapped training data matrix. Our theoretical analysis suggests D2RP may not preserve pairwise data distance as well as its data-independent ancestors, but preserves enough information for reconstructing the training data. Our further analysis shows least square regression in the D2RP projected space has an O(e−k/n) empirical excess risk that decays exponentially faster as k increases, partly suggesting its high dimension efficiency. On the practical side, we apply D2RP to speed up least square regression, kernel ridge regression and ensemble regression. Experimental results on real-world data sets show it achieves the best tradeoff between computation efficiency and dimension efficiency compared to multiple baselines methods.