Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels

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.

References in corpus (14)

• Fully Convolutional Networks for Semantic Segmentation
• Sharp analysis of low-rank kernel matrix approximations
• SparseMAP: Differentiable Sparse Structured Inference
• Learning with Differentiable Perturbed Optimizers
• Deep Value Networks Learn to Evaluate and Iteratively Refine Structured Outputs
• A Consistent Regularization Approach for Structured Prediction
• Kernel methods through the roof: handling billions of points efficiently
• A Generalized Kernel Approach to Structured Output Learning
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings
• Sharp Analysis of Learning with Discrete Losses
• Vector-Valued Least-Squares Regression under Output Regularity Assumptions
• Fast rates in structured prediction
• Fast Kernel Methods for Generic Lipschitz Losses via $p$-Sparsified Sketches
• Nyström $M$-Hilbert-Schmidt Independence Criterion

Cited by in corpus (1)

• Linear quadratic control of nonlinear systems with Koopman operator learning and the Nyström method