Generalized Leverage Score Sampling for Neural Networks

Abstract

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.

References in corpus (18)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity
• Recovery Guarantees for One-hidden-layer Neural Networks
• Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
• Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
• SGD Learns the Conjugate Kernel Class of the Network
• Faster Dynamic Matrix Inverse for Faster LPs
• Quadratic Suffices for Over-parametrization via Matrix Chernoff Bound
• Learning Non-overlapping Convolutional Neural Networks with Multiple Kernels
• Optimal CUR Matrix Decompositions
• Faster Divergence Maximization for Faster Maximum Flow
• Space-Efficient Interior Point Method, with applications to Linear Programming and Maximum Weight Bipartite Matching
• Algorithmic Foundations for the Diffraction Limit
• ${\ell }_p$ Row Sampling by Lewis Weights
• Towards A Unified Analysis of Random Fourier Features

Cited by in corpus (3)

• Even your Teacher Needs Guidance: Ground-Truth Targets Dampen Regularization Imposed by Self-Distillation
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network