随机梯度Langevin动态(SGLD)是一种基本算法随机优化。 Zhang等人最近的工作。 [2017]给出了SGLD对一阶和二阶静止点的击中时间的分析。 Zhang等人的证明。 [2017]是一个两阶段的程序,通过整个Cheeger常数,这是相当复杂的,导致松散的。在本文中,利用随机微分方程的直觉,我们提供了SGLD对一阶和二阶静止点的击中时间的直接分析。我们的分析很简单。它只依赖于基本的线性代数和概率论工具。与Zhang等人相比,我们的直接分析也导致了更严格的界限。 [2017]并显示击球时间对不同因素的显着依赖性,包括维度,平滑度,噪声强度和步长效应。在适当的条件下,我们表明SGLD对一阶静止点的击中时间可以与床层无关。此外,我们应用我们的分析来研究机器学习中的几个重要的在线估计问题,包括线性回归,矩阵分解和在线PCA。
translated by 谷歌翻译
像AlexNet或VGG19这样的经典深网络架构在其“宽度”(即卷积层中的通道数量和完全连接的内层中的节点数量)中对CIFAR-10等标准数据集进行分类的程度如何?允许增加到无穷大?这些问题在理论上理解深度学习及其关于优化和泛化的奥秘的过程中成为最重要的。他们还将deeplearning与高斯过程和内核等概念联系起来。最近的一篇论文[Jacot et al。,2018]引入了神经切线核(NTK),它捕获了在梯度下降训练的无限宽度极限内完全连接的深网的行为;这个对象在其他一些近期的论文中是隐含的。随后的论文[Lee et al。,2019]给出了启发式蒙特卡罗方法来估计NTK及其扩展,卷积神经切线核(CNTK),并用它来试图理解像CIFAR-10这样的数据集上的限制行为。本文给出了第一个用于计算CNTK的高效精确算法(基于上行动态编程)以及该算法的高效GPU实现。这为基于纯核的CIFAR-10方法的性能提供了重要的新基准,比[Novak et al。,2019]报道的方法高10%,仅比相应的有限深网的性能低5%。架构(一旦关闭了batchnormalization等)。我们给出了第一个非渐近证明,表明完全训练的足够宽的网络确实等同于使用NTK的核回归预测器。我们的实验还证明,早期的Monte Carloapproximation可以显着降低性能,从而突出了我们精确内核计算的能力,我们甚至已将其应用于fullCIFAR-10数据集和20层网络。
translated by 谷歌翻译
我们研究了具有从少数潜在状态产生的丰富观察的情节MDP中的探索问题。在某些可识别性假设下,我们演示了如何通过一系列回归和聚类步骤来诱导地估计从观察到状态的映射 - 其中先前解码的潜在状态为后来的回归问题提供标签 - 并用它来构建良好的勘探政策。我们对学习状态解码函数和探索策略的质量提供有限样本保证,并通过对一类硬探索问题的经验评估来补充我们的理论。我们的方法成倍地提高了超过$ Q $ -learning的水平,即使在$ Q $ -learning已经进入潜伏状态时也是如此。
translated by 谷歌翻译
最近的作品揭示了为什么深网适合任何数据的神秘性,并且尽管非常过度参数化但仍然概括。本文分析了具有randominitialization的简单2层ReLU网络的训练和推广,并对近期工作提供了以下改进:(i)使用比最近的论文更严格的训练速度表征,解释为什么用随机标签训练神经网络导致最初在[Zhang et al。 ICLR'17。 (ii)使用数据相关复杂性度量,与网络大小无关的泛化界限。我们的衡量标准明确区分了MNIST和CIFAR上的随机标签和真实标签,如实验所示。此外,近期报纸要求样本复杂度随着大小增加(缓慢),而我们的示例复杂度完全独立于网络大小。 (iii)通过梯度下降网络实现2层ReLU的广泛平滑函数的可学习性。关键思想是通过相关内核的属性跟踪训练和概括的动态。
translated by 谷歌翻译
我们证明对于一个$ L $层完全连接的线性神经网络,如果每个隐藏层的宽度是$ \ tilde \ Omega(L \ cdot r \ cdot d _ {\ mathrm {out}} \ cdot \ kappa ^ 3 )$,其中$ r $和$ \ kappa $是输入数据的排名和条件数,$ d _ {\ mathrm {out}} $是输出维度,高斯随机初始化的梯度下降收敛于全局最小值线性率。找到$ \ epsilon $ -sopoptimal解决方案的迭代次数是$ O(\ kappa \ log(\ frac {1} {\ epsilon}))$。对于宽深线性网络的总运行时间,我们的多项式上界和窄线性神经网络的$ \ exp \ left(\ Omega \ left(L \ right)\ right)$下界[Shamir,2018]一起证明了宽层对于优化深度模型是必要的。
translated by 谷歌翻译
可以从限制常微分方程(ODE)的角度研究基于梯度的优化算法。由于成熟的ODE不能区分两种根本不同的算法--Nesterov的强凸函数加速梯度法(NAG-SC)和Polyak的重球法 - 我们研究了一种产生高分辨率ODE的替代限制过程。我们证明了这些ODEs允许一个一般的Lyapunov函数框架,用于分析连续和离散时间的收敛。我们还表明这些ODE是底层算法的更准确的替代品;特别是,他们不仅区分NAG-SC和Polyak的重球方法,而且它们允许识别我们称之为“梯度校正”的术语,该术语在NAG-SC中存在但在重球法中不存在并且是负责的对于这两种方法收敛的定性差异。我们还使用高分辨率ODE框架来研究Nesterov的(非强)凸函数的加速梯度法,揭示了迄今未知的结果--- NAG-C在倒数立方时最小化平方梯度范数。最后,通过修改NAG-C的高分辨率ODE,我们获得了新的优化方法,这些方法被证明可以保持NAG-C对于平滑凸函数的加速收敛速度。
translated by 谷歌翻译
我们研究了梯度下降对学习多层齐次函数所施加的隐式正则化,包括具有线性,ReLU或Leaky ReLU激活的前馈全连通和卷积深度神经网络。我们严格证明梯度流(即有限步长内的梯度下降)有效地强制执行不同层次的平方之间的差异在没有任何明确的规则化的情况下保持不变。该结果意味着如果权重最初很小,则梯度流自动平衡所有层的大小。利用adiscretization参数,我们分析了具有正步长的梯度下降,得到了非凸低阶非对称矩阵分解问题,没有任何正则化。受我们对梯度流的研究结果的启发,我们证明了步长为$ \ eta_t = O \ left(t ^ { - \ left(\ frac12 + \ delta \ right)} \ right)$($ 0 <\ delta \ le \)的梯度下降frac12 $)自动平衡两个低秩因子并收敛到有界全局最优。此外,对于秩为1美元的非对称矩阵分解,我们给出了更精细的分析,显示梯度下降,恒定步长在全球线性速率下收敛到全局最小值。我们认为,在学习同质模型时检验一阶算法所假设的不变性的想法可以作为研究深度模型学习优化的基本构件。
translated by 谷歌翻译
A widespread folklore for explaining the success of Convolutional Neural Networks (CNNs) is that CNNs use a more compact representation than the Fully-connected Neural Network (FNN) and thus require fewer training samples to accurately estimate their parameters. We initiate the study of rigorously characterizing the sample complexity of estimating CNNs. We show that for an m-dimensional convolutional filter with linear activation acting on a d-dimensional input, the sample complexity of achieving population prediction error of is r Opm{ 2 q 2 , whereas the sample-complexity for its FNN counterpart is lower bounded by Ωpd{ 2 q samples. Since, in typical settings m ! d, this result demonstrates the advantage of using a CNN. We further consider the sample complexity of estimating a one-hidden-layer CNN with linear activation where both the m-dimensional convolu-tional filter and the r-dimensional output weights are unknown. For this model, we show that the sample complexity is r O ` pm`rq{pm`pm`rq{ 2 ˘ when the ratio between the stride size and the filter size is a constant. For both models, we also present lower bounds showing our sample complexities are tight up to logarithmic factors. Our main tools for deriving these results are a localized empirical process analysis and a new lemma characterizing the convolutional structure. We believe that these tools may inspire further developments in understanding CNNs.
translated by 谷歌翻译
我们提供了关于过度参数化在学习神经网络中有效的原因的新理论见解。对于具有二次激活和$ n $训练数据点的$ k $隐藏节点浅网络,我们只要$ k \ ge \ sqrt {2n} $显示,过度参数化使本地搜索算法能够找到\ emph {global}一般情况下,尽管参数的数量可能超过样本量,但使用Rademacher复杂度理论,我们表明,如果数据是从常规分布中采样的,那么解决方案也可以很好地推广。高斯。为了证明$ k \ ge \ sqrt {2n} $,损失函数有benignlandscape属性,我们采用平滑分析的想法,这可能有其他应用于研究神经网络的损失表面。
translated by 谷歌翻译
我们考虑学习具有非重叠卷积层和ReLU激活的单隐层神经网络的问题,即$ f(\ mathbf {Z},\ mathbf {w},\ mathbf {a})= \ sum_j a_j \ sigma(\ mathbf {w} ^ T \ mathbf {Z} _j)$,其中卷积权重$ \ mathbf {w} $和输出权重$ \ mathbf {a} $是要学习的参数。当标签是具有固定权重$(\ mathbf {w} ^ *,\ mathbf {a} ^ *)$的相同架构的教师网络的输出时,我们用高斯输入$ \ mathbf {Z} $证明,有一个有害的局部最小化器。令人惊讶的是,在存在虚假局部最小化的情况下,随机初始化权重的权重归一化的梯度下降仍然可以证明恢复具有恒定概率的真实参数,可以通过多次重启来提升到1美元的概率。 Wealso表明,在恒定的概率下,相同的程序也可以归结为虚假的局部最小值,表明局部最小值在梯度下降的动力学中起着重要的作用。此外,水平分析表明梯度下降动力学有两个阶段:它开始缓慢,但在几次迭代后收敛得更快。
translated by 谷歌翻译