Optimized Gradient Tracking for Decentralized Online Learning
This work addresses the problem of tracking optimal solutions in time-varying distributed systems for applications like sensor networks or federated learning, representing an incremental improvement through parameter optimization.
The authors tackled decentralized online learning by proposing the Generalized Gradient Tracking (GGT) framework, which unifies existing approaches and achieves improved dynamic regret bounds while outperforming state-of-the-art algorithms on synthetic and real-world datasets.
This work considers the problem of decentralized online learning, where the goal is to track the optimum of the sum of time-varying functions, distributed across several nodes in a network. The local availability of the functions and their gradients necessitates coordination and consensus among the nodes. We put forth the Generalized Gradient Tracking (GGT) framework that unifies a number of existing approaches, including the state-of-the-art ones. The performance of the proposed GGT algorithm is theoretically analyzed using a novel semidefinite programming-based analysis that yields the desired regret bounds under very general conditions and without requiring the gradient boundedness assumption. The results are applicable to the special cases of GGT, which include various state-of-the-art algorithms as well as new dynamic versions of various classical decentralized algorithms. To further minimize the regret, we consider a condensed version of GGT with only four free parameters. A procedure for offline tuning of these parameters using only the problem parameters is also detailed. The resulting optimized GGT (oGGT) algorithm not only achieves improved dynamic regret bounds, but also outperforms all state-of-the-art algorithms on both synthetic and real-world datasets.