施莱弗条件下的时变约束分布式带宽凸优化网络累积约束违反减少问题

Reduced Network Cumulative Constraint Violation for Distributed Bandit Convex Optimization under Slater Condition

摘要 Abstract

本文研究了带有时间变化不等式约束的分布式带宽凸优化问题,目标是最小化网络遗憾和累积约束违反。为了计算网络累积约束违反,现有的求解该问题的分布式带宽在线算法直接使用截断约束函数代替其原始约束函数。然而,使用截断操作使施莱弗条件(即在所有迭代中存在一个点严格满足不等式约束)无法实现减少的网络累积约束违反。为了解决这一挑战,我们提出了一种新的分布式带宽原对偶算法。如果局部损失函数是凸的,我们证明所提出的算法建立了次线性的网络遗憾和累积约束违反界限。当施莱弗条件成立时,网络累积约束违反界限得以减少。此外,如果局部损失函数是强凸的,对于强凸参数未知的情况,网络遗憾界限得以减少;对于强凸参数已知的情况,网络遗憾和累积约束违反界限进一步减少。据我们所知,这是首次在施莱弗条件下建立具有时间变化约束的(分布式)带宽凸优化问题的累积约束违反界限的研究。最后,提供了一个数值例子来验证理论结果。

This paper studies the distributed bandit convex optimization problem with time-varying inequality constraints, where the goal is to minimize network regret and cumulative constraint violation. To calculate network cumulative constraint violation, existing distributed bandit online algorithms solving this problem directly use the clipped constraint function to replace its original constraint function. However, the use of the clipping operation renders Slater condition (i.e, there exists a point that strictly satisfies the inequality constraints at all iterations) ineffective to achieve reduced network cumulative constraint violation. To tackle this challenge, we propose a new distributed bandit online primal-dual algorithm. If local loss functions are convex, we show that the proposed algorithm establishes sublinear network regret and cumulative constraint violation bounds. When Slater condition holds, the network cumulative constraint violation bound is reduced. In addition, if local loss functions are strongly convex, for the case where strongly convex parameters are unknown, the network regret bound is reduced. For the case where strongly convex parameters are known, the network regret and cumulative constraint violation bounds are further reduced. To the best of our knowledge, this paper is among the first to establish reduced (network) cumulative constraint violation bounds for (distributed) bandit convex optimization with time-varying constraints under Slater condition. Finally, a numerical example is provided to verify the theoretical results.