当我们扩大数据集，模型尺寸和培训时间时，深入学习方法的能力中存在越来越多的经验证据。尽管有一些关于这些资源如何调节统计能力的说法，但对它们对模型培训的计算问题的影响知之甚少。这项工作通过学习$ k $ -sparse $ n $ bits的镜头进行了探索，这是一个构成理论计算障碍的规范性问题。在这种情况下，我们发现神经网络在扩大数据集大小和运行时间时会表现出令人惊讶的相变。特别是，我们从经验上证明，通过标准培训，各种体系结构以$ n^{o（k）} $示例学习稀疏的平等，而损失（和错误）曲线在$ n^{o（k）}后突然下降。 $迭代。这些积极的结果几乎匹配已知的SQ下限，即使没有明确的稀疏性先验。我们通过理论分析阐明了这些现象的机制：我们发现性能的相变不到SGD“在黑暗中绊倒”，直到它找到了隐藏的特征集（自然算法也以$ n^中的方式运行{o（k）} $ time）;取而代之的是，我们表明SGD逐渐扩大了人口梯度的傅立叶差距。

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.

尽管使用对抗性训练捍卫深度学习模型免受对抗性扰动的经验成功，但到目前为止，仍然不清楚对抗性扰动的存在背后的原则是什么，而对抗性培训对神经网络进行了什么来消除它们。在本文中，我们提出了一个称为特征纯化的原则，在其中，我们表明存在对抗性示例的原因之一是在神经网络的训练过程中，在隐藏的重量中积累了某些小型密集混合物；更重要的是，对抗训练的目标之一是去除此类混合物以净化隐藏的重量。我们介绍了CIFAR-10数据集上的两个实验，以说明这一原理，并且一个理论上的结果证明，对于某些自然分类任务，使用随机初始初始化的梯度下降训练具有RELU激活的两层神经网络确实满足了这一原理。从技术上讲，我们给出了我们最大程度的了解，第一个结果证明，以下两个可以同时保持使用RELU激活的神经网络。 （1）对原始数据的训练确实对某些半径的小对抗扰动确实不舒适。 （2）即使使用经验性扰动算法（例如FGM），实际上也可以证明对对抗相同半径的任何扰动也可以证明具有强大的良好性。最后，我们还证明了复杂性的下限，表明该网络的低复杂性模型，例如线性分类器，低度多项式或什至是神经切线核，无论使用哪种算法，都无法防御相同半径的扰动训练他们。

自我注意事项是一种旨在在顺序数据中建模远程相互作用的建筑主题，它推动了自然语言处理及其他方面的许多最新突破。这项工作提供了对自我发项模块的归纳偏差的理论分析。我们的重点是严格确定哪些功能和远程依赖性自我注意力障碍更喜欢代表。我们的主要结果表明，有限的 - 标志变压器网络“创建稀疏变量”：单个自我发项头可以代表输入序列的稀疏函数，样品复杂性仅与上下文长度进行对数。为了支持我们的分析，我们提出了合成实验，以探测学习稀疏的布尔功能与变压器的样本复杂性。

我们证明了由例如He等人提出的广泛使用的方法。（2015年）并使用梯度下降对最小二乘损失进行训练并不普遍。具体而言，我们描述了一大批一维数据生成分布，较高的概率下降只会发现优化景观的局部最小值不好，因为它无法将其偏离偏差远离其初始化，以零移动。。事实证明，在这些情况下，即使目标函数是非线性的，发现的网络也基本执行线性回归。我们进一步提供了数值证据，表明在实际情况下，对于某些多维分布而发生这种情况，并且随机梯度下降表现出相似的行为。我们还提供了有关初始化和优化器的选择如何影响这种行为的经验结果。

Existing analyses of neural network training often operate under the unrealistic assumption of an extremely small learning rate. This lies in stark contrast to practical wisdom and empirical studies, such as the work of J. Cohen et al. (ICLR 2021), which exhibit startling new phenomena (the "edge of stability" or "unstable convergence") and potential benefits for generalization in the large learning rate regime. Despite a flurry of recent works on this topic, however, the latter effect is still poorly understood. In this paper, we take a step towards understanding genuinely non-convex training dynamics with large learning rates by performing a detailed analysis of gradient descent for simplified models of two-layer neural networks. For these models, we provably establish the edge of stability phenomenon and discover a sharp phase transition for the step size below which the neural network fails to learn "threshold-like" neurons (i.e., neurons with a non-zero first-layer bias). This elucidates one possible mechanism by which the edge of stability can in fact lead to better generalization, as threshold neurons are basic building blocks with useful inductive bias for many tasks.

本文识别数据分布的结构属性，使得深神经网络能够分层学习。我们定义了在布尔超立方体上的功能的“楼梯”属性，该功能在沿着增加链的低阶傅里叶系数可达高阶傅里叶系数。我们证明了满足该属性的功能可以在多项式时间中使用常规神经网络上的分层随机坐标血液中学到多项式时间 - 一类网络架构和具有同质性属性的初始化。我们的分析表明，对于这种阶梯功能和神经网络，基于梯度的算法通过贪婪地组合沿网络深度的较低级别特征来了解高级功能。我们进一步回复了我们的理论结果，实验显示楼梯功能也是由具有随机梯度下降的更多标准Reset架构进行学习的。理论和实验结果都支持阶梯属性在理解基于梯度的学习的能力的情况下，与可以模仿最近所示的任何SQ或PAC算法的一般多项式网络相反，阶梯属性在理解普通网络上的能力相反。

我们证明了通过通过嘈杂梯度下降（GD）训练的神经网络学习的计算限制。每当GD培训是模棱两可的（对于许多标准架构）时，我们的结果就适用，并量化架构和数据之间所需的对齐方式，以便GD学习。作为应用程序，（i）我们表征了完全连接的网络可以在二进制HyperCube和单位球体上弱的功能，这表明Depth-2与此任务的任何其他深度一样强大；（ii）我们将与潜在的低维结构[ABM22]学习的合并楼梯必需结果扩展到均值野外状态之外。我们的技术扩展到随机梯度下降（SGD），为此，我们基于加密假设，通过完全连接的网络来显示非平凡的硬度结果。

本文介绍了在初始化和目标函数的神经网络之间``初始对齐'（inal''（inal）的概念。可以证明，如果网络和布尔目标函数没有明显的信息，则在具有归一化I.I.D的完全连接的网络上嘈杂的梯度下降。初始化不会在多项式时间内学习。因此，在体系结构设计中需要有关目标（由INAL测量）的一定程度的知识。这也为[AS20]中提出的开放问题提供了答案。结果基于在对称神经网络上的下降算法的较低限制，而没有明确了解目标函数以外的目标函数。

重要的理论工作已经确定，在特定的制度中，通过梯度下降训练的神经网络像内核方法一样行为。但是，在实践中，众所周知，神经网络非常优于其相关内核。在这项工作中，我们通过证明有一大批功能可以通过内核方法有效地学习，但是可以通过学习表示与相关的学习表示，可以轻松地学习这一差距。到目标任务。我们还证明了这些表示允许有效的转移学习，这在内核制度中是不可能的。具体而言，我们考虑学习多项式的问题，该问题仅取决于少数相关的方向，即$ f^\ star（x）= g（ux）$ withy $ u：\ r^d \ to \ r^r $ d \ gg r $。当$ f^\ star $的度数为$ p $时，众所周知，在内核制度中学习$ f^\ star $是必要的。我们的主要结果是，梯度下降学会了数据的表示，这仅取决于与$ f^\ star $相关的指示。这导致改进的样本复杂性为$ n \ asymp d^2 r + dr^p $。此外，在转移学习设置中，源和目标域中的数据分布共享相同的表示$ u $，但具有不同的多项式头部，我们表明，转移学习的流行启发式启发式启发式具有目标样本复杂性，独立于$ d $。

这项调查的目的是介绍对深神经网络的近似特性的解释性回顾。具体而言，我们旨在了解深神经网络如何以及为什么要优于其他经典线性和非线性近似方法。这项调查包括三章。在第1章中，我们回顾了深层网络及其组成非线性结构的关键思想和概念。我们通过在解决回归和分类问题时将其作为优化问题来形式化神经网络问题。我们简要讨论用于解决优化问题的随机梯度下降算法以及用于解决优化问题的后传播公式，并解决了与神经网络性能相关的一些问题，包括选择激活功能，成本功能，过度适应问题和正则化。在第2章中，我们将重点转移到神经网络的近似理论上。我们首先介绍多项式近似中的密度概念，尤其是研究实现连续函数的Stone-WeierStrass定理。然后，在线性近似的框架内，我们回顾了馈电网络的密度和收敛速率的一些经典结果，然后在近似Sobolev函数中进行有关深网络复杂性的最新发展。在第3章中，利用非线性近似理论，我们进一步详细介绍了深度和近似网络与其他经典非线性近似方法相比的近似优势。

我们研究了$ \ Mathcal {r} $的结构和统计属性 - 规范最小化由特定目标函数标记的数据集的内侧插值。$ \ MATHCAL {R} $ - 标准是两层神经网络的电感偏差的基础，最近引入了捕获网络权重大小的功能效果，与网络宽度无关。我们发现，即使有适合数据的脊函数，这些插值也是本质上的多元功能，而且$ \ Mathcal {r} $ - 规范归纳偏见不足以实现某些学习问题的统计上最佳概括。总的来说，这些结果为与实际神经网络训练有关的感应偏见提供了新的启示。

近年来，在诸如denoing，压缩感应，介入和超分辨率等反问题中使用深度学习方法的使用取得了重大进展。尽管这种作品主要是由实践算法和实验驱动的，但它也引起了各种有趣的理论问题。在本文中，我们调查了这一作品中一些突出的理论发展，尤其是生成先验，未经训练的神经网络先验和展开算法。除了总结这些主题中的现有结果外，我们还强调了一些持续的挑战和开放问题。

了解通过随机梯度下降（SGD）训练的神经网络的特性是深度学习理论的核心。在这项工作中，我们采取了平均场景，并考虑通过SGD培训的双层Relu网络，以实现一个非变量正则化回归问题。我们的主要结果是SGD偏向于简单的解决方案：在收敛时，Relu网络实现输入的分段线性图，以及“结”点的数量 - 即，Relu网络估计器的切线变化的点数 - 在两个连续的训练输入之间最多三个。特别地，随着网络的神经元的数量，通过梯度流的解决方案捕获SGD动力学，并且在收敛时，重量的分布方法接近相关的自由能量的独特最小化器，其具有GIBBS形式。我们的主要技术贡献在于分析了这一最小化器产生的估计器：我们表明其第二阶段在各地消失，除了代表“结”要点的一些特定地点。我们还提供了经验证据，即我们的理论预测的不同可能发生与数据点不同的位置的结。

近期在应用于培训深度神经网络和数据分析中的其他优化问题中的非凸优化的优化算法的兴趣增加，我们概述了最近对非凸优化优化算法的全球性能保证的理论结果。我们从古典参数开始，显示一般非凸面问题无法在合理的时间内有效地解决。然后，我们提供了一个问题列表，可以通过利用问题的结构来有效地找到全球最小化器，因为可能的问题。处理非凸性的另一种方法是放宽目标，从找到全局最小，以找到静止点或局部最小值。对于该设置，我们首先为确定性一阶方法的收敛速率提出了已知结果，然后是最佳随机和随机梯度方案的一般理论分析，以及随机第一阶方法的概述。之后，我们讨论了非常一般的非凸面问题，例如最小化$ \ alpha $ -weakly-are-convex功能和满足Polyak-lojasiewicz条件的功能，这仍然允许获得一阶的理论融合保证方法。然后，我们考虑更高阶和零序/衍生物的方法及其收敛速率，以获得非凸优化问题。

神经网络（NNS）也很难有效地学习某些问题，例如奇偶校验问题，即使对于这些问题有简单的学习算法。NNS可以自己发现学习算法吗？我们展示了一个NN体系结构，在多项式时期，可以通过恒定尺寸的学习算法来学习以及任何有效的学习算法。例如，在奇偶校验问题上，NN学习和减少行，这是一种可以简单描述的有效算法。我们的体系结构结合了层和卷积重量共享之间的重复分享，即使网络本身可能具有数万亿个节点，也将参数数量降低到常数。在实践中，我们的分析中的常数太大而无法直接有意义，但我们的工作表明，经常性和卷积NNS（RCNN）的协同作用可能比单独的任何一个更强大。

Consider the multivariate nonparametric regression model. It is shown that estimators based on sparsely connected deep neural networks with ReLU activation function and properly chosen network architecture achieve the minimax rates of convergence (up to log nfactors) under a general composition assumption on the regression function. The framework includes many well-studied structural constraints such as (generalized) additive models. While there is a lot of flexibility in the network architecture, the tuning parameter is the sparsity of the network. Specifically, we consider large networks with number of potential network parameters exceeding the sample size. The analysis gives some insights into why multilayer feedforward neural networks perform well in practice. Interestingly, for ReLU activation function the depth (number of layers) of the neural network architectures plays an important role and our theory suggests that for nonparametric regression, scaling the network depth with the sample size is natural. It is also shown that under the composition assumption wavelet estimators can only achieve suboptimal rates.

深度分离结果提出了对深度神经网络过较浅的架构的好处的理论解释，建立前者具有卓越的近似能力。然而，没有已知的结果，其中更深的架构利用这种优势成为可提供的优化保证。我们证明，当数据由具有满足某些温和假设的径向对称的分布产生的数据时，梯度下降可以使用具有两层S形激活的深度2神经网络有效地学习球指示器功能，并且隐藏层固定在一起训练。由于众所周知，当使用用单层非线性的深度2网络（Safran和Shamir，2017）使用深度2网络时，球指示器难以近似于一定的重型分配，这建立了我们最好的知识，基于第一优化的分离结果，其中近似架构的近似效益在实践中可怕的。我们的证明技术依赖于随机特征方法，该方法减少了用单个神经元学习的问题，其中新工具需要在数据分布重尾时显示梯度下降的收敛。

我们在高斯分布下使用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下限补充了我们的上限，这甚至可以为同类半空间的特殊情况而保持。

训练神经网络的一种常见方法是将所有权重初始化为独立的高斯向量。我们观察到，通过将权重初始化为独立对，每对由两个相同的高斯向量组成，我们可以显着改善收敛分析。虽然已经研究了类似的技术来进行随机输入[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]的近期运行时间。对于参数不足的设置，我们还证明了在先前工作时改善的新下限，并且在某些假设下是最好的。