With changes in privacy laws, there is often a hard requirement for client data to remain on the device rather than being sent to the server. Therefore, most processing happens on the device, and only an altered element is sent to the server. Such mechanisms are developed by leveraging differential privacy and federated learning. Differential privacy adds noise to the client outputs and thus deteriorates the quality of each iteration. This distributed setting adds a layer of complexity and additional communication and performance overhead. These costs are additive per round, so we need to reduce the number of iterations. In this work, we provide an analytical framework for studying the convergence guarantees of gradient-based distributed algorithms. We show that our private algorithm minimizes the expected gradient variance by approximately $d^2$ rounds, where d is the dimensionality of the model. We discuss and suggest novel ways to improve the convergence rate to minimize the overhead using Importance Sampling (IS) and gradient diversity. Finally, we provide alternative frameworks that might be better suited to exploit client sampling techniques like IS and gradient diversity.
翻译:随着隐私法的改变,常常很难要求客户数据保留在设备上,而不是发送到服务器。 因此, 大多数处理都发生在设备上, 并且只向服务器发送一个被修改的元素。 这种机制是通过利用差异隐私和联合学习开发的。 差异隐私增加了客户产出的噪音, 从而恶化了每次循环的质量。 这种分布式设置增加了一层复杂程度和额外的通信和性能管理管理费用。 这些成本是每轮的添加值, 所以我们需要减少迭代数量。 在这项工作中, 我们提供了一个分析框架, 用于研究基于梯度分布式算法的聚合保证。 我们显示, 我们的私人算法将预期的梯度差异最小化了大约$d ⁇ 2美元, 也就是模型的维度。 我们讨论并提出新的方法来改进合并率, 以使用重要取样(IS) 和梯度多样性来尽量减少间接费用。 最后, 我们提供了更适合利用客户抽样技术的替代框架, 比如 IS 和 梯度多样性 。