Convergence in High Probability of Distributed Stochastic Gradient Descent Algorithms

Abstract

In this article, the problem of distributed optimization with nonconvex objective functions is studied by employing a network of agents. Each agent only has access to a noisy estimate on the gradient of its own objective function, and can only communicate with its immediate neighbors via a time-varying directed graph. To handle this problem, a distributed stochastic gradient descent algorithm is adopted. Existing works on distributed algorithms involving stochastic gradients only provide convergence results in expectation. Different from them, we study the convergence of the algorithm in high probability, i.e., the asymptotic convergence rate of the algorithm is characterized by the natural logarithm of the failure probability's inverse. Under mild assumptions on the graph connectivity, we prove that for the general nonconvex objective function, the average of gradients' norm squared converges in high probability. Furthermore, we also consider the case where the objective function satisfies the Polyak–Łojasiewicz condition. In this case, the difference between the objective function and its minimum value converges in high probability, and the convergence rate is faster than that in the general nonconvex case. Finally, simulations are provided to demonstrate the effectiveness of our theoretical results.