Scalable Decentralized Algorithms for Online Personalized Mean Estimation

Franco Galante, Giovanni Neglia, Emilio Leonardi

Abstract

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.

Introduction: The Bias-Variance Trade-off in Personalized Learning

In decentralized learning environments, individual agents—such as mobile devices or IoT sensors—often struggle to build accurate models due to limited local data. While collaboration across the network can reduce estimation variance, it introduces potential bias if agents aggregate data from peers with different underlying distributions. This creates a fundamental bias-variance trade-off.

To navigate this, agents must perform personalization: identifying and collaborating only with "similar" peers. However, existing state-of-the-art methods like the original ColME algorithm require every agent to track every other agent in the system. This $O(|A|)$ per-agent complexity makes such systems unscalable for large networks.

Proposed Framework: Sparse Self-Organizing Graphs

The authors propose a scalable alternative where agents are nodes in a sparse graph (e.g., a random regular graph) and only communicate with a small number of neighbors ($r$). The core of the framework is a Dynamic Pruning mechanism. Agents use "optimistic distances"—confidence intervals based on observed data—to determine if a neighbor is similar. If the confidence intervals of two neighbors do not overlap, the link is pruned permanently.

Two Collaborative Algorithms

  1. C-ColME (Consensus-based): Agents maintain a running average and update it by taking a weighted sum of their neighbors' estimates. This method is highly memory-efficient with $O(r)$ complexity.
  2. B-ColME (Message-passing): Inspired by belief propagation, agents broadcast tables of data sums and sample counts to neighbors up to $d$ hops away. This allows for faster data aggregation but requires slightly more overhead ($O(rd)$).

Experimental Evaluation and Key Insights

The researchers evaluated these algorithms using both synthetic data and the MNIST handwritten digit dataset. A key theoretical contribution is the extension of these methods to multidimensional data and distributions with bounded fourth moments, making them more robust for real-world applications.

Comparison of the proposed algorithms (B-COLME, C-COLME) against baselines and the Oracle performance.

As shown in the figure above, both B-ColME and C-ColME eventually match the performance of an "Oracle"—a hypothetical scenario where agents know their similarity classes perfectly from the start. Interestingly, the experiments revealed a "Wrong Link" lag: B-ColME is more sensitive to incorrect links in early stages because it pulls data from multiple hops, whereas C-ColME’s consensus approach is more resilient, showing smoother improvement as the graph prunes.

Application to Federated Learning

The framework was further validated using a decentralized Federated Learning task on MNIST (FL-DG). Agents collaborated to recognize digits while navigating distinct similarity classes (e.g., different label mappings).

Performance of FL-DG on the MNIST dataset, showing the relationship between pruning "Wrong Links" and increasing "Accuracy."

The results demonstrate that the self-organizing graph successfully clusters similar learners. As the number of "Wrong Links" decreases through pruning, the classification accuracy significantly improves, outperforming static graph configurations.

Conclusion and Future Directions

By reducing per-agent complexity from linear to constant or logarithmic scales, C-ColME and B-ColME enable personalized learning in massive networks. While the current model assumes fixed data distributions and lacks a "rewiring" mechanism for agents that become isolated, it provides a rigorous foundation for scalable, decentralized collaboration. Future work will likely explore "soft" similarity measures and more flexible network topologies.

Summary updated

Abstract

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.
BibTeX
@inproceedings{galante2025scalable,
  author = {Franco Galante and Giovanni Neglia and Emilio Leonardi},
  title = {{Scalable Decentralized Algorithms for Online Personalized Mean Estimation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  url = {https://openreview.net/forum?id=peAUOFpmVg},
}
Figure