Regularized ERM on random subspaces
  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\"om 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 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.
