具有自适应缩放不同功能的方法在解决鞍点问题方面起着关键作用，这主要是由于亚当在解决对抗机器学习问题（包括gans训练）方面的受欢迎程度。本文对解决SPPS的以下缩放技术进行了理论分析：众所周知的Adam和Rmsprop缩放以及基于Hutchison近似的较新的Adahessian和Oasis。我们将额外的梯度及其改进的版本带有负动量作为基本方法。关于gan的实验研究不仅对亚当，而且对其他不太流行的方法显示出良好的适用性。

本文着重于随机鞍点问题的分布式优化。本文的第一部分专门针对平滑（强）（强）（强）凹形鞍点问题以及实现这些结合的近乎最佳算法的平滑（强）凸出的凹点鞍点问题的平滑（强）凸出的（强）凸出的凸出鞍点问题。接下来，我们提出了一种新的联合算法，用于分布式鞍点问题 - 额外的步骤本地SGD。对新方法的理论分析是针对强烈凸出的凹形和非convex-non-concave问题进行的。在本文的实验部分中，我们在实践中显示了方法的有效性。特别是，我们以分布方式训练甘恩。

在本文中，我们概括了Gasnikov等人的方法。Al，2017年，它允许使用不精确的无梯度的Oracle解决（随机）凸优化问题，以解决凸 - 凸座鞍点问题。所提出的方法至少像最好的现有方法一样有效。但是，对于特殊的设置（单纯类型的约束和1和2规范中Lipschitz常数的紧密度），我们的方法降低了$ \ frac {n} {\ log n} $ times所需的oracle调用数量（函数计算）。我们的方法通过有限差异使用梯度的随机近似。在这种情况下，该功能不仅必须在优化集本身，而且在其某个邻域中指定。在本文的第二部分中，我们分析了无法做出这样的假设时，我们提出了一种关于如何现代化解决此问题的方法的一般方法，并且我们还将这种方法应用于某些经典集合的特定情况。

最近，有大量的工作致力于研究马尔可夫链随机梯度方法（MC-SGMS），这些方法主要集中于他们解决最小化问题的收敛分析。在本文中，我们通过统计学习理论框架中的算法稳定性镜头对MC-SGM进行了全面的MC-SGMS分析。对于经验风险最小化（ERM）问题，我们通过引入实用的论点稳定性来建立平稳和非平滑案例的最佳人口风险界限。对于最小值问题，我们建立了在平均参数稳定性和概括误差之间的定量连接，该误差扩展了均匀稳定性\ cite {lei2021Staritibal}的现有结果。我们进一步开发了预期和高概率的凸孔问题问题的第一个几乎最佳的收敛速率，这与我们的稳定性结果相结合，表明可以在平滑和非平滑案例中达到最佳的概括界限。据我们所知，这是对梯度从马尔可夫过程采样时对SGM的首次概括分析。

本文重点介绍了解决光滑非凸强凹入最小问题的随机方法，这导致了由于其深度学习中的潜在应用而受到越来越长的关注（例如，深度AUC最大化，分布鲁棒优化）。然而，大多数现有算法在实践中都很慢，并且它们的分析围绕到几乎静止点的收敛。我们考虑利用Polyak-\ L Ojasiewicz（PL）条件来设计更快的随机算法，具有更强的收敛保证。尽管已经用于设计许多随机最小化算法的PL条件，但它们对非凸敏最大优化的应用仍然罕见。在本文中，我们提出并分析了基于近端的跨越时代的方法的通用框架，许多众所周知的随机更新嵌入。以{\ BF原始物镜差和二元间隙}的方式建立快速收敛。与现有研究相比，（i）我们的分析基于一个新的Lyapunov函数，包括原始物理差距和正则化功能的二元间隙，（ii）结果更加全面，提高了更好的依赖性的速率不同假设下的条件号。我们还开展深层和非深度学习实验，以验证我们的方法的有效性。

梯度下降上升（GDA），最简单的单环路算法用于非凸起最小化优化，广泛用于实际应用，例如生成的对抗网络（GANS）和对抗性训练。尽管其理想的简单性，最近的工作表明了理论上的GDA的较差收敛率，即使在一侧对象的强凹面也是如此。本文为两个替代的单环算法建立了新的收敛结果 - 交替GDA和平滑GDA - 在温和的假设下，目标对一个变量的polyak-lojasiewicz（pl）条件满足Polyak-lojasiewicz（pl）条件。我们证明，找到一个$ \ epsilon $ -stationary点，（i）交替的GDA及其随机变体（没有迷你批量），分别需要$ o（\ kappa ^ {2} \ epsilon ^ { - 2}）$和$ o（\ kappa ^ {4} \ epsilon ^ {-4}）$迭代，而（ii）平滑gda及其随机变体（没有迷你批次）分别需要$ o（\ kappa \ epsilon ^ { - 2}） $和$ o（\ kappa ^ {2} \ epsilon ^ { - 4}）$迭代。后者大大改善了Vanilla GDA，并在类似的环境下给出了单环算法之间的最佳已知复杂性结果。我们进一步展示了这些算法在训练GAN和强大的非线性回归中的经验效率。

We consider the constrained sampling problem where the goal is to sample from a distribution $\pi(x)\propto e^{-f(x)}$ and $x$ is constrained on a convex body $\mathcal{C}\subset \mathbb{R}^d$. Motivated by penalty methods from optimization, we propose penalized Langevin Dynamics (PLD) and penalized Hamiltonian Monte Carlo (PHMC) that convert the constrained sampling problem into an unconstrained one by introducing a penalty function for constraint violations. When $f$ is smooth and the gradient is available, we show $\tilde{\mathcal{O}}(d/\varepsilon^{10})$ iteration complexity for PLD to sample the target up to an $\varepsilon$-error where the error is measured in terms of the total variation distance and $\tilde{\mathcal{O}}(\cdot)$ hides some logarithmic factors. For PHMC, we improve this result to $\tilde{\mathcal{O}}(\sqrt{d}/\varepsilon^{7})$ when the Hessian of $f$ is Lipschitz and the boundary of $\mathcal{C}$ is sufficiently smooth. To our knowledge, these are the first convergence rate results for Hamiltonian Monte Carlo methods in the constrained sampling setting that can handle non-convex $f$ and can provide guarantees with the best dimension dependency among existing methods with deterministic gradients. We then consider the setting where unbiased stochastic gradients are available. We propose PSGLD and PSGHMC that can handle stochastic gradients without Metropolis-Hasting correction steps. When $f$ is strongly convex and smooth, we obtain an iteration complexity of $\tilde{\mathcal{O}}(d/\varepsilon^{18})$ and $\tilde{\mathcal{O}}(d\sqrt{d}/\varepsilon^{39})$ respectively in the 2-Wasserstein distance. For the more general case, when $f$ is smooth and non-convex, we also provide finite-time performance bounds and iteration complexity results. Finally, we test our algorithms on Bayesian LASSO regression and Bayesian constrained deep learning problems.

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

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

在本文中，我们提出了一类更快的自适应梯度下降上升（GDA）方法，用于基于统一的自适应矩阵求解基于统一的自适应矩阵的非膨胀强度凹入的最小值问题，该问题包括几乎存在的坐标和全局自适应学习率。具体而言，我们提出了一种基于基本动量技术的快速自适应梯度体面上升（Adagda）方法，该方法达到$ O（\ Kappa ^ 4 \ epsilon ^ { - 4}）$的较低梯度复杂度，用于查找$ \ epsilon $ -Sationary点没有大批次，这通过$ o（\ sqrt {\ kappa}）$。与此同时，我们提出了一种基于势头的阶段的adagda（VR-Adagda）方法的加速版本，这使得可以实现$ O（\ kappa ^ {4.5} \ epsilon ^ { - 3的较低梯度复杂度为了查找$ \ epsilon $ -stationary点，没有大批次，这将通过$ o（\ epsilon ^ {-1}）为现有的自适应GDA方法的结果提高了现有的自适应GDA方法。此外，我们证明了我们的VR-Adagda方法达到了$ O（\ Kappa ^ {3} \ epsilon ^ { - 3}）$的最佳已知的渐变复杂度$ 。特别是，我们为我们的自适应GDA方法提供了有效的收敛分析框架。关于政策评估和公平分类器任务的一些实验结果展示了我们算法的效率。

零顺序（ZO）优化广泛用于处理具有挑战性的任务，例如基于查询的黑匣子对抗攻击和加强学习。已经提出了各种尝试，以基于有限差异将先前信息集成到梯度估计过程中，具有有前途的经验结果。然而，它们的收敛性质不太了解。本文试图通过分析具有各种梯度估计的贪婪下降框架下的先前引导的ZO算法的收敛来填补这种差距。我们为先前引导的随机梯度（PRGF）算法提供了收敛保障。此外，为了进一步加速贪婪的下降方法，我们提出了一种新的加速随机搜索（ARS）算法，其将先前信息与收敛分析一起结合在一起。最后，我们的理论结果是通过关于几个数值基准以及对抗性攻击的实验确认。

随机梯度下降（SGDA）及其变体一直是解决最小值问题的主力。但是，与研究有差异隐私（DP）约束的经过良好研究的随机梯度下降（SGD）相反，在理解具有DP约束的SGDA的概括（实用程序）方面几乎没有工作。在本文中，我们使用算法稳定性方法在不同的设置中建立DP-SGDA的概括（实用程序）。特别是，对于凸 - 凸环设置，我们证明DP-SGDA可以在平滑和非平滑案例中都可以根据弱原始二元人群风险获得最佳的效用率。据我们所知，这是在非平滑案例中DP-SGDA的第一个已知结果。我们进一步在非convex-rong-concave环境中提供了实用性分析，这是原始人口风险的首个已知结果。即使在非私有设置中，此非convex设置的收敛和概括结果也是新的。最后，进行了数值实验，以证明DP-SGDA在凸和非凸病例中的有效性。

本文是对解决平滑（强）单调随机变化不平等的方法的调查。首先，我们给出了随机方法最终发展的确定性基础。然后，我们回顾了通用随机配方的方法，并查看有限的总和设置。本文的最后部分致力于各种算法的各种（不一定是随机）的变化不平等现象。

亚当是训练深神经网络的最具影响力的自适应随机算法之一，即使在简单的凸面设置中，它也被指出是不同的。许多尝试，例如降低自适应学习率，采用较大的批量大小，结合了时间去相关技术，寻求类似的替代物，\ textit {etc。}，以促进Adam-type算法融合。与现有方法相反，我们引入了另一种易于检查的替代条件，这仅取决于基础学习率的参数和历史二阶时刻的组合，以确保通用ADAM的全球融合以解决大型融合。缩放非凸随机优化。这种观察结果以及这种足够的条件，对亚当的差异产生了更深刻的解释。另一方面，在实践中，无需任何理论保证，广泛使用了迷你ADAM和分布式ADAM。我们进一步分析了分布式系统中的批次大小或节点的数量如何影响亚当的收敛性，从理论上讲，这表明迷你批次和分布式亚当可以通过使用较大的迷你批量或较大的大小来线性地加速节点的数量。最后，我们应用了通用的Adam和Mini Batch Adam，具有足够条件来求解反例并在各种真实世界数据集上训练多个神经网络。实验结果完全符合我们的理论分析。

在本文中，我们考虑基于移动普通（SEMA）的广泛使用但不完全了解随机估计器，其仅需要{\ bf是一般无偏的随机oracle}。我们展示了Sema在一系列随机非凸优化问题上的力量。特别是，我们分析了基于SEMA的SEMA的{\ BF差异递归性能的各种随机方法（现有或新提出），即三个非凸优化，即标准随机非凸起最小化，随机非凸强烈凹入最小最大优化，随机均方优化。我们的贡献包括：（i）对于标准随机非凸起最小化，我们向亚当风格方法（包括ADAM，AMSGRAD，Adabound等）提供了一个简单而直观的融合证明，随着越来越大的“势头” “一阶时刻的参数，它给出了一种替代但更自然的方式来保证亚当融合; （ii）对于随机非凸强度凹入的最小值优化，我们介绍了一种基于移动平均估计器的单环原始 - 双随机动量和自适应方法，并确定其Oracle复杂性$ O（1 / \ epsilon ^ 4）$不使用大型批量大小，解决文献中的差距; （iii）对于随机双脚优化，我们介绍了一种基于移动平均估计器的单环随机方法，并确定其Oracle复杂性$ \ widetilde o（1 / \ epsilon ^ 4）$，而无需计算Hessian矩阵的SVD，改善最先进的结果。对于所有这些问题，我们还建立了使用随机梯度估计器的差异递减结果。

我们通过两种类型 - 主/工人（因此集中）架构（因此集中）架构和网格化（因此分散）网络，研究（强）凸起（强）凸起（强）凸起的鞍点问题（SPPS）的解决方案方法。由于统计数据相似度或其他，假设每个节点处的本地功能是相似的。我们为求解SPP的相当一般算法奠定了较低的复杂性界限。我们表明，在$ \ omega \ big（\ delta \ cdot \ delta / \ mu \ cdot \ log（1 / varepsilon）\ big）$ rounds over over over exoptimally $ \ epsilon> 0 $ over over master / workers网络通信，其中$ \ delta> 0 $测量本地功能的相似性，$ \ mu $是它们的强凸起常数，$ \ delta $是网络的直径。较低的通信复杂性绑定在网状网络上读取$ \ omega \ big（1 / {\ sqrt {\ rho}} \ cdot {\ delta} / {\ mu} \ cdot \ log（1 / varepsilon）\ big）$ ，$ \ rho $是用于邻近节点之间通信的八卦矩阵的（归一化）EIGENGAP。然后，我们提出算法与较低限制的网络（最多为日志因子）匹配。我们评估所提出的算法对强大的逻辑回归问题的有效性。

我们考虑光滑的凸孔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}最多达到恒定的预取子。这是在鞍点优化中实现这种相对成熟的最佳表征的第一个结果。

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

在本文中，我们提出了一种称为ANITA的新型加速梯度方法，用于解决基本的有限和优化问题。具体而言，我们同时考虑一般凸面和强烈凸面设置：i）对于一般凸有限的和有限的问题，Anita改善了Varag给定的先前最新结果（Lan等，2019）。特别是，对于大规模问题或收敛错误不是很小，即$ n \ geq \ frac {1} {\ epsilon^2} $，Anita获得\ emph {first} optimal restion $ o（n ）$，匹配Woodworth and Srebro（2016）提供的下限$ \ Omega（N）$，而先前的结果为$ O（N \ log \ frac {1} {\ epsilon}）$ 。 ii）对于强烈凸有限的问题，我们还表明，Anita可以实现最佳收敛速率$ o \ big（（（n+\ sqrt {\ frac {\ frac {nl} {\ mu}} {\ mu}}）\ log \ log \ frac {1} {1} {1} {1} { \ epsilon} \ big）$匹配下限$ \ omega \ big（（（n+\ sqrt {\ frac {nl} {nl} {\ mu}}）\ log \ frac {1} {\ epsilon} {\ epsilon} \ big） Lan and Zhou（2015）。此外，与以前的加速算法（如Varag（Lan等，2019）和Katyusha（Allen-Zhu，2017年），Anita享有更简单的无环算法结构。此外，我们提供了一种新颖的\ emph {动态多阶段收敛分析}，这是将先前结果提高到最佳速率的关键技术。我们认为，针对基本有限和有限问题的新理论率和新颖的收敛分析将直接导致许多其他相关问题（例如分布式/联合/联合/分散的优化问题）的关键改进（例如，Li和Richt \'Arik，2021年，2021年）。最后，数值实验表明，Anita收敛的速度比以前的最先进的Varag（Lan等，2019）更快，从而验证了我们的理论结果并证实了Anita的实践优势。

Adaptive optimization methods are well known to achieve superior convergence relative to vanilla gradient methods. The traditional viewpoint in optimization, particularly in convex optimization, explains this improved performance by arguing that, unlike vanilla gradient schemes, adaptive algorithms mimic the behavior of a second-order method by adapting to the global geometry of the loss function. We argue that in the context of neural network optimization, this traditional viewpoint is insufficient. Instead, we advocate for a local trajectory analysis. For iterate trajectories produced by running a generic optimization algorithm OPT, we introduce $R^{\text{OPT}}_{\text{med}}$, a statistic that is analogous to the condition number of the loss Hessian evaluated at the iterates. Through extensive experiments, we show that adaptive methods such as Adam bias the trajectories towards regions where $R^{\text{Adam}}_{\text{med}}$ is small, where one might expect faster convergence. By contrast, vanilla gradient methods like SGD bias the trajectories towards regions where $R^{\text{SGD}}_{\text{med}}$ is comparatively large. We complement these empirical observations with a theoretical result that provably demonstrates this phenomenon in the simplified setting of a two-layer linear network. We view our findings as evidence for the need of a new explanation of the success of adaptive methods, one that is different than the conventional wisdom.