Research map / Federated learning and privacy / Communication-efficient FL
Communication-Efficient Federated Non-Linear Bandit Optimization
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 Fed-GO-UCB, a communication-efficient federated bandit algorithm for generic non-linear (neural-network) objectives that combines a distributed GLD regression oracle in an initial uniform phase with event-triggered synchronization of shared-gradient confidence sets.
Problem
Federated bandit optimization for generic non-linear black-box objectives has been limited to linear, generalized linear, or bounded-RKHS function classes; generic non-linear models require iterative optimization that makes communication costly.
Approach
Compute all confidence-set statistics from gradients taken at one shared model w0 (obtained after a uniform exploration phase via distributed Gradient Langevin Dynamics), so local statistics can be directly summed across clients and synchronized with an event-triggered protocol borrowed from federated linear bandits.
Key results
- Theory: cumulative regret of Fed-GO-UCB is Õ(√(NT)) (matching centralized GO-UCB) and communication cost Õ(N^1.5 √T), sublinear in T.
- Number of global synchronizations bounded by Õ(√N) with the chosen threshold γ.
- Empirically, Fed-GO-UCB and One-GO-UCB achieve much lower regret than DisLinUCB, Fed-GLB-UCB, ApproxDisKernelUCB and N-GO-UCB on synthetic functions, with much lower communication than One-GO-UCB; it also outperforms baselines on MagicTelescope and Shuttle.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use neural network approximation rather than the baseline algorithms' simpler function classes | Federated bandit optimization · Synthetic test functions | cumulative regret | Helped |
| use event-triggered communication instead of synchronizing every data point | Fed-GO-UCB versus One-GO-UCB · Synthetic test functions | communication cost | Helped |
| use Fed-GO-UCB for generic non-linear function optimization | Federated bandit baselines · MagicTelescope and Shuttle | cumulative regret | Helped |
Surprising findings
- Fed-GO-UCB's per-round communication is larger than linear baselines because statistics have size d_w^2 (~10^4) versus d_x^2 (~10^2).
Limitations
- Communication cost retains a √T dependence due to the iterative distributed optimization of the Phase I estimator.
- Requires realizability and strong smoothness/geometric conditions (growth or local strong convexity, dissipativity, local self-concordance) and a spectral-gap-dependent GLD iteration count that may be exponential in d_x.
- Assumes homogeneous clients sharing one reward function; heterogeneous clients are left to future work.
Experimental setup
Datasets: Synthetic test functions (Hartmann-style f1, cosine-quadratic f2) MagicTelescope (UCI) Shuttle (UCI)
Benchmarks: Synthetic test functions f1, f2 MagicTelescope Shuttle
Metrics: cumulative regret communication cost
Baselines: DisLinUCB Fed-GLB-UCB ApproxDisKernelUCB One-GO-UCB N-GO-UCB
Builds on: GO-UCB federated linear bandits with event-triggered communication Gradient Langevin Dynamics
Closest papers by meaning
- Federated X-armed Bandit (AAAI 2024 · similarity 0.92)
- Incentivized Truthful Communication for Federated Bandits (ICLR 2024 · similarity 0.89)
- On Differentially Private Federated Linear Contextual Bandits (ICLR 2024 · similarity 0.89)
- Federated Combinatorial Multi-Agent Multi-Armed Bandits (ICML 2024 · similarity 0.88)
- Federated Optimization with Doubly Regularized Drift Correction (ICML 2024 · similarity 0.87)
- Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users (AAAI 2024 · similarity 0.87)
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.