Scalable Decentralized Algorithms for Online Personalized Mean Estimation
<|reference_start|>Scalable Decentralized Algorithms for Online Personalized Mean Estimation: 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.<|reference_end|>
@article{galante2024scalable,
    title={Scalable Decentralized Algorithms for Online Personalized Mean
  Estimation},
    author={Franco Galante, Giovanni Neglia, Emilio Leonardi},
    journal={arXiv preprint arXiv:2402.12812},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.12812},
    primaryClass={cs.LG cs.DC}
}