Scalable Decentralized Algorithms for Online Personalized Mean Estimation

Franco Galante, Giovanni Neglia, Emilio Leonardi

TL;DR

Existing algorithms for decentralized, personalized mean estimation—such as ColME—require each agent to track all other agents, incurring an impractical $O(|A|)$ per-agent computation and memory footprint. This paper introduces two sparse-graph algorithms, C-ColME (consensus-based) and B-ColME (message-passing), which restrict communication to small neighborhoods of size $r \ll |A|$. These methods slash per-agent resource costs to $O(r)$ and $O(r \log |A|)$ while guaranteeing provable convergence speedups of $\Omega(|A|^{1/2-\phi})$ over non-collaborative estimation.

What Problem Does This Paper Address?

In collaborative and federated learning, agents often lack sufficient local data to produce accurate estimates on their own. While pooling data reduces variance, it introduces bias when agents have differing underlying data distributions. To collaborate safely, agents must solve a chicken-and-egg problem: identify which peers share the same distribution (the "similarity class") while simultaneously learning the target parameter.

Prior state-of-the-art methods like Collaborative Mean Estimation (ColME) suffer from three critical bottlenecks:

  1. Scalability: Every agent maintains statistics for all other $|A|$ agents in the network, leading to linear $O(|A|)$ per-agent time and memory complexity.
  2. Slow identification: Agents query each other sequentially via round-robin, introducing $O(|A|)$ delays before similarity classes are identified.
  3. Restricted assumptions: Prior convergence bounds were limited to scalar, sub-Gaussian distributions.

Methods

The authors structure the agents into an initial communication graph $\mathcal{G}(A, E)$ where each agent has at most $r$ neighbors (e.g., random regular graphs). As agents collect streaming observations, they prune edges connecting dissimilar neighbors based on overlapping confidence intervals (an "optimistic distance" metric).

The paper introduces two decentralized estimation schemes over this pruned topology:

  • C-ColME (Consensus-based): Agents maintain a running empirical mean and a consensus estimate. Estimates evolve via dynamic average consensus using a symmetric, doubly stochastic mixing matrix $W_t$ and a decaying memory weight $\alpha_t = \frac{t}{t+1}$. It requires $O(r)$ time and space per agent.
  • B-ColME (Message-passing): Neighbors exchange a $d \times 2$ table of message statistics containing running sample sums and counts from up to $d$ hops away. Under the assumption that the $d$-hop neighborhood $\mathcal{N}_a^d$ is a tree, this aggregates observations up to distance $d$ without double-counting. Its per-agent complexity is $O(rd)$ (or $O(r \log |A|)$).

The authors also extend confidence-interval bounds to multidimensional observations and broader distributions with bounded fourth moments (BFMD).

   [ Agent a ] <--- exchanges d x 2 summary table ---> [ Agent a' ]
        |                                                     |
        +-- Compares confidence interval |x_a - x_a'|         +-- Prunes edge if
            against threshold beta_gamma(t)                       distance > 0

Datasets

  • Synthetic Benchmarks: Agents sampled from two Gaussian distributions, $\mathcal{N}(0, 4)$ and $\mathcal{N}(1, 4)$, over simple $r$-regular random graphs ($N = |A| = 10{,}000$, $r = 10$, $d = 4$).
  • MNIST (Handwritten Digits): Used to evaluate an extension to decentralized personalized federated learning (FL-DG). 100 clients were organized into a dynamic graph where distinct data distributions were generated by permuting digit labels.

Key Insights and Ideas

  • Pruning locally bypasses global bottlenecks: Instead of classifying the entire population, an agent only tests its $r$ immediate neighbors. The time to identify same-class neighbors drops from scaling with $|A|$ to scaling with the local neighborhood size.
  • Distinct convergence dynamics:
  • In B-ColME, an incorrect cross-class connection continues to corrupt messages until every path of length $\le d$ connecting to that out-of-class node is severed. Thus, estimates show little improvement until roughly $90\%$ of wrong edges are cut, after which accuracy converges sharply.
  • In C-ColME, consensus weights continuously dilute out-of-class influence as edge cuts accumulate, improving estimates early on, though past errors take longer to fade completely.
  • Random regular graphs strike the sweet spot: Setting degree $r \approx 4 / p_{\min}$ (where $p_{\min}$ is the smallest class fraction) keeps over $99\%$ of same-class agents in one connected component. Setting hop distance $d \approx \frac{1}{2}\log_{r-1}\frac{|A|}{\log_{r-1}|A|}$ ensures the local neighborhood is a tree with high probability, yielding sublinear speedups of $\Omega(|A|^{1/2-\phi})$.

Key Results

  • Complexity: Reduced per-agent memory and computation from $O(|A|)$ in ColME to $O(r)$ in C-ColME and $O(rd)$ in B-ColME.
  • Convergence Speedup: In synthetic experiments ($N = 10{,}000$), both algorithms reliably pruned all wrong links and reached $\epsilon$-accurate estimates significantly faster than non-collaborative local estimation. While standard ColME eventually attains higher asymptotic precision (by aggregating all $|C_a|$ agents across the network), C-ColME and B-ColME achieve faster initial convergence without ColME's prohibitive resource burden.
  • Federated Learning Extension: On MNIST with 100 clients, dynamically pruning dissimilar neighbors via cosine dissimilarity (FL-DG) reached $\approx 85\%$ accuracy, outperforming both purely local models ($\approx 60\%$) and static-graph federated learning ($\approx 70\%$).

Limitations and Future Work

  • Irreversible Edge Pruning: Edges can only be removed, never rewired or added. If an early misclassification severs a connection, or if the initial random topology lacks connectivity, agents cannot discover similar peers elsewhere in the graph.
  • Rigid Similarity Classes: The framework assumes agents partition into discrete groups with identical true means, rather than continuously varying or partially overlapping distributions.
  • Tree-Structure Dependence in B-ColME: If cycles occur within $d$ hops, samples are double-counted, which limits $d$ to logarithmic scaling relative to $|A|$.

Summary updated

Abstract

In numerous settings, agents lack sufficient data to learn a model directly. Collaborating with other agents may help, but 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 particular instance of the overarching problem, where each agent collects samples from a real-valued distribution over time to estimate its mean. Existing algorithms face impractical per-agent space and time complexities (linear 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 propose two collaborative mean estimation algorithms: one employs a consensus-based approach, while the other uses a message-passing scheme, with complexity O(r) and O(r log |A|), respectively. We establish conditions for both algorithms to yield asymptotically optimal estimates and we provide 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},
}

Loading related content...

Figure