An Accelerated Method For Decentralized Distributed Stochastic\n Optimization Over Time-Varying Graphs

We consider a distributed stochastic optimization problem that is solved by a\ndecentralized network of agents with only local communication between\nneighboring agents. The goal of the whole system is to minimize a global\nobjective function given as a sum of local objectives held by each agent. Each\nlocal objective is defined as an expectation of a convex smooth random function\nand the agent is allowed to sample stochastic gradients for this function. For\nthis setting we propose the first accelerated (in the sense of Nesterov's\nacceleration) method that simultaneously attains optimal up to a logarithmic\nfactor communication and oracle complexity bounds for smooth strongly convex\ndistributed stochastic optimization. We also consider the case when the\ncommunication graph is allowed to vary with time and obtain complexity bounds\nfor our algorithm, which are the first upper complexity bounds for this setting\nin the literature.\n