我们考虑培训多层过参数化神经网络的问题,以最大限度地减少损失函数引起的经验风险。在过度参数化的典型设置中,网络宽度$ M $远大于数据维度$ D $和培训数量$ N $($ m = \ mathrm {poly}(n,d)$),其中诱导禁止的大量矩阵$ w \ in \ mathbb {r} ^ {m \ times m} $每层。天真地,一个人必须支付$ O(m ^ 2)$时间读取权重矩阵并评估前向和后向计算中的神经网络功能。在这项工作中,我们展示了如何降低每个迭代的培训成本,具体而言,我们提出了一个仅在初始化阶段使用M ^ 2美元的框架,并且在$ M $的情况下实现了每次迭代的真正子种化成本。 ,$ m ^ {2- \ oomga(1)} $次迭代。为了获得此结果,我们利用各种技术,包括偏移的基于Relu的稀释器,懒惰的低级维护数据结构,快速矩阵矩阵乘法,张量的草图技术和预处理。
translated by 谷歌翻译
深度学习的成功以巨大的计算和能源成本,而训练大规模过度参数的神经网络的可伸缩性正成为AI进步的真正障碍。尽管传统反向传播通过梯度不错的传统反向传播的流行和低成本,但在理论和实践中,SGD在非凸面设置中具有高度的收敛速度。为了减轻这一成本,最近的工作提议采用替代性(牛顿型)培训方法,但收敛速度更快,尽管其每题成本更高。对于具有$ m = \ mathrm {poly}(n)$参数的典型神经网络,$ n $ datapoints in $ \ mathbb {r}^d $ of $ n $ datapoints的输入批次, Weinstein,ITCS'2021]需要$ \ sim mnd + n^3 $每次迭代。在本文中,我们提出了一种新颖的培训方法,它仅需要$ m^{1- \ alpha} n d + n^3 $摊销时间在同一过度叠加机制中,其中$ \ alpha \ in(0.01,1)$是某些固定常数。此方法依赖于神经网络的新替代视图,作为一组二进制搜索树,每个迭代都对应于修改树中节点的一小部分。我们认为,这种观点将在DNN的设计和分析中进一步应用。
translated by 谷歌翻译
对抗训练是一种广泛使用的策略,可以使神经网络具有抵抗对抗性扰动的能力。对于宽度$ m $,$ n $输入培训数据的神经网络,在$ d $ dimension中,需要$ \ omega(MND)$每次培训迭代的时间费用来进行前进和向后计算。在本文中,我们分析了具有转移的Relu激活的两层神经网络上对抗训练程序的收敛保证,并表明每次迭代的每个输入数据都只能激活$ O(M)$神经元。此外,通过应用半空间报告数据结构,我们开发了一种用于对抗培训的算法,以$ O(m n d)$ $ O(m n d)$。
translated by 谷歌翻译
训练神经网络的一种常见方法是将所有权重初始化为独立的高斯向量。我们观察到,通过将权重初始化为独立对,每对由两个相同的高斯向量组成,我们可以显着改善收敛分析。虽然已经研究了类似的技术来进行随机输入[Daniely,Neurips 2020],但尚未使用任意输入进行分析。使用此技术,我们展示了如何显着减少两层relu网络所需的神经元数量,均在逻辑损失的参数化设置不足的情况下,大约$ \ gamma^{ - 8} $ [Ji and telgarsky,ICLR, 2020]至$ \ gamma^{ - 2} $,其中$ \ gamma $表示带有神经切线内核的分离边距,以及在与平方损失的过度参数化设置中,从大约$ n^4 $ [song [song]和Yang,2019年]至$ n^2 $,隐含地改善了[Brand,Peng,Song和Weinstein,ITCS 2021]的近期运行时间。对于参数不足的设置,我们还证明了在先前工作时改善的新下限,并且在某些假设下是最好的。
translated by 谷歌翻译
The fundamental learning theory behind neural networks remains largely open. What classes of functions can neural networks actually learn? Why doesn't the trained network overfit when it is overparameterized?In this work, we prove that overparameterized neural networks can learn some notable concept classes, including two and three-layer networks with fewer parameters and smooth activations. Moreover, the learning can be simply done by SGD (stochastic gradient descent) or its variants in polynomial time using polynomially many samples. The sample complexity can also be almost independent of the number of parameters in the network.On the technique side, our analysis goes beyond the so-called NTK (neural tangent kernel) linearization of neural networks in prior works. We establish a new notion of quadratic approximation of the neural network (that can be viewed as a second-order variant of NTK), and connect it to the SGD theory of escaping saddle points.
translated by 谷歌翻译
This work studies training one-hidden-layer overparameterized ReLU networks via gradient descent in the neural tangent kernel (NTK) regime, where, differently from the previous works, the networks' biases are trainable and are initialized to some constant rather than zero. The first set of results of this work characterize the convergence of the network's gradient descent dynamics. Surprisingly, it is shown that the network after sparsification can achieve as fast convergence as the original network. The contribution over previous work is that not only the bias is allowed to be updated by gradient descent under our setting but also a finer analysis is given such that the required width to ensure the network's closeness to its NTK is improved. Secondly, the networks' generalization bound after training is provided. A width-sparsity dependence is presented which yields sparsity-dependent localized Rademacher complexity and a generalization bound matching previous analysis (up to logarithmic factors). As a by-product, if the bias initialization is chosen to be zero, the width requirement improves the previous bound for the shallow networks' generalization. Lastly, since the generalization bound has dependence on the smallest eigenvalue of the limiting NTK and the bounds from previous works yield vacuous generalization, this work further studies the least eigenvalue of the limiting NTK. Surprisingly, while it is not shown that trainable biases are necessary, trainable bias helps to identify a nice data-dependent region where a much finer analysis of the NTK's smallest eigenvalue can be conducted, which leads to a much sharper lower bound than the previously known worst-case bound and, consequently, a non-vacuous generalization bound.
translated by 谷歌翻译
我们提出了一个算法框架,用于近距离矩阵上的量子启发的经典算法,概括了Tang的突破性量子启发算法开始的一系列结果,用于推荐系统[STOC'19]。由量子线性代数算法和gily \'en,su,low和wiebe [stoc'19]的量子奇异值转换(SVT)框架[SVT)的动机[STOC'19],我们开发了SVT的经典算法合适的量子启发的采样假设。我们的结果提供了令人信服的证据,表明在相应的QRAM数据结构输入模型中,量子SVT不会产生指数量子加速。由于量子SVT框架基本上概括了量子线性代数的所有已知技术,因此我们的结果与先前工作的采样引理相结合,足以概括所有有关取消量子机器学习算法的最新结果。特别是,我们的经典SVT框架恢复并经常改善推荐系统,主成分分析,监督聚类,支持向量机器,低秩回归和半决赛程序解决方案的取消结果。我们还为汉密尔顿低级模拟和判别分析提供了其他取消化结果。我们的改进来自识别量子启发的输入模型的关键功能,该模型是所有先前量子启发的结果的核心:$ \ ell^2 $ -Norm采样可以及时近似于其尺寸近似矩阵产品。我们将所有主要结果减少到这一事实,使我们的简洁,独立和直观。
translated by 谷歌翻译
Gradient descent finds a global minimum in training deep neural networks despite the objective function being non-convex. The current paper proves gradient descent achieves zero training loss in polynomial time for a deep overparameterized neural network with residual connections (ResNet). Our analysis relies on the particular structure of the Gram matrix induced by the neural network architecture. This structure allows us to show the Gram matrix is stable throughout the training process and this stability implies the global optimality of the gradient descent algorithm. We further extend our analysis to deep residual convolutional neural networks and obtain a similar convergence result.
translated by 谷歌翻译
我们研究了用$ q $ modes $ a \ in \ mathbb {r}^{n \ times \ ldots \ times n} $的近似给定张量的问题。图$ g =(v,e)$,其中$ | v | = q $,以及张张量的集合$ \ {u_v \ mid v \ in v \} $,以$ g $指定的方式收缩以获取张量$ t $。对于$ u_v $的每种模式,对应于$ v $的边缘事件,尺寸为$ k $,我们希望找到$ u_v $,以便最小化$ t $和$ a $之间的frobenius norm距离。这概括了许多众所周知的张量网络分解,例如张量列,张量环,塔克和PEPS分解。我们大约是二进制树网络$ t'$带有$ o(q)$核的大约$ a $,因此该网络的每个边缘上的尺寸最多是$ \ widetilde {o}(k^{o(dt) } \ cdot q/\ varepsilon)$,其中$ d $是$ g $的最大度,$ t $是其树宽,因此$ \ | a -t'-t'\ | _f^2 \ leq(1 + \ Varepsilon)\ | a -t \ | _f^2 $。我们算法的运行时间为$ o(q \ cdot \ text {nnz}(a)) + n \ cdot \ text {poly}(k^{dt} q/\ varepsilon)$,其中$ \ text {nnz }(a)$是$ a $的非零条目的数量。我们的算法基于一种可能具有独立感兴趣的张量分解的新维度降低技术。我们还开发了固定参数可处理的$(1 + \ varepsilon)$ - 用于张量火车和塔克分解的近似算法,改善了歌曲的运行时间,Woodruff和Zhong(Soda,2019),并避免使用通用多项式系统求解器。我们表明,我们的算法对$ 1/\ varepsilon $具有几乎最佳的依赖性,假设没有$ O(1)$ - 近似算法的$ 2 \至4 $ norm,并且运行时间比蛮力更好。最后,我们通过可靠的损失函数和固定参数可拖动CP分解给出了塔克分解的其他结果。
translated by 谷歌翻译
许多深度学习任务必须处理图表(例如,蛋白质结构,社交网络,源代码摘要树木)。由于这些任务的重要性,人们转向图形神经网络(GNN)作为图形学习的事实方法。由于他们的令人信服的表现,GNN已经被广泛应用。不幸的是,使用GNN的一个主要障碍是GNN需要大量的时间和资源来训练。最近,在图表数据上学习的新方法是图形神经切线内核(GNTK)[du,Hou,Salakhutdinov,Poczos,Wang和Xu 19]。 GNTK是曲线图数据上神经切线核(NTK)[Jacot,Gabriel和Hipller 18](一个内核方法)的应用,并解决NTK回归等同于使用梯度下降来训练无限宽的神经网络。使用GNTK的主要好处是,类似于任何内核方法,GNTK的参数可以直接在一步中解决。这可以避免耗时的梯度下降。同时,素描越来越多地用于加速各种优化问题,包括解决内核回归。给定$ N $ Graphs的内核矩阵,在解决内核回归中使用素描可以将运行时间减少到$ O(n ^ 3)$。但遗憾的是,此类方法通常需要关于内核矩阵的广泛知识,而在GNTK的情况下,我们发现内核矩阵的构造已经是$ O(n ^ 2n ^ 4)$,假设每个图都有$ n $节点。核矩阵施工时间可以是主要的性能瓶颈,当图的大小为$ n $增加时。因此,要问的自然问题是我们是否可以加快内核矩阵构造以改善GNTK回归的端到端运行时间。本文提供了第一种构建$ O(n ^ 2n ^ 3)$运行时间的内核矩阵的算法。
translated by 谷歌翻译
我们研究了用于线性回归的主动采样算法,该算法仅旨在查询目标向量$ b \ in \ mathbb {r} ^ n $的少量条目,并将近最低限度输出到$ \ min_ {x \ In \ mathbb {r} ^ d} \ | ax-b \ | $,其中$ a \ in \ mathbb {r} ^ {n \ times d} $是一个设计矩阵和$ \ | \ cdot \ | $是一些损失函数。对于$ \ ell_p $ norm回归的任何$ 0 <p <\ idty $,我们提供了一种基于Lewis权重采样的算法,其使用只需$ \ tilde {o}输出$(1+ \ epsilon)$近似解决方案(d ^ {\ max(1,{p / 2})} / \ mathrm {poly}(\ epsilon))$查询到$ b $。我们表明,这一依赖于$ D $是最佳的,直到对数因素。我们的结果解决了陈和Derezi的最近开放问题,陈和Derezi \'{n} Ski,他们为$ \ ell_1 $ norm提供了附近的最佳界限,以及$ p \中的$ \ ell_p $回归的次优界限(1,2) $。我们还提供了$ O的第一个总灵敏度上限(D ^ {\ max \ {1,p / 2 \} \ log ^ 2 n)$以满足最多的$ p $多项式增长。这改善了Tukan,Maalouf和Feldman的最新结果。通过将此与我们的技术组合起来的$ \ ell_p $回归结果,我们获得了一个使$ \ tilde o的活动回归算法(d ^ {1+ \ max \ {1,p / 2 \}} / \ mathrm {poly}。 (\ epsilon))$疑问,回答陈和德里兹的另一个打开问题{n}滑雪。对于Huber损失的重要特殊情况,我们进一步改善了我们对$ \ tilde o的主动样本复杂性的绑定(d ^ {(1+ \ sqrt2)/ 2} / \ epsilon ^ c)$和非活跃$ \ tilde o的样本复杂性(d ^ {4-2 \ sqrt 2} / \ epsilon ^ c)$,由于克拉克森和伍德拉夫而改善了Huber回归的以前的D ^ 4 $。我们的敏感性界限具有进一步的影响,使用灵敏度采样改善了各种先前的结果,包括orlicz规范子空间嵌入和鲁棒子空间近似。最后,我们的主动采样结果为每种$ \ ell_p $ norm提供的第一个Sublinear时间算法。
translated by 谷歌翻译
大规模监督学习中的共同挑战是如何利用新的增量数据到预先训练的模型,而无需从头开始重新培训模型。受到这个问题的激励,我们重新审视动态最小二乘回归(LSR)的规范问题,其中目标是通过增量训练数据学习线性模型。在此设置,数据和标签$(\ mathbf {a} ^ {(t)},\ mathbf {b} ^ {(t)})\ in \ mathbb {r} ^ {t \ times d} \ times \ MathBB {R} ^ T $以在线方式发展($ t \ gg d $),目标是有效地将(近似)解决方案保持为$ \ min _ {\ mathbf {x} ^ {(t)}} \ | \ mathbf {a} ^ {(t)} \ mathbf {x} ^ {(t)} - \ mathbf {b} ^ {(t)} \ | \ | \ |在$中的所有$ t \。我们的主要结果是一种动态数据结构,它将任意小的恒定近似解,与摊销更新时间$ o(d ^ {1 + o(1)})$,几乎匹配静态的运行时间(草图 - 基于)解决方案。相比之下,对于精确的(甚至$ 1 / \ mathrm {poly}(n)$ - 准确性)解决方案,我们在静态和动态设置之间显示了分离,即动态LSR需要$ \ω(d ^ {2- O(1)})OMV猜想下的摊销更新时间(Henzinger等,STOC'15)。我们的数据结构在概念上简单,易于实施,并且在理论和实践中快速速度,通过对合成和现实世界数据集的实验进行了证实。
translated by 谷歌翻译
我们提出了一种输入稀疏时间抽样算法,该算法可以近似于$ q $ - 折叠的列量张量产品$ q $矩阵的量子矩阵,使用几乎最佳的样品,从(q)$因素。此外,对于数据集的$ q $倍自量量的重要特殊情况,这是学位的功能矩阵-y $ q $ polyenmial kernel,我们方法运行时的领先术语与该方法的大小成正比输入数据集,并且不依赖$ Q $。以前的技术要么在其运行时产生Poly $(Q)$的放缓,要么以$ Q $的依赖性为代价,但要以次优目标维度为代价,并在其运行时四处依赖于数据点的数量。我们的抽样技术依赖于$ q $部分相关的随机预测的集合,这些预测可以同时应用于数据集$ x $的总时间,这仅取决于$ x $的大小,同时又有其$ q $ - fold kronecker产品在$ x^{\ otimes q} $的列跨度中的任何固定向量的近乎等值线。我们还表明,我们的采样方法概括为多项式以外的其他类别的内核,例如高斯和神经切线核。
translated by 谷歌翻译
神经切线内核(NTK)已成为提供记忆,优化和泛化的强大工具,可保证深度神经网络。一项工作已经研究了NTK频谱的两层和深网,其中至少具有$ \ omega(n)$神经元的层,$ n $是培训样本的数量。此外,有越来越多的证据表明,只要参数数量超过样品数量,具有亚线性层宽度的深网是强大的记忆和优化器。因此,一个自然的开放问题是NTK是否在如此充满挑战的子线性设置中适应得很好。在本文中,我们以肯定的方式回答了这个问题。我们的主要技术贡献是对最小的深网的最小NTK特征值的下限,最小可能的过度参数化:参数的数量大约为$ \ omega(n)$,因此,神经元的数量仅为$ $ $ \ omega(\ sqrt {n})$。为了展示我们的NTK界限的适用性,我们为梯度下降训练提供了两个有关记忆能力和优化保证的结果。
translated by 谷歌翻译
kronecker回归是一个高度结构的最小二乘问题$ \ min _ {\ mathbf {x}}} \ lvert \ mathbf {k} \ mathbf {x} - \ mathbf {b} \ rvert_ \ rvert_ {2}^2 $矩阵$ \ mathbf {k} = \ mathbf {a}^{(1)} \ otimes \ cdots \ cdots \ otimes \ mathbf {a}^{(n)} $是因子矩阵的Kronecker产品。这种回归问题是在广泛使用的最小二乘(ALS)算法的每个步骤中都出现的,用于计算张量的塔克分解。我们介绍了第一个用于求解Kronecker回归的子次数算法,以避免在运行时间中避免指数项$ o(\ varepsilon^{ - n})$的$(1+ \ varepsilon)$。我们的技术结合了利用分数抽样和迭代方法。通过扩展我们对一个块是Kronecker产品的块设计矩阵的方法,我们还实现了(1)Kronecker Ridge回归的亚次级时间算法,并且(2)更新ALS中Tucker分解的因子矩阵,这不是一个不是一个纯Kronecker回归问题,从而改善了Tucker ALS的所有步骤的运行时间。我们证明了该Kronecker回归算法在合成数据和现实世界图像张量上的速度和准确性。
translated by 谷歌翻译
在本文中,我们研究了学习最适合培训数据集的浅层人工神经网络的问题。我们在过度参数化的制度中研究了这个问题,在该制度中,观测值的数量少于模型中的参数数量。我们表明,通过二次激活,训练的优化景观这种浅神经网络具有某些有利的特征,可以使用各种局部搜索启发式方法有效地找到全球最佳模型。该结果适用于输入/输出对的任意培训数据。对于可区分的激活函数,我们还表明,适当初始化的梯度下降以线性速率收敛到全球最佳模型。该结果着重于选择输入的可实现模型。根据高斯分布和标签是根据种植的重量系数生成的。
translated by 谷歌翻译
鉴于密集的浅色神经网络,我们专注于迭代创建,培训和组合随机选择的子网(代理函数),以训练完整模型。通过仔细分析$ i)$ Subnetworks的神经切线内核,II美元)$代理职能'梯度,以及$ iii)$我们如何对替代品函数进行采样并结合训练错误的线性收敛速度 - 内部一个错误区域 - 对于带有回归任务的Relu激活的过度参数化单隐藏层Perceptron。我们的结果意味着,对于固定的神经元选择概率,当我们增加代理模型的数量时,误差项会减少,并且随着我们增加每个所选子网的本地训练步骤的数量而增加。考虑的框架概括并提供了关于辍学培训,多样化辍学培训以及独立的子网培训的新见解;对于每种情况,我们提供相应的收敛结果,作为我们主要定理的冠状动脉。
translated by 谷歌翻译
尽管使用对抗性训练捍卫深度学习模型免受对抗性扰动的经验成功,但到目前为止,仍然不清楚对抗性扰动的存在背后的原则是什么,而对抗性培训对神经网络进行了什么来消除它们。在本文中,我们提出了一个称为特征纯化的原则,在其中,我们表明存在对抗性示例的原因之一是在神经网络的训练过程中,在隐藏的重量中积累了某些小型密集混合物;更重要的是,对抗训练的目标之一是去除此类混合物以净化隐藏的重量。我们介绍了CIFAR-10数据集上的两个实验,以说明这一原理,并且一个理论上的结果证明,对于某些自然分类任务,使用随机初始初始化的梯度下降训练具有RELU激活的两层神经网络确实满足了这一原理。从技术上讲,我们给出了我们最大程度的了解,第一个结果证明,以下两个可以同时保持使用RELU激活的神经网络。 (1)对原始数据的训练确实对某些半径的小对抗扰动确实不舒适。 (2)即使使用经验性扰动算法(例如FGM),实际上也可以证明对对抗相同半径的任何扰动也可以证明具有强大的良好性。最后,我们还证明了复杂性的下限,表明该网络的低复杂性模型,例如线性分类器,低度多项式或什至是神经切线核,无论使用哪种算法,都无法防御相同半径的扰动训练他们。
translated by 谷歌翻译
通过建立神经网络和内核方法之间的联系,无限宽度极限阐明了深度学习的概括和优化方面。尽管它们的重要性,但这些内核方法的实用性在大规模学习设置中受到限制,因为它们(超)二次运行时和内存复杂性。此外,大多数先前关于神经内核的作品都集中在relu激活上,这主要是由于其受欢迎程度,但这也是由于很难计算此类内核来进行一般激活。在这项工作中,我们通过提供进行一般激活的方法来克服此类困难。首先,我们编译和扩展激活功能的列表,该函数允许精确的双重激活表达式计算神经内核。当确切的计算未知时,我们提出有效近似它们的方法。我们提出了一种快速的素描方法,该方法近似于任何多种多层神经网络高斯过程(NNGP)内核和神经切线核(NTK)矩阵,以实现广泛的激活功能,这超出了常见的经过分析的RELU激活。这是通过显示如何使用任何所需激活函​​数的截短的Hermite膨胀来近似神经内核来完成的。虽然大多数先前的工作都需要单位球体上的数据点,但我们的方法不受此类限制的影响,并且适用于$ \ Mathbb {r}^d $中的任何点数据集。此外,我们为NNGP和NTK矩阵提供了一个子空间嵌入,具有接近输入的距离运行时和接近最佳的目标尺寸,该目标尺寸适用于任何\ EMPH {均质}双重激活功能,具有快速收敛的Taylor膨胀。从经验上讲,关于精确的卷积NTK(CNTK)计算,我们的方法可实现$ 106 \ times $速度,用于在CIFAR-10数据集上的5层默特网络的近似CNTK。
translated by 谷歌翻译
成功的深度学习模型往往涉及培训具有比训练样本数量更多的参数的神经网络架构。近年来已经广泛研究了这种超分子化的模型,并且通过双下降现象和通过优化景观的结构特性,从统计的角度和计算视角都建立了过分统计化的优点。尽管在过上分层的制度中深入学习架构的显着成功,但也众所周知,这些模型对其投入中的小对抗扰动感到高度脆弱。即使在普遍培训的情况下,它们在扰动输入(鲁棒泛化)上的性能也会比良性输入(标准概括)的最佳可达到的性能更糟糕。因此,必须了解如何从根本上影响稳健性的情况下如何影响鲁棒性。在本文中,我们将通过专注于随机特征回归模型(具有随机第一层权重的两层神经网络)来提供超分度化对鲁棒性的作用的精确表征。我们考虑一个制度,其中样本量,输入维度和参数的数量彼此成比例地生长,并且当模型发生前列地训练时,可以为鲁棒泛化误差导出渐近精确的公式。我们的发达理论揭示了过分统计化对鲁棒性的非竞争效果,表明对于普遍训练的随机特征模型,高度公正化可能会损害鲁棒泛化。
translated by 谷歌翻译