Dynamic Regret for Distributed Online Composite Optimization
Ruijie Hou, Yang Yu, Xiuxian Li · IEEE Transactions on Automatic Control · 2024
This article focuses on online composite optimization over multiagent networks. In the distributed setting, each agent has its own local loss function, which consists of a convex, strongly convex or strongly convex and smooth function, and a time-varying nonsmooth regularizer. Two distributed online algorithms are proposed and corresponding dynamic regrets are analyzed. Two proposed algorithms are based on signs of relative states. The first algorithm obtains$\mathcal {O}(\sqrt{T}(C_{T}+1))$dynamic regret bound when each local loss is a general convex composite function, where$C_{T}$is the path variation. If$C_{T}$can be estimated in advance for convex or strongly convex local loss with a time-varying nonsmooth regularizer, then dynamic regret bounds are, respectively, in the order of$\mathcal {O}(\sqrt{T(C_{T}+1)})$and$\mathcal {O}(\log T(1+C_{T}))$. The second algorithm is based on the first one, especially for handling the local loss composed of a strongly convex and smooth function with a nonsmooth regularizer, and then obtains$\mathcal {O}(1+C_{T})$dynamic regret bound. In the end, numerical results are given to support the theoretical findings.