# Online Learning over Dynamic Graphs via Distributed Proximal Gradient Algorithm

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2019.

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

- [Online Federated Learning via Non-Stationary Detection and Adaptation amidst Concept Drift](https://mlsanity.com/paper/2211.12578/) (2022)
- [QC-ODKLA: Quantized and Communication-Censored Online Decentralized Kernel Learning via Linearized ADMM](https://mlsanity.com/paper/2208.02777/) (2022)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Decentralized Online Regularized Learning Over Random Time-Varying Graphs](https://mlsanity.com/paper/2206.03861/) (2022)
- [Optimized Gradient Tracking for Decentralized Online Learning](https://mlsanity.com/paper/2306.06375/) (2023)

## Abstract (arXiv)

We consider the problem of tracking the minimum of a time-varying convex optimization problem over a dynamic graph. Motivated by target tracking and parameter estimation problems in intermittently connected robotic and sensor networks, the goal is to design a distributed algorithm capable of handling non-differentiable regularization penalties. The proposed proximal online gradient descent algorithm is built to run in a fully decentralized manner and utilizes consensus updates over possibly disconnected graphs. The performance of the proposed algorithm is analyzed by developing bounds on its dynamic regret in terms of the cumulative path length of the time-varying optimum. It is shown that as compared to the centralized case, the dynamic regret incurred by the proposed algorithm over T time slots is worse by a factor of log(T) only, despite the disconnected and time-varying network topology. The empirical performance of the proposed algorithm is tested on the distributed dynamic sparse recovery problem, where it is shown to incur a dynamic regret that is close to that of the centralized algorithm.