Efficient Data-Dependent Random Projection for Least Square Regressions

This paper presents a new data-dependent random projection method D<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>RP for least square regressions, which maps data into the row space of a randomly mapped training data matrix. Our theoretical analysis suggests D<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>RP 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 D<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>RP projected space has an O(e<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−k/n</sup>) empirical excess risk that decays exponentially faster as k increases, partly suggesting its high dimension efficiency. On the practical side, we apply D<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>RP 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.