从最佳运输到稳健的维度降低，可以将大量的机器学习应用程序放入Riemannian歧管上的Min-Max优化问题中。尽管在欧几里得的环境中已经分析了许多最小的最大算法，但事实证明，将这些结果转化为Riemannian案例已被证明是难以捉摸的。张等。 [2022]最近表明，测量凸凹入的凹入问题总是容纳鞍点解决方案。受此结果的启发，我们研究了Riemannian和最佳欧几里得空间凸入concove算法之间的性能差距。我们在负面的情况下回答了这个问题，证明Riemannian校正的外部（RCEG）方法在地球上强烈convex-concove案例中以线性速率实现了最后近期收敛，与欧几里得结果匹配。我们的结果还扩展到随机或非平滑案例，在这种情况下，RCEG和Riemanian梯度上升下降（RGDA）达到了近乎最佳的收敛速率，直到因歧管的曲率而定为因素。

本文解决了一个与简单高阶正规化方法设计有关的开放挑战性的问题，该方法用于解决平滑而单调的变化不平等（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满足薄荷条件；此外，如果强烈的薄荷味状况保持，重新启动的版本再次达到全球线性和本地超级线性收敛速率。

我们研究无限制的黎曼优化的免投影方法。特别是，我们提出了黎曼弗兰克 - 沃尔夫（RFW）方法。我们将RFW的非渐近收敛率分析为最佳（高音）凸起问题，以及非凸起目标的临界点。我们还提出了一种实用的设置，其中RFW可以获得线性收敛速度。作为一个具体的例子，我们将RFW专用于正定矩阵的歧管，并将其应用于两个任务：（i）计算矩阵几何平均值（riemannian质心）; （ii）计算Bures-Wasserstein重心。这两个任务都涉及大量凸间间隔约束，为此，我们表明RFW要求的Riemannian“线性”Oracle承认了闭合形式的解决方案;该结果可能是独立的兴趣。我们进一步专门从事RFW到特殊正交组，并表明这里也可以以封闭形式解决riemannian“线性”甲骨文。在这里，我们描述了数据矩阵同步的应用程序（促使问题）。我们补充了我们的理论结果，并对RFW对最先进的riemananian优化方法进行了实证比较，并观察到RFW竞争性地对计算黎曼心质的任务进行竞争性。

Projection robust Wasserstein (PRW) distance, or Wasserstein projection pursuit (WPP), is a robust variant of the Wasserstein distance. Recent work suggests that this quantity is more robust than the standard Wasserstein distance, in particular when comparing probability measures in high-dimensions. However, it is ruled out for practical application because the optimization model is essentially non-convex and non-smooth which makes the computation intractable. Our contribution in this paper is to revisit the original motivation behind WPP/PRW, but take the hard route of showing that, despite its non-convexity and lack of nonsmoothness, and even despite some hardness results proved by~\citet{Niles-2019-Estimation} in a minimax sense, the original formulation for PRW/WPP \textit{can} be efficiently computed in practice using Riemannian optimization, yielding in relevant cases better behavior than its convex relaxation. More specifically, we provide three simple algorithms with solid theoretical guarantee on their complexity bound (one in the appendix), and demonstrate their effectiveness and efficiency by conducing extensive experiments on synthetic and real data. This paper provides a first step into a computational theory of the PRW distance and provides the links between optimal transport and Riemannian optimization.

在本文中，我们通过推断在歧管上的迭代来提出一种简单的加速度方案，用于利曼梯度方法。我们显示何时从Riemannian梯度下降法生成迭代元素，加速方案是渐近地达到最佳收敛速率，并且比最近提出的Riemannian Nesterov加速梯度方法在计算上更有利。我们的实验验证了新型加速策略的实际好处。

我们考虑非凸凹minimax问题，$ \ min _ {\ mathbf {x}} \ mathcal {y}} f（\ mathbf {x}，\ mathbf {y}）$， $ f $在$ \ mathbf {x} $ on $ \ mathbf {y} $和$ \ mathcal {y} $中的$ \ \ mathbf {y} $。解决此问题的最受欢迎的算法之一是庆祝的梯度下降上升（GDA）算法，已广泛用于机器学习，控制理论和经济学。尽管凸凹设置的广泛收敛结果，但具有相等步骤的GDA可以收敛以限制循环甚至在一般设置中发散。在本文中，我们介绍了两次尺度GDA的复杂性结果，以解决非膨胀凹入的最小问题，表明该算法可以找到函数$ \ phi（\ cdot）的静止点：= \ max _ {\ mathbf {Y} \ In \ Mathcal {Y}} F（\ CDOT，\ MATHBF {Y}）高效。据我们所知，这是对这一环境中的两次尺度GDA的第一个非因对药分析，阐明了其在培训生成对抗网络（GANS）和其他实际应用中的优越实际表现。

黎曼优化中加速梯度方法的研究最近见证了显着的进展。然而，与欧几里德的环境相比，利莫曼环境仍然缺乏对加速的系统理解。我们重新审视\ citet {monteiro2013accelerated}的\ citet {monteiro2013accelerated}的\ citeterated {monteiro2013accelerated}，这是一个强大的框架，用于获得加速的欧几里德方法。随后，我们提出了一个Riemannian版的A-HPE。我们对Riemannian A-HPE分析的基础是欧几里德A-HPE的一系列洞察力，我们将仔细控制Riemannian几何形状引起的扭曲。我们描述了许多riemannian加速梯度方法作为我们框架的具体实例。

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

通过在线规范相关性分析的问题，我们提出了\ emph {随机缩放梯度下降}（SSGD）算法，以最小化通用riemannian歧管上的随机功能的期望。 SSGD概括了投影随机梯度下降的思想，允许使用缩放的随机梯度而不是随机梯度。在特殊情况下，球形约束的特殊情况，在广义特征向量问题中产生的，我们建立了$ \ sqrt {1 / t} $的令人反感的有限样本，并表明该速率最佳最佳，直至具有积极的积极因素相关参数。在渐近方面，一种新的轨迹平均争论使我们能够实现局部渐近常态，其速率与鲁普特 - Polyak-Quaditsky平均的速率匹配。我们将这些想法携带在一个在线规范相关分析，从事文献中的第一次获得了最佳的一次性尺度算法，其具有局部渐近融合到正常性的最佳一次性尺度算法。还提供了用于合成数据的规范相关分析的数值研究。

非滑动非概念优化问题在机器学习和业务决策中广泛出现，而两个核心挑战阻碍了具有有限时间收敛保证的有效解决方案方法的开发：缺乏计算可触及的最佳标准和缺乏计算功能强大的口腔。本文的贡献是两个方面。首先，我们建立了著名的Goldstein Subdferential〜 \ Citep {Goldstein-1977-Optimization}与均匀平滑之间的关系，从而为设计有限时间融合到一组无梯度的方法的基础和直觉提供了基础和直觉戈德斯坦固定点。其次，我们提出了无梯度方法（GFM）和随机GFM，用于解决一类非平滑非凸优化问题，并证明它们两个都可以返回$（\ delta，\ epsilon）$ - Lipschitz函数的Goldstein Sentary Point $ f $以$ o（d^{3/2} \ delta^{ - 1} \ epsilon^{ - 4}）$的预期收敛速率为$ o（d^{3/2} \ delta^{ - 1} \ epsilon^{ - 4}）$，其中$ d $是问题维度。还提出了两阶段版本的GFM和SGFM，并被证明可以改善大泄漏结果。最后，我们证明了2-SGFM使用\ textsc {minst}数据集对训练Relu神经网络的有效性。

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.

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

本文重点介绍了静态和时变设置中决策依赖性分布的随机鞍点问题。这些是目标是随机收益函数的预期值，其中随机变量从分布图引起的分布中绘制。对于一般分布地图，即使已知分布是已知的，发现鞍点的问题也是一般的计算繁琐。为了实现易求解的解决方案方法，我们介绍了均衡点的概念 - 这是它们诱导的静止随机最小值问题的马鞍点 - 并为其存在和唯一性提供条件。我们证明，两个类解决方案之间的距离被界定，条件是该目标具有强凸强 - 凹入的收益和Lipschitz连续分布图。我们开发确定性和随机的原始算法，并证明它们对均衡点的收敛性。特别是，通过将来自随机梯度估计器的出现的错误建模为子-Weibull随机变量，我们提供期望的错误界限，并且在每个迭代的高概率中提供的误差;此外，我们向期望和几乎肯定地显示给社区的融合。最后，我们调查了分布地图的条件 - 我们调用相反的混合优势 - 确保目标是强烈的凸强 - 凹陷的。在这种假设下，我们表明原始双算法以类似的方式汇集到鞍座点。

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

In the paper, we study a class of useful minimax problems on Riemanian manifolds and propose a class of effective Riemanian gradient-based methods to solve these minimax problems. Specifically, we propose an effective Riemannian gradient descent ascent (RGDA) algorithm for the deterministic minimax optimization. Moreover, we prove that our RGDA has a sample complexity of $O(\kappa^2\epsilon^{-2})$ for finding an $\epsilon$-stationary solution of the Geodesically-Nonconvex Strongly-Concave (GNSC) minimax problems, where $\kappa$ denotes the condition number. At the same time, we present an effective Riemannian stochastic gradient descent ascent (RSGDA) algorithm for the stochastic minimax optimization, which has a sample complexity of $O(\kappa^4\epsilon^{-4})$ for finding an $\epsilon$-stationary solution. To further reduce the sample complexity, we propose an accelerated Riemannian stochastic gradient descent ascent (Acc-RSGDA) algorithm based on the momentum-based variance-reduced technique. We prove that our Acc-RSGDA algorithm achieves a lower sample complexity of $\tilde{O}(\kappa^{4}\epsilon^{-3})$ in searching for an $\epsilon$-stationary solution of the GNSC minimax problems. Extensive experimental results on the robust distributional optimization and robust Deep Neural Networks (DNNs) training over Stiefel manifold demonstrate efficiency of our algorithms.

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.

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

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.

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

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