A Model-Agnostic Randomized Learning Framework based on Random Hypothesis Subspace Sampling

Yiting Cao, Chao Lan
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:2597-2608, 2022.

Abstract

We propose a model-agnostic randomized learning framework based on Random Hypothesis Subspace Sampling (RHSS). Given any hypothesis class, it randomly samples $k$ hypotheses and learns a near-optimal model from their span by simply solving a linear least square problem in $O(n k^2)$ time, where $n$ is the number of training instances. On the theory side, we derive the performance guarantee of RHSS from a generic subspace approximation perspective, leveraging properties of metric entropy and random matrices. On the practical side, we apply the RHSS framework to learn kernel, network and tree based models. Experimental results show they converge efficiently as $k$ increases and outperform their model-specific counterparts including random Fourier feature, random vector functional link and extra tree on real-world data sets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-cao22a, title = {A Model-Agnostic Randomized Learning Framework based on Random Hypothesis Subspace Sampling}, author = {Cao, Yiting and Lan, Chao}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {2597--2608}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/cao22a/cao22a.pdf}, url = {https://proceedings.mlr.press/v162/cao22a.html}, abstract = {We propose a model-agnostic randomized learning framework based on Random Hypothesis Subspace Sampling (RHSS). Given any hypothesis class, it randomly samples $k$ hypotheses and learns a near-optimal model from their span by simply solving a linear least square problem in $O(n k^2)$ time, where $n$ is the number of training instances. On the theory side, we derive the performance guarantee of RHSS from a generic subspace approximation perspective, leveraging properties of metric entropy and random matrices. On the practical side, we apply the RHSS framework to learn kernel, network and tree based models. Experimental results show they converge efficiently as $k$ increases and outperform their model-specific counterparts including random Fourier feature, random vector functional link and extra tree on real-world data sets.} }
Endnote
%0 Conference Paper %T A Model-Agnostic Randomized Learning Framework based on Random Hypothesis Subspace Sampling %A Yiting Cao %A Chao Lan %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-cao22a %I PMLR %P 2597--2608 %U https://proceedings.mlr.press/v162/cao22a.html %V 162 %X We propose a model-agnostic randomized learning framework based on Random Hypothesis Subspace Sampling (RHSS). Given any hypothesis class, it randomly samples $k$ hypotheses and learns a near-optimal model from their span by simply solving a linear least square problem in $O(n k^2)$ time, where $n$ is the number of training instances. On the theory side, we derive the performance guarantee of RHSS from a generic subspace approximation perspective, leveraging properties of metric entropy and random matrices. On the practical side, we apply the RHSS framework to learn kernel, network and tree based models. Experimental results show they converge efficiently as $k$ increases and outperform their model-specific counterparts including random Fourier feature, random vector functional link and extra tree on real-world data sets.
APA
Cao, Y. & Lan, C.. (2022). A Model-Agnostic Randomized Learning Framework based on Random Hypothesis Subspace Sampling. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:2597-2608 Available from https://proceedings.mlr.press/v162/cao22a.html.

Related Material