Fully Distributed and Asynchronized Stochastic Gradient Descent for Networked Systems
This work addresses the practical implementation difficulties in distributed optimization for networked systems, offering an incremental improvement over existing methods by eliminating the need for central controllers or synchronization.
The paper tackles the challenge of implementing stochastic gradient descent in large, heterogeneous networked systems without central control or synchronization, achieving global optimality and consensus asymptotically through a fully distributed and asynchronous algorithm, with experiments validating the design on synthetic and real-world datasets.
This paper considers a general data-fitting problem over a networked system, in which many computing nodes are connected by an undirected graph. This kind of problem can find many real-world applications and has been studied extensively in the literature. However, existing solutions either need a central controller for information sharing or requires slot synchronization among different nodes, which increases the difficulty of practical implementations, especially for a very large and heterogeneous system. As a contrast, in this paper, we treat the data-fitting problem over the network as a stochastic programming problem with many constraints. By adapting the results in a recent paper, we design a fully distributed and asynchronized stochastic gradient descent (SGD) algorithm. We show that our algorithm can achieve global optimality and consensus asymptotically by only local computations and communications. Additionally, we provide a sharp lower bound for the convergence speed in the regular graph case. This result fits the intuition and provides guidance to design a `good' network topology to speed up the convergence. Also, the merit of our design is validated by experiments on both synthetic and real-world datasets.