引用本文

侯瑞捷, 李修贤, 易新蕾, 洪奕光, 谢立华. 具有反馈延迟分布式在线复合优化的动态遗憾性能. 自动化学报, 2025, 51(4): 835−856 doi: 10.16383/j.aas.c240414

Hou Rui-Jie, Li Xiu-Xian, Yi Xin-Lei, Hong Yi-Guang, Xie Li-Hua. Dynamic regret for distributed online composite optimization with delayed feedbacks. Acta Automatica Sinica, 2025, 51(4): 835−856 doi: 10.16383/j.aas.c240414

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c240414

关键词

分布式在线凸优化，复合优化，反馈延迟，Bandit反馈，动态遗憾 

摘要

研究分布式在线复合优化场景中的几种反馈延迟, 包括梯度反馈、单点Bandit反馈和两点Bandit反馈. 其中, 每个智能体的局部目标函数由一个强凸光滑函数与一个凸的非光滑正则项组成. 在分布式场景下, 研究每个智能体具有不同时变延迟的场景. 基于近端梯度下降算法, 分别设计这三种延迟反馈的分布式在线复合优化算法, 并且对动态遗憾上界进行分析. 分析结果表示, 延迟梯度反馈和延迟两点Bandit反馈的动态遗憾上界阶数在期望意义下相同, 而延迟单点Bandit反馈的动态遗憾上界稍差于前两者. 这表明, 存在延迟时, 两点Bandit反馈可以在期望意义下达到与梯度反馈相同阶数的动态遗憾上界, 且在步长选择合适的情况下, 三种反馈类型的平均延迟在动态遗憾上具有相同的阶数. 最后通过仿真实验验证了算法的性能和理论分析结果.

文章导读

在线优化广泛应用于目标跟踪[1]、在线广告投放[2]等各个领域, 其主要特点是学习者在动态或对抗环境中根据历史信息做出决策, 然后获得当前时刻的代价函数信息[3]. 目前为止, 研究者已经提出许多在线优化算法[4−7], 并分析它们对应的收敛性. 然而, 传统在线算法以轮流顺序的方式处理目标函数, 这会导致多核中央处理器或图形处理器的资源浪费. 为解决这一问题, 出现了分布式在线算法, 其将大型问题分配给具有网络拓扑结构的各个代理或智能体, 或者每个代理天然地具有自己的私有信息, 其中, 每个代理都有自己的处理器和内存. 通过并行计算和相邻智能体之间的协作, 可以有效解决大规模复杂优化问题, 如编队跟踪[8]、智能电网[9]、智能建筑[10]等. 相关的工作包括解决分布式一致问题[7, 11], 并将其拓展到更多复杂场景中, 同时也考虑了时变有向通讯图[12]、不等式约束和Bandit反馈[13]、随机梯度或噪声梯度反馈[14]等情况. 

在分布式在线场景中, 常常会出现每个智能体的局部目标函数由不同性质的函数组成, 例如包含一个非光滑正则项, 将这样的问题称为分布式在线复合优化问题, 如电网资源分配中每个区域的目标函数中包含电压约束的投影算子[15]; 在水下信道识别中, 每个传感器的局部目标函数是其识别信息的均方误差1范数[16]. 这种目标函数为复合函数的优化问题广泛出现于电网资源分配[15]、压缩感知[16]等问题中. 为解决分布式在线复合优化问题, 目前已经提出的相关算法有分布式近似镜像下降法[5]、分布式近端梯度下降法[6]、分布式前向后向分裂法[7]等. 

然而, 在实际应用中, 如多卫星协调[17]、无线传感器网络[16]以及可再生能源分配[15]等问题, 由于昂贵的梯度计算、网络不稳定性、磁盘吞吐量、带宽、硬件、距离等因素, 智能体在更新状态时不得不使用过时的信息, 这就造成分布式计算过程中的延迟现象. 目前的工作主要考虑两种延迟: 反馈延迟和通讯延迟. 反馈延迟是由于智能体获取或计算自身信息(例如函数信息或梯度信息)需要花费额外时间, 从而导致更新状态时使用延迟的信息; 而通讯延迟是由于智能体将信息传输给其他智能体时需要额外时间, 从而导致接收到延迟的邻居信息. 事实上, 不仅硬件条件会导致反馈延迟, 某些问题的设置也不得不使用带有延迟的反馈信息. 例如, 在在线广告推广算法中, 从推广某广告到用户决定点击该广告之间必然存在一定的时间间隔; 在云计算中, 在线算法给出资源分配策略到批处理任务未完成前, 并不能知道该分配策略的效果; 投资组合在线学习算法受到市场信息和交易延迟的影响也无法立刻知道投资策略所获得的收益. Quanrud等[18]在梯度下降算法和follow-the-perturbed-leader算法中考虑使用延迟反馈得到与没有延迟情况下相同的静态遗憾度, 表明在线学习算法在延迟反馈下不影响其静态遗憾上界, 并从理论上证明在延迟反馈下运行一般在线算法的合理性. 目前已经有大量的工作考虑了在线凸优化[18−21]中的延迟现象. 如, Wang等[19]在带有长期和短期约束的在线凸优化问题中考虑反馈延迟并基于路径长度和函数变化度分析动态遗憾上界. Bedi等[22]利用非线性邻近函数作为约束保证智能体之间的状态相近, 并提出梯度延迟下的分布式异步在线鞍点算法, 然后以牺牲遗憾度为代价, 改进算法使得智能体之间的状态一致. Inoue等[23]针对有向通信网络上的通讯延迟和动态不等式约束提出一种分布式原始对偶算法. 在近期相关的工作中, Liu等[24]研究具有时变延迟反馈的分布式分簇博弈问题, 其中, 每个集群智能体的决策在不同的局部可行约束集内, 且所有智能体的决策满足不等式耦合约束. 他们提出的分布式在线延迟容忍广义纳什均衡学习算法在给定条件下建立动态遗憾和约束违反的次线性增长界. 与他们的工作相比, 本文研究了多智能体合作下的分布式在线优化问题. 

另外, 在一些实际问题中, 智能体由于未知函数具体表达式或求解梯度信息需要花费巨大的计算资源, 从而导致无法获得梯度信息, 但可以获得函数在有限点处的取值. 例如, 在实践中, 大规模神经网络中的损失函数参数众多且涉及隐藏参数, 因此, 不易得到解析表达式和梯度信息, 但可以利用数值计算方式估计函数值信息[25]. 类似的情况还出现在数据网络在线路由、黑盒对抗性攻击等问题中[26]. 此时基于梯度信息的算法将不再适用, 需要使用一些无梯度优化算法来解决, 例如利用Bandit反馈技术设计算法, 利用函数在有限点处的取值对梯度进行估计来解决梯度未知的困难. 一些文献考虑没有延迟的Bandit反馈[5, 13, 25], 也有一些文献考虑具有延迟的Bandit反馈. Wan等[20]研究在线有约束凸优化中的不确定延迟, 即延迟随时间发生变化, 当目标函数强凸时, 设计并分析所提出延迟在线梯度下降算法的静态遗憾上界, 然后又将其扩展为两点和n+1点Bandit反馈的情况. 针对完全信息反馈和Bandit反馈中的延迟, Cao等[27]分别设计两种在线分布式梯度下降算法, 并证明只要平均延迟是次线性的, 静态遗憾就是次线性的. 基于时变耦合不等式约束, Wang等[28]在时变有向图上提出分布式在线延迟原始对偶Bandit push-sum算法. Xiong等[29]利用事件触发机制缓解网络带宽有限问题, 并提出具有延迟单点和延迟两点Bandit反馈的事件触发分布式在线凸优化算法. 

事实上, 许多分布式在线复合优化问题都存在延迟反馈现象. 以现实水下无线通信信道识别(经典的分布式在线复合优化问题)为例, 由于许多海洋信道的混响时间很长, 该信道具有很大的延迟[30]. 然而, 很少有研究讨论分布式在线复合优化中的时变延迟问题. 虽然20世纪初期研究人员就发现针对复合函数的不同项进行不同处理所设计的算法的表现效果要优于将函数整体一起处理的表现效果[5−7], 但考虑分布式在线场景的研究是近些年才发展起来的, 目前已有的针对分布式在线复合优化的研究包括设计不同的分布式复合优化算法、考虑不等式约束、考虑动态图下算法的设计和分析等[5−7, 15, 31], 迫切需要理论研究考虑更多复杂且真实的场景, 为分布式在线复合优化应用于更多复杂真实场景做理论保证. 另外, 分布式在线场景中考虑延迟也需要一定的理论突破, 集中式场景下的延迟大都是时变的[18, 20], 而在分布式场景下每个智能体的延迟往往都是时不变的[27−29, 32−33], 少数工作研究了时变的延迟[21, 34]. 设置时变的延迟会导致接收到的函数序列发生变化, 此时需要估计接收函数序列与真实函数序列的差距, 再加上每个智能体具有不同的延迟, 这样的设置会对分析带来困难. 

基于上述事实, 本文分析带有时变反馈延迟的分布式在线复合优化问题的动态遗憾上界, 为分布式在线复合优化算法应用于更多反馈延迟场景奠定理论基础, 针对分布式复合优化问题中的梯度反馈、单点和两点Bandit反馈考虑时变延迟现象, 设计三种算法并分析它们的动态遗憾上界. 本文主要的贡献如下: 

1) 首次考虑分布式在线复合优化问题中具有时变反馈延迟的现象, 同时, 每个智能体的局部目标函数由一个强凸函数与凸的非光滑正则项组成. 具体地, 每个智能体具有不同且时变的反馈延迟, 分别考虑了梯度反馈、单点Bandit反馈和两点Bandit反馈三种情况. 

2)基于这三种反馈延迟设计分布式复合优化算法, 并分析它们的动态遗憾上界. 

本文内容安排如下. 第1节给出相关符号定义; 第2节描述所研究的问题和评价指标, 并给出需要的假设条件; 第3节针对梯度反馈延迟设计算法并分析动态遗憾; 第4节针对单点和两点Bandit反馈延迟设计算法并分析动态遗憾; 第5节描述仿真实验与仿真结果; 第6节总结全文并提出未来的研究方向.

图 1  4种不同规模的网络

图 2  不同网络规模下本文所提出算法的性能表现

图 3  2种不同的网络拓扑

本文研究带有时变反馈延迟的分布式在线复合优化问题, 分别考虑梯度反馈、单点Bandit反馈和两点Bandit反馈三种反馈类型中存在延迟的情况, 其中, 每个智能体可以有不同的时变延迟. 针对这三种情况分别设计相应的算法, 理论分析表明延迟梯度反馈和延迟两点Bandit反馈的动态遗憾上界的阶数在期望意义下相同, 而延迟单点Bandit反馈的动态遗憾上界在期望意义下会稍差于前两种反馈情形, 但在期望意义下动态遗憾上界与平均延迟的关系相同, 这表明不同反馈类型不会影响延迟与动态遗憾上界的关系. 最后通过仿真实验验证算法的性能和理论分析结果. 未来的研究方向包括将其扩展到动态图中、考虑时变非光滑项下的Bandit反馈、考虑函数仅为凸的情况、探索静态遗憾性能或设计算法达到最优动态遗憾界等. 

作者简介

侯瑞捷

同济大学电子与信息工程学院控制科学与工程系博士研究生. 2021年获得兰州大学学士学位. 主要研究方向为分布式在线优化. E-mail: hourj21@tongji.edu.cn

李修贤

同济大学电子与信息工程学院控制科学与工程系、上海自主智能无人系统科学中心教授. 主要研究方向为分布式控制与优化, 智能算法, 博弈论及自主智能无人系统. 本文通信作者. E-mail: xli@tongji.edu.cn

易新蕾

美国麻省理工学院信息与决策系统实验室博士后, 现为同济大学准聘教授. 主要研究方向为分布式优化, 在线优化, 元学习和图神经网络. E-mail: xinleiy@kth.se

洪奕光

同济大学电子与信息工程学院控制科学与工程系、上海自主智能无人系统科学中心教授. 他是 IEEE会士, CAA会士. 主要研究方向为非线性控制, 多智能体系统, 分布式优化与博弈, 机器学习和社交网络. E-mail: yghong@tongji.edu.cn

谢立华

新加坡南洋理工大学电气与电子工程学院教授. 他是新加坡工程院院士、IEEE会士、IFAC会士和CAA会士. 主要研究方向为鲁棒控制与估计, 网络控制系统, 分布式优化, 多智能体网络、定位和无人系统. E-mail: elhxie@ntu.edu.sg