On the Necessity of Collaboration in Online Model Selection with Decentralized Data

我们考虑在$M$个客户端上进行分散数据的在线模型选择，并研究一个基本问题：协作的必要性。之前的研究从最坏情况下的遗憾最小化的角度给出了否定答案，而我们从遗憾-计算成本权衡的角度给出了不同的答案。我们分别提出了具有和不具有通信约束的联邦算法，并证明了遗憾界，表明：(i)如果我们不限制每个客户端的计算成本，则协作是不必要的；(ii)如果我们将每个客户端的计算成本限制为$o(K)$，其中$K$是候选假设空间的数量，则协作是必要的。作为副产品，我们在更小的计算和通信成本下改进了分布式在线多核学习算法的遗憾界。我们的算法依赖于三种新技术，即改进的马丁格尔贝尔斯坦不等式，名为FOMD-No-LU的联邦算法框架，以及模型选择和预测的解耦，这可能是独立感兴趣的。

研究联邦学习中的在线模型选择问题，探讨协作的必要性。

论文提出两种联邦算法，并证明了在限制每个客户端的计算成本时，协作是必要的。同时，论文还提出了三种新技术，包括改进的Bernstein不等式、FOMD-No-LU算法框架以及模型选择和预测的解耦。

论文的算法在计算和通信成本方面都有所改进，并在分布式在线多核学习中获得更好的结果。实验使用了真实数据集，并提供了开源代码。

近期的相关研究包括《Federated Multi-Task Learning with Performance Guarantee》、《Federated Learning with Non-IID Data》等。