Distributed Online Stochastic Convex-Concave Optimization: Dynamic Regret Analyses Under Single and Multiple Consensus Steps

This paper considers the distributed online convex-concave optimization with constraint sets over a multiagent network, in which each agent autonomously generates a series of decision pairs through a designable mechanism to cooperatively minimize the global loss function. To this end, under no-Euclidean distance metrics, we propose a distributed online stochastic mirror descent convex-concave optimization algorithm with time-varying predictive mappings. Taking dynamic saddle point regret as a performance metric, it is proved that the proposed algorithm achieves the regret upper-bound in $\boldsymbol{\mathcal{O}}\mathbf{(}\mathbf{max}\mathbf{\{}\boldsymbol{T^{\theta_{1}}},\boldsymbol{T^{\theta_{2}}}\mathbf{(1+}\boldsymbol{V_{T})}\mathbf{\})}$ for the general convex-concave loss function, where $\boldsymbol{\theta}_{\mathbf 1}\boldsymbol{,\theta}_{\mathbf 2}\boldsymbol{\in}\mathbf{(0,1)}$ are the tuning parameters, $\boldsymbol{T}$ is the total iteration time, and $\boldsymbol{V_{T}}$ is the path-variation. Surely, this algorithm guarantees the sublinear convergence, provided that $\boldsymbol{V_{T}}$ is sublinear. Moreover, aiming to achieve better convergence, we further investigate a variant of this algorithm by employing the multiple consensus technique. The obtained results show that the appropriate setting can effectively tighten the regret bound to a certain extent. Finally, the efficacy of the proposed algorithms is validated and compared through the simulation example of a target tracking problem.