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

在本文中，我们提出了一种新的Hessian逆自由单环算法（FSLA），用于彼此优化问题。 Bilevel优化的经典算法承认计算昂贵的双回路结构。最近，已经提出了几种单循环算法，其具有优化内部和外部变量。但是，这些算法尚未实现完全单循环。因为它们忽略了评估给定内部和外部状态的超梯度所需的循环。为了开发一个完全单环算法，我们首先研究超梯度的结构，并识别超梯度计算的一般近似配方，这些计算包括几种先前的常见方法，例如，通过时间，共轭渐变，\ emph {等}基于此配方，介绍一个新的状态变量来维护历史超梯度信息。将我们的新配方与内外变量的替代更新相结合，我们提出了一种高效的全循环算法。理论上我们可以显示新状态生成的错误可以界限，我们的算法收敛于$ O（\ epsilon ^ {-2}）$。最后，我们通过基于多个Bilevel优化的机器学习任务验证了我们验证的算法。

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

我们研究了一类算法，用于在内部级别物镜强烈凸起时求解随机和确定性设置中的彼此优化问题。具体地，我们考虑基于不精确的隐含区分的算法，并且我们利用热门开始策略来摊销精确梯度的估计。然后，我们介绍了一个统一的理论框架，受到奇异的扰动系统（Habets，1974）的研究来分析这种摊销算法。通过使用此框架，我们的分析显示了匹配可以访问梯度无偏见估计的Oracle方法的计算复杂度的算法，从而优于彼此优化的许多现有结果。我们在合成实验中说明了这些发现，并展示了这些算法对涉及几千个变量的超参数优化实验的效率。

二重优化发现在现代机器学习问题中发现了广泛的应用，例如超参数优化，神经体系结构搜索，元学习等。而具有独特的内部最小点（例如，内部功能是强烈凸的，都具有唯一的内在最小点）的理解，这是充分理解的，多个内部最小点的问题仍然是具有挑战性和开放的。为此问题设计的现有算法适用于限制情况，并且不能完全保证融合。在本文中，我们采用了双重优化的重新制定来限制优化，并通过原始的双二线优化（PDBO）算法解决了问题。 PDBO不仅解决了多个内部最小挑战，而且还具有完全一阶效率的情况，而无需涉及二阶Hessian和Jacobian计算，而不是大多数现有的基于梯度的二杆算法。我们进一步表征了PDBO的收敛速率，它是与多个内部最小值的双光线优化的第一个已知的非质合收敛保证。我们的实验证明了所提出的方法的预期性能。

标准联合优化方法成功地适用于单层结构的随机问题。然而，许多当代的ML问题 - 包括对抗性鲁棒性，超参数调整和参与者 - 批判性 - 属于嵌套的双层编程，这些编程包含微型型和组成优化。在这项工作中，我们提出了\ fedblo：一种联合交替的随机梯度方法来解决一般的嵌套问题。我们在存在异质数据的情况下为\ fedblo建立了可证明的收敛速率，并引入了二聚体，最小值和组成优化的变化。\ fedblo引入了多种创新，包括联邦高级计算和降低方差，以解决内部级别的异质性。我们通过有关超参数\＆超代理学习和最小值优化的实验来补充我们的理论，以证明我们方法在实践中的好处。代码可在https://github.com/ucr-optml/fednest上找到。

Decentralized bilevel optimization has received increasing attention recently due to its foundational role in many emerging multi-agent learning paradigms (e.g., multi-agent meta-learning and multi-agent reinforcement learning) over peer-to-peer edge networks. However, to work with the limited computation and communication capabilities of edge networks, a major challenge in developing decentralized bilevel optimization techniques is to lower sample and communication complexities. This motivates us to develop a new decentralized bilevel optimization called DIAMOND (decentralized single-timescale stochastic approximation with momentum and gradient-tracking). The contributions of this paper are as follows: i) our DIAMOND algorithm adopts a single-loop structure rather than following the natural double-loop structure of bilevel optimization, which offers low computation and implementation complexity; ii) compared to existing approaches, the DIAMOND algorithm does not require any full gradient evaluations, which further reduces both sample and computational complexities; iii) through a careful integration of momentum information and gradient tracking techniques, we show that the DIAMOND algorithm enjoys $\mathcal{O}(\epsilon^{-3/2})$ in sample and communication complexities for achieving an $\epsilon$-stationary solution, both of which are independent of the dataset sizes and significantly outperform existing works. Extensive experiments also verify our theoretical findings.

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

我们分析了一类养生问题，其中高级问题在于平滑的目标函数的最小化和下层问题是找到平滑收缩图的固定点。这种类型的问题包括元学习，平衡模型，超参数优化和数据中毒对抗性攻击的实例。最近的几项作品提出了算法，这些算法温暖了较低级别的问题，即他们使用先前的下级近似解决方案作为低级求解器的凝视点。这种温暖的启动程序使人们可以在随机和确定性设置中提高样品复杂性，在某些情况下可以实现订单的最佳样品复杂性。但是，存在一些情况，例如元学习和平衡模型，其中温暖的启动程序不适合或无效。在这项工作中，我们表明没有温暖的启动，仍然可以实现订单的最佳或近乎最佳的样品复杂性。特别是，我们提出了一种简单的方法，该方法在下层下使用随机固定点迭代，并在上层处预测不精确的梯度下降，该梯度下降到达$ \ epsilon $ -Stationary Point，使用$ O（\ Epsilon^{-2） }）$和$ \ tilde {o}（\ epsilon^{ - 1}）$样本分别用于随机和确定性设置。最后，与使用温暖启动的方法相比，我们的方法产生了更简单的分析，不需要研究上层和下层迭代之间的耦合相互作用

Is it possible for a first-order method, i.e., only first derivatives allowed, to be quadratically convergent? For univariate loss functions, the answer is yes -- the Steffensen method avoids second derivatives and is still quadratically convergent like Newton method. By incorporating an optimal step size we can even push its convergence order beyond quadratic to $1+\sqrt{2} \approx 2.414$. While such high convergence orders are a pointless overkill for a deterministic algorithm, they become rewarding when the algorithm is randomized for problems of massive sizes, as randomization invariably compromises convergence speed. We will introduce two adaptive learning rates inspired by the Steffensen method, intended for use in a stochastic optimization setting and requires no hyperparameter tuning aside from batch size. Extensive experiments show that they compare favorably with several existing first-order methods. When restricted to a quadratic objective, our stochastic Steffensen methods reduce to randomized Kaczmarz method -- note that this is not true for SGD or SLBFGS -- and thus we may also view our methods as a generalization of randomized Kaczmarz to arbitrary objectives.

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.

在本文中，我们提出了一种称为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的实践优势。

标准梯度下降（GDA） - 型算法只能在非凸极小优化中找到固定点，这比局部minimax点比局部最佳。在这项工作中，我们开发了GDA型算法，这些算法在非convex-rong-concave minimax优化中全球收敛到局部minimax点。我们首先观察到局部最小点等效于某个包膜函数的二阶固定点。然后，受到经典立方正则化算法的启发，我们提出了Cubic-GDA（一种用于查找局部最小值点的立方体规范化的GDA算法），并通过利用其内在潜在功能来提供全面的收敛分析。具体而言，我们以sublinear收敛速率建立了立方GDA与局部最小点的全球收敛。我们进一步分析了在局部梯度显性型非凸几何形状的整个频谱中立方GDA的渐近收敛速率，比标准GDA更快地建立秩序的渐近收敛速率。此外，我们提出了用于大规模最小优化的立方GDA的随机变体，并在随机子采样下表征其样品复杂性。

在本文中，我们考虑了在$ N $代理的分布式优化问题，每个都具有本地成本函数，协作最小化连接网络上的本地成本函数的平均值。为了解决问题，我们提出了一种分布式随机重新洗脱（D-RR）算法，该算法结合了经典分布式梯度下降（DGD）方法和随机重新洗脱（RR）。我们表明D-RR继承了RR的优越性，以使光滑强凸和平的非凸起目标功能。特别是，对于平稳强凸的目标函数，D-RR在平方距离方面实现$ \ Mathcal {o}（1 / T ^ 2）$汇率（这里，$ t $计算迭代总数）在迭代和独特的最小化之间。当假设客观函数是平滑的非凸块并且具有Lipschitz连续组件函数时，我们将D-RR以$ \ Mathcal {O}的速率驱动到0美元的平方标准（1 / T ^ {2 / 3}）$。这些收敛结果与集中式RR（最多常数因素）匹配。

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

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

近年来，由于它们在对点对点网络上的分散性学习问题（例如，多机构元学习，多机构的多方强化增强学习学习）上，分散的双层优化问题在网络和机器学习社区中引起了越来越多的关注。 ，个性化的培训和拜占庭的弹性学习）。但是，对于具有有限的计算和通信功能的对等网络上的分散式双层优化，如何实现低样本和通信复杂性是迄今为止尚未探索的两个基本挑战。在本文中，我们首次尝试研究了分别与外部和内部子问题相对应的非凸和强结构结构的分散双重优化问题。本文中我们的主要贡献是两倍：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}）$在达到与确定算法相同的通信复杂性时。据我们所知，这项工作是第一个实现低样本和通信复杂性，以解决网络上的分散双层优化问题。我们的数值实验也证实了我们的理论发现。

Nonconvex optimization is central in solving many machine learning problems, in which block-wise structure is commonly encountered. In this work, we propose cyclic block coordinate methods for nonconvex optimization problems with non-asymptotic gradient norm guarantees. Our convergence analysis is based on a gradient Lipschitz condition with respect to a Mahalanobis norm, inspired by a recent progress on cyclic block coordinate methods. In deterministic settings, our convergence guarantee matches the guarantee of (full-gradient) gradient descent, but with the gradient Lipschitz constant being defined w.r.t.~the Mahalanobis norm. In stochastic settings, we use recursive variance reduction to decrease the per-iteration cost and match the arithmetic operation complexity of current optimal stochastic full-gradient methods, with a unified analysis for both finite-sum and infinite-sum cases. We further prove the faster, linear convergence of our methods when a Polyak-{\L}ojasiewicz (P{\L}) condition holds for the objective function. To the best of our knowledge, our work is the first to provide variance-reduced convergence guarantees for a cyclic block coordinate method. Our experimental results demonstrate the efficacy of the proposed variance-reduced cyclic scheme in training deep neural nets.

交替的梯度 - 下降 - 上升（Altgda）是一种优化算法，已广泛用于各种机器学习应用中的模型培训，其旨在解决非渗透最小新的优化问题。然而，现有的研究表明，它遭受了非凸起最小值优化中的高计算复杂性。在本文中，我们开发了一种单环和快速Altgda型算法，利用了近端渐变更新和动量加速来解决正常的非透露极限优化问题。通过识别该算法的内在Lyapunov函数，我们证明它会收敛到非凸起最小化优化问题的临界点，并实现了计算复杂度$ \ mathcal {o}（\ kappa ^ {1.5} \ epsilon ^ { - 2} ）$，其中$ \ epsilon $是理想的准确度，$ \ kappa $是问题的条件号。这种计算复杂性改善了单环GDA和AltGDA算法的最先进的复杂性（参见表1中的比较摘要）。我们通过对对抗深层学习的实验展示了算法的有效性。

为了提高分布式学习的训练速度，近年来见证了人们对开发同步和异步分布式随机方差减少优化方法的极大兴趣。但是，所有现有的同步和异步分布式训练算法都遭受了收敛速度或实施复杂性的各种局限性。这激发了我们提出一种称为\ algname（\ ul {s} emi-as \ ul {yn}的算法} ent \ ul {s} earch），它利用方差减少框架的特殊结构来克服同步和异步分布式学习算法的局限性，同时保留其显着特征。我们考虑分布式和共享内存体系结构下的\ algname的两个实现。我们表明我们的\ algname算法具有\（o（\ sqrt {n} \ epsilon^{ - 2}（ - 2}（\ delta+1）+n）\）\）和\（o（\ sqrt {n} {n} 2}（\ delta+1）d+n）\）用于实现\（\ epsilon \）的计算复杂性 - 分布式和共享内存体系结构分别在非convex学习中的固定点，其中\（n \）表示培训样本的总数和\（\ delta \）表示工人的最大延迟。此外，我们通过建立二次强烈凸和非convex优化的算法稳定性界限来研究\ algname的概括性能。我们进一步进行广泛的数值实验来验证我们的理论发现