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

arXiv: https://arxiv.org/abs/2302.10128 · HTML: https://mlsanity.com/paper/2302.10128/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 79 references that are in the map.
- First posted on arXiv 20 Feb 2023.

## Builds on (most cited first, 30 of 30)

- [Fully Convolutional Networks for Semantic Segmentation](https://mlsanity.com/paper/1411.4038/) (2014)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [Learning with Differentiable Perturbed Optimizers](https://mlsanity.com/paper/2002.08676/) (2020)
- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [Graph Kernels: State-of-the-Art and Future Challenges](https://mlsanity.com/paper/2011.03854/) (2020)
- [SparseMAP: Differentiable Sparse Structured Inference](https://mlsanity.com/paper/1802.04223/) (2018)
- [Structured Prediction Energy Networks](https://mlsanity.com/paper/1511.06350/) (2015)
- [A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings](https://mlsanity.com/paper/2002.05424/) (2020)
- [A Consistent Regularization Approach for Structured Prediction](https://mlsanity.com/paper/1605.07588/) (2016)
- [Randomized sketches for kernels: Fast and optimal non-parametric regression](https://mlsanity.com/paper/1501.06195/) (2015)
- [On Structured Prediction Theory with Calibrated Convex Surrogate Losses](https://mlsanity.com/paper/1703.02403/) (2017)
- [Random Fourier Features for Operator-Valued Kernels](https://mlsanity.com/paper/1605.02536/) (2016)
- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [Fast Randomized Kernel Methods With Statistical Guarantees](https://mlsanity.com/paper/1411.0306/) (2014)
- [Sharp Analysis of Learning with Discrete Losses](https://mlsanity.com/paper/1810.06839/) (2018)
- [Deep Value Networks Learn to Evaluate and Iteratively Refine Structured Outputs](https://mlsanity.com/paper/1703.04363/) (2017)
- [Fast rates in structured prediction](https://mlsanity.com/paper/2102.00760/) (2021)
- [Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation](https://mlsanity.com/paper/2103.04031/) (2021)
- [Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCA](https://mlsanity.com/paper/2105.08875/) (2021)
- [On the Sample Complexity of Subspace Learning](https://mlsanity.com/paper/1408.5032/) (2014)
- [Gaussian Sketching yields a J-L Lemma in RKHS](https://mlsanity.com/paper/1908.05818/) (2019)
- [Adaptive and Oblivious Randomized Subspace Methods for High-Dimensional Optimization: Sharp Analysis and Lower Bounds](https://mlsanity.com/paper/2012.07054/) (2020)
- [Mean Nystr"om Embeddings for Adaptive Compressive Learning](https://mlsanity.com/paper/2110.10996/) (2021)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [Vector-Valued Least-Squares Regression under Output Regularity Assumptions](https://mlsanity.com/paper/2211.08958/) (2022)

## Built on by (most cited first, 5 of 5)

- [Estimating Koopman operators with sketching to provably learn large scale dynamical systems](https://mlsanity.com/paper/2306.04520/) (2023)
- [Nonparametric Control Koopman Operators](https://mlsanity.com/paper/2405.07312/) (2024)
- [Linear quadratic control of nonlinear systems with Koopman operator learning and the Nystr"om method](https://mlsanity.com/paper/2403.02811/) (2024)
- [Deep Sketched Output Kernel Regression for Structured Prediction](https://mlsanity.com/paper/2406.09253/) (2024)
- [MSAlign: Aligning Molecule and Mass Spectra representations for Metabolite Identification](https://mlsanity.com/paper/2605.19752/) (2026)

## Abstract (arXiv)

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.