尽管使用对抗性训练捍卫深度学习模型免受对抗性扰动的经验成功,但到目前为止,仍然不清楚对抗性扰动的存在背后的原则是什么,而对抗性培训对神经网络进行了什么来消除它们。在本文中,我们提出了一个称为特征纯化的原则,在其中,我们表明存在对抗性示例的原因之一是在神经网络的训练过程中,在隐藏的重量中积累了某些小型密集混合物;更重要的是,对抗训练的目标之一是去除此类混合物以净化隐藏的重量。我们介绍了CIFAR-10数据集上的两个实验,以说明这一原理,并且一个理论上的结果证明,对于某些自然分类任务,使用随机初始初始化的梯度下降训练具有RELU激活的两层神经网络确实满足了这一原理。从技术上讲,我们给出了我们最大程度的了解,第一个结果证明,以下两个可以同时保持使用RELU激活的神经网络。 (1)对原始数据的训练确实对某些半径的小对抗扰动确实不舒适。 (2)即使使用经验性扰动算法(例如FGM),实际上也可以证明对对抗相同半径的任何扰动也可以证明具有强大的良好性。最后,我们还证明了复杂性的下限,表明该网络的低复杂性模型,例如线性分类器,低度多项式或什至是神经切线核,无论使用哪种算法,都无法防御相同半径的扰动训练他们。
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 谷歌翻译
成功的深度学习模型往往涉及培训具有比训练样本数量更多的参数的神经网络架构。近年来已经广泛研究了这种超分子化的模型,并且通过双下降现象和通过优化景观的结构特性,从统计的角度和计算视角都建立了过分统计化的优点。尽管在过上分层的制度中深入学习架构的显着成功,但也众所周知,这些模型对其投入中的小对抗扰动感到高度脆弱。即使在普遍培训的情况下,它们在扰动输入(鲁棒泛化)上的性能也会比良性输入(标准概括)的最佳可达到的性能更糟糕。因此,必须了解如何从根本上影响稳健性的情况下如何影响鲁棒性。在本文中,我们将通过专注于随机特征回归模型(具有随机第一层权重的两层神经网络)来提供超分度化对鲁棒性的作用的精确表征。我们考虑一个制度,其中样本量,输入维度和参数的数量彼此成比例地生长,并且当模型发生前列地训练时,可以为鲁棒泛化误差导出渐近精确的公式。我们的发达理论揭示了过分统计化对鲁棒性的非竞争效果,表明对于普遍训练的随机特征模型,高度公正化可能会损害鲁棒泛化。
translated by 谷歌翻译
Neural networks have many successful applications, while much less theoretical understanding has been gained. Towards bridging this gap, we study the problem of learning a two-layer overparameterized ReLU neural network for multi-class classification via stochastic gradient descent (SGD) from random initialization. In the overparameterized setting, when the data comes from mixtures of wellseparated distributions, we prove that SGD learns a network with a small generalization error, albeit the network has enough capacity to fit arbitrary labels. Furthermore, the analysis provides interesting insights into several aspects of learning neural networks and can be verified based on empirical studies on synthetic data and on the MNIST dataset.
translated by 谷歌翻译
数据增强是机器学习管道的基石,但其理论基础尚不清楚。它只是人为增加数据集大小的一种方法吗?还是鼓励模型满足某些不变性?在这项工作中,我们考虑了另一个角度,我们研究了数据增强对学习过程动态的影响。我们发现,数据增强可以改变各种功能的相对重要性,从而有效地使某些信息性但难以学习的功能更有可能在学习过程中捕获。重要的是,我们表明,对于非线性模型,例如神经网络,这种效果更为明显。我们的主要贡献是对Allen-Zhu和Li [2020]最近提出的多视图数据模型中两层卷积神经网络的学习动态数据的详细分析。我们通过进一步的实验证据来补充这一分析,证明数据增加可以看作是特征操纵。
translated by 谷歌翻译
当我们扩大数据集,模型尺寸和培训时间时,深入学习方法的能力中存在越来越多的经验证据。尽管有一些关于这些资源如何调节统计能力的说法,但对它们对模型培训的计算问题的影响知之甚少。这项工作通过学习$ k $ -sparse $ n $ bits的镜头进行了探索,这是一个构成理论计算障碍的规范性问题。在这种情况下,我们发现神经网络在扩大数据集大小和运行时间时会表现出令人惊讶的相变。特别是,我们从经验上证明,通过标准培训,各种体系结构以$ n^{o(k)} $示例学习稀疏的平等,而损失(和错误)曲线在$ n^{o(k)}后突然下降。 $迭代。这些积极的结果几乎匹配已知的SQ下限,即使没有明确的稀疏性先验。我们通过理论分析阐明了这些现象的机制:我们发现性能的相变不到SGD“在黑暗中绊倒”,直到它找到了隐藏的特征集(自然算法也以$ n^中的方式运行{o(k)} $ time);取而代之的是,我们表明SGD逐渐扩大了人口梯度的傅立叶差距。
translated by 谷歌翻译
在这项工作中,我们在两层relu网络中提供了特征学习过程的表征,这些网络在随机初始化后通过梯度下降对逻辑损失进行了训练。我们考虑使用输入功能的XOR样函数生成的二进制标签的数据。我们允许不断的培训标签被对手破坏。我们表明,尽管线性分类器并不比随机猜测我们考虑的分布更好,但通过梯度下降训练的两层relu网络达到了接近标签噪声速率的概括误差。我们开发了一种新颖的证明技术,该技术表明,在初始化时,绝大多数神经元充当随机特征,仅与有用特征无关紧要,而梯度下降动力学则“放大”这些弱,随机的特征到强,有用的特征。
translated by 谷歌翻译
现代神经网络通常以强烈的过度构造状态运行:它们包含许多参数,即使实际标签被纯粹随机的标签代替,它们也可以插入训练集。尽管如此,他们在看不见的数据上达到了良好的预测错误:插值训练集并不会导致巨大的概括错误。此外,过度散色化似乎是有益的,因为它简化了优化景观。在这里,我们在神经切线(NT)制度中的两层神经网络的背景下研究这些现象。我们考虑了一个简单的数据模型,以及各向同性协变量的矢量,$ d $尺寸和$ n $隐藏的神经元。我们假设样本量$ n $和尺寸$ d $都很大,并且它们在多项式上相关。我们的第一个主要结果是对过份术的经验NT内核的特征结构的特征。这种表征意味着必然的表明,经验NT内核的最低特征值在$ ND \ gg n $后立即从零界限,因此网络可以在同一制度中精确插值任意标签。我们的第二个主要结果是对NT Ridge回归的概括误差的表征,包括特殊情况,最小值-ULL_2 $ NORD插值。我们证明,一旦$ nd \ gg n $,测试误差就会被内核岭回归之一相对于无限宽度内核而近似。多项式脊回归的误差依次近似后者,从而通过与激活函数的高度组件相关的“自我诱导的”项增加了正则化参数。多项式程度取决于样本量和尺寸(尤其是$ \ log n/\ log d $)。
translated by 谷歌翻译
我们在高斯分布下使用Massart噪声与Massart噪声进行PAC学习半个空间的问题。在Massart模型中,允许对手将每个点$ \ mathbf {x} $的标签与未知概率$ \ eta(\ mathbf {x})\ leq \ eta $,用于某些参数$ \ eta \ [0,1 / 2] $。目标是找到一个假设$ \ mathrm {opt} + \ epsilon $的错误分类错误,其中$ \ mathrm {opt} $是目标半空间的错误。此前已经在两个假设下研究了这个问题:(i)目标半空间是同质的(即,分离超平面通过原点),并且(ii)参数$ \ eta $严格小于$ 1/2 $。在此工作之前,当除去这些假设中的任何一个时,不知道非增长的界限。我们研究了一般问题并建立以下内容:对于$ \ eta <1/2 $,我们为一般半个空间提供了一个学习算法,采用样本和计算复杂度$ d ^ {o_ {\ eta}(\ log(1 / \ gamma) )))}} \ mathrm {poly}(1 / \ epsilon)$,其中$ \ gamma = \ max \ {\ epsilon,\ min \ {\ mathbf {pr} [f(\ mathbf {x})= 1], \ mathbf {pr} [f(\ mathbf {x})= -1] \} \} $是目标半空间$ f $的偏差。现有的高效算法只能处理$ \ gamma = 1/2 $的特殊情况。有趣的是,我们建立了$ d ^ {\ oomega(\ log(\ log(\ log(\ log))}}的质量匹配的下限,而是任何统计查询(SQ)算法的复杂性。对于$ \ eta = 1/2 $,我们为一般半空间提供了一个学习算法,具有样本和计算复杂度$ o_ \ epsilon(1)d ^ {o(\ log(1 / epsilon))} $。即使对于均匀半空间的子类,这个结果也是新的;均匀Massart半个空间的现有算法为$ \ eta = 1/2 $提供可持续的保证。我们与D ^ {\ omega(\ log(\ log(\ log(\ log(\ epsilon))} $的近似匹配的sq下限补充了我们的上限,这甚至可以为同类半空间的特殊情况而保持。
translated by 谷歌翻译
对抗训练是一种广泛使用的策略,可以使神经网络具有抵抗对抗性扰动的能力。对于宽度$ m $,$ n $输入培训数据的神经网络,在$ d $ dimension中,需要$ \ omega(MND)$每次培训迭代的时间费用来进行前进和向后计算。在本文中,我们分析了具有转移的Relu激活的两层神经网络上对抗训练程序的收敛保证,并表明每次迭代的每个输入数据都只能激活$ O(M)$神经元。此外,通过应用半空间报告数据结构,我们开发了一种用于对抗培训的算法,以$ O(m n d)$ $ O(m n d)$。
translated by 谷歌翻译
本文识别数据分布的结构属性,使得深神经网络能够分层学习。我们定义了在布尔超立方体上的功能的“楼梯”属性,该功能在沿着增加链的低阶傅里叶系数可达高阶傅里叶系数。我们证明了满足该属性的功能可以在多项式时间中使用常规神经网络上的分层随机坐标血液中学到多项式时间 - 一类网络架构和具有同质性属性的初始化。我们的分析表明,对于这种阶梯功能和神经网络,基于梯度的算法通过贪婪地组合沿网络深度的较低级别特征来了解高级功能。我们进一步回复了我们的理论结果,实验显示楼梯功能也是由具有随机梯度下降的更多标准Reset架构进行学习的。理论和实验结果都支持阶梯属性在理解基于梯度的学习的能力的情况下,与可以模仿最近所示的任何SQ或PAC算法的一般多项式网络相反,阶梯属性在理解普通网络上的能力相反。
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 谷歌翻译
我们考虑培训多层过参数化神经网络的问题,以最大限度地减少损失函数引起的经验风险。在过度参数化的典型设置中,网络宽度$ 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 谷歌翻译
我们研究了学习单个神经元的基本问题,即$ \ mathbf {x} \ mapsto \ sigma(\ mathbf {w} \ cdot \ cdot \ mathbf {x})$单调激活$ \ sigma $ \ sigma: \ mathbb {r} \ mapsto \ mathbb {r} $,相对于$ l_2^2 $ -loss,在存在对抗标签噪声的情况下。具体来说,我们将在$(\ mathbf {x},y)\ in \ mathbb {r}^d \ times \ times \ mathbb {r} $上给我们从$(\ mathbf {x},y)\ on a发行$ d $中给我们标记的示例。 }^\ ast \ in \ mathbb {r}^d $ achieving $ f(\ mathbf {w}^\ ast)= \ epsilon $,其中$ f(\ mathbf {w})= \ m马理bf {e} (\ mathbf {x},y)\ sim d} [(\ sigma(\ mathbf {w} \ cdot \ mathbf {x}) - y)^2] $。学习者的目标是输出假设向量$ \ mathbf {w} $,以使$ f(\ m athbb {w})= c \,\ epsilon $具有高概率,其中$ c> 1 $是通用常数。作为我们的主要贡献,我们为广泛的分布(包括对数 - 循环分布)和激活功能提供有效的恒定因素近似学习者。具体地说,对于各向同性对数凸出分布的类别,我们获得以下重要的推论:对于逻辑激活,我们获得了第一个多项式时间常数因子近似(即使在高斯分布下)。我们的算法具有样品复杂性$ \ widetilde {o}(d/\ epsilon)$,这在多毛体因子中很紧。对于relu激活,我们给出了一个有效的算法,带有样品复杂性$ \ tilde {o}(d \,\ polylog(1/\ epsilon))$。在我们工作之前,最著名的常数因子近似学习者具有样本复杂性$ \ tilde {\ omega}(d/\ epsilon)$。在这两个设置中,我们的算法很简单,在(正规)$ L_2^2 $ -LOSS上执行梯度散发。我们的算法的正确性取决于我们确定的新结构结果,表明(本质上是基本上)基础非凸损失的固定点大约是最佳的。
translated by 谷歌翻译
It has been observed in practice that applying pruning-at-initialization methods to neural networks and training the sparsified networks can not only retain the testing performance of the original dense models, but also sometimes even slightly boost the generalization performance. Theoretical understanding for such experimental observations are yet to be developed. This work makes the first attempt to study how different pruning fractions affect the model's gradient descent dynamics and generalization. Specifically, this work considers a classification task for overparameterized two-layer neural networks, where the network is randomly pruned according to different rates at the initialization. It is shown that as long as the pruning fraction is below a certain threshold, gradient descent can drive the training loss toward zero and the network exhibits good generalization performance. More surprisingly, the generalization bound gets better as the pruning fraction gets larger. To complement this positive result, this work further shows a negative result: there exists a large pruning fraction such that while gradient descent is still able to drive the training loss toward zero (by memorizing noise), the generalization performance is no better than random guessing. This further suggests that pruning can change the feature learning process, which leads to the performance drop of the pruned neural network. Up to our knowledge, this is the \textbf{first} generalization result for pruned neural networks, suggesting that pruning can improve the neural network's generalization.
translated by 谷歌翻译
近似消息传递(AMP)是解决高维统计问题的有效迭代范式。但是,当迭代次数超过$ o \ big(\ frac {\ log n} {\ log log \ log \ log n} \时big)$(带有$ n $问题维度)。为了解决这一不足,本文开发了一个非吸附框架,用于理解峰值矩阵估计中的AMP。基于AMP更新的新分解和可控的残差项,我们布置了一个分析配方,以表征在存在独立初始化的情况下AMP的有限样本行为,该过程被进一步概括以进行光谱初始化。作为提出的分析配方的两个具体后果:(i)求解$ \ mathbb {z} _2 $同步时,我们预测了频谱初始化AMP的行为,最高为$ o \ big(\ frac {n} {\ mathrm {\ mathrm { poly} \ log n} \ big)$迭代,表明该算法成功而无需随后的细化阶段(如最近由\ citet {celentano2021local}推测); (ii)我们表征了稀疏PCA中AMP的非反应性行为(在尖刺的Wigner模型中),以广泛的信噪比。
translated by 谷歌翻译
我们研究了在存在$ \ epsilon $ - 对抗异常值的高维稀疏平均值估计的问题。先前的工作为此任务获得了该任务的样本和计算有效算法,用于辅助性Subgaussian分布。在这项工作中,我们开发了第一个有效的算法,用于强大的稀疏平均值估计,而没有对协方差的先验知识。对于$ \ Mathbb r^d $上的分布,带有“认证有限”的$ t $ tum-矩和足够轻的尾巴,我们的算法达到了$ o(\ epsilon^{1-1/t})$带有样品复杂性$的错误(\ epsilon^{1-1/t}) m =(k \ log(d))^{o(t)}/\ epsilon^{2-2/t} $。对于高斯分布的特殊情况,我们的算法达到了$ \ tilde o(\ epsilon)$的接近最佳错误,带有样品复杂性$ m = o(k^4 \ mathrm {polylog}(d)(d))/\ epsilon^^ 2 $。我们的算法遵循基于方形的总和,对算法方法的证明。我们通过统计查询和低度多项式测试的下限来补充上限,提供了证据,表明我们算法实现的样本时间 - 错误权衡在质量上是最好的。
translated by 谷歌翻译
Machine learning models are often susceptible to adversarial perturbations of their inputs. Even small perturbations can cause state-of-the-art classifiers with high "standard" accuracy to produce an incorrect prediction with high confidence. To better understand this phenomenon, we study adversarially robust learning from the viewpoint of generalization. We show that already in a simple natural data model, the sample complexity of robust learning can be significantly larger than that of "standard" learning. This gap is information theoretic and holds irrespective of the training algorithm or the model family. We complement our theoretical results with experiments on popular image classification datasets and show that a similar gap exists here as well. We postulate that the difficulty of training robust classifiers stems, at least partially, from this inherently larger sample complexity.
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 谷歌翻译
在负面的感知问题中,我们给出了$ n $数据点$({\ boldsymbol x} _i,y_i)$,其中$ {\ boldsymbol x} _i $是$ d $ -densional vector和$ y_i \ in \ { + 1,-1 \} $是二进制标签。数据不是线性可分离的,因此我们满足自己的内容,以找到最大的线性分类器,具有最大的\ emph {否定}余量。换句话说,我们想找到一个单位常规矢量$ {\ boldsymbol \ theta} $,最大化$ \ min_ {i \ le n} y_i \ langle {\ boldsymbol \ theta},{\ boldsymbol x} _i \ rangle $ 。这是一个非凸优化问题(它相当于在Polytope中找到最大标准矢量),我们在两个随机模型下研究其典型属性。我们考虑比例渐近,其中$ n,d \ to \ idty $以$ n / d \ to \ delta $,并在最大边缘$ \ kappa _ {\ text {s}}(\ delta)上证明了上限和下限)$或 - 等效 - 在其逆函数$ \ delta _ {\ text {s}}(\ kappa)$。换句话说,$ \ delta _ {\ text {s}}(\ kappa)$是overparametization阈值:以$ n / d \ le \ delta _ {\ text {s}}(\ kappa) - \ varepsilon $一个分类器实现了消失的训练错误,具有高概率,而以$ n / d \ ge \ delta _ {\ text {s}}(\ kappa)+ \ varepsilon $。我们在$ \ delta _ {\ text {s}}(\ kappa)$匹配,以$ \ kappa \ to - \ idty $匹配。然后,我们分析了线性编程算法来查找解决方案,并表征相应的阈值$ \ delta _ {\ text {lin}}(\ kappa)$。我们观察插值阈值$ \ delta _ {\ text {s}}(\ kappa)$和线性编程阈值$ \ delta _ {\ text {lin {lin}}(\ kappa)$之间的差距,提出了行为的问题其他算法。
translated by 谷歌翻译