Research map / Bandits and online learning / Online convex optimization and games
Communication Bounds for the Distributed Experts Problem
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 communication-efficient distributed experts protocols (DEWA-S, DEWA-M, DEWA-L and high-probability variants) for sum, max and l_p aggregation, plus communication lower bounds, validated on HPO-B.
Problem
Online experts learning where each expert's cost is aggregated across s servers, and the coordinator must pick experts with low regret while minimizing communication in message-passing and broadcast models, against strong adaptive adversaries.
Approach
Use sampling-based unbiased cost estimators (DEWA-S) and random-order server walks where a server only sends a cost when it exceeds the running max (DEWA-M), with exponential-distribution embedding to reduce l_p to max (DEWA-L); boost to high probability by running EWA over log(poly T) meta-experts.
Key results
- On HPO-B with sum aggregation, DEWA-S (b_e=1) uses about 0.0730x the communication of EWA in the blackboard model, while achieving regret comparable to EWA and Exp3.
- Theory: DEWA-S achieves regret O(sqrt(n log n /(T b_e))) with probability 9/10 using O(T(b_e+s)) communication, versus EWA's O(nTs) communication.
- Lower bound: Omega(n/R^2 + Ts) communication is needed for regret R in the broadcast model, even against oblivious adversaries, for l_p aggregation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DEWA-S with b_e=1 instead of EWA | Distributed experts on HPO-B with sum aggregation · HPO-B, blackboard | communication cost: 1× -> 0.0730× | Helped |
| Use DEWA-S with b_e=n instead of EWA | Distributed experts on HPO-B with sum aggregation · HPO-B, blackboard | communication cost: 1× -> 0.0758× | Helped |
| Use DEWA-M with b_e=1 instead of EWA | Distributed experts on HPO-B with max aggregation · HPO-B, blackboard | communication cost: 1× -> 0.0849× | Helped |
| Use DEWA-M with b_e=n instead of EWA | Distributed experts on HPO-B with max aggregation · HPO-B, blackboard | communication cost: 1× -> 0.1834× | Helped |
| Use DEWA-S or DEWA-M instead of Exp3 | Distributed experts on HPO-B · HPO-B, blackboard | regret | No clear effect |
Surprising findings
- For max aggregation in the message-passing model, an Omega(ns) lower bound holds for sub-constant regret when T is polylogarithmic, so naive EWA is near-optimal there.
Limitations
- Upper bounds for DEWA-S and DEWA-M/L hold with constant probability unless boosted by meta-experts, which adds overhead.
- Lower bound for the max aggregation in message-passing is Omega(ns) only for T polylogarithmic in ns; a gap remains for larger T.
- Regret for l_p with p<=2 degrades to a weaker exponent (epsilon-dependent).
Experimental setup
Datasets: HPO-B
Benchmarks: HPO-B
Metrics: regret communication cost relative to EWA
Baselines: EWA Exp3
Builds on: Exponential Weights Algorithm Exp3 epsilon-DIFFDIST communication lower bound
Closest papers by meaning
- Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups (NeurIPS 2024 · similarity 0.86)
- On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.85)
- Individual Regret in Cooperative Stochastic Multi-Armed Bandits (NeurIPS 2025 · similarity 0.85)
- Distributed Multi-Agent Bandits Over Erdős-Rényi Random Networks (NeurIPS 2025 · similarity 0.84)
- Improved Regret Bounds for Online Fair Division with Bandit Learning (AAAI 2025 · similarity 0.84)
- Tracking The Best Expert Privately (ICML 2025 · similarity 0.84)
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.