On the Necessity of Collaboration for Online Model Selection with Decentralized Data
This work addresses the necessity of collaboration in federated learning for online model selection, clarifying previous assumptions and improving regret bounds with lower computational and communication costs.
The paper tackles the problem of determining when collaboration is necessary for online model selection with decentralized data, proving that collaboration is unnecessary without computational constraints but necessary when client computational cost is limited to o(K), where K is the number of candidate hypothesis spaces.
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.