论文标题
通过一声通信的联合回归的确切支持恢复
Exact Support Recovery in Federated Regression with One-shot Communication
论文作者
论文摘要
联合学习提供了一个框架，以应对大量具有低计算和通信功能的分布式客户的分布式计算，数据所有权和隐私的挑战。在本文中，我们研究了学习联合学习设置中稀疏线性回归的确切支持的问题。我们提供了一种简单的通信有效算法，该算法仅需要与集中式服务器进行一次性通信来计算确切的支持。我们的方法不需要客户解决任何优化问题，因此可以在计算功能较低的设备上运行。我们的方法自然会使客户失败，模型中毒和散布客户的问题具有强大的核心。我们正式证明我们的方法需要每个客户端的许多样本，这些样本相对于支持大小而言是多项式的，但与问题的维度无关。我们要求分布式客户端的数量在问题的维度上是对数。如果预测变量是相互独立的，则总体样品复杂性与未拟合集中设置的最佳样品复杂性匹配。此外，我们的方法易于实现，并且具有总体多项式时间的复杂性。
Federated learning provides a framework to address the challenges of distributed computing, data ownership and privacy over a large number of distributed clients with low computational and communication capabilities. In this paper, we study the problem of learning the exact support of sparse linear regression in the federated learning setup. We provide a simple communication efficient algorithm which only needs one-shot communication with the centralized server to compute the exact support. Our method does not require the clients to solve any optimization problem and thus, can be run on devices with low computational capabilities. Our method is naturally robust to the problems of client failure, model poisoning and straggling clients. We formally prove that our method requires a number of samples per client that is polynomial with respect to the support size, but independent of the dimension of the problem. We require the number of distributed clients to be logarithmic in the dimension of the problem. If the predictor variables are mutually independent then the overall sample complexity matches the optimal sample complexity of the non-federated centralized setting. Furthermore, our method is easy to implement and has an overall polynomial time complexity.
