Federated learning (FL) is a distributed learning paradigm in which many clients with heterogeneous, unbalanced, and often sensitive local data, collaborate to learn a model. Local Differential Privacy (LDP) provides a strong guarantee that each client's data cannot be leaked during and after training, without relying on a trusted third party. While LDP is often believed to be too stringent to allow for satisfactory utility, our paper challenges this belief. We consider a general setup with unbalanced, heterogeneous data, disparate privacy needs across clients, and unreliable communication, where a random number/subset of clients is available each round. We propose three LDP algorithms for smooth (strongly) convex FL; each are noisy variations of distributed minibatch SGD. One is accelerated and one involves novel time-varying noise, which we use to obtain the first non-trivial LDP excess risk bound for the fully general non-i.i.d. FL problem. Specializing to i.i.d. clients, our risk bounds interpolate between the best known and/or optimal bounds in the centralized setting and the cross-device setting, where each client represents just one person's data. Furthermore, we show that in certain regimes, our convergence rate (nearly) matches the corresponding non-private lower bound or outperforms state of the art non-private algorithms (``privacy for free''). Finally, we validate our theoretical results and illustrate the practical utility of our algorithm with numerical experiments.
翻译:联邦学习(FL)是一个分布式的学习模式,许多客户拥有不同、不平衡和往往敏感的地方数据,他们可以合作学习模型。地方差异隐私(LDP)提供了强有力的保证,保证每个客户的数据在培训期间和培训之后不会泄露,而不必依赖信任的第三方。虽然人们通常认为LDP过于严格,无法令人满意地发挥效用,但我们的文件挑战了这一信念。我们认为,一个总体的设置,拥有不平衡、差异性的数据,不同客户的隐私需求不均,以及不可靠的通信,每个回合都有随机的客户数/子集。我们建议三种LDP算法用于(强力)配置FLL;每种都是分布的小型批件 SGD的噪音变异。一个是加速的,一个是新颖的时间变异的噪音,我们用来获得第一个非边际的LDP超额风险,而这个完全普通的非i.d.FL问题。我们特别考虑的是,i.d.客户,我们的风险在中央设置中最已知和/或最优化的界限之间,另一个是交叉配置的变异的变异的逻辑,每个客户的逻辑显示我们一个不固定的直线的逻辑。