我们提出了一种联邦平均Langevin算法（FA-LD），用于不确定量化和与分布式客户端的平均预测。特别是，我们概括了正常的后验分布，并考虑一般的模型。我们为FA-LD为具有非I.I.D数据的强烈凹入分布的理论保障，并研究了注入的噪声和随机梯度噪声如何，数据的异质性以及不同的学习率影响收敛性。这样的分析揭示了最佳选择的本地更新，以最大限度地减少通信成本。对于我们的方法很重要，即通信效率不会与Langevin算法中的注入噪声恶化。此外，我们在我们的FA-LD算法中审视了不同客户端使用的独立和相关噪声。我们遵守联邦和沟通成本之间的权衡也在那里。由于本地设备在联合网络中可能处于非活动状态，我们还基于仅可用的部分设备更新的不同平均方案来显示收敛结果。

联邦学习（FL）是大规模分布式学习的范例，它面临两个关键挑战：（i）从高度异构的用户数据和（ii）保护参与用户的隐私的高效培训。在这项工作中，我们提出了一种新颖的流动方法（DP-SCaffold）来通过将差异隐私（DP）约束结合到流行的脚手架算法中来解决这两个挑战。我们专注于有挑战性的环境，用户在没有任何可信中介的情况下与“诚实但奇怪的”服务器沟通，这需要确保隐私不仅可以访问最终模型的第三方，而且还要对服务器观察所有用户通信。使用DP理论的高级结果，我们建立了凸面和非凸面目标算法的融合。我们的分析清楚地突出了数据异质性下的隐私式折衷，并且当局部更新的数量和异质性水平增长时，展示了在最先进的算法DP-Fedivg上的DP-Scaffold的优越性。我们的数值结果证实了我们的分析，并表明DP-Scaffold在实践中提供了重大的收益。

我们展示了一个联合学习框架，旨在强大地提供具有异构数据的各个客户端的良好预测性能。所提出的方法对基于SuperQualile的学习目标铰接，捕获异构客户端的误差分布的尾统计。我们提出了一种随机训练算法，其与联合平均步骤交织差异私人客户重新重量步骤。该提出的算法支持有限时间收敛保证，保证覆盖凸和非凸面设置。关于联邦学习的基准数据集的实验结果表明，我们的方法在平均误差方面与古典误差竞争，并且在误差的尾统计方面优于它们。

本文研究了缺乏值得信赖的服务器/客户的联邦学习（FL）的问题。在此设置中，每个客户端都需要确保其自身数据的隐私，而无需依赖服务器或其他客户端。我们研究了本地差异隐私（LDP）并提供紧密的上限和下限，可以为LDP凸起/强凸的联合随机优化建立最小的最佳速率（最多ogarithms）。我们的利率与某些实际参数制度（免费私隐）相匹配最佳统计率）。其次，我们开发了一种新型时变嘈杂的SGD算法，导致与非I.I.D的第一个非普通LDP风险限制。客户。第三，我们考虑每个客户端损失功能的特殊情况，其中每个客户端的损失函数是与现有工程相比改善通信复杂性的加速的LDP流。我们还提供匹配的下限，建立凸/强凸设置算法的最优性。第四，使用安全的Shuffler匿名客户报告（但没有可信服务器），我们的算法达到了随机凸/强凸优化的最佳中央DP速率，从而同时在局部和中心模型中实现最优性。我们的上限量量化了网络通信可靠性在性能中的作用。

Federated Averaging (FEDAVG) has emerged as the algorithm of choice for federated learning due to its simplicity and low communication cost. However, in spite of recent research efforts, its performance is not fully understood. We obtain tight convergence rates for FEDAVG and prove that it suffers from 'client-drift' when the data is heterogeneous (non-iid), resulting in unstable and slow convergence.As a solution, we propose a new algorithm (SCAFFOLD) which uses control variates (variance reduction) to correct for the 'client-drift' in its local updates. We prove that SCAFFOLD requires significantly fewer communication rounds and is not affected by data heterogeneity or client sampling. Further, we show that (for quadratics) SCAFFOLD can take advantage of similarity in the client's data yielding even faster convergence. The latter is the first result to quantify the usefulness of local-steps in distributed optimization.

在本文中，我们重新审视了私人经验风险最小化（DP-erm）和差异私有随机凸优化（DP-SCO）的问题。我们表明，来自统计物理学（Langevin Exfusion（LD））的经过良好研究的连续时间算法同时为DP-SCO和DP-SCO提供了最佳的隐私/实用性权衡，$ \ epsilon $ -DP和$ $ \ epsilon $ -DP和$ （\ epsilon，\ delta）$ - dp均用于凸和强烈凸损失函数。我们为LD提供新的时间和尺寸独立统一稳定性，并使用我们为$ \ epsilon $ -DP提供相应的最佳超额人口风险保证。 $ \ epsilon $ -DP的DP-SCO保证的一个重要属性是，它们将非私人最佳界限匹配为$ \ epsilon \与\ infty $。在此过程中，我们提供了各种技术工具，这些工具可能引起独立的关注：i）在两个相邻数据集上运行损失功能时，一个新的r \'enyi Divergence绑定了LD，ii）最后一个过多的经验风险范围迭代LD，类似于Shamir和Zhang的嘈杂随机梯度下降（SGD）和iii）的LD，对LD进行了两期多余的风险分析，其中第一阶段是当扩散在任何合理意义上都没有在任何合理意义上融合到固定分布时，在第二阶段扩散已收敛到吉布斯分布的变体。我们的普遍性结果至关重要地依赖于LD的动力学。当它融合到固定分布时，我们获得了$ \ epsilon $ -DP的最佳界限。当它仅在很短的时间内运行$ \ propto 1/p $时，我们在$（\ epsilon，\ delta）$ -DP下获得最佳界限。在这里，$ p $是模型空间的维度。

联合学习（FL）使大量优化的优势计算设备（例如，移动电话）联合学习全局模型而无需数据共享。在FL中，数据以分散的方式产生，具有高异质性。本文研究如何在联邦设置中对统计估算和推断进行统计估算和推理。我们分析所谓的本地SGD，这是一种使用间歇通信来提高通信效率的多轮估计过程。我们首先建立一个{\ IT功能的中央极限定理}，显示了本地SGD的平均迭代弱融合到重新定位的布朗运动。我们接下来提供两个迭代推断方法：{\ IT插件}和{\ IT随机缩放}。随机缩放通过沿整个本地SGD路径的信息构造推断的渐近枢转统计。这两种方法都是通信高效且适用于在线数据。我们的理论和经验结果表明，本地SGD同时实现了统计效率和通信效率。

We consider the constrained sampling problem where the goal is to sample from a distribution $\pi(x)\propto e^{-f(x)}$ and $x$ is constrained on a convex body $\mathcal{C}\subset \mathbb{R}^d$. Motivated by penalty methods from optimization, we propose penalized Langevin Dynamics (PLD) and penalized Hamiltonian Monte Carlo (PHMC) that convert the constrained sampling problem into an unconstrained one by introducing a penalty function for constraint violations. When $f$ is smooth and the gradient is available, we show $\tilde{\mathcal{O}}(d/\varepsilon^{10})$ iteration complexity for PLD to sample the target up to an $\varepsilon$-error where the error is measured in terms of the total variation distance and $\tilde{\mathcal{O}}(\cdot)$ hides some logarithmic factors. For PHMC, we improve this result to $\tilde{\mathcal{O}}(\sqrt{d}/\varepsilon^{7})$ when the Hessian of $f$ is Lipschitz and the boundary of $\mathcal{C}$ is sufficiently smooth. To our knowledge, these are the first convergence rate results for Hamiltonian Monte Carlo methods in the constrained sampling setting that can handle non-convex $f$ and can provide guarantees with the best dimension dependency among existing methods with deterministic gradients. We then consider the setting where unbiased stochastic gradients are available. We propose PSGLD and PSGHMC that can handle stochastic gradients without Metropolis-Hasting correction steps. When $f$ is strongly convex and smooth, we obtain an iteration complexity of $\tilde{\mathcal{O}}(d/\varepsilon^{18})$ and $\tilde{\mathcal{O}}(d\sqrt{d}/\varepsilon^{39})$ respectively in the 2-Wasserstein distance. For the more general case, when $f$ is smooth and non-convex, we also provide finite-time performance bounds and iteration complexity results. Finally, we test our algorithms on Bayesian LASSO regression and Bayesian constrained deep learning problems.

为了在带宽洪泛环境（例如无线网络）中启用大规模的机器学习，最近在设计借助通信压缩的帮助下，最近在设计沟通效率的联合学习算法方面取得了重大进展。另一方面，隐私保护，尤其是在客户层面上，是另一个重要的避税，在存在高级通信压缩技术的情况下尚未同时解决。在本文中，我们提出了一个统一的框架，以通过沟通压缩提高私人联邦学习的沟通效率。利用通用压缩操作员和局部差异隐私，我们首先检查了一种简单的算法，该算法将压缩直接应用于差异私密的随机梯度下降，并确定其局限性。然后，我们为私人联合学习提出了一个统一的框架Soteriafl，该框架适应了一般的局部梯度估计剂家庭，包括流行的随机方差减少梯度方法和最先进的变化压缩方案。我们在隐私，公用事业和沟通复杂性方面提供了其性能权衡的全面表征，在这种情况下，Soterafl被证明可以在不牺牲隐私或实用性的情况下实现更好的沟通复杂性，而不是其他私人联合联盟学习算法而没有沟通压缩。

Federated learning is a distributed framework according to which a model is trained over a set of devices, while keeping data localized. This framework faces several systemsoriented challenges which include (i) communication bottleneck since a large number of devices upload their local updates to a parameter server, and (ii) scalability as the federated network consists of millions of devices. Due to these systems challenges as well as issues related to statistical heterogeneity of data and privacy concerns, designing a provably efficient federated learning method is of significant importance yet it remains challenging. In this paper, we present FedPAQ, a communication-efficient Federated Learning method with Periodic Averaging and Quantization. FedPAQ relies on three key features: (1) periodic averaging where models are updated locally at devices and only periodically averaged at the server; (2) partial device participation where only a fraction of devices participate in each round of the training; and (3) quantized messagepassing where the edge nodes quantize their updates before uploading to the parameter server. These features address the communications and scalability challenges in federated learning. We also show that FedPAQ achieves near-optimal theoretical guarantees for strongly convex and non-convex loss functions and empirically demonstrate the communication-computation tradeoff provided by our method.

联邦平均（FedAVG），也称为本地SGD，是联邦学习中最受欢迎的算法之一（FL）。尽管其简单和普及，但到目前为止，FADVG的收敛速率尚未确定。即使在最简单的假设（凸，平滑，均匀和有界协方差）下，最着名的上限和下限也不匹配，目前尚不清楚现有分析是否捕获算法的容量。在这项工作中，我们首先通过为FedAVG提供与现有的上限相匹配的下限来解决这个问题，这表明现有的FADVG上限分析不可易于解决。另外，我们在异构环境中建立一个下限，几乎与现有的上限相匹配。虽然我们的下限显示了FEDAVG的局限性，但在额外的三阶平滑度下，我们证明了更乐观的最先进的收敛导致凸和非凸面设置。我们的分析源于我们呼叫迭代偏置的概念，这由SGD轨迹的期望从具有相同初始化的无噪声梯度下降轨迹的偏差来定义。我们在此数量上证明了新颖的尖锐边界，并直观地显示了如何从随机微分方程（SDE）的角度来分析该数量。

我们考虑开放的联合学习（FL）系统，客户可以在FL过程中加入和/或离开系统。鉴于当前客户端数量的差异，在开放系统中不能保证与固定模型的收敛性。取而代之的是，我们求助于一个新的性能指标，该指标称我们的开放式FL系统的稳定性为量，该指标量化了开放系统中学习模型的幅度。在假设本地客户端的功能强烈凸出和平滑的假设下，我们从理论上量化了两种FL算法的稳定性半径，即本地SGD和本地ADAM。我们观察到此半径依赖于几个关键参数，包括功能条件号以及随机梯度的方差。通过对合成和现实世界基准数据集的数值模拟，我们的理论结果得到了进一步验证。

In federated optimization, heterogeneity in the clients' local datasets and computation speeds results in large variations in the number of local updates performed by each client in each communication round. Naive weighted aggregation of such models causes objective inconsistency, that is, the global model converges to a stationary point of a mismatched objective function which can be arbitrarily different from the true objective. This paper provides a general framework to analyze the convergence of federated heterogeneous optimization algorithms. It subsumes previously proposed methods such as FedAvg and FedProx and provides the first principled understanding of the solution bias and the convergence slowdown due to objective inconsistency. Using insights from this analysis, we propose Fed-Nova, a normalized averaging method that eliminates objective inconsistency while preserving fast error convergence.

FEDPROX算法是一种简单但功能强大的分布式近端优化方法，广泛用于联合学习（FL）而不是异质数据。尽管在实践中看到了它的知名度和杰出的成功，但对FEDPROX的理论理解在很大程度上是不足的：FedProx的吸引人的融合行为迄今在某些非标准和不切实际的地方功能的差异假设下的特征是，结果的优化仅限于优化的限制。问题。为了解决这些缺陷，我们通过算法稳定性的镜头开发了FedProx及其Minibatch随机扩展的新型局部差异不变理论。结果，我们有助于得出对FedProx的几个新的和更深入的见解，以实现联合优化的非凸面，包括：1）收敛确保独立于局部差异类型条件； 2）融合保证非平滑FL问题； 3）关于Minibatch的尺寸和采样设备的数量，线性加速。我们的理论首次揭示了局部差异和平稳性对于FedProx获得有利的复杂性界限并不是必备的。据报道，一系列基准FL数据集的初步实验结果证明了小型匹配以提高FEDPROX的样品效率的好处。

可扩展性和隐私是交叉设备联合学习（FL）系统的两个关键问题。在这项工作中，我们确定了FL中的客户端更新的同步流动聚合不能高效地缩放到几百个并行培训之外。它导致ModelPerforce和训练速度的回报递减，Ampanysto大批量培训。另一方面，FL（即异步FL）中的客户端更新的异步聚合减轻了可扩展性问题。但是，聚合个性链子更新与安全聚合不兼容，这可能导致系统的不良隐私水平。为了解决这些问题，我们提出了一种新颖的缓冲异步聚合方法FedBuff，这是不可知的优化器的选择，并结合了同步和异步FL的最佳特性。我们经验证明FEDBuff比同步FL更有效，比异步FL效率更高3.3倍，同时兼容保留保护技术，如安全聚合和差异隐私。我们在平滑的非凸设置中提供理论融合保证。最后，我们显示在差异私有培训下，FedBuff可以在低隐私设置下占FEDAVGM并实现更高隐私设置的相同实用程序。

众所周知，客户师沟通可能是联邦学习中的主要瓶颈。在这项工作中，我们通过一种新颖的客户端采样方案解决了这个问题，我们将允许的客户数量限制为将其更新传达给主节点的数量。在每个通信回合中，所有参与的客户都会计算他们的更新，但只有具有“重要”更新的客户可以与主人通信。我们表明，可以仅使用更新的规范来衡量重要性，并提供一个公式以最佳客户参与。此公式将所有客户参与的完整更新与我们有限的更新（参与客户数量受到限制）之间的距离最小化。此外，我们提供了一种简单的算法，该算法近似于客户参与的最佳公式，该公式仅需要安全的聚合，因此不会损害客户的隐私。我们在理论上和经验上都表明，对于分布式SGD（DSGD）和联合平均（FedAvg），我们的方法的性能可以接近完全参与，并且优于基线，在参与客户均匀地采样的基线。此外，我们的方法与现有的减少通信开销（例如本地方法和通信压缩方法）的现有方法兼容。

联合学习（FL）是机器学习的一个子领域，在该子机学习中，多个客户试图在通信约束下通过网络进行协作学习模型。我们考虑在二阶功能相似性条件和强凸度下联合优化的有限和联合优化，并提出了两种新算法：SVRP和催化的SVRP。这种二阶相似性条件最近越来越流行，并且在包括分布式统计学习和差异性经验风险最小化在内的许多应用中得到满足。第一种算法SVRP结合了近似随机点评估，客户采样和降低方差。我们表明，当功能相似性足够高时，SVRP是沟通有效的，并且在许多现有算法上取得了卓越的性能。我们的第二个算法，催化的SVRP，是SVRP的催化剂加速变体，在二阶相似性和强凸度下，现有的联合优化算法可实现更好的性能，并均匀地改善了现有的算法。在分析这些算法的过程中，我们提供了可能具有独立关注的随机近端方法（SPPM）的新分析。我们对SPPM的分析很简单，允许进行近似近端评估，不需要任何平滑度假设，并且在通信复杂性上比普通分布式随机梯度下降显示出明显的好处。

在不同数据分布下由不同优化算法训练的机器学习模型可以表现出明显的泛化行为。在本文中，我们分析了噪声迭代算法训练的模型的概括。通过将噪声迭代算法连接到通信和信息理论中发现的附加噪声信道来源，我们推导出依赖于分布的泛化界限。我们的泛化界限在几种应用中，包括差异私有随机梯度下降（DP-SGD），联合学习和随机梯度Langevin动力学（SGLD）。我们通过数值实验展示了我们的界限，表明他们可以帮助了解神经网络泛化现象的最新实证观察。

我们考虑对跨用户设备分发的私人数据培训模型。为了确保隐私，我们添加了设备的噪声并使用安全的聚合，以便仅向服务器揭示嘈杂的总和。我们提出了一个综合的端到端系统，该系统适当地离散数据并在执行安全聚合之前添加离散的高斯噪声。我们为离散高斯人的总和提供了新的隐私分析，并仔细分析了数据量化和模块化求和算术的影响。我们的理论保证突出了沟通，隐私和准确性之间的复杂张力。我们广泛的实验结果表明，我们的解决方案基本上能够将准确性与中央差分隐私相匹配，而每个值的精度少于16位。

在本文中，我们在使用离散的Langevin扩散的三个方案中从目标密度采样的误差提供非渐近上限。第一个方案是Langevin Monte Carlo（LMC）算法，歌曲的欧拉分散化的歌曲扩散。第二个和第三种方案分别是用于可微分电位和动力学Langevin Monte Carlo的动力学Langevin Monte Carlo（KLMC），用于两次可分视电位（KLMC2）。主要焦点是在$ \ mathbb r ^ p $的目标密度上，但不一定强烈地抖动。在两种类型的平滑假设下获得计算复杂度的界限：电位具有嘴唇连续梯度，并且电位具有嘴角连续的Hessian基质。采样误差由Wassersein-$ Q $距离测量。我们倡导在计算复杂性定义中使用新的维度适应缩放，当考虑Wasserstein-$ Q $距离时。所获得的结果表明，实现小于规定值的缩放误差的迭代次数仅取决于多项尺寸。