Generalization Bounds for Supervised Dimensionality Reduction

Mehryar Mohri, Afshin Rostamizadeh, Dmitry Storcheus
Proceedings of the 1st International Workshop on Feature Extraction: Modern Questions and Challenges at NIPS 2015, PMLR 44:226-241, 2015.

Abstract

We introduce and study the learning scenario of \emphsupervised dimensionality reduction, which couples dimensionality reduction and a subsequent supervised learning step. We present new generalization bounds for this scenario based on a careful analysis of the empirical Rademacher complexity of the relevant hypothesis set. In particular, we show an upper bound on the Rademacher complexity that is in \widetilde O(\sqrt\Lambda_(r)/m), where m is the sample size and \Lambda_(r) the upper bound on the Ky-Fan r-norm of the operator that defines the dimensionality reduction projection. We give both upper and lower bound guarantees in terms of that Ky-Fan r-norm, which strongly justifies the definition of our hypothesis set. To the best of our knowledge, these are the first learning guarantees for the problem of supervised dimensionality reduction with a \emphlearned kernel-based mapping. Our analysis and learning guarantees further apply to several special cases, such as that of using a fixed kernel with supervised dimensionality reduction or that of unsupervised learning of a kernel for dimensionality reduction followed by a supervised learning algorithm.

Cite this Paper

BibTeX
@InProceedings{pmlr-v44-mohri2015generalization, title = {Generalization Bounds for Supervised Dimensionality Reduction}, author = {Mohri, Mehryar and Rostamizadeh, Afshin and Storcheus, Dmitry}, booktitle = {Proceedings of the 1st International Workshop on Feature Extraction: Modern Questions and Challenges at NIPS 2015}, pages = {226--241}, year = {2015}, editor = {Storcheus, Dmitry and Rostamizadeh, Afshin and Kumar, Sanjiv}, volume = {44}, series = {Proceedings of Machine Learning Research}, address = {Montreal, Canada}, month = {11 Dec}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v44/mohri2015generalization.pdf}, url = {https://proceedings.mlr.press/v44/mohri2015generalization.html}, abstract = {We introduce and study the learning scenario of \emphsupervised dimensionality reduction, which couples dimensionality reduction and a subsequent supervised learning step. We present new generalization bounds for this scenario based on a careful analysis of the empirical Rademacher complexity of the relevant hypothesis set. In particular, we show an upper bound on the Rademacher complexity that is in \widetilde O(\sqrt\Lambda_(r)/m), where m is the sample size and \Lambda_(r) the upper bound on the Ky-Fan r-norm of the operator that defines the dimensionality reduction projection. We give both upper and lower bound guarantees in terms of that Ky-Fan r-norm, which strongly justifies the definition of our hypothesis set. To the best of our knowledge, these are the first learning guarantees for the problem of supervised dimensionality reduction with a \emphlearned kernel-based mapping. Our analysis and learning guarantees further apply to several special cases, such as that of using a fixed kernel with supervised dimensionality reduction or that of unsupervised learning of a kernel for dimensionality reduction followed by a supervised learning algorithm.} }
Endnote
%0 Conference Paper %T Generalization Bounds for Supervised Dimensionality Reduction %A Mehryar Mohri %A Afshin Rostamizadeh %A Dmitry Storcheus %B Proceedings of the 1st International Workshop on Feature Extraction: Modern Questions and Challenges at NIPS 2015 %C Proceedings of Machine Learning Research %D 2015 %E Dmitry Storcheus %E Afshin Rostamizadeh %E Sanjiv Kumar %F pmlr-v44-mohri2015generalization %I PMLR %P 226--241 %U https://proceedings.mlr.press/v44/mohri2015generalization.html %V 44 %X We introduce and study the learning scenario of \emphsupervised dimensionality reduction, which couples dimensionality reduction and a subsequent supervised learning step. We present new generalization bounds for this scenario based on a careful analysis of the empirical Rademacher complexity of the relevant hypothesis set. In particular, we show an upper bound on the Rademacher complexity that is in \widetilde O(\sqrt\Lambda_(r)/m), where m is the sample size and \Lambda_(r) the upper bound on the Ky-Fan r-norm of the operator that defines the dimensionality reduction projection. We give both upper and lower bound guarantees in terms of that Ky-Fan r-norm, which strongly justifies the definition of our hypothesis set. To the best of our knowledge, these are the first learning guarantees for the problem of supervised dimensionality reduction with a \emphlearned kernel-based mapping. Our analysis and learning guarantees further apply to several special cases, such as that of using a fixed kernel with supervised dimensionality reduction or that of unsupervised learning of a kernel for dimensionality reduction followed by a supervised learning algorithm.
RIS
TY - CPAPER TI - Generalization Bounds for Supervised Dimensionality Reduction AU - Mehryar Mohri AU - Afshin Rostamizadeh AU - Dmitry Storcheus BT - Proceedings of the 1st International Workshop on Feature Extraction: Modern Questions and Challenges at NIPS 2015 DA - 2015/12/08 ED - Dmitry Storcheus ED - Afshin Rostamizadeh ED - Sanjiv Kumar ID - pmlr-v44-mohri2015generalization PB - PMLR DP - Proceedings of Machine Learning Research VL - 44 SP - 226 EP - 241 L1 - http://proceedings.mlr.press/v44/mohri2015generalization.pdf UR - https://proceedings.mlr.press/v44/mohri2015generalization.html AB - We introduce and study the learning scenario of \emphsupervised dimensionality reduction, which couples dimensionality reduction and a subsequent supervised learning step. We present new generalization bounds for this scenario based on a careful analysis of the empirical Rademacher complexity of the relevant hypothesis set. In particular, we show an upper bound on the Rademacher complexity that is in \widetilde O(\sqrt\Lambda_(r)/m), where m is the sample size and \Lambda_(r) the upper bound on the Ky-Fan r-norm of the operator that defines the dimensionality reduction projection. We give both upper and lower bound guarantees in terms of that Ky-Fan r-norm, which strongly justifies the definition of our hypothesis set. To the best of our knowledge, these are the first learning guarantees for the problem of supervised dimensionality reduction with a \emphlearned kernel-based mapping. Our analysis and learning guarantees further apply to several special cases, such as that of using a fixed kernel with supervised dimensionality reduction or that of unsupervised learning of a kernel for dimensionality reduction followed by a supervised learning algorithm. ER -
APA
Mohri, M., Rostamizadeh, A. & Storcheus, D.. (2015). Generalization Bounds for Supervised Dimensionality Reduction. Proceedings of the 1st International Workshop on Feature Extraction: Modern Questions and Challenges at NIPS 2015, in Proceedings of Machine Learning Research 44:226-241 Available from https://proceedings.mlr.press/v44/mohri2015generalization.html.

Related Material