mlsanityData to 7 Oct 2026

Fast Sketching of Polynomial Kernels of Polynomial Degree

arXiv 2108.09420 ↗First posted 21 Aug 2021cs.DS cs.LG stat.MLcited by 33

Not on the map. Why?

Abstract (arXiv)

Kernel methods are fundamental in machine learning, and faster algorithms for kernel approximation provide direct speedups for many core tasks in machine learning. The polynomial kernel is especially important as other kernels can often be approximated by the polynomial kernel via a Taylor series expansion. Recent techniques in oblivious sketching reduce the dependence in the running time on the degree q of the polynomial kernel from exponential to polynomial, which is useful for the Gaussian kernel, for which q can be chosen to be polylogarithmic. However, for more slowly growing kernels, such as the neural tangent and arc-cosine kernels, q needs to be polynomial, and previous work incurs a polynomial factor slowdown in the running time. We give a new oblivious sketch which greatly improves upon this running time, by removing the dependence on q in the leading order term. Combined with a novel sampling scheme, we give the fastest algorithms for approximating a large family of slow-growing kernels.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). Builds on 30 of its 59 references that are in the map. First posted on arXiv 21 Aug 2021.

Builds on

30 of 59 references.

References · 30

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  3. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  4. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  5. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  6. 2018Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Datacited by 260
  7. 2018On the Convergence Rate of Training Recurrent Neural Networkscited by 82
  8. 2018Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guaranteescited by 71
  9. 2013Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Ratescited by 64
  10. 2019Quadratic Suffices for Over-parametrization via Matrix Chernoff Boundcited by 58
  11. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  12. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
18 more
  1. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  2. 2017Relative Error Tensor Low Rank Approximationcited by 45
  3. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  4. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 43
  5. 2016Diverse Neural Network Learns True Target Functionscited by 33
  6. 2016Preconditioning Kernel Matricescited by 32
  7. 2014Optimal CUR Matrix Decompositionscited by 29
  8. 2017Sketching for Kronecker Product Regression and P-splinescited by 29
  9. 2019Optimal Sketching for Kronecker Product Regression and Low Rank Approximationcited by 29
  10. 2020Generalized Leverage Score Sampling for Neural Networkscited by 26
  11. 2015Optimal Principal Component Analysis in Distributed and Streaming Modelscited by 24
  12. 2020Algorithms and Hardness for Linear Algebra on Geometric Graphscited by 22
  13. 2016Sharper Bounds for Regularized Data Fittingcited by 19
  14. 2018Subspace Embedding and Linear Regression with Orlicz Normcited by 19
  15. 2021FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysiscited by 13
  16. 2020Near Input Sparsity Time Kernel Embeddings via Adaptive Samplingcited by 12
  17. 2017Near Optimal Sketching of Low-Rank Tensor Regressioncited by 11
  18. 2020Scaling up Kernel Ridge Regression via Locality Sensitive Hashingcited by 8

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 8; 2023: 15; 2024: 4; 2025: 4.

33 papers.

Sort:

  1. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  2. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  3. 2023PolySketchFormer: Fast Transformers via Sketching Polynomial Kernelscited by 33
  4. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  5. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  6. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  7. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
  8. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  9. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  10. 2022Dynamic Tensor Product Regressioncited by 17
  11. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
  12. 2022Improved Random Features for Dot Product Kernelscited by 11
21 more
  1. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  2. 2023A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graphcited by 10
  3. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  4. 2023Solving Tensor Low Cycle Rank Approximationcited by 8
  5. 2022Differentially Private Learning with Margin Guaranteescited by 7
  6. 2022Sublinear Time Algorithm for Online Weighted Bipartite Matchingcited by 7
  7. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  8. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  9. 2022Random Gegenbauer Features for Scalable Kernel Methodscited by 6
  10. 2022Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Timecited by 6
  11. 2023Streaming Kernel PCA Algorithm With Small Spacecited by 5
  12. 2022Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernelcited by 3
  13. 2021Fast Graph Neural Tangent Kernel via Kronecker Sketchingcited by 2
  14. 2022On The Relative Error of Random Fourier Features for Preserving Kernel Distancecited by 2
  15. 2024Quantum Speedup for Spectral Approximation of Kronecker Productscited by 1
  16. 2024Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walkcited by 1
  17. 2025Kernel Learning for Mean-Variance Trading Strategiescited by 1
  18. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  19. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  20. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0
  21. 2025Semantic Distance Measurement based on Multi-Kernel Gaussian Processescited by 0