在线分布式复合优化的静态与动态遗憾：基于边缘的动态事件触发算法

《IEEE Transactions on Automatic Control》：Static and Dynamic Regrets for Online Distributed Composite Optimization: Edge-based Dynamic Event-Triggered Algorithms

在线分布凸约束组合优化问题研究，提出基于动态事件触发的通信协议和两种基于 proximal operator 的算法，分析静态和动态 regret bound，并通过LASSO仿真验证。

　　

摘要：

本文研究了在带宽有限的非平衡有向多智能体网络上的在线分布式凸约束组合优化问题。其独特之处在于，每个智能体的目标函数由两部分组成：一个随迭代次数变化的损失函数和一个正则化项。为了解决潜在的网络带宽限制，我们在智能体之间的链接边采用了基于边的动态事件触发通信协议，并引入了控制因子。基于近端算子，我们提出了两种算法，这两种算法仅要求权重矩阵为行随机矩阵：一种是基于边的动态事件触发在线分布式近端梯度下降算法，另一种算法能够为近端步骤提供近似解。此外，我们还分析了这两种算法的静态和动态遗憾界限。在合理的假设和参数设置下，这两种算法分别实现了静态遗憾界限为O(T^?√D)，以及动态遗憾界限为O(T^?√(1+D))（其中T表示时间范围，D表示路径变化水平）。另外，如果能够提前估计出D，这两种算法的动态遗憾界限可进一步提高至O(T^?√(1+D))?√(1+D))。最后，通过在线分布式LASSO问题的仿真验证了我们所提出算法的有效性。