# On the Necessity of Collaboration for Online Model Selection with Decentralized Data

arXiv: https://arxiv.org/abs/2404.09494 · HTML: https://mlsanity.com/paper/2404.09494/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 55 references that are in the map.
- First posted on arXiv 15 Apr 2024.

## Builds on (most cited first, 26 of 26)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Is Local SGD Better than Minibatch SGD?](https://mlsanity.com/paper/2002.07839/) (2020)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Model selection for contextual bandits](https://mlsanity.com/paper/1906.00531/) (2019)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [Parameter-free online learning via model selection](https://mlsanity.com/paper/1801.00101/) (2017)
- [The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication](https://mlsanity.com/paper/2102.01583/) (2021)
- [Random Feature-based Online Multi-kernel Learning in Environments with Unknown Dynamics](https://mlsanity.com/paper/1712.09983/) (2017)
- [Online Active Model Selection for Pre-trained Classifiers](https://mlsanity.com/paper/2010.09818/) (2020)
- [Tighter Regret Analysis and Optimization of Online Federated Learning](https://mlsanity.com/paper/2205.06491/) (2022)
- [Online Distributed Learning Over Networks in RKH Spaces Using Random Fourier Features](https://mlsanity.com/paper/1703.08131/) (2017)
- [Personalized Online Federated Learning with Multiple Kernels](https://mlsanity.com/paper/2311.05108/) (2023)
- [Multi-scale Online Learning and its Applications to Online Auctions](https://mlsanity.com/paper/1705.09700/) (2017)
- [Federated Online and Bandit Convex Optimization](https://mlsanity.com/paper/2311.17586/) (2023)
- [Enhanced Federated Optimization: Adaptive Unbiased Client Sampling with Reduced Variance](https://mlsanity.com/paper/2310.02698/) (2023)
- [Model Selection in Reinforcement Learning with General Function Approximations](https://mlsanity.com/paper/2207.02992/) (2022)
- [Improved Regret Bounds for Online Kernel Selection under Bandit Feedback](https://mlsanity.com/paper/2303.05018/) (2023)

## Built on by (most cited first, 6 of 6)

- [All models are wrong, some are useful: Model Selection with Limited Labels](https://mlsanity.com/paper/2410.13609/) (2024)
- [Large Language Model Selection with Limited Annotations](https://mlsanity.com/paper/2605.24981/) (2026)
- [Learnability in Online Kernel Selection with Memory Constraint via Data-dependent Regret Analysis](https://mlsanity.com/paper/2407.00916/) (2024)
- [Online Optimization for Learning to Communicate over Time-Correlated Channels](https://mlsanity.com/paper/2409.00575/) (2024)
- [Large Language Model Selection with Limited Annotations](https://mlsanity.com/paper/2510.09418/) (2025)
- [A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions](https://mlsanity.com/paper/2510.27177/) (2025)

## Abstract (arXiv)

We consider online model selection with decentralized data over M clients, and study the necessity of collaboration among clients. Previous work proposed various federated algorithms without demonstrating their necessity,while we answer the question from a novel perspective of computational constraints. We prove lower bounds on the regret, and propose a federated algorithm and analyze the upper bound.Our results show (i) collaboration is unnecessary in the absence of computational constraints on clients; (ii) collaboration is necessary if the computational cost on each client is limited to o(K), where K is the number of candidate hypothesis spaces. We clarify the unnecessary nature of collaboration in previous federated algorithms for distributed online multi-kernel learning,and improve the regret bounds at a smaller computational and communication cost. Our algorithm relies on three new techniques including an improved Bernstein's inequality for martingale, a federated online mirror descent framework, and decoupling model selection and prediction, which might be of independent interest.