2020/05/15 by Qureshi, Muhammad I., Xin, Ran, Kar, Soummya +1 · 5 citations
#FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · doi:10.48550/arxiv.2005.07785
In this report, we study decentralized stochastic optimization to minimize a sum of smooth and strongly convex cost functions when the functions are distributed over a directed network of nodes. In contrast to the existing work, we use gradient tracking to improve certain aspects of the resulting algorithm. In particular, we propose the~\textbfS-ADDOPT algorithm that assumes a stochastic first-order oracle at each node and show that for a constant step-size~α, each node converges linearly inside an error ball around the optimal solution, the size of which is controlled by~α. For decaying step-sizes~O(1/k), we show that~\textbfS-ADDOPT reaches the exact solution sublinearly at~O(1/k) and its convergence is asymptotically network-independent. Thus the asymptotic behavior of~\textbfS-ADDOPT is comparable to the centralized stochastic gradient descent. Numerical experiments over both strongly convex and non-convex problems illustrate the convergence behavior and the performance comparison of the proposed algorithm.