论文标题
神经网络的广义杠杆评分抽样
Generalized Leverage Score Sampling for Neural Networks
论文作者
论文摘要
杠杆得分采样是一种强大的技术，源自理论计算机科学，可用于加快大量基本问题，例如线性回归，线性编程，半准编程，切割平面方法，图形稀疏，最大匹配和最大流量。最近，已经表明，利用分数采样有助于加速内核方法[Avron，Kapralov，Musco，Musco，Musco，Velingker和Zandieh 17]。 在这项工作中，我们将结果推广到[Avron，Kapralov，Musco，Musco，Velingker和Zandieh 17]中，将其概括为更广泛的核。我们进一步将杠杆评分抽样带入了深度学习理论领域。 $ \ bullet $，我们显示神经网络训练的初始化与具有随机特征的神经切线内核之间的连接。 $ \ bullet $，我们证明了正则化神经网络与神经切线内核脊在初始化的范围随机高斯和杠杆评分采样的初始化之间的等价性。
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.
