On Data-Dependent Random Features for Improved Generalization in Supervised Learning
This work addresses the efficiency of kernel approximation for practitioners in machine learning, though it is incremental as it builds on existing data-dependent randomization methods.
The paper tackles the problem of reducing the number of random features needed for good generalization in supervised learning by proposing the EERF algorithm, which uses a data-dependent score function to explore and exploit feature regions, achieving smaller feature counts on benchmark datasets with negligible overhead.
The randomized-feature approach has been successfully employed in large-scale kernel approximation and supervised learning. The distribution from which the random features are drawn impacts the number of features required to efficiently perform a learning task. Recently, it has been shown that employing data-dependent randomization improves the performance in terms of the required number of random features. In this paper, we are concerned with the randomized-feature approach in supervised learning for good generalizability. We propose the Energy-based Exploration of Random Features (EERF) algorithm based on a data-dependent score function that explores the set of possible features and exploits the promising regions. We prove that the proposed score function with high probability recovers the spectrum of the best fit within the model class. Our empirical results on several benchmark datasets further verify that our method requires smaller number of random features to achieve a certain generalization error compared to the state-of-the-art while introducing negligible pre-processing overhead. EERF can be implemented in a few lines of code and requires no additional tuning parameters.