This paper presents a margin-based multiclass generalization bound for neural networks that scales with their margin-normalized spectral complexity: their Lipschitz constant, meaning the product of the spectral norms of the weight matrices, times a certain correction factor. This bound is empirically investigated for a standard AlexNet network trained with SGD on the mnist and cifar10 datasets, with both original and random labels; the bound, the Lipschitz constants, and the excess risks are all in direct correlation, suggesting both that SGD selects predictors whose complexity scales with the difficulty of the learning task, and secondly that the presented bound is sensitive to this complexity.
translated by 谷歌翻译
复合值的神经网络(CVNNS)已广泛应用于各种领域,尤其是信号处理和图像识别。然而,很少有作品关注CVNN的泛化,尽管它至关重要,以确保CVNNS在看不见的数据上的性能至关重要。本文是第一项工作,证明了复杂的神经网络的泛化。束缚尺度具有光谱复杂性,其主导因子是重量矩阵的光谱范数产物。此外,我们的工作为训练数据顺序时为CVNN提供了泛化,这也受光谱复杂度的影响。从理论上讲,这些界限通过Maey Sparsification Lemma和Dudley熵整体来源。经验上,我们通过在不同的数据集上培训复杂的卷积神经网络进行实验:Mnist,FashionMnist,CiFar-10,CiFar-100,微小想象成和IMDB。 Spearman的秩序相关系数和这些数据集上的相应P值给出了由权重矩阵光谱规范产品测量的网络的光谱复杂度,与概括能力有统计学显着的相关性。
translated by 谷歌翻译
这项工作研究了浅relu网络通过梯度下降训练的浅relu网络,在底层数据分布一般的二进制分类数据上,(最佳)贝叶斯风险不一定为零。在此设置中,表明,在早期停止的梯度下降达到人口风险在不仅仅是逻辑和错误分类损失方面,也可以在校准方面任意接近最佳,这意味着其输出的符合矩阵映射近似于真正的条件分布任意精细。此外,这种分析的必要迭代,样本和架构复杂性,并且在真实条件模型的某种复杂度测量方面都是自然的。最后,虽然没有表明需要早期停止是必要的,但是显示满足局部内插特性的任何单变量分类器是不一致的。
translated by 谷歌翻译
我们研究神经网络的基于规范的统一收敛范围,旨在密切理解它们如何受到规范约束的架构和类型的影响,对于简单的标量价值一类隐藏的一层网络,并在其中界定了输入。欧几里得规范。我们首先证明,通常,控制隐藏层重量矩阵的光谱规范不足以获得均匀的收敛保证(与网络宽度无关),而更强的Frobenius Norm Control是足够的,扩展并改善了以前的工作。在证明构造中,我们识别和分析了两个重要的设置,在这些设置中(可能令人惊讶)仅光谱规范控制就足够了:首先,当网络的激活函数足够平滑时(结果扩展到更深的网络);其次,对于某些类型的卷积网络。在后一种情况下,我们研究样品复杂性如何受到参数的影响,例如斑块之间的重叠量和斑块的总数。
translated by 谷歌翻译
这项工作确立了梯度流量(GF)和随机梯度下降(SGD)的低测试误差(SGD)在具有标准初始化的两层relu网络上,在三个方案中,关键的重量集很少旋转(自然要么是由于GF和SGD,要么是由于GF和SGD,或达到人为的约束),并利用边缘作为核心分析技术。第一个制度几乎是初始化的,特别是直到权重以$ \ mathcal {o}(\ sqrt m)$移动为止,其中$ m $表示网络宽度,这与$ \ mathcal {o}(O}(O}(O})形成鲜明对比) 1)神经切线内核(NTK)允许的重量运动;在这里显示,GF和SGD仅需要网络宽度和样本数量与NTK边缘成反比,此外,GF至少达到了NTK保证金本身,这足以建立避免距离范围目标的不良KKT点的逃脱,该点的距离逃脱了。而先前的工作只能确定不折扣但任意的边缘。第二个制度是神经塌陷(NC)设置,其中数据在于极度隔离的组中,样品复杂性尺度与组数。在这里,先前工作的贡献是对初始化的整个GF轨迹的分析。最后,如果内层的权重限制为仅在规范中变化并且无法旋转,则具有较大宽度的GF达到了全球最大边缘,并且其样品复杂度与它们的逆尺度相比;这与先前的工作相反,后者需要无限的宽度和一个棘手的双收敛假设。作为纯粹的技术贡献,这项工作开发了各种潜在功能和其他工具,希望有助于未来的工作。
translated by 谷歌翻译
Deep nets generalize well despite having more parameters than the number of training samples. Recent works try to give an explanation using PAC-Bayes and Margin-based analyses, but do not as yet result in sample complexity bounds better than naive parameter counting. The current paper shows generalization bounds that're orders of magnitude better in practice. These rely upon new succinct reparametrizations of the trained net -a compression that is explicit and efficient. These yield generalization bounds via a simple compression-based framework introduced here. Our results also provide some theoretical justification for widespread empirical success in compressing deep nets.Analysis of correctness of our compression relies upon some newly identified "noise stability"properties of trained deep nets, which are also experimentally verified. The study of these properties and resulting generalization bounds are also extended to convolutional nets, which had eluded earlier attempts on proving generalization.
translated by 谷歌翻译
我们研究了$ \ Mathcal {r} $的结构和统计属性 - 规范最小化由特定目标函数标记的数据集的内侧插值。$ \ MATHCAL {R} $ - 标准是两层神经网络的电感偏差的基础,最近引入了捕获网络权重大小的功能效果,与网络宽度无关。我们发现,即使有适合数据的脊函数,这些插值也是本质上的多元功能,而且$ \ Mathcal {r} $ - 规范归纳偏见不足以实现某些学习问题的统计上最佳概括。总的来说,这些结果为与实际神经网络训练有关的感应偏见提供了新的启示。
translated by 谷歌翻译
我们在监督分类的背景下研究深网的过剩能力。也就是说,给定对基本假设类别的能力度量(在我们的情况下,是经验性的Rademacher的复杂性),我们(先验)可以限制该类别的数量,同时在与无约束性方面保持经验误差的同时保留经验误差?为了评估现代体系结构(例如残留网络)的过剩能力,我们扩展并统一了先前的Rademacher复杂性界限,以适应功能组成和添加以及卷积的结构。我们边界中的容量驱动项是层的Lipschitz常数和卷积权重初始化的(2,1)组的范围距离。在不同任务难度的基准数据集上进行的实验表明,(1)每个任务的容量大量超过容量,并且(2)可以将容量保持在整个任务的惊人相似水平。总体而言,这表明了重量规范的可压缩性概念,这是通过重量修剪正交的经典压缩概念。
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 谷歌翻译
We present a generalization bound for feedforward neural networks with ReLU activations in terms of the product of the spectral norm of the layers and the Frobenius norm of the weights. The key ingredient is a bound on the changes in the output of a network with respect to perturbation of its weights, thereby bounding the sharpness of the network. We combine this perturbation bound with the PAC-Bayes analysis to derive the generalization bound.
translated by 谷歌翻译
由学习的迭代软阈值算法(Lista)的动机,我们介绍了一种适用于稀疏重建的一般性网络,从少数线性测量。通过在层之间允许各种重量共享度,我们为非常不同的神经网络类型提供统一分析,从复发到网络更类似于标准前馈神经网络。基于训练样本,通过经验风险最小化,我们旨在学习最佳网络参数,从而实现从其低维线性测量的最佳网络。我们通过分析由这种深网络组成的假设类的RadeMacher复杂性来衍生泛化界限,这也考虑了阈值参数。我们获得了对样本复杂性的估计,基本上只取决于参数和深度的数量。我们应用主要结果以获得几个实际示例的特定泛化界限,包括(隐式)字典学习和卷积神经网络的不同算法。
translated by 谷歌翻译
Deep neural networks are vulnerable to adversarial attacks. Ideally, a robust model shall perform well on both the perturbed training data and the unseen perturbed test data. It is found empirically that fitting perturbed training data is not hard, but generalizing to perturbed test data is quite difficult. To better understand adversarial generalization, it is of great interest to study the adversarial Rademacher complexity (ARC) of deep neural networks. However, how to bound ARC in multi-layers cases is largely unclear due to the difficulty of analyzing adversarial loss in the definition of ARC. There have been two types of attempts of ARC. One is to provide the upper bound of ARC in linear and one-hidden layer cases. However, these approaches seem hard to extend to multi-layer cases. Another is to modify the adversarial loss and provide upper bounds of Rademacher complexity on such surrogate loss in multi-layer cases. However, such variants of Rademacher complexity are not guaranteed to be bounds for meaningful robust generalization gaps (RGG). In this paper, we provide a solution to this unsolved problem. Specifically, we provide the first bound of adversarial Rademacher complexity of deep neural networks. Our approach is based on covering numbers. We provide a method to handle the robustify function classes of DNNs such that we can calculate the covering numbers. Finally, we provide experiments to study the empirical implication of our bounds and provide an analysis of poor adversarial generalization.
translated by 谷歌翻译
With a goal of understanding what drives generalization in deep networks, we consider several recently suggested explanations, including norm-based control, sharpness and robustness. We study how these measures can ensure generalization, highlighting the importance of scale normalization, and making a connection between sharpness and PAC-Bayes theory. We then investigate how well the measures explain different observed phenomena.
translated by 谷歌翻译
这项工作为线性预测指标上的迭代固定点方法提供了测试误差范围 - 特别是随机和批次镜下降(MD)和随机时间差学习(TD),并具有两个核心贡献:(a)一种单个证明技术尽管没有预测,正则化或任何等效物,即使Optima具有较大或无限的规范,也可以给予高概率保证,以实现四足动物的损失(例如,提供平方和物流损失的统一处理); (b)不取决于全局问题结构(例如条件数和最大利润率)的本地适应率,而是基于可能遭受一些小额测试误差的低规范预测因子的性质。证明技术是一个基本和多功能的耦合参数,在以下设置中进行了证明:在可实现的情况下随机MD;一般马尔可夫数据的随机MD;一般IID数据的批量MD;重尾数据的随机MD(仍然没有预测);马尔可夫链上的随机TD(所有先前的随机TD边界都在预期)。
translated by 谷歌翻译
由于其出色的近似功率和泛化能力,物理知识的神经网络(PINNS)已成为求解高维局部微分方程(PDE)的流行选择。最近,基于域分解方法的扩展Pinns(Xpinns)由于其在模拟多尺度和多体问题问题及其平行化方面的有效性而引起了相当大的关注。但是,对其融合和泛化特性的理论理解仍未开发。在这项研究中,我们迈出了了解XPinns优于拼接的方式和当Xpinns差异的初步步骤。具体地,对于一般多层PinNS和Xpinn,我们首先通过PDE问题中的目标函数的复杂性提供先前的泛化,并且在优化之后通过网络的后矩阵规范结合。此外,根据我们的界限,我们分析了Xpinns改善泛化的条件。具体地,我们的理论表明,XPinn的关键构建块,即域分解,介绍了泛化的权衡。一方面,Xpinns将复杂的PDE解决方案分解为几个简单的部分,这降低了学习每个部分所需的复杂性并提高泛化。另一方面,分解导致每个子域内可用的训练数据较少,因此这种模型通常容易过度拟合,并且可能变得不那么广泛。经验上,我们选择五个PDE来显示XPinns比Pinns更好,类似于或更差,因此证明和证明我们的新理论。
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 谷歌翻译
古典统计学习理论表示,拟合太多参数导致过度舒服和性能差。尽管大量参数矛盾,但是现代深度神经网络概括了这一发现,并构成了解释深度学习成功的主要未解决的问题。随机梯度下降(SGD)引起的隐式正规被认为是重要的,但其特定原则仍然是未知的。在这项工作中,我们研究了当地最小值周围的能量景观的局部几何学如何影响SGD的统计特性,具有高斯梯度噪声。我们争辩说,在合理的假设下,局部几何形状力强制SGD保持接近低维子空间,这会引起隐式正则化并导致深神经网络的泛化误差界定更严格的界限。为了获得神经网络的泛化误差界限,我们首先引入局部最小值周围的停滞迹象,并施加人口风险的局部基本凸性财产。在这些条件下,推导出SGD的下界,以保留在这些停滞套件中。如果发生停滞,我们会导出涉及权重矩阵的光谱规范的深神经网络的泛化误差的界限,但不是网络参数的数量。从技术上讲,我们的证据基于控制SGD中的参数值的变化以及基于局部最小值周围的合适邻域的熵迭代的参数值和局部均匀收敛。我们的工作试图通过统一收敛更好地连接非凸优化和泛化分析。
translated by 谷歌翻译
我们使用边缘赋予易于思考Pac-Bayesian界的一般配方,临界成分是我们随机预测集中在某种程度上集中。我们开发的工具直接导致各种分类器的裕度界限,包括线性预测 - 一个类,包括升高和支持向量机 - 单隐藏层神经网络,具有异常\(\ ERF \)激活功能,以及深度释放网络。此外,我们延伸到部分易碎的预测器,其中只去除一些随机性,让我们延伸到我们预测器的浓度特性否则差的情况。
translated by 谷歌翻译
在深度学习中的优化分析是连续的,专注于(变体)梯度流动,或离散,直接处理(变体)梯度下降。梯度流程可符合理论分析,但是风格化并忽略计算效率。它代表梯度下降的程度是深度学习理论的一个开放问题。目前的论文研究了这个问题。将梯度下降视为梯度流量初始值问题的近似数值问题,发现近似程度取决于梯度流动轨迹周围的曲率。然后,我们表明,在具有均匀激活的深度神经网络中,梯度流动轨迹享有有利的曲率,表明它们通过梯度下降近似地近似。该发现允许我们将深度线性神经网络的梯度流分析转换为保证梯度下降,其几乎肯定会在随机初始化下有效地收敛到全局最小值。实验表明,在简单的深度神经网络中,具有传统步长的梯度下降确实接近梯度流。我们假设梯度流动理论将解开深入学习背后的奥秘。
translated by 谷歌翻译
本文证明了鲁棒性意味着通过数据依赖性的概括界限进行概括。结果,鲁棒性和概括被证明是以数据依赖性方式紧密连接的。我们的界限改善了以前的两个方向的界限,以解决自2010年以来几乎没有发展的开放问题。第一个是减少对覆盖码的依赖。第二个是消除对假设空间的依赖性。我们提供了几个示例,包括套索和深度学习的例子,其中我们的界限被证明是可取的。关于现实世界数据和理论模型的实验表明,在各种情况下的近乎指数改进。为了实现这些改进,我们不需要关于未知分布的其他假设。取而代之的是,我们仅包含训练样本的可观察到的可计算特性。一个关键的技术创新是对多项式随机变量的改善浓度,它超出了鲁棒性和泛化。
translated by 谷歌翻译