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 parameters which are optimal in terms of a global 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 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.

References in corpus (2)

• Convex Optimization for Big Data
• Stability and Performance Limits of Adaptive Primal-Dual Networks

Cited by in corpus (15)

• Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applications
• Multitask learning over graphs: An Approach for Distributed, Streaming Machine Learning
• GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning
• Adaptation and learning over networks under subspace constraints -- Part I: Stability Analysis
• Asynchronous Incremental Stochastic Dual Descent Algorithm for Network Resource Allocation
• Decentralized Sparse Multitask RLS over Networks
• Accelerated Distributed Dual Averaging over Evolving Networks of Growing Connectivity
• Communication-Efficient Robust Federated Learning Over Heterogeneous Datasets
• Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data
• Multi-task Reinforcement Learning in Reproducing Kernel Hilbert Spaces via Cross-learning
• Optimally Compressed Nonparametric Online Learning
• Asynchronous Decentralized Stochastic Optimization in Heterogeneous Networks
• Resilient Consensus via Weight Learning and Its Application in Fault-Tolerant Clock Synchronization
• A Stochastic Primal-Dual Method for Optimization with Conditional Value at Risk Constraints
• Secure Distributed On-Device Learning Networks With Byzantine Adversaries