Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems
Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problems
复制标题
DOI：
10.48550/arxiv.2302.12320
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Ting-Jui Chang;Sapana Chaudhary;D. Kalathil;Shahin Shahrampour
中科院分区：
文献类型：
--
作者：
Ting-Jui Chang;Sapana Chaudhary;D. Kalathil;Shahin Shahrampour
本文讨论了一组未知的线性安全约束的安全分布式在线优化。智能体网络的目标是共同最小化全局的、随时间变化的函数，而每个个体智能体只能部分地观察到该函数。因此，智能体必须进行本地通信，以生成与事后最佳最小化序列竞争的安全动作序列，并且通过动态后悔来量化两个序列之间的差距。我们提出具有探索阶段的分布式安全在线梯度下降（D-Safe-OGD），其中所有智能体协作估计约束参数以构建估计的可行集，确保优化阶段动作选择的安全性。我们证明，对于凸函数，D-Safe-OGD 实现了 $O(T^{2/3} \sqrt{\log T} + T^{1/3}C_T^*)$ 的动态后悔界限，其中 $C_T^*$ 表示最佳最小化序列的路径长度。我们进一步证明了对于某些非凸问题的 $O(T^{2/3} \sqrt{\log T} + T^{2/3}C_T^*)$ 的动态遗憾界限，这为非凸设置中的安全分布式算法建立了第一个动态遗憾界限。
This paper addresses safe distributed online optimization over an unknown set of linear safety constraints. A network of agents aims at jointly minimizing a global, time-varying function, which is only partially observable to each individual agent. Therefore, agents must engage in local communications to generate a safe sequence of actions competitive with the best minimizer sequence in hindsight, and the gap between the two sequences is quantified via dynamic regret. We propose distributed safe online gradient descent (D-Safe-OGD) with an exploration phase, where all agents estimate the constraint parameters collaboratively to build estimated feasible sets, ensuring the action selection safety during the optimization phase. We prove that for convex functions, D-Safe-OGD achieves a dynamic regret bound of $O(T^{2/3} \sqrt{\log T} + T^{1/3}C_T^*)$, where $C_T^*$ denotes the path-length of the best minimizer sequence. We further prove a dynamic regret bound of $O(T^{2/3} \sqrt{\log T} + T^{2/3}C_T^*)$ for certain non-convex problems, which establishes the first dynamic regret bound for a safe distributed algorithm in the non-convex setting.