Dynamic Regret for Distributed Online Composite Optimization

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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(\sqrt{T}(C_{T}+1))$</tex-math></inline-formula> dynamic regret bound when each local loss is a general convex composite function, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$C_{T}$</tex-math></inline-formula> is the path variation. If <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$C_{T}$</tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(\sqrt{T(C_{T}+1)})$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(\log T(1+C_{T}))$</tex-math></inline-formula>. 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathcal {O}(1+C_{T})$</tex-math></inline-formula> dynamic regret bound. In the end, numerical results are given to support the theoretical findings.