我们提供一种新型计算机辅助技术，用于系统地分析一阶方法进行优化。与以前的作品相比，该方法特别适用于处理汇总收敛速率和随机岩岩。该技术依赖于SEMIDEFINITE编程和潜在功能。它允许同时获得对这些算法的行为的最坏情况保证，并协助选择适当的参数来调整其最坏情况的性能。该技术也有益于舒适的紧密性保证，这意味着只有通过改变设置，才能提高不令人满意的结果。我们利用了在随机噪声性质的不同假设下分析了确定性和随机第一阶方法的方法。其中，我们对具有有界方差的非结构化噪声，在过度参数期预期最小化问题中产生的不同噪声模型，以及随机块坐标性下降方案。

PEPIT是一种Python软件包，旨在简化对可能涉及梯度，投影，近端或线性优化oracels的大型一阶优化方法的最坏情况分析的最坏情况分析，以及它们的近似或布赖曼变体。简而言之，PEPIT是一种封装，可实现一级优化方法的计算机辅助案例分析。关键的潜在思想是施放执行最坏情况分析的问题，通常称为性能估计问题（PEP），作为可以在数字上解决的半纤维程序（SDP）。为此，只需要包用户才能像他们已经实现的那样写出一阶方法。然后，包裹处理SDP建模部件，并且最坏情况分析通过标准求解器进行数字地执行。

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

用于解决无约束光滑游戏的两个最突出的算法是经典随机梯度下降 - 上升（SGDA）和最近引入的随机共识优化（SCO）[Mescheder等，2017]。已知SGDA可以收敛到特定类别的游戏的静止点，但是当前的收敛分析需要有界方差假设。 SCO用于解决大规模对抗问题，但其收敛保证仅限于其确定性变体。在这项工作中，我们介绍了预期的共同胁迫条件，解释了它的好处，并在这种情况下提供了SGDA和SCO的第一次迭代收敛保证，以解决可能是非单调的一类随机变分不等式问题。我们将两种方法的线性会聚到解决方案的邻域时，当它们使用恒定的步长时，我们提出了富有识别的步骤化切换规则，以保证对确切解决方案的融合。此外，我们的收敛保证在任意抽样范式下担保，因此，我们对迷你匹配的复杂性进行了解。

我们提出了随机方差降低算法，以求解凸 - 凸座鞍点问题，单调变异不平等和单调夹杂物。我们的框架适用于Euclidean和Bregman设置中的外部，前向前后和前反向回复的方法。所有提出的方法都在与确定性的对应物相同的环境中收敛，并且它们要么匹配或改善了解决结构化的最低最大问题的最著名复杂性。我们的结果加强了变异不平等和最小化之间的差异之间的对应关系。我们还通过对矩阵游戏的数值评估来说明方法的改进。

In this book chapter, we briefly describe the main components that constitute the gradient descent method and its accelerated and stochastic variants. We aim at explaining these components from a mathematical point of view, including theoretical and practical aspects, but at an elementary level. We will focus on basic variants of the gradient descent method and then extend our view to recent variants, especially variance-reduced stochastic gradient schemes (SGD). Our approach relies on revealing the structures presented inside the problem and the assumptions imposed on the objective function. Our convergence analysis unifies several known results and relies on a general, but elementary recursive expression. We have illustrated this analysis on several common schemes.

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.

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

我们考虑光滑的凸孔concave双线性耦合的鞍点问题，$ \ min _ {\ mathbf {x}}} \ max _ {\ mathbf {y Mathbf {y}} 〜f（\ mathbf {x}} }，\ mathbf {y}） - g（\ mathbf {y}）$，其中一个人可以访问$ f $，$ g $的随机一阶oracles以及biinear耦合函数$ h $。基于标准的随机外部分析，我们提出了随机\ emph {加速梯度 - extragradient（ag-eg）}下降的算法，该算法在一般随机设置中结合了外部和Nesterov的加速度。该算法利用计划重新启动以接收一种良好的非震动收敛速率，该算法与\ citet {ibrahim202020linear}和\ citet {zhang2021lower}相匹配，并在其相应的设置中，还有一个额外的统计误差期限，以及\ citet {zhang2021lower}最多达到恒定的预取子。这是在鞍点优化中实现这种相对成熟的最佳表征的第一个结果。

We study stochastic monotone inclusion problems, which widely appear in machine learning applications, including robust regression and adversarial learning. We propose novel variants of stochastic Halpern iteration with recursive variance reduction. In the cocoercive -- and more generally Lipschitz-monotone -- setup, our algorithm attains $\epsilon$ norm of the operator with $\mathcal{O}(\frac{1}{\epsilon^3})$ stochastic operator evaluations, which significantly improves over state of the art $\mathcal{O}(\frac{1}{\epsilon^4})$ stochastic operator evaluations required for existing monotone inclusion solvers applied to the same problem classes. We further show how to couple one of the proposed variants of stochastic Halpern iteration with a scheduled restart scheme to solve stochastic monotone inclusion problems with ${\mathcal{O}}(\frac{\log(1/\epsilon)}{\epsilon^2})$ stochastic operator evaluations under additional sharpness or strong monotonicity assumptions.

由于其吸引人的稳健性以及可提供的效率保证，随机模型的方法最近得到了最新的关注。我们为改善基于模型的方法进行了两个重要扩展，即在随机弱凸优化上提高了基于模型的方法。首先，我们通过涉及一组样本来提出基于MiniBatch模型的方法，以近似每次迭代中的模型函数。我们首次表明随机算法即使对于非平滑和非凸（特别是弱凸）问题，即使是批量大小也可以实现线性加速。为此，我们开发了对每个算法迭代中涉及的近端映射的新颖敏感性分析。我们的分析似乎是更多常规设置的独立利益。其次，由于动量随机梯度下降的成功，我们提出了一种新的随机外推模型的方法，大大延伸到更广泛的随机算法中的经典多济会动量技术，用于弱凸优化。在相当灵活的外推术语范围内建立收敛速率。虽然主要关注弱凸优化，但我们还将我们的工作扩展到凸优化。我们将小纤维和外推模型的方法应用于随机凸优化，为此，我们为其提供了一种新的复杂性绑定和有前途的线性加速，批量尺寸。此外，提出了一种基于基于Nesterov动量的基于模型的方法，为此，我们建立了达到最优性的最佳复杂性。

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.

本文解决了一个与简单高阶正规化方法设计有关的开放挑战性的问题，该方法用于解决平滑而单调的变化不平等（VIS）。一个vi涉及在\ mathcal {x} $中查找$ x^\ star \，以使$ \ langle f（x），x -x^\ star \ star \ rangle \ geq 0 $ for All $ x \ in \ Mathcal {x} $，我们考虑$ f：\ mathbb {r}^d \ mapsto \ mathbb {r}^d $的设置，最多$（p-1）^{th} $ - 订购衍生物。对于$ p = 2 $，〜\ citet {Nesterov-2006限制}扩展了立方正规化的牛顿的方法，以$ o（\ epsilon^{ - 1}）$。 -Iteration}提出了另一种二阶方法，该方法获得了$ O（\ epsilon^{ - 2/3} \ log（1/\ epsilon））$的提高速率，但是此方法需要一个非平凡的二进制搜索过程作为内部搜索过程环形。基于类似二进制搜索过程的高阶方法已进一步开发并显示出$ o（\ epsilon^{ - 2/（p+1）} \ log（1/\ epsilon））$的速率。但是，这种搜索程序在实践中可能在计算上是过敏性的，并且在优化理论中找到一种简单的高级正则方法的问题仍然是一个开放而充满挑战的问题。我们提出了一个$ p^{th} $ - 订购方法，该方法\ textit {not}需要任何二进制搜索过程，并证明它可以以$ o（\ epsilon^{ - 2/ （P+1）}）$。还建立了$ \ omega（\ epsilon^{ - 2/（p+1）}）$的下限，以证明我们的方法在单调设置中是最佳的。重新启动的版本达到了平滑且强烈单调的全球线性和局部超级线性收敛速率。此外，我们的方法可以实现$ o（\ epsilon^{ - 2/p}）$的全局速率，以解决平滑和非单调的vis满足薄荷条件；此外，如果强烈的薄荷味状况保持，重新启动的版本再次达到全球线性和本地超级线性收敛速率。

我们的目标是使随机梯度$ \ sigma^2 $在随机梯度和（ii）问题依赖性常数中自适应（i）自适应。当最大程度地减少条件编号$ \ kappa $的平滑，强大的功能时，我们证明，$ t $ t $ toerations sgd的$ t $ toerations sgd具有指数降低的阶跃尺寸和对平滑度的知识可以实现$ \ tilde {o} \ left（\ exp） \ left（\ frac {-t} {\ kappa} \ right） + \ frac {\ sigma^2} {t} \ right）$ rate，而又不知道$ \ sigma^2 $。为了适应平滑度，我们使用随机线路搜索（SLS）并显示（通过上下距离），其SGD的SGD与SLS以所需的速率收敛，但仅针对溶液的邻域。另一方面，我们证明具有平滑度的离线估计值的SGD会收敛到最小化器。但是，其速率与估计误差成正比的速度减慢。接下来，我们证明具有Nesterov加速度和指数步骤尺寸（称为ASGD）的SGD可以实现接近最佳的$ \ tilde {o} \ left（\ exp \ left（\ frac {-t} {-t} {\ sqrt {\ sqrt {\ sqrt { \ kappa}}} \ right） + \ frac {\ sigma^2} {t} \ right）$ rate，而无需$ \ sigma^2 $。当与平滑度和强频率的离线估计值一起使用时，ASGD仍会收敛到溶液，尽管速度较慢。我们从经验上证明了指数级尺寸的有效性以及新型SLS的变体。

随机以外的（SEG）方法是解决各种机器学习任务中出现的最小最大优化和变分不等式问题（VIP）的最流行算法之一。然而，有关SEG的收敛性质的几个重要问题仍然是开放的，包括随机梯度的采样，迷你批量，用于单调有限和变分不等式的单调有限和变分别不等式，以及其他问题。为了解决这些问题，在本文中，我们开发了一种新颖的理论框架，使我们能够以统一的方式分析赛季的几种变体。除了标准设置之外，与均有界差异下的LipsChitzness和单调性或独立样本SEG相同 - 样本SEG，我们的方法可以分析之前从未明确考虑过的SEG的变体。值得注意的是，我们用任意抽样分析SEG，其中包括重要性采样和各种批量批量策略作为特殊情况。我们为SEG的新变种的率优于目前最先进的融合保证并依赖于更少的限制性假设。

加速的近端算法（APPA），也称为“催化剂”，是从凸优化到近似近端计算（即正则最小化）的确定还原。这种减少在概念上是优雅的，可以保证强大的收敛速度。但是，这些速率具有多余的对数项，因此需要计算每个近端点至高精度。在这项工作中，我们提出了一个新颖的放松误差标准，用于加速近端点（recapp），以消除对高精度子问题解决方案的需求。我们将recapp应用于两个规范问题：有限的和最大结构的最小化。对于有限和问题，我们匹配了以前通过精心设计的问题特异性算法获得的最著名的复杂性。为了最大程度地减少$ \ max_y f（x，y）$，其中$ f $以$ x $为$ x $，而在$ y $中强烈concave，我们改进了受对数因素限制的最著名的（基于催化剂）。

我们研究了具有有限和结构的平滑非凸化优化问题的随机重新洗脱（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框架。我们总结了我们在非正式分析框架中的主要步骤和核心思想，这些框架是独立的兴趣。作为本框架的直接应用，我们还建立了类似的强极限点收敛结果，为重组的近端点法。

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

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.

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