Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels
Tamim El Ahmad, Luc Brogat-Motte, Pierre Laforgue, Florence d’Alché-Buc
Abstract
Leveraging the kernel trick in both the input and output spaces, surrogate kernel methods are a flexible and theoretically grounded solution to structured output prediction. If they provide state-of-the-art performance on complex data sets of moderate size (e.g., in chemoinformatics), these approaches however fail to scale. We propose to equip surrogate kernel methods with sketching-based approximations, applied to both the input and output feature maps. We prove excess risk bounds on the original structured prediction problem, showing how to attain close-to-optimal rates with a reduced sketch size that depends on the eigendecay of the input/output covariance operators. From a computational perspective, we show that the two approximations have distinct but complementary impacts: sketching the input kernel mostly reduces training time, while sketching the output kernel decreases the inference time. Empirically, our approach is shown to scale, achieving state-of-the-art performance on benchmark data sets where non-sketched methods are intractable.
BibTeX
@InProceedings{pmlr-v238-el-ahmad24a,
title = {Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels},
author = {El Ahmad, Tamim and Brogat-Motte, Luc and Laforgue, Pierre and d'Alch\'{e}-Buc, Florence},
booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics},
pages = {109--117},
year = {2024},
editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen},
volume = {238},
series = {Proceedings of Machine Learning Research},
month = {02--04 May},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v238/el-ahmad24a/el-ahmad24a.pdf},
url = {https://proceedings.mlr.press/v238/el-ahmad24a.html},
abstract = {Leveraging the kernel trick in both the input and output spaces, surrogate kernel methods are a flexible and theoretically grounded solution to structured output prediction. If they provide state-of-the-art performance on complex data sets of moderate size (e.g., in chemoinformatics), these approaches however fail to scale. We propose to equip surrogate kernel methods with sketching-based approximations, applied to both the input and output feature maps. We prove excess risk bounds on the original structured prediction problem, showing how to attain close-to-optimal rates with a reduced sketch size that depends on the eigendecay of the input/output covariance operators. From a computational perspective, we show that the two approximations have distinct but complementary impacts: sketching the input kernel mostly reduces training time, while sketching the output kernel decreases the inference time. Empirically, our approach is shown to scale, achieving state-of-the-art performance on benchmark data sets where non-sketched methods are intractable.}
}