mlsanityData to 7 Oct 2026

Generalized Leverage Score Sampling for Neural Networks

arXiv 2009.09829 ↗First posted 21 Sep 2020cs.LG stat.MLcited by 26

Not on the map. Why?

Abstract (arXiv)

Leverage score sampling is a powerful technique that originates from theoretical computer science, which can be used to speed up a large number of fundamental questions, e.g. linear regression, linear programming, semi-definite programming, cutting plane method, graph sparsification, maximum matching and max-flow. Recently, it has been shown that leverage score sampling helps to accelerate kernel methods [Avron, Kapralov, Musco, Musco, Velingker and Zandieh 17]. In this work, we generalize the results in [Avron, Kapralov, Musco, Musco, Velingker and Zandieh 17] to a broader class of kernels. We further bring the leverage score sampling into the field of deep learning theory. bullet We show the connection between the initialization for neural network training and approximating the neural tangent kernel with random features. bullet We prove the equivalence between regularized neural network and neural tangent kernel ridge regression under the initialization of both classical random Gaussian and leverage score sampling.

Key facts. Cited by 26 papers in the map (data through 7 Oct 2026). First posted on arXiv 21 Sep 2020.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 9; 2022: 4; 2023: 10; 2024: 3.

26 papers.

Sort:

  1. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  2. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  3. 2021Scaling Neural Tangent Kernels via Sketching and Random Featurescited by 32
  4. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  5. 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
  6. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  7. 2023How to Protect Copyright Data in Optimization of Large Language Models?cited by 26
  8. 2022A Sublinear Adversarial Training Algorithmcited by 22
  9. 2022Federated Adversarial Learning: A Framework with Convergence Analysiscited by 17
  10. 2022Bounding the Width of Neural Networks via Coupled Initialization -- A Worst Case Analysiscited by 15
  11. 2024Differential Privacy Mechanisms in Neural Tangent Kernel Regressioncited by 14
  12. 2021FL-NTK: A Neural Tangent Kernel-based Framework for Federated Learning Convergence Analysiscited by 13
14 more
  1. 2021Even your Teacher Needs Guidance: Ground-Truth Targets Dampen Regularization Imposed by Self-Distillationcited by 11
  2. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  3. 2023Unmasking Transformers: A Theoretical Approach to Data Recovery via Attention Weightscited by 11
  4. 2023Controlling the Inductive Bias of Wide Neural Networks by Modifying the Kernel's Spectrumcited by 9
  5. 2023An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descentcited by 9
  6. 2023Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?cited by 8
  7. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  8. 2021Random Features for the Neural Tangent Kernelcited by 6
  9. 2023Convergence of Two-Layer Regression with Nonlinear Unitscited by 6
  10. 2023A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformercited by 6
  11. 2023Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basiscited by 4
  12. 2021Fast Graph Neural Tangent Kernel via Kronecker Sketchingcited by 2
  13. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  14. 2021Learning with Neural Tangent Kernels in Near Input Sparsity Timecited by 0