在本文中，我们研究了多块最小双重双层优化问题，其中上层是非凸线的最小值最小值目标，而下层级别是一个强烈的凸目标，并且有多个双重变量块和下层级别。问题。由于交织在一起的多块最小双重双重结构，每次迭代处的计算成本可能高高，尤其是在大量块中。为了应对这一挑战，我们提出了一种单循环随机随机算法，该算法需要在每次迭代时仅恒定数量的块进行更新。在对问题的一些温和假设下，我们建立了$ \ Mathcal {o}（1/\ Epsilon^4）$的样本复杂性，用于查找$ \ epsilon $ - 稳定点。这匹配了在一般无偏见的随机甲骨文模型下求解随机非convex优化的最佳复杂性。此外，我们在多任务深度AUC（ROC曲线下）最大化和多任务深度部分AUC最大化中提供了两种应用。实验结果验证了我们的理论，并证明了我们方法对数百个任务问题的有效性。

在本文中，我们考虑基于移动普通（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，改善最先进的结果。对于所有这些问题，我们还建立了使用随机梯度估计器的差异递减结果。

在本文中，我们提出了适用于深度学习的单向和双向部分AUC（PAUC）最大化的系统和高效的基于梯度的方法。我们通过使用分布强大的优化（DRO）来定义每个单独的积极数据的损失，提出了PAUC替代目标的新公式。我们考虑了两种DRO的配方，其中一种是基于条件 - 价值风险（CVAR），该风险（CVAR）得出了PAUC的非平滑但精确的估计器，而另一个基于KL差异正则DRO产生不确定的dro。但是PAUC的平滑（软）估计器。对于单向和双向PAUC最大化，我们提出了两种算法，并证明了它们分别优化其两种配方的收敛性。实验证明了所提出的算法对PAUC最大化的有效性，以对各种数据集进行深度学习。

NDCG是标准化的折扣累积增益，是信息检索和机器学习中广泛使用的排名指标。但是，仍然缺乏最大化NDCG的有效且可证明的随机方法，尤其是对于深层模型。在本文中，我们提出了一种优化NDCG及其最高$ K $变体的原则方法。首先，我们制定了一个新颖的组成优化问题，以优化NDCG替代物，以及一个新型的双层构图优化问题，用于优化顶部$ K $ NDCG代理。然后，我们开发有效的随机算法，并为非凸目标提供可证明的收敛保证。与现有的NDCG优化方法不同，我们的算法量表的均量复杂性与迷你批量大小，而不是总项目的数量。为了提高深度学习的有效性，我们通过使用初始热身和停止梯度操作员进一步提出实用策略。多个数据集的实验结果表明，我们的方法在NDCG方面优于先前的排名方法。据我们所知，这是首次提出随机算法以优化具有可证明的收敛保证的NDCG。我们提出的方法在https://libauc.org/的libauc库中实现。

X-fisk是一个介绍的术语，以代表组成量度或目标家族，其中每个数据点与一组数据点显式或隐式进行比较，以定义风险函数。它包括许多广泛使用的措施或目标在一定的召回水平上的精确度，对比目标等处于最高$ K $的位置。尽管在机器学习，计算机视觉，信息检索等文献中已经研究了这些措施/目标及其优化算法，但优化了这些措施/目标在深度学习方面遇到了一些独特的挑战。在这份技术报告中，我们通过重点关注其算法基础，调查了最近对深X风险优化（DXO）的严格努力。我们介绍了一类技术，以优化X风险以进行深度学习。我们分别将DXO分别属于非凸端优化的非凸优化问题的三个特殊家族，分别分别属于Min-Max优化，非凸组成优化和非Convex Bilevel优化。对于每个问题家族，我们提出了一些强大的基线算法及其复杂性，这将激发进一步的研究以改善现有结果。关于提出的结果和未来研究的讨论在最后进行。在www.libauc.org的libauc库中实现了用于优化各种X风险的有效算法。

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

ROC（AUROC）和精密召回曲线（AUPRC）的区域是用于评估不平衡问题的分类性能的常见度量。与AUROC相比，AUPRC是一个更合适的度量，用于高度不平衡的数据集。虽然已经广泛研究了Auroc的随机优化，但Auprc的原则随机优化已经很少被探索。在这项工作中，我们提出了一个原则的技术方法来优化Auprc进行深度学习。我们的方法是基于最大化平均精度（AP），这是Auprc的一个非偏见点估计器。我们将目标分为{\ IT依赖的组成函数}的总和，内部函数取决于外层的随机变量。通过利用随机成分优化的最新进展，我们提出了具有{\ IT可提供的收敛保证的皂的适应性和非自适应随机算法。图像和图表数据集的广泛实验结果表明，我们所提出的方法在AUPRC方面占据了对不平衡问题的现有方法。据我们所知，我们的工作代表了第一次尝试使用可提供的融合优化AUPRC。 SOAP已在Libauc库中在〜\ URL {https://libauc.org/}中实现。

在本文中，我们提出了一种实用的在线方法，用于解决具有非凸面目标的一类分布稳健优化（DRO），这在机器学习中具有重要应用，以改善神经网络的稳健性。在文献中，大多数用于解决DRO的方法都基于随机原始方法。然而，DRO的原始方法患有几个缺点：（1）操纵对应于数据尺寸的高维双变量是昂贵的; （2）他们对网上学习不友好，其中数据顺序地发表。为了解决这些问题，我们考虑一类具有KL发散正则化的Dual变量的DRO，将MIN-MAX问题转换为组成最小化问题，并提出了无需较大的批量批量的无需线在线随机方法。我们建立了所提出的方法的最先进的复杂性，而无需多达\ L Ojasiewicz（PL）条件。大规模深度学习任务（i）的实证研究表明，我们的方法可以将培训加速超过2次，而不是基线方法，并在带有$ \ SIM $ 265K图像的大型数据集上节省培训时间。 （ii）验证DRO对实证数据集上的经验风险最小化（ERM）的最高表现。独立兴趣，所提出的方法也可用于解决与最先进的复杂性的随机成分问题家族。

本文研究了一系列组成函数的随机优化，其中每个汇总的内部函数与相应的求和指数耦合。我们将这个问题家族称为有限和耦合的组成优化（FCCO）。它在机器学习中具有广泛的应用，用于优化非凸或凸组成措施/目标，例如平均精度（AP），p-norm推动，列表排名损失，邻居组成分析（NCA），深度生存分析，深层可变模型等等，这应该得到更精细的分析。然而，现有的算法和分析在一个或其他方面受到限制。本文的贡献是为非凸和凸目标的简单随机算法提供全面的收敛分析。我们的关键结果是通过使用带有微型批次的基于移动平均的估计器，通过并行加速提高了Oracle的复杂性。我们的理论分析还展示了通过对外部和内部水平相等大小的批量来改善实际实现的新见解。关于AP最大化，NCA和P-norm推动的数值实验证实了该理论的某些方面。

本文分析了双模的彼此优化随机算法框架。 Bilevel优化是一类表现出两级结构的问题，其目标是使具有变量的外目标函数最小化，该变量被限制为对（内部）优化问题的最佳解决方案。我们考虑内部问题的情况是不受约束的并且强烈凸起的情况，而外部问题受到约束并具有平滑的目标函数。我们提出了一种用于解决如此偏纤维问题的两次时间尺度随机近似（TTSA）算法。在算法中，使用较大步长的随机梯度更新用于内部问题，而具有较小步长的投影随机梯度更新用于外部问题。我们在各种设置下分析了TTSA算法的收敛速率：当外部问题强烈凸起（RESP。〜弱凸）时，TTSA算法查找$ \ MATHCAL {O}（k ^ { - 2/3}）$ -Optimal（resp。〜$ \ mathcal {o}（k ^ {-2/5}）$ - 静止）解决方案，其中$ k $是总迭代号。作为一个应用程序，我们表明，两个时间尺度的自然演员 - 批评批评近端策略优化算法可以被视为我们的TTSA框架的特殊情况。重要的是，与全球最优政策相比，自然演员批评算法显示以预期折扣奖励的差距，以$ \ mathcal {o}（k ^ { - 1/4}）的速率收敛。

ROC曲线下的区域（又称AUC）是评估分类器不平衡数据的性能的选择。 AUC最大化是指通过直接最大化其AUC分数来学习预测模型的学习范式。它已被研究了二十年来，其历史可以追溯到90年代后期，从那时起，大量工作就致力于最大化。最近，对大数据和深度学习的深度最大化的随机AUC最大化已受到越来越多的关注，并对解决现实世界中的问题产生了巨大的影响。但是，据我们所知，没有对AUC最大化的相关作品进行全面调查。本文旨在通过回顾过去二十年来审查文献来解决差距。我们不仅给出了文献的整体看法，而且还提供了从配方到算法和理论保证的不同论文的详细解释和比较。我们还确定并讨论了深度AUC最大化的剩余和新兴问题，并就未来工作的主题提供建议。

自2014年发明以来，亚当优化器得到了巨大的关注。一方面，它已被广泛用于深度学习，并且已经提出了许多变体，而另一方面，他们的理论会聚属性仍然是一个谜。在某种意义上，某些研究需要对更新的强烈假设不一定适用，而其他研究仍然遵循ADAM的原始问题收敛分析，这是令人满意的，而其他研究仍然是确保收敛的原始问题收敛分析。虽然ADAM存在严格的收敛分析，但它们对自适应步长的更新施加了特定的要求，这不足以覆盖亚当的许多其他变体。为了解决这些问题，在这个扩展的摘要中，我们为ADAM样式方法（包括亚当，AMSGRAD，Adabound等）提供了一个简单而通用的融合证明。我们的分析只需要一个增加或大的“动量”参数，用于一阶时刻，这实际上是在实践中使用的情况，以及对阶梯尺寸的自适应因子的界限条件，其适用于在温和下的亚当的所有变体随机梯度的条件。我们还建立了使用随机梯度估计器的差异递减结果。实际上，我们对亚当的分析如此简单，通用，可以利用来建立求解更广泛的非凸优化问题的收敛性，包括最小，组成和彼得优化问题。对于此扩展摘要的完整（早期）版本，请参阅ARXIV：2104.14840。

已经对蜘蛛/莎拉/风暴等方差降低技术进行了广泛的研究，以提高随机非凸优化的收敛速率，这些优化通常维护和更新跨迭代中单个函数的估计器序列。 {\如果我们需要在迭代中跟踪多个功能映射，但是只有访问$ \ Mathcal {o}的随机样品（1）$在每次迭代时$ functional映射？}在解决一个新兴的家族时，有一个重要的应用程序以$ \ sum_ {i = 1}^m f_i（g_i（\ mathbf {w}））的形式形式的耦合组合优化问题，其中$ g_i $可通过随机甲骨文访问$ g_i $。关键问题是跟踪和估计$ \ mathbf g（\ mathbf {w}）=（g_1（\ mathbf {w}），\ ldots，g_m（\ mathbf {w}）$ $ \ mathbf g（\ mathbf {w}）$具有$ m $块，只允许探测$ \ mathcal {o}（1）$块才能达到其随机值和雅各布人。为了提高解决这些问题的复杂性，我们提出了一种新型随机方法，称为多块单个探针差异（MSVR）估计器，以跟踪$ \ mathbf g（\ mathbf {w}）$的序列。它的灵感来自风暴，但引入了定制的误差校正术语，不仅可以减轻所选块的随机样品中的噪声，而且还可以减轻那些未进行采样的块中的噪声。在MSVR估计器的帮助下，我们开发了几种算法来解决上述组成问题，并在具有非convex/convex/convex/strank strank convex目标的各种设置中具有改善的复杂性。我们的结果在几个方面都改善了先前的结果，包括样本复杂性和对强凸参数的依赖。多任务深度AUC最大化的经验研究表明，使用新估计器的性能更好。

我们考虑非凸凹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）和其他实际应用中的优越实际表现。

彼得纤维优化已广泛应用于许多重要的机器学习应用，例如普带的参数优化和元学习。最近，已经提出了几种基于动量的算法来解决贝韦尔优化问题。但是，基于SGD的算法的$ \ Mathcal {\ widetilde o}（\ epsilon ^ {-2}），那些基于势头的算法不会达到可释放的计算复杂性。在本文中，我们提出了两种用于双纤维优化的新算法，其中第一算法采用基于动量的递归迭代，第二算法采用嵌套环路中的递归梯度估计来降低方差。我们表明这两种算法都达到了$ \ mathcal {\ widetilde o}的复杂性（\ epsilon ^ { - 1.5}）$，这优于所有现有算法的级别。我们的实验验证了我们的理论结果，并展示了我们在封路数据应用程序中的算法的卓越实证性能。

最近，由于这些问题与一些新兴应用的相关性，最近有许多研究工作用于开发有效算法，以解决理论收敛的保证。在本文中，我们提出了一种统一的单环交替梯度投影（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问题。我们可以在这四个不同的设置下类似地建立所提出算法的梯度复杂性。

In this paper, we tackle a novel federated learning (FL) problem for optimizing a family of X-risks, to which no existing FL algorithms are applicable. In particular, the objective has the form of $\mathbb E_{z\sim S_1} f(\mathbb E_{z'\sim S_2} \ell(w; z, z'))$, where two sets of data $S_1, S_2$ are distributed over multiple machines, $\ell(\cdot)$ is a pairwise loss that only depends on the prediction outputs of the input data pairs $(z, z')$, and $f(\cdot)$ is possibly a non-linear non-convex function. This problem has important applications in machine learning, e.g., AUROC maximization with a pairwise loss, and partial AUROC maximization with a compositional loss. The challenges for designing an FL algorithm lie in the non-decomposability of the objective over multiple machines and the interdependency between different machines. To address the challenges, we propose an active-passive decomposition framework that decouples the gradient's components with two types, namely active parts and passive parts, where the active parts depend on local data that are computed with the local model and the passive parts depend on other machines that are communicated/computed based on historical models and samples. Under this framework, we develop two provable FL algorithms (FeDXL) for handling linear and nonlinear $f$, respectively, based on federated averaging and merging. We develop a novel theoretical analysis to combat the latency of the passive parts and the interdependency between the local model parameters and the involved data for computing local gradient estimators. We establish both iteration and communication complexities and show that using the historical samples and models for computing the passive parts do not degrade the complexities. We conduct empirical studies of FeDXL for deep AUROC and partial AUROC maximization, and demonstrate their performance compared with several baselines.

在许多机器学习应用程序中出现了非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算法在健壮训练中的实际效率。

Bilevel优化是在机器学习的许多领域中最小化涉及另一个功能的价值函数的问题。在大规模的经验风险最小化设置中，样品数量很大，开发随机方法至关重要，而随机方法只能一次使用一些样品进行进展。但是，计算值函数的梯度涉及求解线性系统，这使得很难得出无偏的随机估计。为了克服这个问题，我们引入了一个新颖的框架，其中内部问题的解决方案，线性系统的解和主要变量同时发展。这些方向是作为总和写成的，使其直接得出无偏估计。我们方法的简单性使我们能够开发全球差异算法，其中所有变量的动力学都会降低差异。我们证明，萨巴（Saba）是我们框架中著名的传奇算法的改编，具有$ o（\ frac1t）$收敛速度，并且在polyak-lojasciewicz的假设下实现了线性收敛。这是验证这些属性之一的双光线优化的第一种随机算法。数值实验验证了我们方法的实用性。

近年来，由于它们在对点对点网络上的分散性学习问题（例如，多机构元学习，多机构的多方强化增强学习学习）上，分散的双层优化问题在网络和机器学习社区中引起了越来越多的关注。 ，个性化的培训和拜占庭的弹性学习）。但是，对于具有有限的计算和通信功能的对等网络上的分散式双层优化，如何实现低样本和通信复杂性是迄今为止尚未探索的两个基本挑战。在本文中，我们首次尝试研究了分别与外部和内部子问题相对应的非凸和强结构结构的分散双重优化问题。本文中我们的主要贡献是两倍：i）我们首先提出了一种称为Interact的确定性算法（Inter-gradient-descent-out-outer-tracked-gradeent），需要$ \ Mathcal {o}的样品复杂性（n \ epsilon） ^{ - 1}）$和$ \ mathcal {o}的通信复杂性（\ epsilon^{ - 1}）$解决双重优化问题，其中$ n $和$ \ epsilon> 0 $是样本的数量在每个代理和所需的平稳性差距上。 ii）为了放宽每次迭代中进行全面梯度评估的需求，我们提出了一个随机方差的互动版本（SVR Interact），该版本将样品复杂性提高到$ \ Mathcal {o}（\ sqrt {n} \ epsilon ^{ - 1}）$在达到与确定算法相同的通信复杂性时。据我们所知，这项工作是第一个实现低样本和通信复杂性，以解决网络上的分散双层优化问题。我们的数值实验也证实了我们的理论发现。