在本文中，我们介绍了训练两层过度参数的Relu神经网络中动量方法的收敛分析，其中参数的数量明显大于训练实例的参数。动量方法上的现有作品表明，重球方法（HB）和Nesterov的加速方法（NAG）共享相同的限制普通微分方程（ODE），从而导致相同的收敛速率。从高分辨率的动力学角度来看，我们表明HB与NAG在收敛速率方面有所不同。此外，我们的发现为HB和NAG的高分辨率ODES的收敛性提供了更严格的上限。

神经网络在许多领域取得了巨大的经验成功。已经观察到，通过一阶方法训练的随机初始化的神经网络能够实现接近零的训练损失，尽管其损失景观是非凸的并且不平滑的。这种现象很少有理论解释。最近，通过分析过参数化制度中的梯度下降〜（GD）和重球方法〜（HB）的梯度来弥合实践和理论之间的这种差距。在这项工作中，通过考虑Nesterov的加速梯度方法〜（nag），我们通过恒定的动量参数进行进一步进展。我们通过Relu激活分析其用于过度参数化的双层完全连接神经网络的收敛性。具体而言，我们证明了NAG的训练误差以非渐近线性收敛率$（1- \θ（1 / \ sqrt {\ kappa}））收敛到零（1 / \ sqrt {\ kappa}）^ t $ the $ t $迭代，其中$ \ Kappa> 1 $由神经网络的初始化和架构决定。此外，我们在NAG和GD和HB的现有收敛结果之间提供了比较。我们的理论结果表明，NAG实现了GD的加速度，其会聚率与HB相当。此外，数值实验验证了我们理论分析的正确性。

Gradient-based first-order convex optimization algorithms find widespread applicability in a variety of domains, including machine learning tasks. Motivated by the recent advances in fixed-time stability theory of continuous-time dynamical systems, we introduce a generalized framework for designing accelerated optimization algorithms with strongest convergence guarantees that further extend to a subclass of non-convex functions. In particular, we introduce the \emph{GenFlow} algorithm and its momentum variant that provably converge to the optimal solution of objective functions satisfying the Polyak-{\L}ojasiewicz (PL) inequality, in a fixed-time. Moreover for functions that admit non-degenerate saddle-points, we show that for the proposed GenFlow algorithm, the time required to evade these saddle-points is bounded uniformly for all initial conditions. Finally, for strongly convex-strongly concave minimax problems whose optimal solution is a saddle point, a similar scheme is shown to arrive at the optimal solution again in a fixed-time. The superior convergence properties of our algorithm are validated experimentally on a variety of benchmark datasets.

如今，重球（HB）是非凸优化中最流行的动量方法之一。已经广泛观察到，将重球动态纳入基于梯度的方法中可以加速现代机器学习模型的训练过程。但是，建立其加速理论基础的进展显然远远落后于其经验成功。现有的可证明的加速结果是二次或近二次功能，因为当前显示HB加速度的技术仅限于Hessian固定时的情况。在这项工作中，我们开发了一些新技术，这些新技术有助于表现出二次超越二次的加速度，这是通过分析在两个连续时间点上如何变化的Hessian的变化来实现的，从而影响了收敛速度。基于我们的技术结果，一类Polyak- \ l {} Ojasiewicz（PL）优化问题可以通过HB确定可证明的加速度。此外，我们的分析证明了适应性设置动量参数的好处。

在本文中，我们遵循Eftekhari的工作，为深线性网络提供非局部收敛性分析。具体地，我们考虑优化具有在二次损耗下具有一个神经元的层的深度线性网络。我们描述了在梯度流动下具有任意起点的轨迹的收敛点，包括将其收敛到鞍点或原始点之一的路径。我们还显示了通过阶段收敛到全球最小化器的轨迹的特定收敛速度。为实现这些结果，本文主要延伸了Eftekhari的工作中的机器，以证明秩稳定集和全球最小化器会聚集。我们还提供具体示例以表明我们定义的必要性。据我们所知，我们的结果似乎是第一个从任意初始化点给出线性神经网络的非本地全球分析，而不是借导于神经网络文献，并限制良性培训制度Eftekhari工作中的初始化。我们还注意到，在没有一个隐藏的神经元假设的情况下将结果扩展到一般线性网络，仍然是一个具有挑战性的公开问题。

在一阶算法的历史中，Nesterov的加速梯度下降（NAG）是里程碑之一。但是，长期以来，加速的原因一直是一个谜。直到[Shi等，2021]中提出的高分辨率微分方程框架之前，梯度校正的存在尚未得到揭示。在本文中，我们继续研究加速现象。首先，我们基于精确的观察结果和$ L $ SMOTH功能的不等式提供了明显的简化证明。然后，提出了一个新的隐式高分辨率差分方程框架，以及相应的隐式 - 速度版本的相位空间表示和lyapunov函数，以研究迭代序列$ \ {x_k \} _的迭代序列的收敛行为{k = 0}^{\ infty} $的nag。此外，从两种类型的相空间表示形式中，我们发现梯度校正所起的作用等同于按速度隐含在梯度中包含的作用，其中唯一的区别来自迭代序列$ \ \ {y_ {y_ {k} \} _ {k = 0}^{\ infty} $由$ \ {x_k \} _ {k = 0}^{\ infty} $代替。最后，对于NAG的梯度规范最小化是否具有更快的速率$ O（1/K^3）$的开放问题，我们为证明提供了一个积极的答案。同时，为$ r> 2 $显示了目标值最小化$ o（1/k^2）$的更快的速度。

尽管他们的超大容量过度装备能力，但是由特定优化算法训练的深度神经网络倾向于概括到看不见的数据。最近，研究人员通过研究优化算法的隐式正则化效果来解释它。卓越的进展是工作（Lyu＆Li，2019），其证明了梯度下降（GD）最大化了均匀深神经网络的余量。除GD外，诸如Adagrad，RMSProp和Adam之类的自适应算法由于其快速培训过程而流行。然而，仍然缺乏适应性优化算法的概括的理论保证。在本文中，我们研究了自适应优化算法的隐式正则化，当它们在均匀深神经网络上优化逻辑损失时。我们证明了在调节器（如亚当和RMSProp）中采用指数移动平均策略的自适应算法可以最大化神经网络的余量，而Adagrad直接在调节器中总和历史平方梯度。它表明了调节剂设计中指数移动平均策略的概括的优越性。从技术上讲，我们提供统一的框架，通过构建新的自适应梯度流量和代理余量来分析自适应优化算法的会聚方向。我们的实验可以很好地支持适应性优化算法的会聚方向的理论发现。

加速梯度方法是大规模，数据驱动优化问题的基石，其在机器学习和其他关于数据分析的其他领域出现的自然。我们介绍了一种基于梯度的优化框架，用于实现加速度，基于最近引入了动态系统的固定时间稳定性的概念。该方法本身表示作为基于简单的基于梯度的方法的概括，适当地缩放以在固定时间内实现对优化器的收敛，与初始化无关。我们通过首先利用用于设计定时稳定动态系统的连续时间框架来实现这一目标，并且稍后提供一致的离散化策略，使得等效的离散时间算法在实际固定数量的迭代中跟踪优化器。我们还提供了对所提出的梯度流动的收敛行为的理论分析，以及他们对遵循强大凸起，严格凸起，并且可能不承受的功能的一系列功能的鲁造性，但满足Polyak - {\ l} Ojasiewicz不平等。我们还表明，由于定时收敛，收敛率的遗憾是恒定的。普遍的参数具有直观的解释，可以调整以适应所需的收敛速率的要求。我们验证了针对最先进的优化算法的一系列数值示例上提出的方案的加速收敛性。我们的工作提供了通过连续时间流动的离散化开发新颖优化算法的见解。

优化算法越来越多地用于具有有限时间预算的应用中。在许多实时和嵌入式方案中，只能执行少数迭代，并且传统的收敛度量不能用于评估这些非渐近制度中的性能。在本文中，我们研究了加速的一阶优化算法的瞬态行为。对于凸二次出现问题，我们采用了线性系统理论的工具，以表明瞬态增长出现来自非正常动态的存在。我们确定存在早期迭代中的代数生长的模式的存在，并量化由这些模式引起的最佳解决方案的瞬态偏​​移。对于强烈凸的光滑优化问题，我们利用积分二次限制（IQC）的理论来建立核心加速算法瞬态响应的大小。我们表明，优化变量与全球最小化器之间的欧几里德距离和瞬态峰值的上升时间与问题的条件数量的平方根成比例。最后，对于条件数量的问题，我们展示了我们导致恒定因素的界限的紧张性。

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

Q学习长期以来一直是最受欢迎的强化学习算法之一，几十年来，Q学习的理论分析一直是一个活跃的研究主题。尽管对Q-学习的渐近收敛分析的研究具有悠久的传统，但非肿瘤收敛性直到最近才受到积极研究。本文的主要目的是通过控制系统的观点研究马尔可夫观察模型下异步Q学习的新有限时间分析。特别是，我们引入了Q学习的离散时间变化的开关系统模型，并减少了分析的步骤尺寸，这显着改善了使用恒定步骤尺寸的开关系统分析的最新开发，并导致\（\（\）（\） Mathcal {o} \ left（\ sqrt {\ frac {\ log k} {k}}} \ right）\）\）\）\）\）\）\）\）与大多数艺术状态相当或更好。同时，新应用了使用类似转换的技术，以避免通过减小的步骤尺寸提出的分析中的难度。提出的分析带来了其他见解，涵盖了不同的方案，并提供了新的简化模板，以通过其独特的连接与离散时间切换系统的独特联系来加深我们对Q学习的理解。

几种广泛使用的一阶马鞍点优化方法将衍生天然衍生时的梯度下降成本（GDA）方法的相同连续时间常分等式（ODE）。然而，即使在简单的双线性游戏上，它们的收敛性也很差异。我们使用一种来自流体动力学的技术，称为高分辨率微分方程（HRDE）来设计几个骑马点优化方法的杂散。在双线性游戏中，派生HRDE的收敛性属性对应于起始离散方法的收敛性。使用这些技术，我们表明乐观梯度下降的HRDE具有最后迭代单调变分不等式的迭代收敛。据我们所知，这是第一个连续时间动态，用于收敛此类常规设置。此外，我们提供了ogda方法的最佳迭代收敛的速率，仅依靠单调运营商的一阶平滑度。

我们调查随机镜面下降（SMD）的趋同相对光滑和平滑凸优化。在相对平滑的凸优化中，我们为SMD提供了新的收敛保证，并持续步骤。对于平滑的凸优化，我们提出了一种新的自适应步骤方案 - 镜子随机Polyak Spectize（MSP）。值得注意的是，我们的收敛导致两个设置都不会使有界渐变假设或有界方差假设，并且我们向邻域显示在插值下消失的邻居的融合。MSP概括了最近提出的随机Polyak Spectize（SPS）（Loizou等，2021）以镜子血液镜子，并且在继承镜子血清的好处的同时，现代机器学习应用仍然是实用和高效的。我们将我们的结果与各种监督的学习任务和SMD的不同实例相结合，展示了MSP的有效性。

Nesterov's accelerated gradient descent (NAG) is one of the milestones in the history of first-order algorithms. It was not successfully uncovered until the high-resolution differential equation framework was proposed in [Shi et al., 2022] that the mechanism behind the acceleration phenomenon is due to the gradient correction term. To deepen our understanding of the high-resolution differential equation framework on the convergence rate, we continue to investigate NAG for the $\mu$-strongly convex function based on the techniques of Lyapunov analysis and phase-space representation in this paper. First, we revisit the proof from the gradient-correction scheme. Similar to [Chen et al., 2022], the straightforward calculation simplifies the proof extremely and enlarges the step size to $s=1/L$ with minor modification. Meanwhile, the way of constructing Lyapunov functions is principled. Furthermore, we also investigate NAG from the implicit-velocity scheme. Due to the difference in the velocity iterates, we find that the Lyapunov function is constructed from the implicit-velocity scheme without the additional term and the calculation of iterative difference becomes simpler. Together with the optimal step size obtained, the high-resolution differential equation framework from the implicit-velocity scheme of NAG is perfect and outperforms the gradient-correction scheme.

在分析过度参数化神经网络的训练动力学方面的最新进展主要集中在广泛的网络上，因此无法充分解决深度在深度学习中的作用。在这项工作中，我们介绍了第一个无限深层但狭窄的神经网络的训练保证。我们研究具有特定初始化的多层感知器（MLP）的无限深度极限，并使用NTK理论建立了可训练性保证。然后，我们将分析扩展到无限深的卷积神经网络（CNN），并进行简短的实验。

本文研究了拟牛顿方法求解强凸强凹鞍点问题（SPP）。我们提出了SPP一般贪婪Broyden族更新，其中有$明确的局部超线性收敛速度的变体{\mathcalØ}\大（\大（1\压裂{1}{N\卡帕^2}\大）^ {K（K-1）/ 2}\大）$，其中$N $是问题的尺寸，$ \卡帕$是条件数和$$ķ是迭代次数。设计和算法的分析是基于估计不定Hessian矩阵的平方，这是从在凸优化古典准牛顿方法的不同。我们还提出两个具体Broyden族算法与BFGS型和SR1型更新，其享受的$更快的局部收敛速度\mathcalØ\大（\大（1\压裂{1} {N}\大）^{K（K-1）/ 2}\大）$。

具有动量（SGDM）的SGD是一种广泛使用的算法系列，用于大规模优化机器学习问题。但是，当优化通用凸功能时，任何SGDM算法都不知道与普通SGD相比。此外，即使最近的结果也需要更改SGDM算法，例如平均迭代元素和对有限域的投影，这些域很少在实践中使用。在本文中，我们关注SGDM最后一次迭代的收敛速率。我们第一次证明，对于任何恒定的动量因素，都存在Lipschitz和凸功能，SGDM的最后一次迭代均具有$ \ omega的次优收敛速率（\ frac {\ ln t} {\ ln t} {\ sqrt {\ sqrt { $ t $迭代后的t}}）$。基于这一事实，我们研究了一类（自适应和非自适应）遵循基于调查的领导者的SGDM算法，并随着动量的增加和缩小的更新而进行。对于这些算法，我们表明，最后一个迭代具有最佳收敛$ O（\ frac {1} {\ sqrt {t}}）$，用于无约束的凸随机优化问题，而没有投影到有限域的域也没有$ t $的知识。此外，当与自适应步骤一起使用时，我们显示了基于FTRL的SGDM的各种结果。也显示了经验结果。

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.

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

在本文中，我们研究并证明了拟牛顿算法的Broyden阶级的非渐近超线性收敛速率，包括Davidon - Fletcher - Powell（DFP）方法和泡沫 - 弗莱彻 - 夏诺（BFGS）方法。这些准牛顿方法的渐近超线性收敛率在文献中已经广泛研究，但它们明确的有限时间局部会聚率未得到充分调查。在本文中，我们为Broyden Quasi-Newton算法提供了有限时间（非渐近的）收敛分析，在目标函数强烈凸起的假设下，其梯度是Lipschitz连续的，并且其Hessian在最佳解决方案中连续连续。我们表明，在最佳解决方案的本地附近，DFP和BFGS生成的迭代以$（1 / k）^ {k / 2} $的超连线率收敛到最佳解决方案，其中$ k $是迭代次数。我们还证明了类似的本地超连线收敛结果，因为目标函数是自我协调的情况。几个数据集的数值实验证实了我们显式的收敛速度界限。我们的理论保证是第一个为准牛顿方法提供非渐近超线性收敛速率的效果之一。