深度神经网络和其他现代机器学习模型的培训通常包括解决高维且受大规模数据约束的非凸优化问题。在这里，基于动量的随机优化算法在近年来变得尤其流行。随机性来自数据亚采样，从而降低了计算成本。此外，动量和随机性都应该有助于算法克服当地的最小化器，并希望在全球范围内融合。从理论上讲，这种随机性和动量的结合被糟糕地理解。在这项工作中，我们建议并分析具有动量的随机梯度下降的连续时间模型。该模型是一个分段确定的马尔可夫过程，它通过阻尼不足的动态系统和通过动力学系统的随机切换来代表粒子运动。在我们的分析中，我们研究了长期限制，子采样到无填充采样极限以及动量到非摩托车的限制。我们对随着时间的推移降低动量的情况特别感兴趣：直觉上，动量有助于在算法的初始阶段克服局部最小值，但禁止后来快速收敛到全球最小化器。在凸度的假设下，当降低随时间的动量时，我们显示了动力学系统与全局最小化器的收敛性，并让子采样率转移到无穷大。然后，我们提出了一个稳定的，合成的离散方案，以从我们的连续时间动力学系统中构造算法。在数值实验中，我们研究了我们在凸面和非凸测试问题中的离散方案。此外，我们训练卷积神经网络解决CIFAR-10图像分类问题。在这里，与动量相比，我们的算法与随机梯度下降相比达到了竞争性结果。

连续数据的优化问题出现在，例如强大的机器学习，功能数据分析和变分推理。这里，目标函数被给出为一个（连续）索引目标函数的系列 - 相对于概率测量集成的族聚集。这些问题通常可以通过随机优化方法解决：在随机切换指标执行关于索引目标函数的优化步骤。在这项工作中，我们研究了随机梯度下降算法的连续时间变量，以进行连续数据的优化问题。该所谓的随机梯度过程包括最小化耦合与确定索引的连续时间索引过程的索引目标函数的梯度流程。索引过程是例如，反射扩散，纯跳跃过程或紧凑空间上的其他L evy过程。因此，我们研究了用于连续数据空间的多种采样模式，并允许在算法的运行时进行模拟或流式流的数据。我们分析了随机梯度过程的近似性质，并在恒定下进行了长时间行为和遍历的学习率。我们以噪声功能数据的多项式回归问题以及物理知识的神经网络在多项式回归问题中结束了随机梯度过程的适用性。

本文评价用机器学习问题的数值优化方法。由于机器学习模型是高度参数化的，我们专注于适合高维优化的方法。我们在二次模型上构建直觉，以确定哪种方法适用于非凸优化，并在凸函数上开发用于这种方法的凸起函数。随着随机梯度下降和动量方法的这种理论基础，我们试图解释为什么机器学习领域通常使用的方法非常成功。除了解释成功的启发式之外，最后一章还提供了对更多理论方法的广泛审查，这在实践中并不像惯例。所以在某些情况下，这项工作试图回答这个问题：为什么默认值中包含的默认TensorFlow优化器？

随机梯度算法在大规模学习和推理问题中广泛用于优化和采样。但是，实际上，调整这些算法通常是使用启发式和反复试验而不是严格的，可概括的理论来完成的。为了解决理论和实践之间的这一差距，我们通过表征具有固定步长的非常通用的预处理随机梯度算法的迭代术的大样本行为来对调整参数的效果进行新的见解。在优化设置中，我们的结果表明，具有较大固定步长的迭代平均值可能会导致（局部）M-静态器的统计效率近似。在抽样环境中，我们的结果表明，通过适当的调整参数选择，限制固定协方差可以与Bernstein匹配 - 后验的von Mises限制，对模型错误指定后验的调整或MLE的渐近分布；而幼稚的调整极限与这些都不相对应。此外，我们认为可以在数据集对固定数量的通行证后获得基本独立的样本。我们使用模拟和真实数据通过多个实验来验证渐近样结果。总体而言，我们证明具有恒定步长的正确调整的随机梯度算法为获得点估计或后部样品提供了计算上有效且统计上健壮的方法。

We consider stochastic gradient descents on the space of large symmetric matrices of suitable functions that are invariant under permuting the rows and columns using the same permutation. We establish deterministic limits of these random curves as the dimensions of the matrices go to infinity while the entries remain bounded. Under a "small noise" assumption the limit is shown to be the gradient flow of functions on graphons whose existence was established in arXiv:2111.09459. We also consider limits of stochastic gradient descents with added properly scaled reflected Brownian noise. The limiting curve of graphons is characterized by a family of stochastic differential equations with reflections and can be thought of as an extension of the classical McKean-Vlasov limit for interacting diffusions. The proofs introduce a family of infinite-dimensional exchangeable arrays of reflected diffusions and a novel notion of propagation of chaos for large matrices of interacting diffusions.

变性推理（VI）为基于传统的采样方法提供了一种吸引人的替代方法，用于实施贝叶斯推断，因为其概念性的简单性，统计准确性和计算可扩展性。然而，常见的变分近似方案（例如平均场（MF）近似）需要某些共轭结构以促进有效的计算，这可能会增加不必要的限制对可行的先验分布家族，并对变异近似族对差异进行进一步的限制。在这项工作中，我们开发了一个通用计算框架，用于实施MF-VI VIA WASSERSTEIN梯度流（WGF），这是概率度量空间上的梯度流。当专门针对贝叶斯潜在变量模型时，我们将分析基于时间消化的WGF交替最小化方案的算法收敛，用于实现MF近似。特别是，所提出的算法类似于EM算法的分布版本，包括更新潜在变量变异分布的E step以及在参数的变异分布上进行最陡峭下降的m step。我们的理论分析依赖于概率度量空间中的最佳运输理论和细分微积分。我们证明了时间限制的WGF的指数收敛性，以最大程度地减少普通大地测量学严格的凸度的通用物镜功能。我们还提供了通过使用时间限制的WGF的固定点方程从MF近似获得的变异分布的指数收缩的新证明。我们将方法和理论应用于两个经典的贝叶斯潜在变量模型，即高斯混合模型和回归模型的混合物。还进行了数值实验，以补充这两个模型下的理论发现。

在一个拟合训练数据的深度神经网络（NN）中找到参数是一个非渗透优化问题，但基本的一阶优化方法（梯度下降）在许多实际情况下，具有完美拟合（零损失）的全局优化器。我们在限制性制度中检查残留神经网络（Reset）的剩余神经网络（Reset）的情况的这种现象，其中每个层（宽度）的层数（深度）和权重的数量均转到无穷大。首先，我们使用平均场限制参数来证明参数训练的梯度下降成为概率分布的梯度流，其特征在于大NN限制中的部分微分方程（PDE）。接下来，我们表明，在某些假设下，PDE的解决方案在训练时间内收敛到零损失解决方案。这些结果表明，如果Reset足够大，则reset的培训给出了近零损失。我们给出了减少给定阈值以下低于给定阈值的损失所需的深度和宽度的估计值。

在本文中，我们提供了一种新颖的方法来分析标签开关的动力学模型，该模型用于可以在不同能量景观中随机切换的粒子系统。除了生物学和物理学方面的问题外，我们还证明了随机梯度下降是机器学习中最受欢迎的技术，在这种情况下，可以在考虑及时的变体时可以理解。我们的分析集中在外部电位集合中的进化情况下，我们为此提供了有关进化以及固定问题的分析和数值结果。

了解训练算法的隐性偏见对于解释过多散热性神经网络的成功至关重要。在本文中，我们研究了标签噪声在通过其连续时间版本的四次参数化模型的训练动力学中的作用。我们明确表征由随机流选择的解决方案，并证明它隐含地解决了套索程序。为了充分完成我们的分析，我们为动力学提供非沉积收敛保证以及支持恢复的条件。我们还提供了支持我们理论主张的实验结果。我们的发现强调了一个事实，即结构化噪声可以引起更好的概括，并有助于解释在实践中观察到的随机动力学的更大性能。

找到Reset中的参数的最佳配置是一个非凸显最小化问题，但一阶方法尽管如此，找到了过度分辨率制度的全局最优。通过将Reset的训练过程转化为梯度流部分微分方程（PDE）和检查该限制过程的收敛性能，我们研究了这种现象。假设激活函数为2美元 - 最佳或部分$ 1 $-homerence;正则Relu满足后一种条件。我们表明，如果Reset足够大，则深度和宽度根据代数上的准确性和置信水平，一阶优化方法可以找到适合培训数据的全局最小化器。

We introduce a class of first-order methods for smooth constrained optimization that are based on an analogy to non-smooth dynamical systems. Two distinctive features of our approach are that (i) projections or optimizations over the entire feasible set are avoided, in stark contrast to projected gradient methods or the Frank-Wolfe method, and (ii) iterates are allowed to become infeasible, which differs from active set or feasible direction methods, where the descent motion stops as soon as a new constraint is encountered. The resulting algorithmic procedure is simple to implement even when constraints are nonlinear, and is suitable for large-scale constrained optimization problems in which the feasible set fails to have a simple structure. The key underlying idea is that constraints are expressed in terms of velocities instead of positions, which has the algorithmic consequence that optimizations over feasible sets at each iteration are replaced with optimizations over local, sparse convex approximations. In particular, this means that at each iteration only constraints that are violated are taken into account. The result is a simplified suite of algorithms and an expanded range of possible applications in machine learning.

我们研究了具有有限和结构的平滑非凸化优化问题的随机重新洗脱（RR）方法。虽然该方法在诸如神经网络的训练之类的实践中广泛利用，但其会聚行为仅在几个有限的环境中被理解。在本文中，在众所周知的Kurdyka-LojasiewiCz（KL）不等式下，我们建立了具有适当递减步长尺寸的RR的强极限点收敛结果，即，RR产生的整个迭代序列是会聚并会聚到单个静止点几乎肯定的感觉。 In addition, we derive the corresponding rate of convergence, depending on the KL exponent and the suitably selected diminishing step sizes.当KL指数在$ [0，\ FRAC12] $以$ [0，\ FRAC12] $时，收敛率以$ \ mathcal {o}（t ^ { - 1}）$的速率计算，以$ t $ counting迭代号。当KL指数属于$（\ FRAC12,1）$时，我们的派生收敛速率是FORM $ \ MATHCAL {O}（T ^ { - Q}）$，$ Q \ IN（0,1）$取决于在KL指数上。基于标准的KL不等式的收敛分析框架仅适用于具有某种阶段性的算法。我们对基于KL不等式的步长尺寸减少的非下降RR方法进行了新的收敛性分析，这概括了标准KL框架。我们总结了我们在非正式分析框架中的主要步骤和核心思想，这些框架是独立的兴趣。作为本框架的直接应用，我们还建立了类似的强极限点收敛结果，为重组的近端点法。

遵循与[SSJ20]相同的常规，我们继续在本文中介绍具有动量（SGD）的随机梯度下降的理论分析。不同的是，对于具有动量的SGD，我们证明了这是两个超参数在一起，学习率和动量系数，它在非convex优化中的线性收敛速率起着重要作用。我们的分析基于使用超参数依赖性随机微分方程（HP依赖性SDE），该方程是SGD的连续替代，并具有动量。同样，我们通过动量建立了SGD连续时间公式的线性收敛，并通过分析Kramers-Fokker-Planck操作员的光谱来获得最佳线性速率的显式表达。相比之下，我们证明，仅在引入动量时，仅在学习率方面的最佳线性收敛速率和SGD的最终差距如何随着动量系数从零增加到一个而变化。然后，我们提出了一种数学解释，为什么具有动量的SGD比在实践中比标准SGD更快，更强大的学习率收敛。最后，我们显示了在噪声存在下的Nesterov动量与标准动量没有根本差异。

了解随机梯度下降（SGD）的隐式偏见是深度学习的关键挑战之一，尤其是对于过度透明的模型，损失功能的局部最小化$ l $可以形成多种多样的模型。从直觉上讲，SGD $ \ eta $的学习率很小，SGD跟踪梯度下降（GD），直到它接近这种歧管为止，梯度噪声阻止了进一步的收敛。在这样的政权中，Blanc等人。 （2020）证明，带有标签噪声的SGD局部降低了常规术语，损失的清晰度，$ \ mathrm {tr} [\ nabla^2 l] $。当前的论文通过调整Katzenberger（1991）的想法提供了一个总体框架。它原则上允许使用随机微分方程（SDE）描述参数的限制动力学的SGD围绕此歧管的正规化效应（即“隐式偏见”）的正则化效应，这是由损失共同确定的功能和噪声协方差。这产生了一些新的结果：（1）与Blanc等人的局部分析相比，对$ \ eta^{ - 2} $ steps有效的隐性偏差进行了全局分析。 （2020）仅适用于$ \ eta^{ - 1.6} $ steps和（2）允许任意噪声协方差。作为一个应用程序，我们以任意大的初始化显示，标签噪声SGD始终可以逃脱内核制度，并且仅需要$ o（\ kappa \ ln d）$样本用于学习$ \ kappa $ -sparse $ -sparse yroverparame parametrized linearized Linear Modal in $ \ Mathbb {r}^d $（Woodworth等，2020），而GD在内核制度中初始化的GD需要$ \ omega（d）$样本。该上限是最小值的最佳，并改善了先前的$ \ tilde {o}（\ kappa^2）$上限（Haochen等，2020）。

在负面的感知问题中，我们给出了$ n $数据点$（{\ boldsymbol x} _i，y_i）$，其中$ {\ boldsymbol x} _i $是$ d $ -densional vector和$ y_i \ in \ { + 1，-1 \} $是二进制标签。数据不是线性可分离的，因此我们满足自己的内容，以找到最大的线性分类器，具有最大的\ emph {否定}余量。换句话说，我们想找到一个单位常规矢量$ {\ boldsymbol \ theta} $，最大化$ \ min_ {i \ le n} y_i \ langle {\ boldsymbol \ theta}，{\ boldsymbol x} _i \ rangle $ 。这是一个非凸优化问题（它相当于在Polytope中找到最大标准矢量），我们在两个随机模型下研究其典型属性。我们考虑比例渐近，其中$ n，d \ to \ idty $以$ n / d \ to \ delta $，并在最大边缘$ \ kappa _ {\ text {s}}（\ delta）上证明了上限和下限）$或 - 等效 - 在其逆函数$ \ delta _ {\ text {s}}（\ kappa）$。换句话说，$ \ delta _ {\ text {s}}（\ kappa）$是overparametization阈值：以$ n / d \ le \ delta _ {\ text {s}}（\ kappa） - \ varepsilon $一个分类器实现了消失的训练错误，具有高概率，而以$ n / d \ ge \ delta _ {\ text {s}}（\ kappa）+ \ varepsilon $。我们在$ \ delta _ {\ text {s}}（\ kappa）$匹配，以$ \ kappa \ to - \ idty $匹配。然后，我们分析了线性编程算法来查找解决方案，并表征相应的阈值$ \ delta _ {\ text {lin}}（\ kappa）$。我们观察插值阈值$ \ delta _ {\ text {s}}（\ kappa）$和线性编程阈值$ \ delta _ {\ text {lin {lin}}（\ kappa）$之间的差距，提出了行为的问题其他算法。

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

在当前文献中，随机梯度下降（SGD）的扩散近似仅在有限的时间间隔内有效。在本文中，我们仅假设预期损失是强烈的凸和其他轻度条件，建立了SGD的均匀扩散近似值，而无需假设每个随机损耗函数的凸度。主要技术是建立向后kolmogorov方程的溶液衍生物的指数衰减速率。均匀的近似近似使我们能够通过连续的随机微分方程（SDE）研究SGD的渐近行为，即使随机目标函数$ f（\ cdot; \ xi）$不是强烈的凸。

在本文中，我们重新审视了私人经验风险最小化（DP-erm）和差异私有随机凸优化（DP-SCO）的问题。我们表明，来自统计物理学（Langevin Exfusion（LD））的经过良好研究的连续时间算法同时为DP-SCO和DP-SCO提供了最佳的隐私/实用性权衡，$ \ epsilon $ -DP和$ $ \ epsilon $ -DP和$ （\ epsilon，\ delta）$ - dp均用于凸和强烈凸损失函数。我们为LD提供新的时间和尺寸独立统一稳定性，并使用我们为$ \ epsilon $ -DP提供相应的最佳超额人口风险保证。 $ \ epsilon $ -DP的DP-SCO保证的一个重要属性是，它们将非私人最佳界限匹配为$ \ epsilon \与\ infty $。在此过程中，我们提供了各种技术工具，这些工具可能引起独立的关注：i）在两个相邻数据集上运行损失功能时，一个新的r \'enyi Divergence绑定了LD，ii）最后一个过多的经验风险范围迭代LD，类似于Shamir和Zhang的嘈杂随机梯度下降（SGD）和iii）的LD，对LD进行了两期多余的风险分析，其中第一阶段是当扩散在任何合理意义上都没有在任何合理意义上融合到固定分布时，在第二阶段扩散已收敛到吉布斯分布的变体。我们的普遍性结果至关重要地依赖于LD的动力学。当它融合到固定分布时，我们获得了$ \ epsilon $ -DP的最佳界限。当它仅在很短的时间内运行$ \ propto 1/p $时，我们在$（\ epsilon，\ delta）$ -DP下获得最佳界限。在这里，$ p $是模型空间的维度。

本文涉及由马尔可夫噪声驱动的随机近似的收敛和渐近统计：$$ \ theta_ {n + 1} = \ theta_n + \ alpha_ {n + 1} f（\ theta_n，\ phi_ {n + 1}）\， ，\ quad n \ ge 0，$$，其中每个$ \ theta_n \ in \ re ^ d $，$ \ {\ phi_n \} $是一般状态空间x上的马尔可夫链，静止分配$ \ pi $和$ f：\ re ^ d \ times \ text {x} \ to \ re ^ d $。除了在$ f $的标准lipschitz边界，以及消失的步骤大小序列$ \ {\ alpha_n \ \} $的条件外，假设相关ode是全局渐近稳定的静止点表示$ \ theta ^ * $ ，其中$ \ bar f（\ theta）= e [f（\ theta，\ phi）] $ with $ \ phi \ sim \ pi $。而且，ode @ $ \ infty $ virect with advoore字段，$$ \ bar f_ \ idty（\ theta）：= \ lim_ {r \ to \ infty} r ^ { - 1} \ bar f（r \ theta）\ ,, \ qquad \ theta \ in \ re ^ d，$$是渐近稳定的。主要贡献总结如下：（i）如果$ \ phi $是几何ergodic，则序列$ \ theta $是融合的，并且在$ f $兼容兼容的界限。剩余的结果是在马尔可夫链的更强大假设下建立：Donsker-varadhan Lyapunov漂移条件的稍微弱版本（DV3）。 （ii）为联合过程$ \ {\ theta_n，\ phi_n \} $构建Lyapunov函数，这意味着$ \ {\ theta_n \} $ in $ l_4 $的融合。 （iii）建立了功能性CLT，以及归一化误差$ z_n：=（\ theta_n- \ theta ^ *）/ \ sqrt {\ alpha_n} $的常规一维CLT。时刻界限结合了CLT暗示了归一化协方差的收敛，$$ \ lim_ {n \ to \ infty} e [z_n z_n ^ t] = \ sigma_ \ theta，$$在$ \ sigma_ \ theta $ where asbptotic协方差出现在CLT中。 （iv）提供了一个例子，其中马尔可夫链$ \ phi $是几何ergodic，但它不满足（dv3）。虽然算法收敛，但第二个时刻是无限的。

最近，随机梯度下降（SGD）及其变体已成为机器学习（ML）问题大规模优化的主要方法。已经提出了各种策略来调整步骤尺寸，从自适应步骤大小到启发式方法，以更改每次迭代中的步骤大小。此外，动力已被广泛用于ML任务以加速训练过程。然而，我们对它们的理论理解存在差距。在这项工作中，我们开始通过为一些启发式优化方法提供正式保证并提出改进的算法来缩小这一差距。首先，我们分析了凸面和非凸口设置的Adagrad（延迟Adagrad）步骤大小的广义版本，这表明这些步骤尺寸允许算法自动适应随机梯度的噪声水平。我们首次显示延迟Adagrad的足够条件，以确保梯度几乎融合到零。此外，我们对延迟的Adagrad及其在非凸面设置中的动量变体进行了高概率分析。其次，我们用指数级和余弦的步骤分析了SGD，在经验上取得了成功，但缺乏理论支持。我们在平滑和非凸的设置中为它们提供了最初的收敛保证，有或没有polyak-{\ l} ojasiewicz（pl）条件。我们还显示了它们在PL条件下适应噪声的良好特性。第三，我们研究动量方法的最后迭代。我们证明了SGD的最后一个迭代的凸设置中的第一个下限，并以恒定的动量。此外，我们研究了一类跟随基于领先的领导者的动量算法，并随着动量和收缩的更新而增加。我们表明，他们的最后一个迭代具有最佳的收敛性，用于无约束的凸随机优化问题。