在本文中，我们考虑了分散的优化问题，在这些问题中，代理具有个人成本函数，以最大程度地减少受到子空间约束的约束，这些子空间约束需要整个网络的最小化器才能位于低维子空间中。这种约束的公式包括共识或单任务优化作为特殊情况，并允许更一般的任务相关性模型，例如多任务平滑度和耦合优化。为了应对沟通限制，我们提出并研究一种自适应分散策略，在该策略中，代理人在与邻居进行交流之前，使用差异随机量化器来压缩其估计。分析表明，在量化噪声的某些一般条件下，对于足够小的步长$ \ mu $，该策略在均方误差和平均比特率方面都是稳定的：通过减少$ \ mu $，可以将估计错误保持较小（按$ \ mu $）保持较小，而不会无限地增加比特率为$ \ mu \ rightarrow 0 $。模拟说明了理论发现和提议方法的有效性，表明可以实现分散学习，但仅需少量。

这项工作审查了旨在在通信约束下运行的自适应分布式学习策略。我们考虑一个代理网络，必须从持续观察流数据来解决在线优化问题。代理商实施了分布式合作策略，其中允许每个代理商与其邻居执行本地信息交换。为了应对通信约束，必须不可避免地压缩交换信息。我们提出了一种扩散策略，昵称为ACTC（适应 - 压缩 - 然后组合），其依赖于以下步骤：i）每个代理执行具有恒定步长大小的单独随机梯度更新的适应步骤; ii）一种压缩步骤，它利用最近引入的随机压缩操作员;和III）每个代理组合从其邻居接收的压缩更新的组合步骤。这项工作的区别要素如下。首先，我们专注于自适应策略，其中常数（而不是递减）阶梯大小对于实时响应非间断变化至关重要。其次，我们考虑一般的指导图表和左随机组合政策，使我们能够增强拓扑和学习之间的相互作用。第三，与对所有个人代理的成本职能承担强大的凸起的相关作品相比，我们只需要在网络水平的强大凸起，即使单个代理具有强凸的成本，剩余的代理商也不满足凸起成本。第四，我们专注于扩散（而不是共识）战略。在压缩信息的苛刻设置下，建立ACTC迭代在所需的优化器周围波动，在相邻代理之间交换的比特方面取得了显着的节省。

我们在限制下研究了一阶优化算法，即使用每个维度的$ r $ bits预算进行量化下降方向，其中$ r \ in（0，\ infty）$。我们提出了具有收敛速率的计算有效优化算法，与信息理论性能匹配：（i）：（i）具有访问精确梯度甲骨文的平稳且强烈的符合目标，以及（ii）一般凸面和非平滑目标访问嘈杂的亚级别甲骨文。这些算法的关键是一种多项式复杂源编码方案，它在量化它之前将矢量嵌入随机子空间中。这些嵌入使得具有很高的概率，它们沿着转换空间的任何规范方向的投影很小。结果，量化这些嵌入，然后对原始空间进行逆变换产生一种源编码方法，具有最佳的覆盖效率，同时仅利用每个维度的$ r $ bits。我们的算法保证了位预算$ r $的任意值的最佳性，其中包括次线性预算制度（$ r <1 $），以及高预算制度（$ r \ geq 1 $），虽然需要$ o \ left（n^2 \右）$乘法，其中$ n $是尺寸。我们还提出了使用Hadamard子空间对这种编码方案的有效放松扩展以显着提高梯度稀疏方案的性能。数值模拟验证我们的理论主张。我们的实现可在https://github.com/rajarshisaha95/distoptconstrocncomm上获得。

通过使多个代理在缺乏中央协调员的情况下合作解决全球优化问题，分散的随机优化在像机器学习，控制和传感器网络这样的多种多样的领域中，人们的注意力越来越多。由于相关数据通常包含敏感信息，例如用户位置和个人身份，因此在实施分散的随机优化时，隐私保护已成为至关重要的需求。在本文中，我们提出了一种分散的随机优化算法，即使在存在与量化幅度成正比的积极量化误差的情况下，该算法也能够保证可证明的收敛精度。该结果同时适用于凸面和非凸目标函数，使我们能够利用积极的量化方案来混淆共享信息，因此可以在不失去可证明的优化精度的情况下进行隐私保护。实际上，通过使用将任何值量化为三个数值级别的任何值的{随机}三元量化方案，我们在分散的随机优化中实现了基于量化的严格差异隐私，以前尚未报告。结合提出的量化方案，提出的算法首次确保了分散的随机优化中的严格差异隐私，而不会失去可证明的收敛精度。分布式估计问题以及基准计算机学习数据集上分散学习的数值实验的仿真结果证实了所提出方法的有效性。

这项工作提出了一种分散的架构，其中个别代理旨在解决分类问题，同时观察不同尺寸的流特征，并从可能不同的分布产生。在社会学习的背景下，已经开发了几种有用的策略，通过跨分布式代理的本地合作解决了决策问题，并允许他们从流数据中学习。然而，传统的社会学习策略依赖于每个代理人对观察结果分布的重要知识的基本假设。在这项工作中，我们通过引入一种机器学习框架来克服这一问题，该机器学习框架利用图形的社交交互，导致分布式分类问题的完全数据驱动的解决方案。在拟议的社交机器学习（SML）策略中，存在两个阶段：在训练阶段，分类器被独立培训，以使用有限数量的训练样本来产生一组假设的信念;在预测阶段，分类器评估流媒体未标记的观察，并与邻近分类器共享他们的瞬时信仰。我们表明SML策略使得代理能够在这种高度异构的环境下一致地学习，并且即使在预测阶段决定未标记的样本时，即使在预测阶段也允许网络继续学习。预测决策用于以明显不同的方式不断地提高性能，这些方式与大多数现有的静态分类方案不同，在培训之后，未标记数据的决策不会重新用于改善未来的性能。

This work studies networked agents cooperating to track a dynamical state of nature under partial information. The proposed algorithm is a distributed Bayesian filtering algorithm for finite-state hidden Markov models (HMMs). It can be used for sequential state estimation tasks, as well as for modeling opinion formation over social networks under dynamic environments. We show that the disagreement with the optimal centralized solution is asymptotically bounded for the class of geometrically ergodic state transition models, which includes rapidly changing models. We also derive recursions for calculating the probability of error and establish convergence under Gaussian observation models. Simulations are provided to illustrate the theory and to compare against alternative approaches.

机器学习已开始在许多应用中发挥核心作用。这些应用程序中的许多应用程序通常还涉及由于设计约束（例如多元系统）或计算/隐私原因（例如，在智能手机数据上学习），这些数据集分布在多个计算设备/机器上。这样的应用程序通常需要以分散的方式执行学习任务，其中没有直接连接到所有节点的中央服务器。在现实世界中的分散设置中，由于设备故障，网络攻击等，节点容易出现未发现的故障，这可能会崩溃非稳固的学习算法。本文的重点是在发生拜占庭失败的节点的存在下对分散学习的鲁棒化。拜占庭故障模型允许故障节点任意偏离其预期行为，从而确保设计最健壮的算法的设计。但是，与分布式学习相反，对分散学习中拜占庭式的弹性的研究仍处于起步阶段。特别是，现有的拜占庭式分散学习方法要么不能很好地扩展到大规模的机器学习模型，要么缺乏统计收敛性可确保有助于表征其概括错误。在本文中，引入了一个可扩展的，拜占庭式的分散的机器学习框架，称为拜占庭的分散梯度下降（桥梁）。本文中还提供了强烈凸出问题和一类非凸问题的算法和统计收敛保证。此外，使用大规模的分散学习实验来确定桥梁框架是可扩展的，并且为拜占庭式弹性凸和非convex学习提供了竞争结果。

分布式平均值估计（DME）是联邦学习中的一个中央构建块，客户将本地梯度发送到参数服务器，以平均和更新模型。由于通信限制，客户经常使用有损压缩技术来压缩梯度，从而导致估计不准确。当客户拥有多种网络条件（例如限制的通信预算和数据包损失）时，DME更具挑战性。在这种情况下，DME技术通常会导致估计误差显着增加，从而导致学习绩效退化。在这项工作中，我们提出了一种名为Eden的强大DME技术，该技术自然会处理异质通信预算和数据包损失。我们为伊甸园提供了有吸引力的理论保证，并通过经验进行评估。我们的结果表明，伊甸园对最先进的DME技术持续改进。

我们介绍了一个框架 - Artemis-，以解决分布式或联合设置中的学习问题，并具有通信约束和设备部分参与。几位工人（随机抽样）使用中央服务器执行优化过程来汇总其计算。为了减轻通信成本，Artemis允许在两个方向上（从工人到服务器，相反）将发送的信息与内存机制相结合。它改进了仅考虑单向压缩（对服务器）的现有算法，或在压缩操作员上使用非常强大的假设，并且通常不考虑设备的部分参与。我们在非I.I.D中的随机梯度（仅在最佳点界定的噪声方差）提供了快速的收敛速率（线性最高到阈值）。设置，突出显示内存对单向和双向压缩的影响，分析Polyak-Ruppert平均。我们在分布中使用收敛性，以获得渐近方差的下限，该方差突出了实际的压缩极限。我们提出了两种方法，以解决设备部分参与的具有挑战性的案例，并提供实验结果以证明我们的分析有效性。

我们考虑使用随机球形代码的高维信号$ x $的有损压缩表示之间的分布连接，并在添加白色高斯噪声（AWGN）下的$ X $观察$ x $。我们展示了比特率 - $ R $压缩版的Wassersein距离$ x $及其在AWGN-噪声比率下的AWGN噪声比率下的观察2 ^ {2R} -1 $ 2 ^ {2r} -1 $中的下线性。我们利用此事实基于AWGN损坏的$ x $的AWGN损坏版本的估算者的风险连接到与其比特率 - $ r $量化版本相同的估算器所获得的风险。我们通过在压缩约束下导出推导问题的各种新结果来展示这种联系的有用性，包括Minimax估计，稀疏回归，压缩感和远程源编码中的线性估计的普遍性。

高维模型通常具有较大的内存足迹，必须在训练后进行量化，然后将其部署在资源受限的边缘设备上以进行推理任务。在这项工作中，我们开发了一个信息理论框架，用于量化从训练数据$（\ mathbf {x}，\ mathbf {y}）$的线性回归剂的问题，用于某些基本统计关系$ \ mathbf {y} = \ Mathbf {X} \ BoldSymbol {\ Theta} + \ Mathbf {V} $。博学的模型是对潜在参数$ \ boldsymbol {\ theta} \ in \ mathbb {r}^d $的估计值，仅使用$ bd $ bits来代表，其中$ b \ in（0，in 0，0，in（0） \ infty）$是预先指定的预算，$ d $是维度。在此设置下，我们为Minimax风险提供了信息理论的下限，并建议使用基于嵌入的算法进行匹配的上限，该算法紧密到恒定因素。上限和上限共同表征了达到与未量化设置相当的性能风险所需的最小阈值位预算。我们还提出了在计算上有效且最佳的随机hadamard嵌入到下限的轻度对数因子。我们的模型量化策略可以概括，我们通过将方法和上限扩展到两层relu神经网络以进行非线性回归来显示其功效。数值模拟表明，我们提出的方案的性能得到改善，以及其与下限的亲密关系。

在过去的几年中，各种通信压缩技术已经出现为一个不可或缺的工具，有助于缓解分布式学习中的通信瓶颈。然而，尽管{\ em偏见}压缩机经常在实践中显示出卓越的性能，但与更多的研究和理解的{\ EM无偏见}压缩机相比，非常少见。在这项工作中，我们研究了三类偏置压缩操作员，其中两个是新的，并且它们在施加到（随机）梯度下降和分布（随机）梯度下降时的性能。我们首次展示偏置压缩机可以在单个节点和分布式设置中导致线性收敛速率。我们证明了具有错误反馈机制的分布式压缩SGD方法，享受ergodic速率$ \ mathcal {o} \ left（\ delta l \ exp [ - \ frac {\ mu k} {\ delta l}] + \ frac {（c + \ delta d）} {k \ mu} \右）$，其中$ \ delta \ ge1 $是一个压缩参数，它在应用更多压缩时增长，$ l $和$ \ mu $是平滑性和强凸常数，$ C $捕获随机渐变噪声（如果在每个节点上计算完整渐变，则$ C = 0 $如果在每个节点上计算），则$ D $以最佳（$ d = 0 $ for over参数化模型）捕获渐变的方差）。此外，通过对若干合成和经验的通信梯度分布的理论研究，我们阐明了为什么和通过多少偏置压缩机优于其无偏的变体。最后，我们提出了几种具有有希望理论担保和实际表现的新型偏置压缩机。

分散和联合学习的关键挑战之一是设计算法，这些算法有效地处理跨代理商的高度异构数据分布。在本文中，我们在数据异质性下重新审视分散的随机梯度下降算法（D-SGD）的分析。我们在D-SGD的收敛速率上展示了新数量的关键作用，称为\ emph {邻居异质性}。通过结合通信拓扑结构和异质性，我们的分析阐明了这两个分散学习中这两个概念之间的相互作用较低。然后，我们认为邻里的异质性提供了一种自然标准，可以学习数据依赖性拓扑结构，以减少（甚至可以消除）数据异质性对D-SGD收敛时间的有害影响。对于与标签偏度分类的重要情况，我们制定了学习这样一个良好拓扑的问题，例如我们使用Frank-Wolfe算法解决的可拖动优化问题。如一组模拟和现实世界实验所示，我们的方法提供了一种设计稀疏拓扑的方法，可以在数据异质性下平衡D-SGD的收敛速度和D-SGD的触电沟通成本。

Parallel implementations of stochastic gradient descent (SGD) have received significant research attention, thanks to its excellent scalability properties. A fundamental barrier when parallelizing SGD is the high bandwidth cost of communicating gradient updates between nodes; consequently, several lossy compresion heuristics have been proposed, by which nodes only communicate quantized gradients. Although effective in practice, these heuristics do not always converge. In this paper, we propose Quantized SGD (QSGD), a family of compression schemes with convergence guarantees and good practical performance. QSGD allows the user to smoothly trade off communication bandwidth and convergence time: nodes can adjust the number of bits sent per iteration, at the cost of possibly higher variance. We show that this trade-off is inherent, in the sense that improving it past some threshold would violate information-theoretic lower bounds. QSGD guarantees convergence for convex and non-convex objectives, under asynchrony, and can be extended to stochastic variance-reduced techniques. When applied to training deep neural networks for image classification and automated speech recognition, QSGD leads to significant reductions in end-to-end training time. For instance, on 16GPUs, we can train the ResNet-152 network to full accuracy on ImageNet 1.8× faster than the full-precision variant. time to the same target accuracy is 2.7×. Further, even computationally-heavy architectures such as Inception and ResNet can benefit from the reduction in communication: on 16GPUs, QSGD reduces the end-to-end convergence time of ResNet152 by approximately 2×. Networks trained with QSGD can converge to virtually the same accuracy as full-precision variants, and that gradient quantization may even slightly improve accuracy in some settings. Related Work. One line of related research studies the communication complexity of convex optimization. In particular, [40] studied two-processor convex minimization in the same model, provided a lower bound of Ω(n(log n + log(1/ ))) bits on the communication cost of n-dimensional convex problems, and proposed a non-stochastic algorithm for strongly convex problems, whose communication cost is within a log factor of the lower bound. By contrast, our focus is on stochastic gradient methods. Recent work [5] focused on round complexity lower bounds on the number of communication rounds necessary for convex learning.Buckwild! [10] was the first to consider the convergence guarantees of low-precision SGD. It gave upper bounds on the error probability of SGD, assuming unbiased stochastic quantization, convexity, and gradient sparsity, and showed significant speedup when solving convex problems on CPUs. QSGD refines these results by focusing on the trade-off between communication and convergence. We view quantization as an independent source of variance for SGD, which allows us to employ standard convergence results [7]. The main differences from Buckw

我们考虑分散的优化问题，其中许多代理通过在基础通信图上交换来最大程度地减少其本地功能的平均值。具体而言，我们将自己置于异步模型中，其中只有一个随机部分在每次迭代时执行计算，而信息交换可以在所有节点之间进行，并以不对称的方式进行。对于此设置，我们提出了一种算法，该算法结合了整个网络上梯度跟踪和差异的差异。这使每个节点能够跟踪目标函数梯度的平均值。我们的理论分析表明，在预期混合矩阵的轻度连通性条件下，当局部目标函数强烈凸面时，算法会汇聚。特别是，我们的结果不需要混合矩阵是双随机的。在实验中，我们研究了一种广播机制，该机制将信息从计算节点传输到其邻居，并确认我们方法在合成和现实世界数据集上的线性收敛性。

近似消息传递（AMP）是解决高维统计问题的有效迭代范式。但是，当迭代次数超过$ o \ big（\ frac {\ log n} {\ log log \ log \ log n} \时big）$（带有$ n $问题维度）。为了解决这一不足，本文开发了一个非吸附框架，用于理解峰值矩阵估计中的AMP。基于AMP更新的新分解和可控的残差项，我们布置了一个分析配方，以表征在存在独立初始化的情况下AMP的有限样本行为，该过程被进一步概括以进行光谱初始化。作为提出的分析配方的两个具体后果：（i）求解$ \ mathbb {z} _2 $同步时，我们预测了频谱初始化AMP的行为，最高为$ o \ big（\ frac {n} {\ mathrm {\ mathrm { poly} \ log n} \ big）$迭代，表明该算法成功而无需随后的细化阶段（如最近由\ citet {celentano2021local}推测）; （ii）我们表征了稀疏PCA中AMP的非反应性行为（在尖刺的Wigner模型中），以广泛的信噪比。

在分散的优化中，通信网络的节点每个都具有局部目标函数，并使用基于八卦的方法进行通信，以最大程度地减少这些每节点函数的平均值。尽管同步算法受到图表中的一些慢节点或边缘的影响（\ emph {straggler问题}），但众所周知，它们的异步对应物很难参数化。实际上，到目前为止，它们针对具有异质通信和计算延迟的网络的收敛属性已经违反了分析。在本文中，我们使用\ emph {Continuized}框架来分析具有延迟的网络中的异步算法。我们的方法对收敛时间及其对网络中异质延迟的依赖性的精确表征。我们的连续框架受益于连续和离散世界中最好的：它适用的算法基于事件驱动的更新。因此，它们本质上是离散的，因此很容易实现。然而，他们的分析本质上是连续的，部分依赖于延迟的ODE理论。此外，我们的算法实现了\ emph {异步加速}：它们的收敛速率受到局部延迟加权的网络图的特征控制，而不是以前的分析中的网络范围最差的延迟。因此，我们的方法享有改善对散乱者的鲁棒性。

当数据自然分配到通过基础图的代理商之间，分散学习提供了隐私和沟通效率。通过过度参数化的学习设置，在该设置中，在该设置中训练了零训练损失，我们研究了分散学习的分散学习算法和概括性能，并在可分离的数据上下降。具体而言，对于分散的梯度下降（DGD）和各种损失函数，在无穷大（包括指数损失和逻辑损失）中渐近为零，我们得出了新的有限时间泛化界限。这补充了一长串最近的工作，该工作研究了概括性能和梯度下降的隐含偏见，而不是可分离的数据，但迄今为止，梯度下降的偏见仅限于集中学习方案。值得注意的是，我们的概括范围匹配其集中式同行。这背后的关键和独立感兴趣的是，在一类自我结合的损失方面建立了关于训练损失和DGD的传记率的新界限。最后，在算法方面，我们设计了改进的基于梯度的例程，可分离数据，并在经验上证明了训练和概括性能方面的加速命令。

在本文中，我们提出了一种均匀抖动的一位量化方案，以进行高维统计估计。该方案包含截断，抖动和量化，作为典型步骤。作为规范示例，量化方案应用于三个估计问题：稀疏协方差矩阵估计，稀疏线性回归和矩阵完成。我们研究了高斯和重尾政权，假定重尾数据的基本分布具有有限的第二或第四刻。对于每个模型，我们根据一位量化的数据提出新的估计器。在高斯次级政权中，我们的估计器达到了对数因素的最佳最小速率，这表明我们的量化方案几乎没有额外的成本。在重尾状态下，虽然我们的估计量基本上变慢，但这些结果是在这种单位量化和重型尾部设置中的第一个结果，或者比现有可比结果表现出显着改善。此外，我们为一位压缩传感和一位矩阵完成的问题做出了巨大贡献。具体而言，我们通过凸面编程将一位压缩感传感扩展到次高斯甚至是重尾传感向量。对于一位矩阵完成，我们的方法与标准似然方法基本不同，并且可以处理具有未知分布的预量化随机噪声。提出了有关合成数据的实验结果，以支持我们的理论分析。

Privacy protection and nonconvexity are two challenging problems in decentralized optimization and learning involving sensitive data. Despite some recent advances addressing each of the two problems separately, no results have been reported that have theoretical guarantees on both privacy protection and saddle/maximum avoidance in decentralized nonconvex optimization. We propose a new algorithm for decentralized nonconvex optimization that can enable both rigorous differential privacy and saddle/maximum avoiding performance. The new algorithm allows the incorporation of persistent additive noise to enable rigorous differential privacy for data samples, gradients, and intermediate optimization variables without losing provable convergence, and thus circumventing the dilemma of trading accuracy for privacy in differential privacy design. More interestingly, the algorithm is theoretically proven to be able to efficiently { guarantee accuracy by avoiding} convergence to local maxima and saddle points, which has not been reported before in the literature on decentralized nonconvex optimization. The algorithm is efficient in both communication (it only shares one variable in each iteration) and computation (it is encryption-free), and hence is promising for large-scale nonconvex optimization and learning involving high-dimensional optimization parameters. Numerical experiments for both a decentralized estimation problem and an Independent Component Analysis (ICA) problem confirm the effectiveness of the proposed approach.