Regularized ERM on random subspaces

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 Nystrom 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 extend these results to convex Lipschitz loss functions, that might not be smooth, such as the hinge loss used in support vector machines. This unified analysis requires developing new proofs, that use different technical tools, such as sub-gaussian inputs, to achieve fast rates. 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.

arXiv commentSubmission withdrawn. Readers should please refer to arXiv:2006.10016

References in corpus (13)

• Scikit-learn: Machine Learning in Python
• Sketching as a Tool for Numerical Linear Algebra
• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Fast learning rates for plug-in classifiers
• Risk bounds for statistical learning
• Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization
• Generalization Properties of Learning with Random Features
• Fast approximation of matrix coherence and statistical leverage
• Randomized algorithms for matrices and data
• But How Does It Work in Theory? Linear SVM with Random Features
• Concentration Inequalities and Moment Bounds for Sample Covariance Operators
• Statistical and Computational Trade-Offs in Kernel K-Means
• Gaussian Sketching yields a J-L Lemma in RKHS