# Oblivious Sketching of High-Degree Polynomial Kernels

**Authors:** Michael Kapralov, Rasmus Pagh, Ameya Velingker, David Woodruff, Amir Zandieh  
**arXiv:** [1909.01410](https://arxiv.org/abs/1909.01410)  
**Date:** 2019-09-03  
**Summary page:** https://www.summarizepaper.com/en/paper/1909.01410v1/

## Key points

- Kernel methods are used in machine learning to detect non-linear dependencies between data without explicitly constructing feature vectors in high-dimensional spaces.
- Existing kernel methods suffer from poor scalability due to the computational cost of operations on dense kernel matrices.
- Oblivious sketching has emerged as a technique for accelerating numerical linear algebra, but applying it to kernel matrices has been challenging and limited by exponential dependence on input parameters.
- The authors propose a general method that applies sketching solutions developed in numerical linear algebra to a tensoring of data points without explicitly forming the tensoring, overcoming previous limitations and achieving significant improvements in efficiency.
- The main contribution is the development of an oblivious sketch for polynomial kernels with a target dimension that is only polynomially dependent on the degree of the kernel function.
- They also present an oblivious sketch for Gaussian kernels on bounded datasets that does not suffer from exponential dependence on the dimensionality of input data points.
- This research addresses a major drawback of kernel methods by introducing efficient techniques for handling large-scale datasets.
- Potential applications include pattern recognition and data analysis.

## Summary

Kernel methods are widely used in machine learning to detect non-linear dependencies between data without explicitly constructing feature vectors in high-dimensional spaces. However, these methods suffer from poor scalability due to the computational cost of operations on kernel matrices, which are typically dense. Existing approaches for speeding up kernel linear algebra either suffer from exponential time complexity with respect to the dimensionality of input points or the degree of the kernel function. In recent years, oblivious sketching has emerged as a powerful technique for accelerating numerical linear algebra. However, applying oblivious sketching to kernel matrices has been challenging and limited by its exponential dependence on input parameters. In this study, the authors propose a general method that applies sketching solutions developed in numerical linear algebra to a tensoring of data points without explicitly forming the tensoring. This novel approach overcomes the previous limitations and achieves significant improvements in efficiency. The main contribution of this work is the development of an oblivious sketch for polynomial kernels with a target dimension that is only polynomially dependent on the degree of the kernel function. Additionally, they present an oblivious sketch for Gaussian kernels on bounded datasets that does not suffer from an exponential dependence on the dimensionality of input data points. Overall, this research addresses a major drawback of kernel methods by introducing efficient techniques for handling large-scale datasets. The proposed method has potential applications in various areas where kernel methods are utilized, such as pattern recognition and data analysis.