我们表明,具有随机性访问的神经网络可以通过扩增胜过确定性网络。我们称此类网络融合的神经网络或CFNN。我们表明,CFNN可以将$ d $维球的指标近似于任意准确性,仅使用2层和$ \ Mathcal {o}(1)$ Neurrons,其中显示了2层确定性网络所需的$ \ \欧米茄(E^d)$神经元,指数改进(ARXIV:1610.09887 [CS.LG])。我们证明了一个高度不平凡的结果,即对于几乎任何分类问题,都存在一个简单的网络,可以解决该网络权重的足够强大的发电机。结合了这些结果,我们猜测,对于大多数分类问题,有一个CFNN可以比任何确定性网络更高的精度或更少的神经元解决。最后,我们使用CIFAR10和CIFAR100上的新型CFNN体系结构实验验证了我们的证明,从基线提高了9.25 \%。
translated by 谷歌翻译
当我们扩大数据集,模型尺寸和培训时间时,深入学习方法的能力中存在越来越多的经验证据。尽管有一些关于这些资源如何调节统计能力的说法,但对它们对模型培训的计算问题的影响知之甚少。这项工作通过学习$ k $ -sparse $ n $ bits的镜头进行了探索,这是一个构成理论计算障碍的规范性问题。在这种情况下,我们发现神经网络在扩大数据集大小和运行时间时会表现出令人惊讶的相变。特别是,我们从经验上证明,通过标准培训,各种体系结构以$ n^{o(k)} $示例学习稀疏的平等,而损失(和错误)曲线在$ n^{o(k)}后突然下降。 $迭代。这些积极的结果几乎匹配已知的SQ下限,即使没有明确的稀疏性先验。我们通过理论分析阐明了这些现象的机制:我们发现性能的相变不到SGD“在黑暗中绊倒”,直到它找到了隐藏的特征集(自然算法也以$ n^中的方式运行{o(k)} $ time);取而代之的是,我们表明SGD逐渐扩大了人口梯度的傅立叶差距。
translated by 谷歌翻译
众所周知,神经网络(NNS)很容易受到对抗扰动的影响,因此有一系列旨在为NNS提供稳健性认证的工作,例如随机平滑性,从某个分布中样本平滑噪声,以证明具有稳健性的稳健性分类器。但是,正如先前的工作所表明的那样,随机平滑的认证鲁棒半径从缩放到大数据集(“维度的诅咒”)。为了克服这一障碍,我们提出了一个双重抽样随机平滑(DSR)框架,该框架利用了采样概率从额外的平滑分布来拧紧先前平滑分类器的稳健性认证。从理论上讲,在温和的假设下,我们证明DSR可以证明$ \ theta(\ sqrt d)$ robust radius $ \ ell_2 $ norm,其中$ d $是输入维度,这意味着DSR可以破坏DSR的诅咒随机平滑的维度。我们将DSR实例化为高斯平滑的广义家族,并根据采样误差提出了一种基于自定义双重优化的高效和声音计算方法。关于MNIST,CIFAR-10和Imagenet的广泛实验验证了我们的理论,并表明DSR与在不同设置下始终如一的现有基准相比,稳健的半径比现有基线更大。代码可在https://github.com/llylly/dsrs上找到。
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 谷歌翻译
众所周知,现代神经网络容易受到对抗例子的影响。为了减轻这个问题,已经提出了一系列强大的学习算法。但是,尽管通过某些方法可以通过某些方法接近稳定的训练误差,但所有现有的算法都会导致较高的鲁棒概括误差。在本文中,我们从深层神经网络的表达能力的角度提供了对这种令人困惑的现象的理论理解。具体而言,对于二进制分类数据,我们表明,对于Relu网络,虽然轻度的过度参数足以满足较高的鲁棒训练精度,但存在持续的稳健概括差距,除非神经网络的大小是指数的,却是指数的。数据维度$ d $。即使数据是线性可分离的,这意味着要实现低清洁概括错误很容易,我们仍然可以证明$ \ exp({\ omega}(d))$下限可用于鲁棒概括。通常,只要它们的VC维度最多是参数数量,我们的指数下限也适用于各种神经网络家族和其他功能类别。此外,我们为网络大小建立了$ \ exp({\ mathcal {o}}(k))$的改进的上限,当数据放在具有内在尺寸$ k $的歧管上时,以实现低鲁棒的概括错误($) k \ ll d $)。尽管如此,我们也有一个下限,相对于$ k $成倍增长 - 维度的诅咒是不可避免的。通过证明网络大小之间的指数分离以实现较低的鲁棒训练和泛化错误,我们的结果表明,鲁棒概括的硬度可能源于实用模型的表现力。
translated by 谷歌翻译
Deep neural networks can approximate functions on different types of data, from images to graphs, with varied underlying structure. This underlying structure can be viewed as the geometry of the data manifold. By extending recent advances in the theoretical understanding of neural networks, we study how a randomly initialized neural network with piece-wise linear activation splits the data manifold into regions where the neural network behaves as a linear function. We derive bounds on the density of boundary of linear regions and the distance to these boundaries on the data manifold. This leads to insights into the expressivity of randomly initialized deep neural networks on non-Euclidean data sets. We empirically corroborate our theoretical results using a toy supervised learning problem. Our experiments demonstrate that number of linear regions varies across manifolds and the results hold with changing neural network architectures. We further demonstrate how the complexity of linear regions is different on the low dimensional manifold of images as compared to the Euclidean space, using the MetFaces dataset.
translated by 谷歌翻译
这项调查的目的是介绍对深神经网络的近似特性的解释性回顾。具体而言,我们旨在了解深神经网络如何以及为什么要优于其他经典线性和非线性近似方法。这项调查包括三章。在第1章中,我们回顾了深层网络及其组成非线性结构的关键思想和概念。我们通过在解决回归和分类问题时将其作为优化问题来形式化神经网络问题。我们简要讨论用于解决优化问题的随机梯度下降算法以及用于解决优化问题的后传播公式,并解决了与神经网络性能相关的一些问题,包括选择激活功能,成本功能,过度适应问题和正则化。在第2章中,我们将重点转移到神经网络的近似理论上。我们首先介绍多项式近似中的密度概念,尤其是研究实现连续函数的Stone-WeierStrass定理。然后,在线性近似的框架内,我们回顾了馈电网络的密度和收敛速率的一些经典结果,然后在近似Sobolev函数中进行有关深网络复杂性的最新发展。在第3章中,利用非线性近似理论,我们进一步详细介绍了深度和近似网络与其他经典非线性近似方法相比的近似优势。
translated by 谷歌翻译
尽管使用对抗性训练捍卫深度学习模型免受对抗性扰动的经验成功,但到目前为止,仍然不清楚对抗性扰动的存在背后的原则是什么,而对抗性培训对神经网络进行了什么来消除它们。在本文中,我们提出了一个称为特征纯化的原则,在其中,我们表明存在对抗性示例的原因之一是在神经网络的训练过程中,在隐藏的重量中积累了某些小型密集混合物;更重要的是,对抗训练的目标之一是去除此类混合物以净化隐藏的重量。我们介绍了CIFAR-10数据集上的两个实验,以说明这一原理,并且一个理论上的结果证明,对于某些自然分类任务,使用随机初始初始化的梯度下降训练具有RELU激活的两层神经网络确实满足了这一原理。从技术上讲,我们给出了我们最大程度的了解,第一个结果证明,以下两个可以同时保持使用RELU激活的神经网络。 (1)对原始数据的训练确实对某些半径的小对抗扰动确实不舒适。 (2)即使使用经验性扰动算法(例如FGM),实际上也可以证明对对抗相同半径的任何扰动也可以证明具有强大的良好性。最后,我们还证明了复杂性的下限,表明该网络的低复杂性模型,例如线性分类器,低度多项式或什至是神经切线核,无论使用哪种算法,都无法防御相同半径的扰动训练他们。
translated by 谷歌翻译
众所周知,给定顺滑,界限 - 下面,并且可能的非透露函数,标准梯度的方法可以找到$ \ epsilon $ -stationary积分(渐变范围小于$ \ epsilon $)$ \ mathcal {O}(1 / \ epsilon ^ 2)$迭代。然而,许多重要的非渗透优化问题,例如与培训现代神经网络相关的问题,本质上是不平衡的,使这些结果不适用。在本文中,我们研究了来自Oracle复杂性视点的非透射性优化,其中假设算法仅向各个点处的函数提供访问。我们提供两个主要结果:首先,我们考虑越近$ \ epsilon $ -storationary积分的问题。这也许是找到$ \ epsilon $ -storationary积分的最自然的放松,这在非对象案例中是不可能的。我们证明,对于任何距离和epsilon $小于某些常数,无法有效地实现这种轻松的目标。我们的第二次结果涉及通过减少到平滑的优化来解决非光度非渗透优化的可能性:即,在光滑的近似值对目标函数的平滑近似下应用平滑的优化方法。对于这种方法,我们在温和的假设下证明了oracle复杂性和平滑度之间的固有权衡:一方面,可以非常有效地平滑非光滑非凸函数(例如,通过随机平滑),但具有尺寸依赖性因子在平滑度参数中,在插入标准平滑优化方法时,这会强烈影响迭代复杂性。另一方面,可以用合适的平滑方法消除这些尺寸因子,而是仅通过使平滑过程的Oracle复杂性呈指数大。
translated by 谷歌翻译
我们研究了回归中神经网络(NNS)的模型不确定性的方法。为了隔离模型不确定性的效果,我们专注于稀缺训练数据的无噪声环境。我们介绍了关于任何方法都应满足的模型不确定性的五个重要的逃亡者。但是,我们发现,建立的基准通常无法可靠地捕获其中一些逃避者,即使是贝叶斯理论要求的基准。为了解决这个问题,我们介绍了一种新方法来捕获NNS的模型不确定性,我们称之为基于神经优化的模型不确定性(NOMU)。 NOMU的主要思想是设计一个由两个连接的子NN组成的网络体系结构,一个用于模型预测,一个用于模型不确定性,并使用精心设计的损耗函数进行训练。重要的是,我们的设计执行NOMU满足我们的五个Desiderata。由于其模块化体系结构,NOMU可以为任何给定(先前训练)NN提供模型不确定性,如果访问其培训数据。我们在各种回归任务和无嘈杂的贝叶斯优化(BO)中评估NOMU,并具有昂贵的评估。在回归中,NOMU至少和最先进的方法。在BO中,Nomu甚至胜过所有考虑的基准。
translated by 谷歌翻译
深度分离结果提出了对深度神经网络过较浅的架构的好处的理论解释,建立前者具有卓越的近似能力。然而,没有已知的结果,其中更深的架构利用这种优势成为可提供的优化保证。我们证明,当数据由具有满足某些温和假设的径向对称的分布产生的数据时,梯度下降可以使用具有两层S形激活的深度2神经网络有效地学习球指示器功能,并且隐藏层固定在一起训练。由于众所周知,当使用用单层非线性的深度2网络(Safran和Shamir,2017)使用深度2网络时,球指示器难以近似于一定的重型分配,这建立了我们最好的知识,基于第一优化的分离结果,其中近似架构的近似效益在实践中可怕的。我们的证明技术依赖于随机特征方法,该方法减少了用单个神经元学习的问题,其中新工具需要在数据分布重尾时显示梯度下降的收敛。
translated by 谷歌翻译
Neural networks with random weights appear in a variety of machine learning applications, most prominently as the initialization of many deep learning algorithms and as a computationally cheap alternative to fully learned neural networks. In the present article, we enhance the theoretical understanding of random neural networks by addressing the following data separation problem: under what conditions can a random neural network make two classes $\mathcal{X}^-, \mathcal{X}^+ \subset \mathbb{R}^d$ (with positive distance) linearly separable? We show that a sufficiently large two-layer ReLU-network with standard Gaussian weights and uniformly distributed biases can solve this problem with high probability. Crucially, the number of required neurons is explicitly linked to geometric properties of the underlying sets $\mathcal{X}^-, \mathcal{X}^+$ and their mutual arrangement. This instance-specific viewpoint allows us to overcome the usual curse of dimensionality (exponential width of the layers) in non-pathological situations where the data carries low-complexity structure. We quantify the relevant structure of the data in terms of a novel notion of mutual complexity (based on a localized version of Gaussian mean width), which leads to sound and informative separation guarantees. We connect our result with related lines of work on approximation, memorization, and generalization.
translated by 谷歌翻译
众所周知,进食前馈神经网络的学习速度很慢,并且在深度学习应用中呈现了几十年的瓶颈。例如,广泛用于训练神经网络的基于梯度的学习算法在所有网络参数都必须迭代调整时往往会缓慢起作用。为了解决这个问题,研究人员和从业人员都尝试引入随机性来减少学习要求。基于Igelnik和Pao的原始结构,具有随机输入层的重量和偏见的单层神经网络在实践中取得了成功,但是缺乏必要的理论理由。在本文中,我们开始填补这一理论差距。我们提供了一个(校正的)严格证明,即Igelnik和PAO结构是连续函数在紧凑型域上连续函数的通用近似值,并且近似错误渐近地衰减,例如$ o(1/\ sqrt {n})网络节点。然后,我们将此结果扩展到非反应设置,证明人们可以在$ n $的情况下实现任何理想的近似误差,而概率很大。我们进一步调整了这种随机神经网络结构,以近似欧几里得空间的平滑,紧凑的亚曼叶量的功能,从而在渐近和非催化形式的理论保证中提供了理论保证。最后,我们通过数值实验说明了我们在歧管上的结果。
translated by 谷歌翻译
当前,随机平滑被认为是获得确切可靠分类器的最新方法。尽管其表现出色,但该方法仍与各种严重问题有关,例如``认证准确性瀑布'',认证与准确性权衡甚至公平性问题。已经提出了依赖输入的平滑方法,目的是克服这些缺陷。但是,我们证明了这些方法缺乏正式的保证,因此所产生的证书是没有道理的。我们表明,一般而言,输入依赖性平滑度遭受了维数的诅咒,迫使方差函数具有低半弹性。另一方面,我们提供了一个理论和实用的框架,即使在严格的限制下,即使在有维度的诅咒的情况下,即使在存在维度的诅咒的情况下,也可以使用依赖输入的平滑。我们提供平滑方差功能的一种混凝土设计,并在CIFAR10和MNIST上进行测试。我们的设计减轻了经典平滑的一些问题,并正式下划线,但仍需要进一步改进设计。
translated by 谷歌翻译
We show how to turn any classifier that classifies well under Gaussian noise into a new classifier that is certifiably robust to adversarial perturbations under the 2 norm. This "randomized smoothing" technique has been proposed recently in the literature, but existing guarantees are loose. We prove a tight robustness guarantee in 2 norm for smoothing with Gaussian noise. We use randomized smoothing to obtain an ImageNet classifier with e.g. a certified top-1 accuracy of 49% under adversarial perturbations with 2 norm less than 0.5 (=127/255). No certified defense has been shown feasible on ImageNet except for smoothing. On smaller-scale datasets where competing approaches to certified 2 robustness are viable, smoothing delivers higher certified accuracies. Our strong empirical results suggest that randomized smoothing is a promising direction for future research into adversarially robust classification. Code and models are available at http: //github.com/locuslab/smoothing.
translated by 谷歌翻译
彩票假设引发了通过识别大型随机初始化神经网络的稀疏子网来实现结构学习的修剪算法的快速发展。这些“胜利门票”的存在理论上已被证明,但在次优稀疏水平。当代修剪算法还在努力确定复杂的学习任务的稀疏彩票票。这个次优稀疏仅仅是存在证明和算法的文物还是修剪方法的一般限制?并且,如果存在非常稀疏的罚单,则当前算法是能够找到它们的当前算法,或者是实现有效网络压缩所需的进一步改进吗?为了系统地回答这些问题,我们推导了一个框架来植物并隐藏大型随机初始化的神经网络中的目标架构。对于机器学习中的三个共同挑战,我们手工制作极其稀疏的网络拓扑,将它们植入大型神经网络,并评估最先进的彩票修剪方法。我们发现,修剪算法的当前局限性识别极其稀疏的票证是算法的,而不是基本的性质,并且预期我们的种植框架将促进有效修剪算法的未来发展,因为我们已经解决了所提出的领域缺失基线的问题Frankle等人。
translated by 谷歌翻译
对对抗性示例强大的学习分类器已经获得了最近的关注。标准强大学习框架的主要缺点是人为强大的RADIUS $ R $,适用于所有输入。这忽略了数据可能是高度异构的事实,在这种情况下,它是合理的,在某些数据区域中,鲁棒性区域应该更大,并且在其他区域中更小。在本文中,我们通过提出名为邻域最佳分类器的新限制分类器来解决此限制,该分类通过使用最接近的支持点的标签扩展其支持之外的贝叶斯最佳分类器。然后,我们认为该分类器可能会使其稳健性区域的大小最大化,但受到等于贝叶斯的准确性的约束。然后,我们存在足够的条件,该条件下可以表示为重量函数的一般非参数方法会聚在此限制,并且显示最近的邻居和内核分类器在某些条件下满足它们。
translated by 谷歌翻译
自动编码是表示学习的一种流行方法。常规的自动编码器采用对称编码编码程序和简单的欧几里得潜在空间,以无监督的方式检测隐藏的低维结构。这项工作介绍了一个图表自动编码器,其中具有不对称编码编码过程,该过程可以包含其他半监督信息,例如类标签。除了增强使用复杂的拓扑结构和几何结构处理数据的能力外,这些模型还可以成功区分附近的数据,但仅与少量监督相交并与歧管相交。此外,该模型仅需要较低的复杂性编码器,例如局部线性投影。我们讨论了此类网络的理论近似能力,基本上取决于数据歧管的固有维度,而不是观测值的维度。我们对合成和现实世界数据的数值实验验证了所提出的模型可以有效地通过附近的多类,但分离不同类别,重叠的歧管和具有非平凡拓扑的歧管的数据。
translated by 谷歌翻译
我们研究了$ \ Mathcal {r} $的结构和统计属性 - 规范最小化由特定目标函数标记的数据集的内侧插值。$ \ MATHCAL {R} $ - 标准是两层神经网络的电感偏差的基础,最近引入了捕获网络权重大小的功能效果,与网络宽度无关。我们发现,即使有适合数据的脊函数,这些插值也是本质上的多元功能,而且$ \ Mathcal {r} $ - 规范归纳偏见不足以实现某些学习问题的统计上最佳概括。总的来说,这些结果为与实际神经网络训练有关的感应偏见提供了新的启示。
translated by 谷歌翻译
我们观察到,给定两个(兼容的)函数类别$ \ MATHCAL {f} $和$ \ MATHCAL {h} $,具有较小的容量,按其均匀覆盖的数字测量,组成类$ \ Mathcal {H} \ Circ \ Mathcal {f} $可能会变得非常大,甚至无限。然后,我们证明,在用$ \ Mathcal {h} $构成$ \ Mathcal {f} $的输出中,添加少量高斯噪声可以有效地控制$ \ Mathcal {H} \ Circ \ Mathcal { F} $,提供模块化设计的一般配方。为了证明我们的结果,我们定义了均匀覆盖随机函数数量的新概念,相对于总变异和瓦斯坦斯坦距离。我们将结果实例化,以实现多层Sigmoid神经​​网络。 MNIST数据集的初步经验结果表明,在现有统一界限上改善所需的噪声量在数值上可以忽略不计(即,元素的I.I.D. I.I.D.高斯噪声,具有标准偏差$ 10^{ - 240} $)。源代码可从https://github.com/fathollahpour/composition_noise获得。
translated by 谷歌翻译