Scalable Decentralized Algorithms for Online Personalized Mean Estimation
Not on the map. Why?
Abstract (arXiv)
In numerous settings, agents lack sufficient data to directly learn a model. Collaborating with other agents may help, but it introduces a bias-variance trade-off, when local data distributions differ. A key challenge is for each agent to identify clients with similar distributions while learning the model, a problem that remains largely unresolved. This study focuses on a simplified version of the overarching problem, where each agent collects samples from a real-valued distribution over time to estimate its mean. Existing algorithms face impractical space and time complexities (quadratic in the number of agents A). To address scalability challenges, we propose a framework where agents self-organize into a graph, allowing each agent to communicate with only a selected number of peers r. We introduce two collaborative mean estimation algorithms: one draws inspiration from belief propagation, while the other employs a consensus-based approach, with complexity of O( r |A| log |A|) and O(r |A|), respectively. We establish conditions under which both algorithms yield asymptotically optimal estimates and offer a theoretical characterization of their performance.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 17 of its 41 references that are in the map. First posted on arXiv 20 Feb 2024.
Builds on
17 of 41 references.
References · 17
- 2019Advances and Open Problems in Federated Learningcited by 3,021
- 2020Ditto: Fair and Robust Federated Learning Through Personalizationcited by 665
- 2020An Efficient Framework for Clustered Federated Learningcited by 505
- 2019Clustered Federated Learning: Model-Agnostic Distributed Multi-Task Optimization under Privacy Constraintscited by 499
- 2021Towards Personalized Federated Learningcited by 462
- 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
- 2020Three Approaches for Personalization with Applications to Federated Learningcited by 321
- 2019A Joint Learning and Communications Framework for Federated Learning over Wireless Networkscited by 262
- 2021Federated Multi-Task Learning under a Mixture of Distributionscited by 189
- 2020Model-sharing Games: Analyzing Federated Learning Under Voluntary Participationcited by 60
- 2021WAFFLE: Weighted Averaging for Personalized Federated Learningcited by 9
- 2021Linear Speedup in Personalized Collaborative Learningcited by 8
5 more
- 2020Machine learning and data analytics for the IoTcited by 7
- 2021Optimal Model Averaging: Towards Personalized Collaborative Learningcited by 7
- 2023Incentivizing Honesty among Competitors in Collaborative Learning and Optimizationcited by 6
- 2022Collaborative Algorithms for Online Personalized Mean Estimationcited by 5
- 2016Threshold models of cascades in large-scale networkscited by 1
Built on by
Citing papers per year: 2024: 1; 2025: 1.
2 papers.