Privacy-Preserving Distributed Online Optimization Over Unbalanced Digraphs via Subgradient Rescaling

In this article, we investigate a distributed online constrained optimization problem with differential privacy where the network is modeled by an unbalanced digraph with a row-stochastic adjacency matrix. To address such a problem, a distributed differentially private algorithm without introducing a trusted third-party is proposed to preserve the privacy of the participating nodes. Under mild conditions, we show that the proposed algorithm attains an <inline-formula><tex-math notation="LaTeX">$O(\log T)$</tex-math></inline-formula> expected regret bound for strongly convex local cost functions, where <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> is the time horizon. Moreover, we remove the need for knowing the time horizon <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> in advance by adopting doubling trick scheme, and derive an <inline-formula><tex-math notation="LaTeX">$O(\sqrt{T})$</tex-math></inline-formula> expected regret bound for general convex local cost functions. Our results coincide with the best theoretical regrets that can be achieved in the state-of-the-art algorithms. Finally, simulation results are conducted to validate the efficiency of our proposed algorithm.