Adaptive collaboration for online personalized distributed learning with heterogeneous clients
This work addresses the challenge of efficient collaboration in distributed learning for heterogeneous clients, offering an incremental improvement over existing methods.
The paper tackles the problem of online personalized decentralized learning with heterogeneous clients by introducing a gradient-based collaboration criterion to dynamically select peers, reducing gradient variance while mitigating bias, and shows that one variant preserves optimality with theoretical bounds and experimental validation on synthetic and real datasets.
We study the problem of online personalized decentralized learning with $N$ statistically heterogeneous clients collaborating to accelerate local training. An important challenge in this setting is to select relevant collaborators to reduce gradient variance while mitigating the introduced bias. To tackle this, we introduce a gradient-based collaboration criterion, allowing each client to dynamically select peers with similar gradients during the optimization process. Our criterion is motivated by a refined and more general theoretical analysis of the All-for-one algorithm, proved to be optimal in Even et al. (2022) for an oracle collaboration scheme. We derive excess loss upper-bounds for smooth objective functions, being either strongly convex, non-convex, or satisfying the Polyak-Lojasiewicz condition; our analysis reveals that the algorithm acts as a variance reduction method where the speed-up depends on a sufficient variance. We put forward two collaboration methods instantiating the proposed general schema; and we show that one variant preserves the optimality of All-for-one. We validate our results with experiments on synthetic and real datasets.