Regularized ERM on random subspaces

Andrea Della Vecchia, Jaouad Mourtada, Ernesto De Vito, Lorenzo Rosasco
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:4006-4014, 2021.

Abstract

We study a natural extension of classical empirical risk minimization, where the hypothesis space is a random subspace of a given space. In particular, we consider possibly data dependent subspaces spanned by a random subset of the data, recovering as a special case Nyström approaches for kernel methods. Considering random subspaces naturally leads to computational savings, but the question is whether the corresponding learning accuracy is degraded. These statistical-computational tradeoffs have been recently explored for the least squares loss and self-concordant loss functions, such as the logistic loss. Here, we work to ex- tend these results to convex Lipschitz loss functions, that might not be smooth, such as the hinge loss used in support vector ma- chines. This extension requires developing new proofs, that use different technical tools. Our main results show the existence of different settings, depending on how hard the learning problem is, for which computational efficiency can be improved with no loss in performance. Theoretical results are illustrated with simple numerical experiments.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-della-vecchia21a, title = { Regularized ERM on random subspaces }, author = {Della Vecchia, Andrea and Mourtada, Jaouad and De Vito, Ernesto and Rosasco, Lorenzo}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {4006--4014}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/della-vecchia21a/della-vecchia21a.pdf}, url = {https://proceedings.mlr.press/v130/della-vecchia21a.html}, abstract = { We study a natural extension of classical empirical risk minimization, where the hypothesis space is a random subspace of a given space. In particular, we consider possibly data dependent subspaces spanned by a random subset of the data, recovering as a special case Nyström approaches for kernel methods. Considering random subspaces naturally leads to computational savings, but the question is whether the corresponding learning accuracy is degraded. These statistical-computational tradeoffs have been recently explored for the least squares loss and self-concordant loss functions, such as the logistic loss. Here, we work to ex- tend these results to convex Lipschitz loss functions, that might not be smooth, such as the hinge loss used in support vector ma- chines. This extension requires developing new proofs, that use different technical tools. Our main results show the existence of different settings, depending on how hard the learning problem is, for which computational efficiency can be improved with no loss in performance. Theoretical results are illustrated with simple numerical experiments. } }
Endnote
%0 Conference Paper %T Regularized ERM on random subspaces %A Andrea Della Vecchia %A Jaouad Mourtada %A Ernesto De Vito %A Lorenzo Rosasco %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-della-vecchia21a %I PMLR %P 4006--4014 %U https://proceedings.mlr.press/v130/della-vecchia21a.html %V 130 %X We study a natural extension of classical empirical risk minimization, where the hypothesis space is a random subspace of a given space. In particular, we consider possibly data dependent subspaces spanned by a random subset of the data, recovering as a special case Nyström approaches for kernel methods. Considering random subspaces naturally leads to computational savings, but the question is whether the corresponding learning accuracy is degraded. These statistical-computational tradeoffs have been recently explored for the least squares loss and self-concordant loss functions, such as the logistic loss. Here, we work to ex- tend these results to convex Lipschitz loss functions, that might not be smooth, such as the hinge loss used in support vector ma- chines. This extension requires developing new proofs, that use different technical tools. Our main results show the existence of different settings, depending on how hard the learning problem is, for which computational efficiency can be improved with no loss in performance. Theoretical results are illustrated with simple numerical experiments.
APA
Della Vecchia, A., Mourtada, J., De Vito, E. & Rosasco, L.. (2021). Regularized ERM on random subspaces . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:4006-4014 Available from https://proceedings.mlr.press/v130/della-vecchia21a.html.

Related Material