Convergence in High Probability of Distributed Stochastic Gradient Descent Algorithms

• 成果类型: Article
• 署名作者: Lu, Kaihong; Wang, Hongxia; Zhang, Huanshui; Wang, Long
• 署名单位: Shandong University of Science & Technology; Peking University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3327319
• 发表日期: 2024
• 页码: 2189-2204
• 关键词: convergence; optimization; linear programming; Noise measurement; TOPOLOGY; Target tracking; Directed graphs; distributed optimization; high probability; Nonconvex Optimization; Stochastic Gradient

摘要

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-Lojasiewicz 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.