Research map / Federated learning and privacy / Communication-efficient FL
Federated X-armed Bandit
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.
Introduces federated X-armed bandit with heterogeneous local objectives and proposes Fed-PNE, a phased hierarchical node-elimination algorithm with logarithmic communication rounds and sublinear regret in clients and budget.
Problem
Collaboratively finding the optimum of a global objective (average of heterogeneous local objectives) over a continuous, infinite-cardinality domain, when clients keep raw rewards private and communicate only limited summary statistics.
Approach
A phased hierarchical node-elimination algorithm over a fixed partition of the domain: the server eliminates sub-optimal partition nodes using averaged client mean rewards plus confidence and smoothness terms, so only aggregated means are communicated in O(M log T) rounds.
Key results
- Fed-PNE achieves client-wise regret of order Õ(M^{-1/(d+2)} T^{(d+1)/(d+2)}) and communication Õ(M log T) for sufficiently large T.
- Regret lower bound Ω(M^{(d+1)/(d+2)} T^{(d+1)/(d+2)}) shows the upper bound is tight up to log factors.
- Fed-PNE has the smallest cumulative regret versus HCT, KernelTS, Fed1-UCB and FN-UCB on Garland, DoubleSine, Landmine and COVID-19 tasks.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Fed-PNE instead of HCT, KernelTS, Fed1-UCB, or FN-UCB | Federated X-armed bandit · Garland | average cumulative regret | Helped |
| Use Fed-PNE instead of HCT, KernelTS, Fed1-UCB, or FN-UCB | Federated X-armed bandit · DoubleSine | average cumulative regret | Helped |
| Use Fed-PNE instead of HCT, KernelTS, Fed1-UCB, or FN-UCB | Federated X-armed bandit · Landmine | average cumulative regret | Helped |
| Use Fed-PNE instead of HCT, KernelTS, Fed1-UCB, or FN-UCB | Federated X-armed bandit · COVID | average cumulative regret | Helped |
Surprising findings
- Communicated information can grow as O(M T^{d/(d+2)}) when near-optimality dimension d>0, and the paper claims this dependence is unavoidable for any algorithm with the same regret rate.
Limitations
- Requires the smoothness parameters (ν1, ρ) as input and uses the stronger Bubeck et al. local smoothness assumption rather than the weaker metric-free one.
- Early-stage regret has a super-linear dependence on M when T is small.
- Communicated information can grow polynomially in T when near-optimality dimension d>0.
Experimental setup
Datasets: Garland function DoubleSine function Landmine dataset COVID-19 epidemiological model
Benchmarks: Garland DoubleSine Landmine COVID-19 vaccine dosage
Metrics: cumulative regret
Baselines: HCT KernelTS Fed1-UCB FN-UCB
Builds on: HOO HCT Phased Elimination Fed1-UCB
Closest papers by meaning
- Communication-Efficient Federated Non-Linear Bandit Optimization (ICLR 2024 · similarity 0.92)
- Federated Combinatorial Multi-Agent Multi-Armed Bandits (ICML 2024 · similarity 0.88)
- Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users (AAAI 2024 · similarity 0.88)
- Incentivized Truthful Communication for Federated Bandits (ICLR 2024 · similarity 0.87)
- On Differentially Private Federated Linear Contextual Bandits (ICLR 2024 · similarity 0.87)
- Federated Q-Learning: Linear Regret Speedup with Low Communication Cost (ICLR 2024 · similarity 0.85)
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.