Proximity Without Consensus in Online Multiagent Optimization

By Alec Koppel, Brian M. Sadler, Alejandro Ribeiro. 2016

90 citations recorded by the source corpus.

We consider stochastic optimization problems in multiagent settings, where a network of agents aims to learn parameters that are optimal in terms of a global convex objective, while giving preference to locally observed streaming information. To do so, we depart from the canonical decentralized optimization framework where agreement constraints are enforced, and instead formulate a problem where each agent minimizes a global convex objective while enforcing network proximity constraints. This formulation includes online consensus optimization as a special case, but allows for the more general hypothesis that there is data heterogeneity across the network. To solve this problem, we propose using a stochastic saddle point algorithm inspired by Arrow and Hurwicz. This method yields a decentralized algorithm for processing observations sequentially received at each node of the network. Using Lagrange multipliers to penalize the discrepancy between them, only neighboring nodes exchange model information. We establish that under a constant step-size regime the time-average suboptimality and constraint violation are contained in a neighborhood whose radius vanishes with increasing number of iterations. As a consequence, we prove that the time-average primal vectors converge to the optimal objective while satisfying the network proximity constraints. We apply this method to the problem of sequentially estimating a correlated random field in a sensor network, as well as an online source localization problem, both of which demonstrate the empirical validity of the aforementioned convergence results.

Subfields: 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 Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “…using the primal-dual based algorithms as in (Chang et al., 2014b; Touri and Nedic, 2009; Nedi´c and Ozdaglar, 2009), saddle point algorithms proposed in (Koppel et al., 2017; Bedi et al., 2019), and ADMM based techniques such as (Glowinski and Marroco, 1975; Boyd et al., 2011; Deng et al., 2017).”
Asynchronous Saddle Point Algorithm for Stochastic Optimization in Heterogeneous Networks (2019, methodology): “(cid:2) This formulation is more generic than [19] in the sense that we allow stochastic constraints and use of delayed gradients in the algorithm updates which are rarely addressed in the literature.”
Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation (2017, methodology): “Finally, saddle point algorithms have recently been applied to unconstrained [32] or proximity-constrained [33] network optimization problems, but do not readily generalize to the general form constrained optimization problem considered here.”