具有反馈延迟分布式在线复合优化的动态遗憾性能
2025-05-26 14:46阅读：
引用本文
侯瑞捷,
李修贤, 易新蕾, 洪奕光, 谢立华. 具有反馈延迟分布式在线复合优化的动态遗憾性能.
自动化学报, 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反馈
