过度分辨率是指选择神经网络的宽度，使得学习算法可以在非凸训练中可被估计零损失的重要现象。现有理论建立了各种初始化策略，培训修改和宽度缩放等全局融合。特别地，最先进的结果要求宽度以二次逐步缩放，并在实践中使用的标准初始化策略下进行培训数据的数量，以获得最佳泛化性能。相比之下，最新的结果可以获得线性缩放，需要导致导致“懒惰训练”的初始化，或者仅训练单层。在这项工作中，我们提供了一个分析框架，使我们能够采用标准的初始化策略，可能避免懒惰的训练，并在基本浅色神经网络中同时培训所有层，同时获得网络宽度的理想子标缩放。我们通过Polyak-Lojasiewicz条件，平滑度和数据标准假设实现了Desiderata，并使用随机矩阵理论的工具。

在本文中，我们研究了学习最适合培训数据集的浅层人工神经网络的问题。我们在过度参数化的制度中研究了这个问题，在该制度中，观测值的数量少于模型中的参数数量。我们表明，通过二次激活，训练的优化景观这种浅神经网络具有某些有利的特征，可以使用各种局部搜索启发式方法有效地找到全球最佳模型。该结果适用于输入/输出对的任意培训数据。对于可区分的激活函数，我们还表明，适当初始化的梯度下降以线性速率收敛到全球最佳模型。该结果着重于选择输入的可实现模型。根据高斯分布和标签是根据种植的重量系数生成的。

古典统计学习理论表示，拟合太多参数导致过度舒服和性能差。尽管大量参数矛盾，但是现代深度神经网络概括了这一发现，并构成了解释深度学习成功的主要未解决的问题。随机梯度下降（SGD）引起的隐式正规被认为是重要的，但其特定原则仍然是未知的。在这项工作中，我们研究了当地最小值周围的能量景观的局部几何学如何影响SGD的统计特性，具有高斯梯度噪声。我们争辩说，在合理的假设下，局部几何形状力强制SGD保持接近低维子空间，这会引起隐式正则化并导致深神经网络的泛化误差界定更严格的界限。为了获得神经网络的泛化误差界限，我们首先引入局部最小值周围的停滞迹象，并施加人口风险的局部基本凸性财产。在这些条件下，推导出SGD的下界，以保留在这些停滞套件中。如果发生停滞，我们会导出涉及权重矩阵的光谱规范的深神经网络的泛化误差的界限，但不是网络参数的数量。从技术上讲，我们的证据基于控制SGD中的参数值的变化以及基于局部最小值周围的合适邻域的熵迭代的参数值和局部均匀收敛。我们的工作试图通过统一收敛更好地连接非凸优化和泛化分析。

最近的一项工作已经通过神经切线核（NTK）分析了深神经网络的理论特性。特别是，NTK的最小特征值与记忆能力，梯度下降算法的全球收敛性和深网的概括有关。但是，现有结果要么在两层设置中提供边界，要么假设对于多层网络，将NTK矩阵的频谱从0界限为界限。在本文中，我们在无限宽度和有限宽度的限制情况下，在最小的ntk矩阵的最小特征值上提供了紧密的界限。在有限宽度的设置中，我们认为的网络体系结构相当笼统：我们需要大致订购$ n $神经元的宽层，$ n $是数据示例的数量；剩余层宽度的缩放是任意的（取决于对数因素）。为了获得我们的结果，我们分析了各种量的独立兴趣：我们对隐藏特征矩阵的最小奇异值以及输入输出特征图的Lipschitz常数上的上限给出了下限。

Artificial neural networks are functions depending on a finite number of parameters typically encoded as weights and biases. The identification of the parameters of the network from finite samples of input-output pairs is often referred to as the \emph{teacher-student model}, and this model has represented a popular framework for understanding training and generalization. Even if the problem is NP-complete in the worst case, a rapidly growing literature -- after adding suitable distributional assumptions -- has established finite sample identification of two-layer networks with a number of neurons $m=\mathcal O(D)$, $D$ being the input dimension. For the range $D<m<D^2$ the problem becomes harder, and truly little is known for networks parametrized by biases as well. This paper fills the gap by providing constructive methods and theoretical guarantees of finite sample identification for such wider shallow networks with biases. Our approach is based on a two-step pipeline: first, we recover the direction of the weights, by exploiting second order information; next, we identify the signs by suitable algebraic evaluations, and we recover the biases by empirical risk minimization via gradient descent. Numerical results demonstrate the effectiveness of our approach.

在深度学习中的优化分析是连续的，专注于（变体）梯度流动，或离散，直接处理（变体）梯度下降。梯度流程可符合理论分析，但是风格化并忽略计算效率。它代表梯度下降的程度是深度学习理论的一个开放问题。目前的论文研究了这个问题。将梯度下降视为梯度流量初始值问题的近似数值问题，发现近似程度取决于梯度流动轨迹周围的曲率。然后，我们表明，在具有均匀激活的深度神经网络中，梯度流动轨迹享有有利的曲率，表明它们通过梯度下降近似地近似。该发现允许我们将深度线性神经网络的梯度流分析转换为保证梯度下降，其几乎肯定会在随机初始化下有效地收敛到全局最小值。实验表明，在简单的深度神经网络中，具有传统步长的梯度下降确实接近梯度流。我们假设梯度流动理论将解开深入学习背后的奥秘。

通过梯度流优化平均平衡误差，研究了功能空间中神经网络的动态。我们认为，在underParameterized制度中，网络了解由与其特征值对应的率的神经切线内核（NTK）确定的整体运算符$ t_ {k ^ \ infty} $的特征功能。例如，对于SPENTE $ S ^ {D-1} $和旋转不变的权重分配的均匀分布式数据，$ t_ {k ^ \ infty} $的特征函数是球形谐波。我们的结果可以理解为描述interparameterized制度中的光谱偏压。证据使用“阻尼偏差”的概念，其中NTK物质对具有由于阻尼因子的发生而具有大特征值的特征的偏差。除了下公共条例的制度之外，阻尼偏差可用于跟踪过度分辨率设置中经验风险的动态，允许我们在文献中延长某些结果。我们得出结论，阻尼偏差在优化平方误差时提供了动态的简单和统一的视角。

现代神经网络通常以强烈的过度构造状态运行：它们包含许多参数，即使实际标签被纯粹随机的标签代替，它们也可以插入训练集。尽管如此，他们在看不见的数据上达到了良好的预测错误：插值训练集并不会导致巨大的概括错误。此外，过度散色化似乎是有益的，因为它简化了优化景观。在这里，我们在神经切线（NT）制度中的两层神经网络的背景下研究这些现象。我们考虑了一个简单的数据模型，以及各向同性协变量的矢量，$ d $尺寸和$ n $隐藏的神经元。我们假设样本量$ n $和尺寸$ d $都很大，并且它们在多项式上相关。我们的第一个主要结果是对过份术的经验NT内核的特征结构的特征。这种表征意味着必然的表明，经验NT内核的最低特征值在$ ND \ gg n $后立即从零界限，因此网络可以在同一制度中精确插值任意标签。我们的第二个主要结果是对NT Ridge回归的概括误差的表征，包括特殊情况，最小值-ULL_2 $ NORD插值。我们证明，一旦$ nd \ gg n $，测试误差就会被内核岭回归之一相对于无限宽度内核而近似。多项式脊回归的误差依次近似后者，从而通过与激活函数的高度组件相关的“自我诱导的”项增加了正则化参数。多项式程度取决于样本量和尺寸（尤其是$ \ log n/\ log d $）。

神经切线内核（NTK）已成为提供记忆，优化和泛化的强大工具，可保证深度神经网络。一项工作已经研究了NTK频谱的两层和深网，其中至少具有$ \ omega（n）$神经元的层，$ n $是培训样本的数量。此外，有越来越多的证据表明，只要参数数量超过样品数量，具有亚线性层宽度的深网是强大的记忆和优化器。因此，一个自然的开放问题是NTK是否在如此充满挑战的子线性设置中适应得很好。在本文中，我们以肯定的方式回答了这个问题。我们的主要技术贡献是对最小的深网的最小NTK特征值的下限，最小可能的过度参数化：参数的数量大约为$ \ omega（n）$，因此，神经元的数量仅为$ $ $ \ omega（\ sqrt {n}）$。为了展示我们的NTK界限的适用性，我们为梯度下降训练提供了两个有关记忆能力和优化保证的结果。

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.

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.

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

深度学习理论的最新目标是确定神经网络如何逃脱“懒惰训练”或神经切线内核（NTK）制度，在该制度中，网络与初始化时的一阶泰勒扩展相结合。尽管NTK是最大程度地用于学习密集多项式的最佳选择（Ghorbani等，2021），但它无法学习特征，因此对于学习包括稀疏多项式（稀疏多项式）的许多类别的功能的样本复杂性较差。因此，最近的工作旨在确定基于梯度的算法比NTK更好地概括的设置。一个这样的例子是Bai和Lee（2020）的“ Quadntk”方法，该方法分析了泰勒膨胀中的二阶项。 Bai和Lee（2020）表明，二阶项可以有效地学习稀疏的多项式。但是，它牺牲了学习一般密集多项式的能力。在本文中，我们分析了两层神经网络上的梯度下降如何通过利用NTK（Montanari和Zhong，2020）的光谱表征并在Quadntk方法上构建来逃脱NTK制度。我们首先扩展了光谱分析，以确定参数空间中的“良好”方向，在该空间中我们可以在不损害概括的情况下移动。接下来，我们表明一个宽的两层神经网络可以共同使用NTK和QUADNTK来适合由密集的低度项和稀疏高度术语组成的目标功能 - NTK和Quadntk无法在他们自己的。最后，我们构建了一个正常化程序，该正规化器鼓励我们的参数向量以“良好”的方向移动，并表明正规化损失上的梯度下降将融合到全局最小化器，这也有较低的测试误差。这产生了端到端的融合和概括保证，并自行对NTK和Quadntk进行了可证明的样本复杂性的改善。

Autoencoders are a popular model in many branches of machine learning and lossy data compression. However, their fundamental limits, the performance of gradient methods and the features learnt during optimization remain poorly understood, even in the two-layer setting. In fact, earlier work has considered either linear autoencoders or specific training regimes (leading to vanishing or diverging compression rates). Our paper addresses this gap by focusing on non-linear two-layer autoencoders trained in the challenging proportional regime in which the input dimension scales linearly with the size of the representation. Our results characterize the minimizers of the population risk, and show that such minimizers are achieved by gradient methods; their structure is also unveiled, thus leading to a concise description of the features obtained via training. For the special case of a sign activation function, our analysis establishes the fundamental limits for the lossy compression of Gaussian sources via (shallow) autoencoders. Finally, while the results are proved for Gaussian data, numerical simulations on standard datasets display the universality of the theoretical predictions.

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

过度分化的深网络的泛化神秘具有有动力的努力，了解梯度下降（GD）如何收敛到概括井的低损耗解决方案。现实生活中的神经网络从小随机值初始化，并以分类的“懒惰”或“懒惰”或“NTK”的训练训练，分析更成功，以及最近的结果序列（Lyu和Li ，2020年; Chizat和Bach，2020; Ji和Telgarsky，2020）提供了理论证据，即GD可以收敛到“Max-ramin”解决方案，其零损失可能呈现良好。但是，仅在某些环境中证明了余量的全球最优性，其中神经网络无限或呈指数级宽。目前的纸张能够为具有梯度流动训练的两层泄漏的Relu网，无论宽度如何，都能为具有梯度流动的双层泄漏的Relu网建立这种全局最优性。分析还为最近的经验研究结果（Kalimeris等，2019）给出了一些理论上的理由，就GD的所谓简单的偏见为线性或其他“简单”的解决方案，特别是在训练中。在悲观方面，该论文表明这种结果是脆弱的。简单的数据操作可以使梯度流量会聚到具有次优裕度的线性分类器。

This paper investigates the stability of deep ReLU neural networks for nonparametric regression under the assumption that the noise has only a finite p-th moment. We unveil how the optimal rate of convergence depends on p, the degree of smoothness and the intrinsic dimension in a class of nonparametric regression functions with hierarchical composition structure when both the adaptive Huber loss and deep ReLU neural networks are used. This optimal rate of convergence cannot be obtained by the ordinary least squares but can be achieved by the Huber loss with a properly chosen parameter that adapts to the sample size, smoothness, and moment parameters. A concentration inequality for the adaptive Huber ReLU neural network estimators with allowable optimization errors is also derived. To establish a matching lower bound within the class of neural network estimators using the Huber loss, we employ a different strategy from the traditional route: constructing a deep ReLU network estimator that has a better empirical loss than the true function and the difference between these two functions furnishes a low bound. This step is related to the Huberization bias, yet more critically to the approximability of deep ReLU networks. As a result, we also contribute some new results on the approximation theory of deep ReLU neural networks.

通过在线规范相关性分析的问题，我们提出了\ emph {随机缩放梯度下降}（SSGD）算法，以最小化通用riemannian歧管上的随机功能的期望。 SSGD概括了投影随机梯度下降的思想，允许使用缩放的随机梯度而不是随机梯度。在特殊情况下，球形约束的特殊情况，在广义特征向量问题中产生的，我们建立了$ \ sqrt {1 / t} $的令人反感的有限样本，并表明该速率最佳最佳，直至具有积极的积极因素相关参数。在渐近方面，一种新的轨迹平均争论使我们能够实现局部渐近常态，其速率与鲁普特 - Polyak-Quaditsky平均的速率匹配。我们将这些想法携带在一个在线规范相关分析，从事文献中的第一次获得了最佳的一次性尺度算法，其具有局部渐近融合到正常性的最佳一次性尺度算法。还提供了用于合成数据的规范相关分析的数值研究。

在过分层化的模型中，随机梯度下降（SGD）中的噪声隐含地规则地规则地规范优化轨迹并确定哪个局部最小SGD收敛到。通过实证研究的推动，表明利用嘈杂标签的培训改善了泛化，我们研究了SGD与标签噪声的隐式正则化效果。我们展示了标签噪声的SGD收敛到正规化损失$ l（\θ）+ \ lambda r（\ theta）$的静止点，其中$ l（\ theta）$是培训损失，$ \ lambda $有效的正则化参数，具体取决于步骤尺寸，标签噪声的强度和批量大小，以及$ r（\ theta）$是一个惩罚剧本最小化器的显式规范器。我们的分析揭示了大型学习率的额外正则化效果，超出了线性扩展规则，这些规则惩罚了Hessian的大型特征值，而不是小小的。我们还证明了与一般损失职能，SGD的分类分类，以及具有一般噪声协方差的SGD，大大加强了Blanc等人的前后工作。全球融合和大型学习率和哈奇等人。一般模型。

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.