具有严格约束的去中心化在线学习：一种双界队列方法

《IEEE Transactions on Networking》：Decentralized Online Learning with Hard Constraints: A Doubly-Bounded Queue Approach

　　

我们研究了具有时变约束的去中心化在线凸优化问题，并使用两个严格的指标进行了性能分析：一是相对于在线全局解基准的网络动态遗憾（network dynamic regret）；二是不允许随时间对学习者进行任何补偿性违规的硬约束违规（hard constraint violation）。我们提出了一种名为“带双重界限队的受限在线学习算法”（Constrained Online Learning with Doubly-bounded Queue，简称COLDQ），该算法引入了一种同时有下界和上界的虚拟队列，无需Slater条件即可严格控制约束违规。通过新的Lyapunov drift分析，我们证明了COLDQ具有O(T^1 + Vx/2)的网络动态遗憾和O(min(T^3 + Vx/4; TVg))的硬约束违规，其中Vx和Vg分别表示损失函数和约束函数的动态特性。在集中式和去中心化环境下，当损失和约束的动态性减弱时，这两个界限首次平滑地趋近于已知的最佳结果O(T^1/2)的遗憾和O(1)的违规。对于强凸损失函数，COLDQ还实现了O(log T)的静态遗憾和O(min(T^(1/2) * (log T)^(1/2), TVg))的硬约束违规。基于合成数据和典型数据集的仿真结果表明，COLDQ在处理凸损失函数和非凸损失函数时均显著优于现有的最先进方法。