$p$-Sparsified Sketches for Fast Multiple Output Kernel Methods
Kernel methods are learning algorithms that enjoy solid theoretical
foundations while suffering from important computational limitations.
Sketching, that consists in looking for solutions among a subspace of reduced
dimension, is a widely studied approach to alleviate this numerical burden.
However, fast sketching strategies, such as non-adaptive subsampling,
significantly degrade the guarantees of the algorithms, while
theoretically-accurate sketches, such as the Gaussian one, turn out to remain
relatively slow in practice. In this paper, we introduce the $p$-sparsified
sketches, that combine the benefits from both approaches to achieve a good
tradeoff between statistical accuracy and computational efficiency. To support
our method, we derive excess risk bounds for both single and multiple output
problems, with generic Lipschitz losses, providing new guarantees for a wide
range of applications, from robust regression to multiple quantile regression.
We also provide empirical evidences of the superiority of our sketches over
recent SOTA approaches.