我院机械学习与应用中心濮实教授团队的论文“Improving the transient times for distributed stochastic gradient methods”以长文揭晓在自动控制领域国际顶刊 IEEE Transactions on Automatic Control 上。。。。。。。
该文章提出了一种新的无中心漫衍式随机梯度算法 EDAS，，，，，并从理论和实验上证实晰其先进性。。。。。。。
论文链接：https://ieeexplore.ieee.org/abstract/document/9865230
研究配景
近年来，，，，，基于无中心网络拓扑结构的无中心漫衍式优化算法逐渐受到研究者的关注。。。。。。。无中心漫衍式的架构不依赖于中心主节点举行协调，，，，，而是由每个节点在与其邻人节点举行有限的信息交流的基础上实现自主决议，，，，，具有通讯价钱低、数据清静性强、适合实时应用等诸多优点。。。。。。。图一展示了无中心漫衍式结构与有中心漫衍式结构的区别。。。。。。。
图一：无中心漫衍式结构（左）和有中心漫衍式结构（右）
然而，，，，，无中心漫衍式优化算法的收敛速率会受到网络通讯拓扑结构的显著影响。。。。。。。近期，，，，，一些漫衍式随机梯度算法被证实在经由若干步迭代后，，，，，能够取得与有中心随机梯度下降（SGD）算法相当的收敛速率，，，，，似乎不受网络结构的影响。。。。。。。该征象被称为渐近网络无关。。。。。。。而抵达与网络无关的收敛速率所需要的迭代次数被称为暂态时间[1]。。。。。。。本文提出了一类新的无中心漫衍式随机优化算法（EDAS），，，，，针对强凸平滑目的函数实现了已知最短的暂态时间 O(n/(1-λ))，，，，，其中 n 体现网络节点数，，，，，1-λ 代表混淆矩阵（mixing matrix）的谱隙（spectral gap）。。。。。。。为利便较量，，，，，表1列出了相关算法的暂态时间（参考文献[7]和[8]于近期更新了的关于DSGT的暂态时间为 O(max{n/(1-λ), n1/3/(1-λ)4/3})）。。。。。。。
表1: 差别算法的暂态时间较量
图二：EDAS 算法的渐近网络无关特征展示
研究要领
本文解决如下的漫衍式优化问题：
其中 fi(x) 为每个节点 i 的（期望意义下的）外地损失函数。。。。。。。受算法 Exact Diffusion[2]和 NIDS[3]启发，，，，，我们提出新的基于递减步长的漫衍式随机梯度下降算法 EDAS：
无中心漫衍式优化算法的误差通？？？？ ？善饰鑫恢滦晕蟛睿╟onsensus error）和优化误差（optimization error）两部分。。。。。。。因此本文剖析的焦点头脑是，，，，，通太过别获得上述两种误差的递归关系，，，，，推导算法的收敛速率。。。。。。。由于 EDAS 更新时涉及到多步的迭代变量，，，，，我们引入新的变量 y，，，，，获得一个易于剖析的等价形式：
其中矩阵 V=[vij] 知足 V 2=I-W。。。。。。。之后，，，，，通过给出 x 和 y 的最优条件（optimality conditions），，，，，我们研究上述迭代式经由一系列转换后的两个误差项，，，，，其中一项体现优化误差，，，，，一项体现 x 和 y 的一致性误差。。。。。。。只管这两个误差项是经由变换后的，，，，，我们仍能通过其与原误差的关系获得 EDAS 的误差收敛效果。。。。。。。文章余下的办法即为描绘前述两项转换后的误差项的递归关系式。。。。。。。最终经由详细推导，，，，，我们获得关于 EDAS 的如下收敛效果：
通太过析以上收敛性效果，，，，，我们描绘出 EDAS 的暂态时间为 n/(1-λ) 。。。。。。。同时，，，，，我们也用一组数值实验验证了该效果的准确性（图3-4）：
图 3：EDAS 在环形图上的暂态时间
图 4：EDAS 在网格图上的暂态时间
最后，，，，，我们较量了 EDAS 与 DSGD，，，，，DSGT，，，，，以及 SGD 等算法在差别网络结构下的收敛性效果（图6-7）。。。。。。？？？？ ？梢钥闯 EDAS 相关于其他无中心漫衍式随机梯度算法的优越性。。。。。。。
图 5：环形图，，，，，n=60
图 6：网格图，，，，，n=121
研究结论
本文提出了新的无中心漫衍式随机梯度算法 EDAS。。。。。。。针对平滑强凸的目的函数，，，，，EDAS 不但具有渐近网络无关性子，，，，，其暂态时间 O(n/(1-λ)) 也领先于所有已知算法。。。。。。。文章从理论和实验两方面证实晰新算法的先进性。。。。。。。
作者简介
黄琨于2018年获同济大学数学科学学院数学与应用数学学士学位，，，，，2020年获康涅狄格大学统计学硕士学位，，，，，现在在香港中文大学（深圳）数据科学学院攻读数据科学博士学位。。。。。。。他的研究兴趣包括漫衍式优化。。。。。。。
濮实现任香港中文大学（深圳）数据科学学院助理教授，，，，，优德官网 副研究员。。。。。。。在此之前，，，，，他曾任佛罗里达大学、亚利桑那州立大学和波士顿大学博士后研究员。。。。。。。2012年取得北京大学工学学士学位，，，，，2016年取得弗吉尼亚大学系统工程博士学位。。。。。。。他的主要研究偏向为多智能体网络中的漫衍式优化和机械学习算法。。。。。。。2017年濮实获弗吉尼亚大学 Louis T. Rader 优异结业生声誉称呼。。。。。。。以第一或通讯作者身份在 Mathematical Programming、IEEE Transactions on Automatic Control、SIAM Journal on Control and Optimization、Operations Research 等运筹优化和控制领域的顶级期刊揭晓10余篇论文，，，，，其中一篇代表作入选 ESI 高被引论文。。。。。。。他正在主持国家自然科学基金青年项目、深圳市优异科技立异人才作育项目（优异青年基础研究）等。。。。。。。自2022年起担当 IEEE Control Systems Society 聚会编委。。。。。。。
期刊先容
IEEE Transactions on Automatic Control 建设于1956年，，，，，是自动控制领域的国际顶级期刊，，，，，WJCI 天下期刊影响力指数（自动化与控制辖档挽域）排名第一。。。。。。。论文分为长文（full paper）和随笔两类，，，，，其中长文揭晓需要主要研究（significant research）。。。。。。。
参考文献：
[1] Pu, S., Olshevsky, A., & Paschalidis, I. C. (2020). Asymptotic network independence in distributed stochastic optimization for machine learning: Examining distributed and centralized stochastic gradient descent. IEEE signal processing magazine, 37(3), 114-122.
[2] Yuan, K., Ying, B., Zhao, X., & Sayed, A. H. (2018). Exact diffusion for distributed optimization and learning—Part I: Algorithm development. IEEE Transactions on Signal Processing, 67(3), 708-723.
[3] Li, Z., Shi, W., & Yan, M. (2019). A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates. IEEE Transactions on Signal Processing, 67(17), 4494-4506.
[4] Koloskova, A., Stich, S., & Jaggi, M. (2019, May). Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning (pp. 3478-3487). PMLR.
[5] Pu, S., Olshevsky, A., & Paschalidis, I. C. (2021). A sharp estimate on the transient time of distributed stochastic gradient descent. IEEE Transactions on Automatic Control.
[6] Pu, S., & Nedi?, A. (2021). Distributed stochastic gradient tracking methods. Mathematical Programming, 187(1), 409-457.
[7] Alghunaim, S. A., & Yuan, K. (2022). A unified and refined convergence analysis for non-convex decentralized learning. IEEE Transactions on Signal Processing, 70, 3264-3279.
[8] Koloskova, A., Lin, T., & Stich, S. U. (2021). An improved analysis of gradient tracking for decentralized machine learning. Advances in Neural Information Processing Systems, 34, 11422-11435.
