Online Distributed Stochastic Gradient Algorithm for Nonconvex Optimization with Compressed Communication

This article examines an online distributed optimization problem over an unbalanced digraph, in which a group of nodes in the network tries to collectively search for a minimizer of a time-varying global cost function while data are distributed among computing nodes. As the problem size becomes large, it will inevitably suffer from the communication bottleneck since each node that exchanges messages potentially transmits large amounts of information to its neighbors. To handle the issue, we design an online stochastic gradient algorithm with compressed communication when the knowledge of the gradient is available. We obtain the regret bounds for both nonconvex and convex cost functions, which can reach almost the same order of classic distributed optimization algorithms with exact communication. To resolve the scenario when the information of gradients is not accessible, a bandit version of the previous algorithm is then proposed. Explicit regret bounds of the bandit algorithm are also established for both nonconvex and convex cost functions. The result reveals that the performance of the bandit-feedback method is almost close to that of the gradient-feedback method. Several numerical experiments corroborate the main theoretical findings obtained in this article and exemplify a remarkable speedup when compared to existing distributed algorithms with exact communication.

© 2023 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.