2014/03/03 by Konstantinos I. Tsianos, Michael Rabbat, Tsianos, Konstantinos I. +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Distributed #Distributed Control Multi-Agent Systems #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Information Theory (cs.IT) #Optimization and Control (math.OC) #Parallel #Stochastic Gradient Optimization Techniques #Systems and Control (eess.SY) #and Cluster Computing (cs.DC) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.1403.0603
openalex publication_date 2014/03/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study distributed methods for online prediction and stochastic\noptimization. Our approach is iterative: in each round nodes first perform\nlocal computations and then communicate in order to aggregate information and\nsynchronize their decision variables. Synchronization is accomplished through\nthe use of a distributed averaging protocol. When an exact distributed\naveraging protocol is used, it is known that the optimal regret bound of\n\O(\√(m)) can be achieved using the distributed mini-batch\nalgorithm of Dekel et al. (2012), where m is the total number of samples\nprocessed across the network. We focus on methods using approximate distributed\naveraging protocols and show that the optimal regret bound can also be achieved\nin this setting. In particular, we propose a gossip-based optimization method\nwhich achieves the optimal regret bound. The amount of communication required\ndepends on the network topology through the second largest eigenvalue of the\ntransition matrix of a random walk on the network. In the setting of stochastic\noptimization, the proposed gossip-based approach achieves nearly-linear\nscaling: the optimization error is guaranteed to be no more than \ε\nafter \O(\(1)/(n \ε2)) rounds, each of which involves\n\O(\log n) gossip iterations, when nodes communicate over a\nwell-connected graph. This scaling law is also observed in numerical\nexperiments on a cluster.\n