Research map / Federated learning and privacy / Communication-efficient FL
On the Necessity of Collaboration for Online Model Selection with Decentralized Data
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.
Studies whether collaboration is necessary for online model selection with decentralized data, proving that it is unnecessary without client computational limits but necessary when per-client cost is o(K), and proposes FOMD-OMS with decoupled server-side model selection.
Problem
Online model selection over M clients with decentralized data (OMS-DecD): whether federated collaboration reduces regret, especially under per-client computational constraints, and how it applies to distributed online multi-kernel learning.
Approach
Decouple model selection (performed on server by sampling J of K hypotheses per client) from prediction (done on clients), run federated online mirror descent over the simplex and hypothesis spaces, and show via matching-style lower bounds that collaboration only helps when per-client computation is o(K).
Key results
- Theory: with J=2 per-client cost O(1), FOMD-OMS regret O(M B sqrt(T) + B sqrt(MKT/J)) beats the lower bound for noncooperative algorithms, so collaboration is necessary when per-client cost is o(K).
- Experiments on 8 regression datasets with K=10 nested spaces: with J=2, FOMD-OMS has lower MSE than NCO-OMS on all datasets (e.g., elevators 1.024 vs 1.168 x10^-2), while with J=K the gap is negligible.
- Against eM-KOFL and POF-MKL with J=2, FOMD-OMS achieves similar MSE to eM-KOFL at much lower client time (e.g., elevator 0.52s vs 2.67s) and beats POF-MKL on MSE and time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FOMD-OMS (J=2) instead of POF-MKL | Distributed online kernel selection · All eight kernel-selection datasets | MSE | Helped |
| Use FOMD-OMS (J=2) instead of eM-KOFL | Distributed online kernel selection · elevator, bank, calhousing, Year, Slice | MSE | Mixed |
| Use FOMD-OMS (J=2) instead of eM-KOFL | Distributed online kernel selection · TomsHardware, Twitter, ailerons | MSE | Hurt |
| Set sampled hypotheses J=2 rather than J=K (ablation) | FOMD-OMS vs NCO-OMS · Eight regression datasets | MSE | Helped |
| Use collaboration (FOMD-OMS) rather than noncooperative NCO-OMS with J=K (ablation) | Online model selection · Eight regression datasets | MSE | No clear effect |
| Use collaboration (FOMD-OMS) rather than noncooperative NCO-OMS with J=2 (ablation) | Online model selection · Eight regression datasets | MSE | Helped |
Surprising findings
- With unlimited client computation, collaboration gives only marginal MSE improvement over the noncooperative algorithm, suggesting it is unnecessary.
- On some datasets (TomsHardware, Twitter, ailerons), eM-KOFL achieves slightly better MSE than FOMD-OMS.
Limitations
- Experiments use serial simulation and do not measure actual communication cost.
- Lower bound for noncooperative algorithms assumes outputs lie in the union of the hypothesis-space output ranges, and the no-constraint lower bound is stated for a specific linear setting.
- Improvement over eM-KOFL is not uniform; for large K eM-KOFL's regret can be better by O(sqrt(K)).
Experimental setup
Datasets: elevators bank ailerons calhousing TomsHardware Twitter Year Slice
Benchmarks: elevators bank ailerons calhousing TomsHardware Twitter Year Slice
Metrics: mean squared error running time per client
Baselines: NCO-OMS eM-KOFL POF-MKL
Builds on: online mirror descent federated online mirror descent eM-KOFL POF-MKL intermittent communication
Closest papers by meaning
- Federated Online and Bandit Convex Optimization (ICML 2023 · similarity 0.88)
- Communication-Efficient Federated Non-Linear Bandit Optimization (ICLR 2024 · similarity 0.87)
- Decentralized Sporadic Federated Learning: A Unified Algorithmic Framework with Convergence Guarantees (ICLR 2025 · similarity 0.87)
- Communication Efficient Federated Learning for Generalized Linear Bandits (NeurIPS 2022 · similarity 0.87)
- Federated Optimization with Doubly Regularized Drift Correction (ICML 2024 · similarity 0.86)
- Pursuing Overall Welfare in Federated Learning through Sequential Decision Making (ICML 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.