  In this paper, we address learning problems for high dimensional data.
Previously, oblivious random projection based approaches that project high
dimensional features onto a random subspace have been used in practice for
tackling high-dimensionality challenge in machine learning. Recently, various
non-oblivious randomized reduction methods have been developed and deployed for
solving many numerical problems such as matrix product approximation, low-rank
matrix approximation, etc. However, they are less explored for the machine
learning tasks, e.g., classification. More seriously, the theoretical analysis
of excess risk bounds for risk minimization, an important measure of
generalization performance, has not been established for non-oblivious
randomized reduction methods. It therefore remains an open problem what is the
benefit of using them over previous oblivious random projection based
approaches. To tackle these challenges, we propose an algorithmic framework for
employing non-oblivious randomized reduction method for general empirical risk
minimizing in machine learning tasks, where the original high-dimensional
features are projected onto a random subspace that is derived from the data
with a small matrix approximation error. We then derive the first excess risk
bound for the proposed non-oblivious randomized reduction approach without
requiring strong assumptions on the training data. The established excess risk
bound exhibits that the proposed approach provides much better generalization
performance and it also sheds more insights about different randomized
reduction approaches. Finally, we conduct extensive experiments on both
synthetic and real-world benchmark datasets, whose dimension scales to
$O(10^7)$, to demonstrate the efficacy of our proposed approach.
