Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks
Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks
复制标题
DOI：
10.48550/arxiv.2206.10870
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Shuoguang Yang;Xuezhou Zhang;Mengdi Wang
中科院分区：
文献类型：
--
作者：
Shuoguang Yang;Xuezhou Zhang;Mengdi Wang
双层优化已经获得了越来越多的关注，在Meta学习，极大极小游戏，强化学习和嵌套组合优化中发现了许多应用。本文研究了网络上的分布式双层优化问题，其中智能体只能与邻居通信，包括多任务，多智能体学习和联邦学习的例子。在本文中，我们提出了一个基于流言的分布式双层学习算法，允许网络代理解决内部和外部优化问题在一个单一的时间尺度和共享信息通过网络传播。我们发现，我们的算法享有$\mathcal{O}（\frac{1}{K\epsilon ^2}）$一般非凸双层优化和$\mathcal{O}（\frac{1}{K \epsilon ^2}）$的每个代理的样本复杂度为强凸目标，实现了与网络规模线性缩放的加速比。样本复杂度在$\k $和$K$中都是最优的。我们在超参数调整和分散强化学习的例子上测试了我们的算法。仿真实验表明，该算法在训练效率和测试准确率上都达到了最高水平。
Bilevel optimization have gained growing interests, with numerous applications found in meta learning, minimax games, reinforcement learning, and nested composition optimization. This paper studies the problem of distributed bilevel optimization over a network where agents can only communicate with neighbors, including examples from multi-task, multi-agent learning and federated learning. In this paper, we propose a gossip-based distributed bilevel learning algorithm that allows networked agents to solve both the inner and outer optimization problems in a single timescale and share information via network propagation. We show that our algorithm enjoys the $\mathcal{O}(\frac{1}{K \epsilon^2})$ per-agent sample complexity for general nonconvex bilevel optimization and $\mathcal{O}(\frac{1}{K \epsilon})$ for strongly convex objective, achieving a speedup that scales linearly with the network size. The sample complexities are optimal in both $\epsilon$ and $K$. We test our algorithm on the examples of hyperparameter tuning and decentralized reinforcement learning. Simulated experiments confirmed that our algorithm achieves the state-of-the-art training efficiency and test accuracy.