Proximity without consensus in online multi-agent optimization

Abstract

We consider stochastic optimization problems in multi-agent settings, where a network of agents aims to learn decision variables which are optimal in terms of a global objective, while giving preference to locally and sequentially observed information. To do so, we formulate a problem where each agent minimizes a global objective while enforcing network proximity constraints, which includes consensus optimization as a special case. We propose a stochastic variant of the saddle point algorithm proposed by Arrow and Hurwicz to solve it, which yields a decentralized algorithm that is shown to asymptotically converge to a primal-dual optimal pair of the problem in expectation when a diminishing algorithm step-size is chosen. Moreover, the algorithm converges linearly to a neighborhood when a constant step-size is chosen. We apply this method to the problem of sequentially estimating a correlated random field in a sensor network, which corroborates these performance guarantees.