S-DIGing: A Stochastic Gradient Tracking Algorithm for Distributed Optimization

作     者：Li, Huaqing Zheng, Lifeng Wang, Zheng Yan, Yu Feng, Liping Guo, Jing 

作者机构：Southwest Univ Coll Elect & Informat Engn Chongqing Key Lab Nonlinear Circuits & Intelligen Chongqing 400715 Peoples R China Xinzhou Teachers Univ Dept Comp Sci Xinzhou 034000 Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE》 (IEEE Trans. Emerging Topics Comp. Intell.)

年 卷 期：2022年第6卷第1期

页      面：53-65页

核心收录：

基　　金：Fundamental Research Funds for the Central Universities [XDJK2019AC001] Innovation Support Program for Chongqing Overseas Returnees [cx2019005] National Natural Science Foundation of China 

主　　题：Optimization Convergence Linear programming Approximation algorithms Stochastic processes Machine learning algorithms Convex functions Distributed optimization gradient tracking stochastic averaging gradient multi-agent systems linear convergence 

摘      要：In this article, we study convex optimization problems where agents of a network cooperatively minimize the global objective function which consists of multiple local objective functions. The intention of this work is to solve large-scale optimization problems where the local objective function is complicated, and numerous. Different from most of the existing works, the local objective function of each agent is presented as the average of finite instantaneous functions. Integrating the gradient tracking algorithm with stochastic averaging gradient technology, a distributed stochastic gradient tracking (termed as S-DIGing) algorithm is proposed. At each time instant, only one randomly selected gradient of an instantaneous function is computed, and applied to approximate the local batch gradient for each agent. Based on a novel primal-dual interpretation of the S-DIGing algorithm, it is shown that the S-DIGing algorithm linearly converges to the global optimal solution when step-size do not exceed an explicit upper bound, and the instantaneous functions are strongly convex with Lipschitz continuous gradients. Numerical experiments are presented to demonstrate the practicability of the S-DIGing algorithm, and correctness of the theoretical results.