西南大学李华青等 | 基于梯度跟踪和重球加速的分布式随机优化算法研究

基于梯度跟踪和重球加速的分布式随机优化算法研究

孙碧皓¹，胡锦辉¹，夏大文²，李华青^*1

¹西南大学电子信息工程学院非线性电路与智能信息处理重庆市重点实验室，中国重庆市，400715

²贵州民族大学数据科学与信息工程学院，中国贵阳市，550025

【本文已在线出版，全文请见https://doi.org/10.1631/FITEE.2000615】

01

研究背景

近年来，随着通信技术与计算机技术飞速发展，传统集中式优化算法需要消耗大量时间与计算资源，已不能满足日益增长的大规模问题研究要求；更具鲁棒性和灵活性的分布式优化算法开始受到越来越多关注，逐渐成为新的研究热点。与传统集中式算法不同，分布式优化算法主要包含多个智能体网络，将复杂的大规模问题分解为多个简单的局部目标问题，并分配至网络中的智能体，这些智能体只需处理简单的局部优化问题以及与其邻居节点进行信息交互，即可在数次迭代后求得全局最优解，完成优化任务。许多分布式优化理论研究中，依然存在一些悬而未决的难题，如何设计出更具普适性、能够适应更复杂的具有实际意义问题模型的算法，更深入地研究多智能体分布式优化算法，具有深远意义。

02

研究内容

基于以上背景，我们研究了无向拓扑网络环境下复杂大规模多智能体分布式优化问题，其目标是一个光滑和强凸的局部代价函数的总和，分布在一个具有n个节点的无向网络上。基于已有的分布式一阶优化算法，采用分布重球项提高算法收敛性能，同时，为加快现有分布随机一阶梯度方法的收敛，将动量项与梯度跟踪技术结合。最后，选取适当步长和动量参数，使得提出的算法能够以线性速度收敛至全局最优解。通过逻辑回归、最小二乘和分布式二次规划数值实验及其仿真结果，验证了所提算法理论分析的正确性和可应用性，具有一定的理论意义和应用价值。重点开展了具有梯度跟踪和重球加速的分布式随机优化算法的理论研究，对已有分布式优化理论作了更深入探索，为降低大规模复杂网络环境下的分布式优化所需的计算资源和时间成本提供了重要理论和关键技术。

03

算法分析

设计了基于梯度跟踪和重球加速的分布式随机优化算法，算法的更新框架如图1所示。其中算法引用了无偏平均随机梯度技术，利用k时刻随机计算的瞬时函数的梯度来逼近，当更新时，算法迭代中被替换为，而其余梯度保持不变:

因此，可以得到如下更新公式：

根据上式可得出，只有第一次迭代需要计算全梯度，后续计算通过存储上一次迭代的梯度，只需少量计算即可实现更新，节约了大量计算成本。在第k次迭代时，智能体i的梯度更新如图2所示。

图1  算法更新框架

图2  智能体i在第k次迭代中的梯度更新

04

仿真结果

通过求解一些优化问题，如分布式逻辑回归问题、分布最小二乘回归问题和分布二次规划问题，将提出的算法与已有方法比较，以证明其在收敛速度上明显优于其他算法。所有被测试算法的性能都由表示，仿真实验分别如图3~6所示，实验算法性能数据比较如表1~3所示。其中逻辑回归实验数据集来源于UCI机器学习库http://archive.ics.uci.edu/ml。

图3 逻辑回归实验算法收敛速度比较

图4 逻辑回归实验不同算法精度测试

图5 最小二乘实验算法收敛速度比较

图6 二次规划实验不同算法收敛速度比较

表1 逻辑回归实验算法性能数据比较

表2 最小二乘实验算法性能数据比较

表3 二次规划问题实验算法性能数据比较

引用信息

Bihao Sun, Jinhui Hu, Dawen Xia, Huaqing Li, 2021. A distributed stochastic optimization algorithm with gradient-tracking and distributed heavy-ball acceleration. Frontiers of Information Technology & Electronic Engineering, online. https://doi.org/10.1631/FITEE.2000615

作者简介

孙碧皓：2018年获辽宁师范大学电子信息工程专业学士学位，2021年获西南大学电子与通信工程硕士学位。主要研究方向为多智能体分布式优化算法。

胡锦辉：2021年获西南大学信息与通信工程专业硕士学位。现于中南大学自动化学院攻读控制科学与工程专业博士学位。主要研究方向包括随机优化、分布式学习、能源资源协调和多智能体系统。

夏大文：贵州民族大学贵州民族大学数据科学与信息工程学院院长，博士生导师。兼任中国现场统计研究会大数据统计分会常务理事、中国商业统计学会数据科学与商业智能分会常务理事、贵州省应用统计学会常务副理事长、贵州省计算机学会副秘书长兼常务理事、ACM重庆分会专家委员会委员。2004年获得贵州民族大学计算机科学与技术专业学士学位，2010年获贵州大学计算机应用技术专业硕士学位，2016年获西南大学统计学专业博士学位。主要从事大数据、人工智能、机器学习和数据挖掘等领域的研究。

李华青（本文通讯作者）：西南大学电子信息工程学院教授、博士生导师。2009年获重庆邮电大学信息与计算科学学士学位，2013年获重庆大学计算机科学与技术专业博士学位。主要研究方向为多智能体系统分布式协同控制、优化与博弈。2020年起担任FITEE通讯专家。

热点文章

期刊动态

关于本刊

Frontiers of Information Technology & Electronic Engineering（简称FITEE，中文名《信息与电子工程前沿（英文）》，ISSN 2095-9184，CN 33-1389/TP）是信息电子类综合性英文学术月刊，SCI-E、EI收录，最新影响因子2.161，位于JCR Q2分区。前身为2010年创办的《浙江大学学报英文版C辑：计算机与电子》，2015年更为现名，现为中国工程院信息与电子工程学部唯一院刊。覆盖计算机、信息与通信、控制、电子、光学等领域。文章类型包括研究论文、综述、个人视点、评述等。现任主编为中国工程院院士潘云鹤、卢锡城。实行国际同行评审制，初次转达意见一般在2~3个月内。文章一经录用将快速在线。

2019年，荣获中国科协等七部委推出的中国科技期刊卓越行动计划项目资助（梯队期刊）。

官网：http://www.jzus.zju.edu.cn

期刊Springer主页：

http://www.springer.com/computer/journal/11714

在线投稿：

http://www.editorialmanager.com/zusc

更多信息，请见：

微信加群

---

为方便广大科研人员交流讨论，本平台建有以下学科微信群。有需要加群的用户，请加小编个人微信号fitee_xb，并留言想要加入的群，小编会拉您进群。营销广告人员请勿扰。

计算机科学与技术学术群	光学工程与技术学术群
控制科学与技术学术群	信息与通信学术群
电力电子学术群	人工智能学术

加关注  ID: fitee_cae

本公众号为中国工程院院刊《信息与电子工程前沿（英文）》（SCI-E、EI检索期刊）官方微信，功能包括：传播期刊的学术文章；为刊物关联学人（读者、作者、评审人、编委，等）提供便捷服务；发布学术写作、评审、编辑、出版等相关资讯；介绍信息与电子工程领域学术人物、学术思想、学术成果，展示该领域科学研究前沿进展；为该领域海内外学者提供友好互动平台。