Research map / Multi-agent systems and games / Cooperative multi-agent RL
Scalable Decentralized Algorithms for Online Personalized Mean Estimation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes two scalable decentralized collaborative mean-estimation algorithms (consensus-based C-ColME and message-passing B-ColME) over a sparse random regular graph, pruning wrong-class neighbors so per-agent cost is O(r) or O(r log|A|) instead of O(|A|).
Problem
Online decentralized mean estimation where agents must identify which peers share their true mean while learning; existing ColME has per-agent time and space linear in the number of agents and only handles scalar sub-Gaussian data.
Approach
Agents self-organize into a sparse graph with at most r neighbors, prune dissimilar neighbors via optimistic confidence-interval distances, and then average either through a consensus iteration (C-ColME) or through d-hop message passing (B-ColME), extending the guarantees to multidimensional distributions with bounded fourth moment.
Key results
- B-ColME and C-ColME converge faster than ColME on a 10000-agent Gaussian two-class simulation (|A|=10000, r=10, d=4), at the cost of higher asymptotic error.
- C-ColME's estimates start improving as soon as the first wrong links are removed, whereas B-ColME only improves after about 90% of wrong links are removed.
- Decentralized FL over a dynamic graph (FL-DG) on MNIST with 100 agents reaches higher accuracy than static-graph decentralized FL by pruning cross-class links.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace ColME's population-wide collaboration with pruned-graph consensus | Mean estimation · Bounded fourth-moment distributions | convergence time | Helped |
| Replace ColME's population-wide collaboration with pruned-graph message passing | Mean estimation · Bounded fourth-moment distributions | convergence time | Helped |
| Use pruned-graph collaboration instead of ColME's population-wide collaboration | Mean estimation · Bounded fourth-moment distributions | asymptotic estimation error | Hurt |
| Adapt consensus-based decentralized FL to progressively exclude dissimilar neighbors | MNIST handwritten digit recognition · MNIST | accuracy | Helped |
Surprising findings
- B-ColME shows no apparent estimate improvement until about 90% of wrong links are removed, whereas C-ColME improves as soon as the first edges are eliminated.
Limitations
- Agents can only remove connections, not establish new ones.
- Assumes agents are partitioned into similarity classes with identical true means within each class.
- C-ColME and B-ColME reach a higher asymptotic error than ColME because they collaborate with smaller groups.
Experimental setup
Datasets: MNIST synthetic Gaussian agent distributions
Benchmarks: MNIST
Metrics: fraction of incorrect estimates fraction of wrong links accuracy
Baselines: ColME s-ColME local estimate oracle neighbor selection
Builds on: ColME ClusteredFL consensus algorithms
Closest papers by meaning
- Mechanism Design for Collaborative Normal Mean Estimation (NeurIPS 2023 · similarity 0.89)
- Collaborative Mean Estimation Among Heterogeneous Strategic Agents: Individual Rationality, Fairness, and Truthful Contribution (ICML 2025 · similarity 0.89)
- Accelerating Federated Learning with Quick Distributed Mean Estimation (ICML 2024 · similarity 0.84)
- Robust Distributed Estimation: Extending Gossip Algorithms to Ranking and Trimmed Means (NeurIPS 2025 · similarity 0.83)
- Adaptive Sample Sharing for Multi Agent Linear Bandits (ICML 2025 · similarity 0.83)
- Fundamental Limits of Distributed Covariance Matrix Estimation Under Communication Constraints (ICML 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.