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

我们研究了基于动量的一阶优化算法，其中迭代利用了前两个步骤中的信息，并受到加性白噪声的影响。这类算法包括重型球和Nesterov作为特殊情况的加速方法。对于强烈凸出的二次问题，我们在优化变量中使用误差的稳态差异来量化噪声放大并利用新颖的几何观点，以在沉降时间和最小/最大的可实现的噪声扩增之间建立分析性下限。对于所有稳定参数，这些边界与条件编号双重规模。我们还使用本文中开发的几何见解来引入两个参数化的算法族，这些算法族在噪声放大和沉降时间之间取得平衡，同时保留订单的帕累托最佳性。最后，对于一类连续的时梯度流动动力学（其合适的离散化都会产生两步动量算法），我们建立了类似的下限，同时也随条件数的数字四次扩展。

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

简单的随机动量方法被广泛用于机器学习优化，但它们的良好实践表现与文献中没有理论保证的理论保证相矛盾。在这项工作中，我们的目标是通过表明随机重球动量来弥合理论和实践之间的差距，该动力可以解释为具有动量的随机kaczmarz算法，保留了二次优化问题（确定性）重球动量的快速线性速率，至少在使用足够大的批次大小的小型匹配时。该分析依赖于仔细分解动量过渡矩阵，并使用新的光谱范围浓度界限来进行独立随机矩阵的产物。我们提供数值实验，以证明我们的边界相当锐利。

我们提供了新的基于梯度的方法，以便有效解决广泛的病态化优化问题。我们考虑最小化函数$ f：\ mathbb {r} ^ d \ lightarrow \ mathbb {r} $的问题，它是隐含的可分解的，作为$ m $未知的非交互方式的总和，强烈的凸起功能并提供方法这解决了这个问题，这些问题是缩放（最快的对数因子）作为组件的条件数量的平方根的乘积。这种复杂性绑定（我们证明几乎是最佳的）可以几乎指出的是加速梯度方法的几乎是指数的，这将作为$ F $的条件数量的平方根。此外，我们提供了求解该多尺度优化问题的随机异标变体的有效方法。而不是学习$ F $的分解（这将是过度昂贵的），而是我们的方法应用一个清洁递归“大步小步”交错标准方法。由此产生的算法使用$ \ tilde {\ mathcal {o}}（d m）$空间，在数字上稳定，并打开门以更细粒度的了解凸优化超出条件号的复杂性。

诸如压缩感测，图像恢复，矩阵/张恢复和非负矩阵分子等信号处理和机器学习中的许多近期问题可以作为约束优化。预计的梯度下降是一种解决如此约束优化问题的简单且有效的方法。本地收敛分析将我们对解决方案附近的渐近行为的理解，与全球收敛分析相比，收敛率的较小界限提供了较小的界限。然而，本地保证通常出现在机器学习和信号处理的特定问题领域。此稿件在约束最小二乘范围内，对投影梯度下降的局部收敛性分析提供了统一的框架。该建议的分析提供了枢转局部收敛性的见解，例如线性收敛的条件，收敛区域，精确的渐近收敛速率，以及达到一定程度的准确度所需的迭代次数的界限。为了证明所提出的方法的适用性，我们介绍了PGD的收敛分析的配方，并通过在四个基本问题上的配方的开始延迟应用来证明它，即线性约束最小二乘，稀疏恢复，最小二乘法使用单位规范约束和矩阵完成。

随机重球（SHB）和Nesterov的加速随机梯度（ASG）是随机优化的流行动量方法。尽管对确定性环境中这种加速思想的好处有充分的理解，但它们在随机优化方面的优势仍然尚不清楚。实际上，在某些特定情况下，众所周知，在样本复杂性意义上，动量无济于事。我们的工作表明，类似的结果实际上是整个二次优化的。具体而言，我们为该家族获得了SHB和ASG样品复杂性的下限，并表明Vanilla SGD可以实现相同的结合。我们注意到，存在二次优化中基于动量方法的优势的结果，但这些方法基于单方面或有缺陷的分析。

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

梯度下降（GDA）方法是生成对抗网络（GAN）中最小值优化的主流算法。 GDA的收敛特性引起了最近文献的重大兴趣。具体而言，对于$ \ min _ {\ mathbf {x}} \ max _ {\ mathbf {y}} f（\ mathbf {x}; \ m m缩y} $以及$ \ mathbf {x} $，（lin等，2020）中的nonConvex证明了GDA的收敛性，带有sptepize的比率$ \ eta _ {\ mathbf {y}}}}/\ eta _ { }} = \ theta（\ kappa^2）$ with $ \ eta _ {\ mathbf {x}} $和$ \ eta _ {\ eta _ {\ mathbf {y}} $是$ \ mathbf {x}} $和$ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ Mathbf {y} $和$ \ kappa $是$ \ mathbf {y} $的条件号。尽管该步骤大比表明对最小玩家进行缓慢的训练，但实用的GAN算法通常对两个变量采用类似的步骤，表明理论和经验结果之间存在较大差距。在本文中，我们的目标是通过分析常规\ emph {nonconvex-nonconcave} minimax问题的\ emph {local contergence}来弥合这一差距。我们证明，$ \ theta（\ kappa）$的得分比是必要且足够的，足以使GDA局部收敛到Stackelberg equilibrium，其中$ \ kappa $是$ \ mathbf {y} $的本地条件号。我们证明了与匹配的下限几乎紧密的收敛速率。我们进一步将收敛保证扩展到随机GDA和额外梯度方法（例如）。最后，我们进行了几项数值实验来支持我们的理论发现。

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

广义自我符合是许多重要学习问题的目标功能中存在的关键属性。我们建立了一个简单的Frank-Wolfe变体的收敛速率，该变体使用开环步数策略$ \ gamma_t = 2/（t+2）$，获得了$ \ Mathcal {o}（1/t）$收敛率对于这类功能，就原始差距和弗兰克 - 沃尔夫差距而言，$ t $是迭代计数。这避免了使用二阶信息或估计以前工作的局部平滑度参数的需求。我们还显示了各种常见病例的收敛速率的提高，例如，当所考虑的可行区域均匀地凸或多面体时。

Recently, there has been great interest in connections between continuous-time dynamical systems and optimization algorithms, notably in the context of accelerated methods for smooth and unconstrained problems. In this paper we extend this perspective to nonsmooth and constrained problems by obtaining differential inclusions associated to novel accelerated variants of the alternating direction method of multipliers (ADMM). Through a Lyapunov analysis, we derive rates of convergence for these dynamical systems in different settings that illustrate an interesting tradeoff between decaying versus constant damping strategies. We also obtain perturbed equations capturing fine-grained details of these methods, which have improved stability and preserve the leading order convergence rates.

我们开发了一种使用无遗憾的游戏动态解决凸面优化问题的算法框架。通过转换最小化凸起函数以顺序方式解决Min-Max游戏的辅助问题的问题，我们可以考虑一系列必须在另一个之后选择其行动的两名员工的一系列策略。这些策略的常见选择是所谓的无悔的学习算法，我们描述了许多此类并证明了遗憾。然后，我们表明许多凸面优化的经典一阶方法 - 包括平均迭代梯度下降，弗兰克 - 沃尔夫算法，重球算法和Nesterov的加速方法 - 可以被解释为我们框架的特殊情况由于每个玩家都做出正确选择无悔的策略。证明该框架中的收敛速率变得非常简单，因为它们遵循适当已知的遗憾范围。我们的框架还引发了一些凸优化的特殊情况的许多新的一阶方法。

This paper shows that a perturbed form of gradient descent converges to a second-order stationary point in a number iterations which depends only poly-logarithmically on dimension (i.e., it is almost "dimension-free"). The convergence rate of this procedure matches the wellknown convergence rate of gradient descent to first-order stationary points, up to log factors. When all saddle points are non-degenerate, all second-order stationary points are local minima, and our result thus shows that perturbed gradient descent can escape saddle points almost for free.Our results can be directly applied to many machine learning applications, including deep learning. As a particular concrete example of such an application, we show that our results can be used directly to establish sharp global convergence rates for matrix factorization. Our results rely on a novel characterization of the geometry around saddle points, which may be of independent interest to the non-convex optimization community.

Convex function constrained optimization has received growing research interests lately. For a special convex problem which has strongly convex function constraints, we develop a new accelerated primal-dual first-order method that obtains an $\Ocal(1/\sqrt{\vep})$ complexity bound, improving the $\Ocal(1/{\vep})$ result for the state-of-the-art first-order methods. The key ingredient to our development is some novel techniques to progressively estimate the strong convexity of the Lagrangian function, which enables adaptive step-size selection and faster convergence performance. In addition, we show that the complexity is further improvable in terms of the dependence on some problem parameter, via a restart scheme that calls the accelerated method repeatedly. As an application, we consider sparsity-inducing constrained optimization which has a separable convex objective and a strongly convex loss constraint. In addition to achieving fast convergence, we show that the restarted method can effectively identify the sparsity pattern (active-set) of the optimal solution in finite steps. To the best of our knowledge, this is the first active-set identification result for sparsity-inducing constrained optimization.

我们考虑凸优化问题，这些问题被广泛用作低级基质恢复问题的凸松弛。特别是，在几个重要问题（例如相位检索和鲁棒PCA）中，在许多情况下的基本假设是最佳解决方案是排名一列。在本文中，我们考虑了目标上的简单自然的条件，以使这些放松的最佳解决方案确实是独特的，并且是一个排名。主要是，我们表明，在这种情况下，使用线路搜索的标准Frank-Wolfe方法（即，没有任何参数调整），该方法仅需要单个排名一级的SVD计算，可以找到$ \ epsilon $ - 仅在$ o（\ log {1/\ epsilon}）$迭代（而不是以前最著名的$ o（1/\ epsilon）$）中的近似解决方案，尽管目的不是强烈凸。我们考虑了基本方法的几种变体，具有改善的复杂性，以及由强大的PCA促进的扩展，最后是对非平滑问题的扩展。

最近，在学习没有更换SGD的收敛率的情况下，有很多兴趣，并证明它在最坏情况下比更换SGD更快。然而，已知的下限忽略了问题的几何形状，包括其条件号，而上限明确取决于它。也许令人惊讶的是，我们证明，当考虑条件号时，没有替换SGD \ EMPH {没有}在最坏情况下，除非是时期的数量（通过数据来说）大于条件号。由于机器学习和其他领域的许多问题都没有条件并涉及大型数据集，这表明没有替换不一定改善用于现实迭代预算的更换采样。我们通过提供具有紧密（最多日志因子）的新下限和上限来展示这一点，用于致通二次术语的二次问题，精确地量化了对问题参数的依赖性。

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

我们考虑使用梯度下降来最大程度地减少$ f（x）= \ phi（xx^{t}）$在$ n \ times r $因件矩阵$ x $上，其中$ \ phi是一种基础平稳凸成本函数定义了$ n \ times n $矩阵。虽然只能在合理的时间内发现只有二阶固定点$ x $，但如果$ x $的排名不足，则其排名不足证明其是全球最佳的。这种认证全球最优性的方式必然需要当前迭代$ x $的搜索等级$ r $，以相对于级别$ r^{\ star} $过度参数化。不幸的是，过度参数显着减慢了梯度下降的收敛性，从$ r = r = r = r^{\ star} $的线性速率到$ r> r> r> r> r^{\ star} $，即使$ \ phi $是$ \ phi $强烈凸。在本文中，我们提出了一项廉价的预处理，该预处理恢复了过度参数化的情况下梯度下降回到线性的收敛速率，同时也使在全局最小化器$ x^{\ star} $中可能不良条件变得不可知。

We initiate a formal study of reproducibility in optimization. We define a quantitative measure of reproducibility of optimization procedures in the face of noisy or error-prone operations such as inexact or stochastic gradient computations or inexact initialization. We then analyze several convex optimization settings of interest such as smooth, non-smooth, and strongly-convex objective functions and establish tight bounds on the limits of reproducibility in each setting. Our analysis reveals a fundamental trade-off between computation and reproducibility: more computation is necessary (and sufficient) for better reproducibility.