提出无需二阶信息的分布式双层优化算法，效率更高。
Fully First-Order Methods for Decentralized Bilevel Optimization
- 仅用一阶梯度信息，降低计算成本。
- 在n个节点下，样本复杂度达O(n⁻¹ε⁻⁷)，实现线性加速。
- 适合大规模分布式机器学习任务，通信与训练更高效。
本文研究分布式随机双层优化（DSBO）问题，其中各智能体仅与邻居通信。提出一种新型算法DSGDA-GT，仅需一阶信息，显著低于现有方法依赖的二阶信息。理论分析表明，当n个智能体协同求解时，找到ε-驻点的样本复杂度为O(n⁻¹ε⁻⁷)，达到单智能体最优结果的线性加速。数值实验验证了该算法在通信和训练效率上的优势。
原文摘要 · Abstract (English)
This paper focuses on decentralized stochastic bilevel optimization (DSBO) where agents only communicate with their neighbors. We propose Decentralized Stochastic Gradient Descent and Ascent with Gradient Tracking (DSGDA-GT), a novel algorithm that only requires first-order oracles that are much cheaper than second-order oracles widely adopted in existing works. We further provide a finite-time convergence analysis showing that for $n$ agents collaboratively solving the DSBO problem, the sample complexity of finding an $ε$-stationary point in our algorithm is $\mathcal{O}(n^{-1}ε^{-7})$, which matches the currently best-known results of the single-agent counterpart with linear speedup. The numerical experiments demonstrate both the communication and training efficiency of our algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。