我们介绍了正规化的弗兰克 - 沃尔夫（Frank-Wolfe），这是一种通用有效的算法，用于推断和学习密集的有条件随机场（CRF）。该算法使用Vanilla Frank-Wolfe优化了CRF推理问题的不连续放松，并具有近似更新，这相当于最大程度地减少正则能量函数。我们提出的方法是对现有算法（例如平均字段或凹形通用程序）的概括。这种观点不仅提供了对这些算法的统一分析，而且还允许一种简单的方法来探索不同的变体，这些变体可能会产生更好的性能。我们在标准语义分割数据集的经验结果中说明了这一点，在该数据集中，我们正规化的Frank-Wolfe优于均值均值推断的几个实例化，无论是独立的组件还是作为神经网络中的端到端可训练层。我们还表明，密集的CRF与我们的新算法相结合，对强CNN基准产生了重大改进。

人工神经网络（ANN）训练景观的非凸起带来了固有的优化困难。虽然传统的背传播随机梯度下降（SGD）算法及其变体在某些情况下是有效的，但它们可以陷入杂散的局部最小值，并且对初始化和普通公共表敏感。最近的工作表明，随着Relu激活的ANN的培训可以重新重整为凸面计划，使希望能够全局优化可解释的ANN。然而，天真地解决凸训练制剂具有指数复杂性，甚至近似启发式需要立方时间。在这项工作中，我们描述了这种近似的质量，并开发了两个有效的算法，这些算法通过全球收敛保证培训。第一算法基于乘法器（ADMM）的交替方向方法。它解决了精确的凸形配方和近似对应物。实现线性全局收敛，并且初始几次迭代通常会产生具有高预测精度的解决方案。求解近似配方时，每次迭代时间复杂度是二次的。基于“采样凸面”理论的第二种算法更简单地实现。它解决了不受约束的凸形制剂，并收敛到大约全球最佳的分类器。当考虑对抗性培训时，ANN训练景观的非凸起加剧了。我们将稳健的凸优化理论应用于凸训练，开发凸起的凸起制剂，培训Anns对抗对抗投入。我们的分析明确地关注一个隐藏层完全连接的ANN，但可以扩展到更复杂的体系结构。

现代统计应用常常涉及最小化可能是非流动和/或非凸起的目标函数。本文侧重于广泛的Bregman-替代算法框架，包括本地线性近似，镜像下降，迭代阈值，DC编程以及许多其他实例。通过广义BREGMAN功能的重新发出使我们能够构建合适的误差测量并在可能高维度下建立非凸起和非凸起和非球形目标的全球收敛速率。对于稀疏的学习问题，在一些规律性条件下，所获得的估算器作为代理人的固定点，尽管不一定是局部最小化者，但享受可明确的统计保障，并且可以证明迭代顺序在所需的情况下接近统计事实准确地快速。本文还研究了如何通过仔细控制步骤和放松参数来设计基于适应性的动力的加速度而不假设凸性或平滑度。

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

在许多机器学习应用程序中出现了非convex-concave min-max问题，包括最大程度地减少一组非凸函数的最大程度，并对神经网络的强大对抗训练。解决此问题的一种流行方法是梯度下降（GDA）算法，不幸的是，在非凸性的情况下可以表现出振荡。在本文中，我们引入了一种“平滑”方案，该方案可以与GDA结合以稳定振荡并确保收敛到固定溶液。我们证明，稳定的GDA算法可以实现$ O（1/\ epsilon^2）$迭代复杂性，以最大程度地减少有限的非convex函数收集的最大值。此外，平滑的GDA算法达到了$ O（1/\ epsilon^4）$ toseration复杂性，用于一般的nonconvex-concave问题。提出了这种稳定的GDA算法的扩展到多块情况。据我们所知，这是第一个实现$ o（1/\ epsilon^2）$的算法，用于一类NonConvex-Concave问题。我们说明了稳定的GDA算法在健壮训练中的实际效率。

We present a new family of subgradient methods that dynamically incorporate knowledge of the geometry of the data observed in earlier iterations to perform more informative gradient-based learning. Metaphorically, the adaptation allows us to find needles in haystacks in the form of very predictive but rarely seen features. Our paradigm stems from recent advances in stochastic optimization and online learning which employ proximal functions to control the gradient steps of the algorithm. We describe and analyze an apparatus for adaptively modifying the proximal function, which significantly simplifies setting a learning rate and results in regret guarantees that are provably as good as the best proximal function that can be chosen in hindsight. We give several efficient algorithms for empirical risk minimization problems with common and important regularization functions and domain constraints. We experimentally study our theoretical analysis and show that adaptive subgradient methods outperform state-of-the-art, yet non-adaptive, subgradient algorithms.

我们在高维批处理设置中提出了统计上健壮和计算高效的线性学习方法，其中功能$ d $的数量可能超过样本量$ n $。在通用学习环境中，我们采用两种算法，具体取决于所考虑的损失函数是否为梯度lipschitz。然后，我们将我们的框架实例化，包括几种应用程序，包括香草稀疏，群 - 帕克斯和低升级矩阵恢复。对于每种应用，这导致了有效而强大的学习算法，这些算法在重尾分布和异常值的存在下达到了近乎最佳的估计率。对于香草$ S $ -SPARSITY，我们能够以重型尾巴和$ \ eta $ - 腐败的计算成本与非企业类似物相当的计算成本达到$ s \ log（d）/n $速率。我们通过开放源代码$ \ mathtt {python} $库提供了有效的算法实现文献中提出的最新方法。

目前的论文研究了最小化损失$ f（\ boldsymbol {x}）$的问题，而在s $ \ boldsymbol {d} \ boldsymbol {x} \的约束，其中$ s $是一个关闭的集合，凸面或非，$ \ boldsymbol {d} $是熔化参数的矩阵。融合约束可以捕获平滑度，稀疏或更一般的约束模式。为了解决这个通用的问题，我们将Beltrami-Courant罚球方法与近距离原则相结合。后者是通过最小化惩罚目标的推动$ f（\ boldsymbol {x}）+ \ frac {\ rho} {2} \ text {dist}（\ boldsymbol {d} \ boldsymbol {x}，s）^ 2 $涉及大型调整常量$ \ rho $和$ \ boldsymbol {d} \ boldsymbol {x} $的平方欧几里德距离$ s $。通过最小化大多数代理函数$ f（\ boldsymbol {x}，从当前迭代$ \ boldsymbol {x} _n $构建相应的近距离算法的下一个迭代$ \ boldsymbol {x} _ {n + 1} $。 ）+ \ frac {\ rho} {2} \ | \ boldsymbol {d} \ boldsymbol {x} - \ mathcal {p} _ {s}（\ boldsymbol {d} \ boldsymbol {x} _n）\ | ^ 2 $。对于固定$ \ rho $和subanalytic损失$ f（\ boldsymbol {x}）$和子质约束设置$ s $，我们证明了汇聚点。在更强大的假设下，我们提供了收敛速率并展示线性本地收敛性。我们还构造了一个最陡的下降（SD）变型，以避免昂贵的线性系统解决。为了基准我们的算法，我们比较乘法器（ADMM）的交替方向方法。我们广泛的数值测试包括在度量投影，凸回归，凸聚类，总变化图像去噪和矩阵的投影到良好状态数的问题。这些实验表明了我们在高维问题上最陡的速度和可接受的准确性。

BREGMAN近端点算法（BPPA）是优化工具箱中的核心之一，一直在目睹新兴应用程序。通过简单易于实现更新规则，该算法对实证成功进行了几种引人注目的直觉，但严格的理由仍然很大程度上是未开发的。我们通过具有可分离数据的分类任务研究BPPA的计算属性，并证明与BPPA相关的可提供算法正则化效果。我们表明BPPA达到了非平凡的余量，这密切依赖于诱导BREGMAN发散的距离产生功能的条件数。我们进一步证明，对于一类问题，对条件数量的依赖性是紧张的，从而表明发散在影响所获得的解决方案的质量方面的重要性。此外，我们还将我们的调查结果扩展到镜像血统（MD），我们建立了边缘和BREGMAN发散之间的类似联系。我们通过具体示例演示，并显示BPPA / MD在相对于Mahalanobis距离的最大边缘解决方案方向上会聚。我们的理论调查结果是第一个展示良性学习特性BPPA / MD的态度，并且还提供校正算法设计中仔细选择的腐败。

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.

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.

Iterative regularization is a classic idea in regularization theory, that has recently become popular in machine learning. On the one hand, it allows to design efficient algorithms controlling at the same time numerical and statistical accuracy. On the other hand it allows to shed light on the learning curves observed while training neural networks. In this paper, we focus on iterative regularization in the context of classification. After contrasting this setting with that of regression and inverse problems, we develop an iterative regularization approach based on the use of the hinge loss function. More precisely we consider a diagonal approach for a family of algorithms for which we prove convergence as well as rates of convergence. Our approach compares favorably with other alternatives, as confirmed also in numerical simulations.

基于梯度的高参数调整的优化方法可确保理论收敛到固定解决方案时，对于固定的上层变量值，双光线程序的下层级别强烈凸（LLSC）和平滑（LLS）。对于在许多机器学习算法中调整超参数引起的双重程序，不满足这种情况。在这项工作中，我们开发了一种基于不精确度（VF-IDCA）的基于依次收敛函数函数算法。我们表明，该算法从一系列的超级参数调整应用程序中实现了无LLSC和LLS假设的固定解决方案。我们的广泛实验证实了我们的理论发现，并表明，当应用于调子超参数时，提出的VF-IDCA会产生较高的性能。

在本文中，我们介绍了泰坦（Titan），这是一种新型的惯性块最小化框架，用于非平滑非凸优化问题。据我们所知，泰坦是块坐标更新方法的第一个框架，该方法依赖于大型最小化框架，同时将惯性力嵌入到块更新的每个步骤中。惯性力是通过外推算子获得的，该操作员累积了重力和Nesterov型加速度，以作为特殊情况作为块近端梯度方法。通过选择各种替代功能，例如近端，Lipschitz梯度，布雷格曼，二次和复合替代功能，并通过改变外推操作员来生成一组丰富的惯性块坐标坐标更新方法。我们研究了泰坦生成序列的子顺序收敛以及全局收敛。我们说明了泰坦对两个重要的机器学习问题的有效性，即稀疏的非负矩阵分解和矩阵完成。

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.

给定数据点之间的一组差异测量值，确定哪种度量表示与输入测量最“一致”或最能捕获数据相关几何特征的度量是许多机器学习算法的关键步骤。现有方法仅限于特定类型的指标或小问题大小，因为在此类问题中有大量的度量约束。在本文中，我们提供了一种活跃的集合算法，即项目和忘记，该算法使用Bregman的预测，以解决许多（可能是指数）不平等约束的度量约束问题。我们提供了\ textsc {project and Hoses}的理论分析，并证明我们的算法会收敛到全局最佳解决方案，并以指数速率渐近地渐近地衰减了当前迭代的$ L_2 $距离。我们证明，使用我们的方法，我们可以解决三种类型的度量约束问题的大型问题实例：一般体重相关聚类，度量近距离和度量学习；在每种情况下，就CPU时间和问题尺寸而言，超越了艺术方法的表现。

本文评价用机器学习问题的数值优化方法。由于机器学习模型是高度参数化的，我们专注于适合高维优化的方法。我们在二次模型上构建直觉，以确定哪种方法适用于非凸优化，并在凸函数上开发用于这种方法的凸起函数。随着随机梯度下降和动量方法的这种理论基础，我们试图解释为什么机器学习领域通常使用的方法非常成功。除了解释成功的启发式之外，最后一章还提供了对更多理论方法的广泛审查，这在实践中并不像惯例。所以在某些情况下，这项工作试图回答这个问题：为什么默认值中包含的默认TensorFlow优化器？

最近，由于这些问题与一些新兴应用的相关性，最近有许多研究工作用于开发有效算法，以解决理论收敛的保证。在本文中，我们提出了一种统一的单环交替梯度投影（AGP）算法，用于求解平滑的非convex-（强烈）凹面和（强烈）凸出 - 非concave minimax问题。 AGP采用简单的梯度投影步骤来更新每次迭代时的原始变量和双变量。我们表明，它可以在$ \ MATHCAL {O} \ left（\ Varepsilon ^{ - 2} \ right）$（rep. $ \ Mathcal {O} \ left）中找到目标函数的$ \ VAREPSILON $ -STAIMATARY点。 （\ varepsilon ^{ - 4} \ right）$）$迭代，在nonconvex-strongly凹面（resp。nonconvex-concave）设置下。此外，获得目标函数的$ \ VAREPSILON $ -STAIMATARY的梯度复杂性由$ \ Mathcal {o} \ left（\ varepsilon ^{ - 2} \ right）界限O} \ left（\ varepsilon ^{ - 4} \ right）$在强烈的convex-nonconcave（resp。，convex-nonconcave）设置下。据我们所知，这是第一次开发出一种简单而统一的单环算法来解决非convex-（强烈）凹面和（强烈）凸出 - 非concave minimax问题。此外，在文献中从未获得过解决后者（强烈）凸线 - 非孔孔的最小问题的复杂性结果。数值结果表明所提出的AGP算法的效率。此外，我们通过提出块交替近端梯度（BAPG）算法来扩展AGP算法，以求解更通用的多块非块非conmooth nonmooth nonmooth noncovex-（强）凹面和（强烈）convex-nonconcave minimax问题。我们可以在这四个不同的设置下类似地建立所提出算法的梯度复杂性。

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

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