Efficient Distributed Online Prediction and Stochastic Optimization With Approximate Distributed Averaging

By Konstantinos I. Tsianos, Michael G. Rabbat. 2014

35 citations recorded by the source corpus.

We study distributed methods for online prediction and stochastic optimization. Our approach is iterative: In each round, nodes first perform local computations and then communicate in order to aggregate information and synchronize their decision variables. Synchronization is accomplished through the use of a distributed averaging protocol. When an exact distributed averaging protocol is used, it is known that the optimal regret bound of O(√(m)) can be achieved using the distributed minibatch algorithm in [“Optimal distributed online prediction using minibatches,” J. Mach. Learn. Res., vol. 13, pp. 165-202, 2012], where m is the total number of samples processed across the network. We focus on methods using approximate distributed averaging protocols and show that the optimal regret bound can also be achieved in this setting. In particular, we propose a gossip-based optimization method that achieves the optimal regret bound. The amount of communication required depends on the network topology through the second largest eigenvalue of the transition matrix of a random walk on the network. In the setting of stochastic optimization, the proposed gossip-based approach achieves nearly linear scaling: The optimization error is guaranteed to be no more than ∈ after O(1/nϵ2) rounds, each of which involves O(log n) gossip iterations, when n nodes communicate over a well-connected graph.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Optimal Statistical Rates for Decentralised Non-Parametric Regression with Linear Speed-Up (2019, background): “The authors in [37, 51] investigate a distributed regularised online learning setting [55] and obtain guarantees for a “multi-step” Distributed Stochastic Mirror Descent algorithm where agents reach consensus on their stochastic gradients in-between computation steps.”
Asynchronous Decentralized Online Learning (2021, unknown): “When receiving the feedback, learner i begins to calculate the gradient ∇ f τi ( w τi ) .”
Anytime Minibatch: Exploiting Stragglers in Online Distributed Optimization (2020, methodology): “(57) Bounding E[〈q(t), w∗ − w(t)〉] and E[‖q(t)‖2] follows the same approach as in (Dekel et al., 2012, Appendix A.1) or Tsianos & Rabbat (2016).”