# Proximity Without Consensus in Online Multi-Agent Optimization

arXiv: https://arxiv.org/abs/1606.05578 · HTML: https://mlsanity.com/paper/1606.05578/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2016.

## Built on by (most cited first, 14 of 14)

- [Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data](https://mlsanity.com/paper/2204.04452/) (2022)
- [Decentralized Multi-Task Stochastic Optimization With Compressed Communications](https://mlsanity.com/paper/2112.12373/) (2021)
- [FedBC: Calibrating Global and Local Models via Federated Learning Beyond Consensus](https://mlsanity.com/paper/2206.10815/) (2022)
- [Decentralized Multi-Task Online Convex Optimization Under Random Link Failures](https://mlsanity.com/paper/2401.02011/) (2024)
- [Convergence Rates of Average-Reward Multi-agent Reinforcement Learning via Randomized Linear Programming](https://mlsanity.com/paper/2110.12929/) (2021)
- [Decentralized Personalized Federated Learning](https://mlsanity.com/paper/2406.06520/) (2024)
- [Decentralized Optimization with Topology-Independent Communication](https://mlsanity.com/paper/2509.14488/) (2025)
- [Dencentralized learning in the presence of low-rank noise](https://mlsanity.com/paper/2203.09810/) (2022)
- [AFAFed -- Protocol analysis](https://mlsanity.com/paper/2206.14927/) (2022)
- [Exact Subspace Diffusion for Decentralized Multitask Learning](https://mlsanity.com/paper/2304.07358/) (2023)
- [A Tensor Low-Rank Approximation for Value Functions in Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2501.10529/) (2025)
- [Signal attenuation enables scalable decentralized multi-agent reinforcement learning over networks](https://mlsanity.com/paper/2505.11461/) (2025)
- [Online Decentralized Federated Multi-task Learning With Trustworthiness in Cyber-Physical Systems](https://mlsanity.com/paper/2509.00992/) (2025)
- [A non-smooth regularization framework for learning over multitask graphs](https://mlsanity.com/paper/2509.17728/) (2025)

## Abstract (arXiv)

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.