Distributed Online Convex Optimization With Time-Varying Constraints: Tighter Cumulative Constraint Violation Bounds Under Slater's Condition

• 成果类型: Article
• 署名作者: Yi, Xinlei; Li, Xiuxian; Yang, Tao; Xie, Lihua; Hong, Yiguang; Chai, Tianyou; Johansson, Karl H.
• 署名单位: Tongji University; Massachusetts Institute of Technology (MIT); Northeastern University - China; Nanyang Technological University; Royal Institute of Technology
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2025.3547606
• 发表日期: 2025
• 页码: 5764-5779
• 关键词: Convex functions; measurement; training; STANDARDS; optimization; Loss measurement; Autonomous systems; Reactive power; Numerical simulation; Linear Regression; Cumulative constraint violation; distributed optimization; online convex optimization; Slater's condition; time-varying constraints

摘要

This article considers distributed online convex optimization with time-varying constraints. In this setting, a network of agents makes decisions at each round, and then, only a portion of the loss function and a coordinate block of the constraint function are privately revealed to each agent. The loss and constraint functions are convex and can vary arbitrarily across rounds. The agents collaborate to minimize static network regret and network cumulative constraint violation. A novel distributed online algorithm with a vanishing stepsize is proposed and it achieves an O(T-max{c,T-1-c}) static network regret bound and an O(T1-c/2) network cumulative constraint violation bound, where T is the number of rounds and c is an element of (0, 1) is a user-defined tradeoff parameter. When Slater's condition holds (i.e., there is a point that strictly satisfies the inequality constraints), the network cumulative constraint violation bound is reduced to O(T1-c). Moreover, if the loss functions are strongly convex, then static network regret bound is reduced to O(log(T)), and the network cumulative constraint violation bound is reduced to O(root log(T )T ) and O(log(T)) without and with Slater's condition, respectively. To the best of the authors' knowledge, this article is the first to achieve tighter (network) cumulative constraint violation bounds for (distributed) online convex optimization with time-varying constraints under Slater's condition. Finally, the theoretical results are verified through numerical simulations.