数据爆炸和模型尺寸的增加推动了大规模机器学习的显着进步,但也使模型训练时间耗时和模型存储变得困难。为了解决具有较高计算效率和设备限制的分布式模型培训设置中的上述问题,仍然存在两个主要困难。一方面,交换信息的沟通成本,例如,不同工人之间的随机梯度是分布式培训效率的关键瓶颈。另一方面,较少的参数模型容易用于存储和通信,但是损坏模型性能的风险。为了同时平衡通信成本,模型容量和模型性能,我们提出了量化的复合镜下降自适应亚基(QCMD Adagrad),并量化正规化双平均平均自适应亚级别(QRDA ADAGRAD)进行分布式培训。具体来说,我们探讨了梯度量化和稀疏模型的组合,以降低分布式培训中每次迭代的通信成本。构建了基于量化梯度的自适应学习率矩阵,以在沟通成本,准确性和模型稀疏性之间达到平衡。此外,从理论上讲,我们发现大量化误差会引起额外的噪声,从而影响模型的收敛性和稀疏性。因此,在QCMD Adagrad和QRDA Adagrad中采用了具有相对较小误差的阈值量化策略,以提高信噪比并保留模型的稀疏性。理论分析和经验结果都证明了所提出的算法的功效和效率。
translated by 谷歌翻译
High network communication cost for synchronizing gradients and parameters is the well-known bottleneck of distributed training. In this work, we propose TernGrad that uses ternary gradients to accelerate distributed deep learning in data parallelism. Our approach requires only three numerical levels {−1, 0, 1}, which can aggressively reduce the communication time. We mathematically prove the convergence of TernGrad under the assumption of a bound on gradients. Guided by the bound, we propose layer-wise ternarizing and gradient clipping to improve its convergence. Our experiments show that applying TernGrad on AlexNet doesn't incur any accuracy loss and can even improve accuracy. The accuracy loss of GoogLeNet induced by TernGrad is less than 2% on average. Finally, a performance model is proposed to study the scalability of TernGrad. Experiments show significant speed gains for various deep neural networks. Our source code is available 1 .
translated by 谷歌翻译
深度学习在广泛的AI应用方面取得了有希望的结果。较大的数据集和模型一致地产生更好的性能。但是,我们一般花费更长的培训时间,以更多的计算和沟通。在本调查中,我们的目标是在模型精度和模型效率方面提供关于大规模深度学习优化的清晰草图。我们调查最常用于优化的算法,详细阐述了大批量培训中出现的泛化差距的可辩论主题,并审查了解决通信开销并减少内存足迹的SOTA策略。
translated by 谷歌翻译
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.
translated by 谷歌翻译
分布式机器学习实现可扩展性和计算卸载,但需要大量的通信。因此,分布式学习设置中的沟通效率是一个重要的考虑因素,尤其是当通信是无线且采用电池驱动设备时。在本文中,我们开发了一种基于审查的重球(CHB)方法,用于在服务器工作者体系结构中分布式学习。除非其本地梯度与先前传播的梯度完全不同,否则每个工人的自我审查员。 HB学习问题的显着实际优势是众所周知的,但是尚未解决降低通信的问题。 CHB充分利用HB平滑来消除报告的微小变化,并证明达到了与经典HB方法相当的线性收敛速率,以平滑和强烈凸出目标函数。 CHB的收敛保证在理论上是合理的,对于凸和非凸案。此外,我们证明,在某些情况下,至少可以消除所有通信的一半,而不会对收敛率产生任何影响。广泛的数值结果验证了CHB在合成和真实数据集(凸,非凸和非不同情况)上的通信效率。鉴于目标准确性,与现有算法相比,CHB可以显着减少通信数量,从而实现相同的精度而不减慢优化过程。
translated by 谷歌翻译
现代深度学习模型通常在分布式机器集合中并行培训,以减少训练时间。在这种情况下,机器之间模型更新的通信变成了一个重要的性能瓶颈,并且已经提出了各种有损的压缩技术来减轻此问题。在这项工作中,我们介绍了一种新的,简单但理论上和实践上有效的压缩技术:自然压缩(NC)。我们的技术分别应用于要进行压缩的更新向量的所有条目,并通过随机舍入到两个的(负或正)两种功能,可以通过忽略Mantissa来以“自然”方式计算。我们表明,与没有压缩相比,NC将压缩向量的第二刻增加不超过微小因子$ \ frac {9} {8} $,这意味着NC对流行训练算法的收敛速度的影响,例如分布式SGD,可以忽略不计。但是,NC启用的通信节省是可观的,导致$ 3 $ - $ 4 \ times $ $改善整体理论运行时间。对于需要更具侵略性压缩的应用,我们将NC推广到自然抖动,我们证明这比常见的随机抖动技术要好得多。我们的压缩操作员可以自行使用,也可以与现有操作员结合使用,从而产生更具侵略性的结合效果,并在理论和实践中提供新的最先进。
translated by 谷歌翻译
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
translated by 谷歌翻译
由于培训数据集的大小爆炸,分布式学习近年来受到了日益增长的兴趣。其中一个主要瓶颈是中央服务器和本地工人之间的沟通成本。虽然已经证明错误反馈压缩以通过随机梯度下降(SGD)降低通信成本,但在培训大规模机器学习方面广泛用于培训的通信有效的适应性梯度方法楷模。在本文中,我们提出了一种新的通信 - 压缩AMSGRAD,用于分布式非透明的优化问题,可提供有效的效率。我们所提出的分布式学习框架具有有效的渐变压缩策略和工人侧模型更新设计。我们证明所提出的通信有效的分布式自适应梯度方法会聚到具有与随机非凸化优化设置中的未压缩的vanilla amsgrad相同的迭代复杂度的一阶静止点。关于各种基准备份我们理论的实验。
translated by 谷歌翻译
在分散的学习中,节点网络协作以最小化通常是其本地目标的有限总和的整体目标函数,并结合了非平滑的正则化术语,以获得更好的泛化能力。分散的随机近端梯度(DSPG)方法通常用于培训这种类型的学习模型,而随机梯度的方差延迟了收敛速率。在本文中,我们提出了一种新颖的算法,即DPSVRG,通过利用方差减少技术来加速分散的训练。基本思想是在每个节点中引入估计器,该节点周期性地跟踪本地完整梯度,以校正每次迭代的随机梯度。通过将分散的算法转换为具有差异减少的集中内隙近端梯度算法,并控制错误序列的界限,我们证明了DPSVRG以o(1 / t)$的速率收敛于一般凸起目标加上非平滑术语以$ t $作为迭代的数量,而dspg以$ o(\ frac {1} {\ sqrt {t}})$汇聚。我们对不同应用,网络拓扑和学习模型的实验表明,DPSVRG会收敛于DSPG的速度要快得多,DPSVRG的损耗功能与训练时期顺利降低。
translated by 谷歌翻译
随着大数据的快速增长,分布式机器学习(ML)已广泛应用于培训大型模型。随机梯度下降(SGD)可以说是ML的Workhorse算法。 SGD培训的分布式ML型号涉及大量的梯度通信,这限制了分布式ML的可扩展性。因此,压缩梯度以减少通信是重要的。在本文中,我们提出了FastSGD,一种用于分布式ML的快速压缩的SGD框架。为了以低成本实现高压缩比,FastSGD表示梯度作为键值对,并在线性时间复杂度压缩梯度键和值。对于梯度值压缩,FASTSGD首先使用互焦数映射器将原始值转换为互焦值,然后,它利用对数量化来进一步将互焦值减少到小整数。最后,FastSGD通过给定阈值过滤减少梯度整数。对于渐变键压缩,FastSGD提供了一种自适应细粒度的Δ编码方法,用于存储具有更少位的渐变键。实际ML模型和数据集的广泛实验证明,与最先进的方法相比,FastSGD实现了高达4个级别的压缩比,并加速了高达8倍的收敛时间。
translated by 谷歌翻译
联合学习可以使远程工作人员能够协作培训共享机器学习模型,同时允许在本地保持训练数据。在无线移动设备的用例中,由于功率和带宽有限,通信开销是关键瓶颈。前工作已经利用了各种数据压缩工具,例如量化和稀疏,以减少开销。在本文中,我们提出了一种用于联合学习的预测编码的压缩方案。该方案在所有设备中具有共享预测功能,并且允许每个工作人员发送来自参考的压缩残余矢量。在每个通信中,我们基于速率失真成本选择预测器和量化器,并进一步降低熵编码的冗余。广泛的模拟表明,与其他基线方法相比,甚至更好的学习性能,通信成本可以减少高达99%。
translated by 谷歌翻译
分布式学习的主要重点之一是沟通效率,因为每一轮训练的模型聚集可能包括数百万到数十亿个参数。已经提出了几种模型压缩方法,例如梯度量化和稀疏方法,以提高模型聚合的通信效率。但是,对于给定梯度估计器的给定扭曲的信息理论的最低通信成本仍然未知。在本文中,我们研究了从率延伸的角度研究分布式学习中模型聚集的基本限制。通过将模型聚合作为矢量高斯首席执行官问题,我们得出了模型聚合问题的速率区域和总成绩 - 距离函数,这揭示了在特定梯度失真上限处的最小通信速率。我们还根据现实世界数据集的梯度统计数据,分析了每次迭代和总通信成本的通信成本和总通信成本。发现通过利用工人节点之间的相关性来获得沟通增益,对于符号来说是显着的,并且梯度估计器的高扭曲可以实现梯度压缩中的较低总通信成本。
translated by 谷歌翻译
我们在限制下研究了一阶优化算法,即使用每个维度的$ 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上获得。
translated by 谷歌翻译
在本文中,提出了一个绿色,量化的FL框架,该框架在本地培训和上行链路传输中代表具有有限精度水平的数据。在这里,有限的精度级别是通过使用量化的神经网络(QNN)来捕获的,该神经网络(QNN)以固定精确格式量化权重和激活。在考虑的FL模型中,每个设备训练其QNN并将量化的训练结果传输到基站。严格得出了局部训练和传输的能量模型。为了同时最大程度地减少能耗和交流的数量,相对于本地迭代的数量,选定设备的数量以及本地培训和传输的精确级别,在确保融合的同时,提出了多目标优化问题目标准确性约束。为了解决此问题,相对于系统控制变量,分析得出所提出的FL系统的收敛速率。然后,该问题的帕累托边界被表征为使用正常边界检查方法提供有效的解决方案。通过使用NASH讨价还价解决方案并分析派生的收敛速率,从两个目标之间平衡了两种目标之间的权衡的洞察力。仿真结果表明,与代表完全精确的数据相比,提出的FL框架可以减少能源消耗,直到收敛高达52%。
translated by 谷歌翻译
分布式优化和学习的最新进展表明,沟通压缩是减少交流的最有效手段之一。尽管在通信压缩下的收敛速率有很多结果,但理论下限仍然缺失。通过通信压缩的算法的分析将收敛归因于两个抽象属性:无偏见的属性或承包属性。它们可以通过单向压缩(仅从工人到服务器的消息被压缩)或双向压缩来应用它们。在本文中,我们考虑了分布式随机算法,以最大程度地减少通信压缩下的平滑和非凸目标函数。我们为算法建立了收敛的下限,无论是在单向或双向中使用无偏压缩机还是使用承包压缩机。为了缩小下限和现有上限之间的差距,我们进一步提出了一种新石器时代的算法,该算法在轻度条件下几乎达到了我们的下限(达到对数因素)。我们的结果还表明,使用承包双向压缩可以产生迭代方法,该方法的收敛速度与使用无偏见的单向压缩的方法一样快。实验结果验证了我们的发现。
translated by 谷歌翻译
由于客户端的通信资源有限和大量的模型参数,大规模分布式学习任务遭受通信瓶颈。梯度压缩是通过传输压缩梯度来减少通信负载的有效方法。由于在随机梯度下降的情况下,相邻轮的梯度可能具有高相关,因为他们希望学习相同的模型,提出了一种用于联合学习的实用梯度压缩方案,它使用历史梯度来压缩梯度并且基于Wyner-Ziv编码但没有任何概率的假设。我们还在实时数据集上实现了我们的渐变量化方法,我们的方法的性能优于前一个方案。
translated by 谷歌翻译
我们开发了一种新方法来解决中央服务器中分布式学习问题中的通信约束。我们提出和分析了一种执行双向压缩的新算法,并仅使用uplink(从本地工人到中央服务器)压缩达到与算法相同的收敛速率。为了获得此改进,我们设计了MCM,一种算法,使下行链路压缩仅影响本地模型,而整体模型则保留。结果,与以前的工作相反,本地服务器上的梯度是在干扰模型上计算的。因此,融合证明更具挑战性,需要精确控制这种扰动。为了确保它,MCM还将模型压缩与存储机制相结合。该分析打开了新的门,例如纳入依赖工人的随机模型和部分参与。
translated by 谷歌翻译
We present a new family of subgradient methods that dynamically incorporate knowledge of the geometry of the data observed in earlier iterations to perform more informative gradient-based learning. Metaphorically, the adaptation allows us to find needles in haystacks in the form of very predictive but rarely seen features. Our paradigm stems from recent advances in stochastic optimization and online learning which employ proximal functions to control the gradient steps of the algorithm. We describe and analyze an apparatus for adaptively modifying the proximal function, which significantly simplifies setting a learning rate and results in regret guarantees that are provably as good as the best proximal function that can be chosen in hindsight. We give several efficient algorithms for empirical risk minimization problems with common and important regularization functions and domain constraints. We experimentally study our theoretical analysis and show that adaptive subgradient methods outperform state-of-the-art, yet non-adaptive, subgradient algorithms.
translated by 谷歌翻译
大规模凸孔concave minimax问题在许多应用中出现,包括游戏理论,强大的培训和生成对抗网络的培训。尽管它们的适用性广泛,但使用现有的随机最小值方法在大量数据的情况下,有效,有效地解决此类问题是具有挑战性的。我们研究了一类随机最小值方法,并开发了一种沟通效率的分布式随机外算法Localadaseg,其自适应学习速率适合在参数 - 服务器模型中求解凸Conconcove minimax问题。 Localadaseg具有三个主要功能:(i)定期沟通策略,可降低工人与服务器之间的通信成本; (ii)在本地计算并允许无调实现的自适应学习率; (iii)从理论上讲,在随机梯度的估计中,相对于主要差异项的几乎线性加速在平滑和非平滑凸凸环设置中都证明了。 Localadaseg用于解决随机双线游戏,并训练生成的对抗网络。我们将localadaseg与几个用于最小问题的现有优化者进行了比较,并通过在均质和异质环境中的几个实验来证明其功效。
translated by 谷歌翻译
我们介绍了一个框架 - Artemis-,以解决分布式或联合设置中的学习问题,并具有通信约束和设备部分参与。几位工人(随机抽样)使用中央服务器执行优化过程来汇总其计算。为了减轻通信成本,Artemis允许在两个方向上(从工人到服务器,相反)将发送的信息与内存机制相结合。它改进了仅考虑单向压缩(对服务器)的现有算法,或在压缩操作员上使用非常强大的假设,并且通常不考虑设备的部分参与。我们在非I.I.D中的随机梯度(仅在最佳点界定的噪声方差)提供了快速的收敛速率(线性最高到阈值)。设置,突出显示内存对单向和双向压缩的影响,分析Polyak-Ruppert平均。我们在分布中使用收敛性,以获得渐近方差的下限,该方差突出了实际的压缩极限。我们提出了两种方法,以解决设备部分参与的具有挑战性的案例,并提供实验结果以证明我们的分析有效性。
translated by 谷歌翻译