# Decentralized Multi-Task Online Convex Optimization Under Random Link Failures

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 43 references that are in the map.
- First posted on arXiv 4 Jan 2024.

## Builds on (most cited first, 11 of 11)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [MonoPair: Monocular 3D Object Detection Using Pairwise Spatial Relationships](https://mlsanity.com/paper/2003.00504/) (2020)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [Proximity Without Consensus in Online Multi-Agent Optimization](https://mlsanity.com/paper/1606.05578/) (2016)
- [Linear convergence in optimization over directed graphs with row-stochastic matrices](https://mlsanity.com/paper/1611.06160/) (2016)
- [Zero-Regret Performative Prediction Under Inequality Constraints](https://mlsanity.com/paper/2309.12618/) (2023)
- [CP-mtML: Coupled Projection multi-task Metric Learning for Large Scale Face Retrieval](https://mlsanity.com/paper/1604.02975/) (2016)
- [Decentralized Multi-Task Stochastic Optimization With Compressed Communications](https://mlsanity.com/paper/2112.12373/) (2021)
- [Passive Beamforming and Information Transfer via Large Intelligent Surface](https://mlsanity.com/paper/1905.01491/) (2019)
- [Passive Beamforming and Information Transfer Design for Reconfigurable Intelligent Surfaces Aided Multiuser MIMO Systems](https://mlsanity.com/paper/1912.10209/) (2019)

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

- [Decentralized Optimization with Topology-Independent Communication](https://mlsanity.com/paper/2509.14488/) (2025)
- [Online Decentralized Federated Multi-task Learning With Trustworthiness in Cyber-Physical Systems](https://mlsanity.com/paper/2509.00992/) (2025)

## Abstract (arXiv)

Decentralized optimization methods often entail information exchange between neighbors. Transmission failures can happen due to network congestion, hardware/software issues, communication outage, and other factors. In this paper, we investigate the random link failure problem in decentralized multi-task online convex optimization, where agents have individual decisions that are coupled with each other via pairwise constraints. Although widely used in constrained optimization, conventional saddle-point algorithms are not directly applicable here because of random packet dropping. To address this issue, we develop a robust decentralized saddle-point algorithm against random link failures with heterogeneous probabilities by replacing the missing decisions of neighbors with their latest received values. Then, by judiciously bounding the accumulated deviation stemming from this replacement, we first establish that our algorithm achieves O(√T) regret and O(T^frac34) constraint violations for the full information scenario, where the complete information on the local cost function is revealed to each agent at the end of each time slot. These two bounds match, in order sense, the performance bounds of algorithms with perfect communications. Further, we extend our algorithm and analysis to the two-point bandit feedback scenario, where only the values of the local cost function at two random points are disclosed to each agent sequentially. Performance bounds of the same orders as the full information case are derived. Finally, we corroborate the efficacy of the proposed algorithms and the analytical results through numerical simulations.