Decentralized Multi-Task Online Convex Optimization Under Random Link
  Failures
Wenjing Yan Xuanyu Cao
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 $\mathcal{O}(\sqrt{T})$ regret and
$\mathcal{O}(T^\frac{3}{4})$ 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.