Nov, 2023

分布式双层优化的单循环算法

PDF
TL;DR在这篇论文中，我们考虑了分散网络中的双层优化问题，提出了一种针对具有强凸下层问题的分散式双层优化的新型单循环算法。我们的算法完全是单循环算法，在逼近超梯度时不需要进行复杂的矩阵向量乘法。此外，与现有的分散式双层优化和联邦双层优化方法不同的是，我们的算法不需要任何梯度异质性假设。我们的分析结果显示，该算法达到了迄今为止双层优化算法的最佳收敛速度。
bilevel optimizationdecentralized networkssingle-loop algorithmstrongly convex lower level problemconvergence rate
发现论文，激发创造
  • 去中心化双层优化

    研究了分散设置下非凸强凸双层优化问题，在确定性和随机双层优化问题上设计了分散算法。分析了算法的收敛速度，包括在代理间观察到数据异构性的情况。通过对合成和真实数据的数值实验表明，所提出的方法是有效的。

    Jun, 2022

  • 分散双层优化的通信复杂度

    我们开发了一种新颖的去中心化随机双层梯度下降算法，在异构环境中具有每轮小的通信成本和通信轮数，从而比现有算法实现了更好的通信复杂度。我们还将我们的算法扩展到更具挑战性的去中心化多级优化问题。根据我们的知识，我们是第一次在异构环境下实现这些理论结果。最后，实验结果证实了我们算法的有效性。

    Nov, 2023

  • 无黑塞矩阵逆的双层优化全单循环算法

    本文提出了一种新的基于 Hessian 的、不需要求逆的完全单循环算法 (FSLA) 用于双层优化问题，并理论和实践上验证了该算法的有效性。

    Dec, 2021

  • 图上分布式双层优化：无环算法更新和瞬态迭代复杂度

    通过引入单循环去中心化的 SBO（D-SOBA）算法，并建立其瞬态迭代复杂度，本文首次澄清了网络拓扑和数据异质性对去中心化双层算法的联合影响。与现有方法相比，D-SOBA 算法在更宽松的假设条件下实现了与现有方法相比最先进的渐近速率、渐近梯度 / 海森复杂度和瞬态迭代复杂度。数值实验验证了我们的理论发现。

    Feb, 2024

  • 双层优化的下界和加速算法

    该论文从两个方面揭示双层优化的收敛率：提出首个双层加速优化器 AccBiO 并给出无梯度边界假设的复杂度上限，同时得出更紧的下限。此外，论文还证明在某些情况下，双层优化比极大极小问题更具有挑战性。关键词包括双层优化、收敛率、下限复杂度、AccBiO 和二次型条件数。

    Feb, 2021

  • 无界平滑的双层优化：一种新算法和收敛性分析

    设计了一种名为 BO-REP 的新的双层优化算法，用于解决具有潜在无界平滑性的神经网络在双层优化问题中的挑战。证明了在随机环境下，该算法需要大约 1/ε^4 次迭代来找到一个 ε- 稳定点，结果与有界平滑度设置和没有均方平滑性的随机梯度的最新复杂度结果相匹配。实验证明了所提出算法在超表征学习、超参数优化和文本分类任务中的有效性。

    Jan, 2024

  • 异步分布式双层优化

    提出了一种异步分布式双层优化 (ADBO) 算法，旨在解决中心化和同步分布式双层优化遇到的难题，可处理具有非凸上下层目标函数的双层优化问题，理论上收敛，并且迭代复杂度上界是 O (1/ε²)；通过实验研究验证了 ADBO 的有效性和高效性。

    Dec, 2022

  • 双层优化的可证明更快算法

    本论文提出了两种新的双层优化算法，第一种采用基于动量的递归迭代算法，第二种采用嵌套循环中的递归梯度估计以减少方差。我们表明，两种算法都实现了 Ω（ε^ -1.5）计算量的复杂度，超越了所有现有算法一个数量级。本文的实验证明了我们算法在超参数优化应用中的优越性能。

    Jun, 2021

  • 一种通用的交替方法用于满足 Polyak-Łojasiewicz 条件的二层优化

    提出了一种推广后的交替优化方法（GALET）用于双层优化问题，可以适用于具有非凸下层目标函数的问题，并具有与一阶梯度下降相同的收敛速度。

    Jun, 2023

  • 机器学习中的双层优化：算法设计与收敛分析

    本篇论文提供了多方面的双层优化算法收敛速度分析，包括问题和算法两个方面，提出了更加高效可扩展的算法设计，并最终提出了新的随机双层优化算法降低了实践中的复杂度并提高其效率。

    Jul, 2021