检索结果-内蒙古大学图书馆

gradient coding With Dynamic Clustering for Straggler-Tolerant Distributed Learning

IEEE TRANSACTIONS ON COMMUNICATIONS 2023年第6期71卷 3317-3332页

作者： Buyukates, Baturalp Ozfatura, Emre Ulukus, Sennur Gunduz, Deniz Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Univ Southern Calif Dept Elect & Comp Engn Los Angeles CA 90007 USA Imperial Coll London Dept Elect & Elect Engn London SW7 2BX England Univ Modena & Reggio Emilia Unimore Dept Engn Enzo Ferrari I-41121 Modena Italy

Distributed implementations are crucial in speeding up large scale machine learning applications. Distributed gradient descent (GD) is widely employed to parallelize the learning task by distributing the dataset across multiple workers. A significant performance bottleneck for the per-iteration completion time in distributed synchronous GD is straggling workers. Coded distributed computation techniques have been introduced recently to mitigate stragglers and to speed up GD iterations by assigning redundant computations to workers. In this paper, we introduce a novel paradigm of dynamic coded computation, which assigns redundant data to workers to acquire the flexibility to dynamically choose from among a set of possible codes depending on the past straggling behavior. In particular, we propose gradient coding (GC) with dynamic clustering, called GC-DC, and regulate the number of stragglers in each cluster by dynamically forming the clusters at each iteration. With time-correlated straggling behavior, GC-DC adapts to the straggling behavior over time;in particular, at each iteration, GC-DC aims at distributing the stragglers across clusters as uniformly as possible based on the past straggler behavior. For both homogeneous and heterogeneous worker models, we numerically show that GC-DC provides significant improvements in the average per-iteration completion time without an increase in the communication load compared to the original GC scheme.

关键词： Distributed coded computation gradient descent straggler mitigation gradient coding clustering

来源：评论

学校读者我要写书评

暂无评论

gradient coding in Decentralized Learning for Evading Stragglers 32

Gradient Coding in Decentralized Learning for Evading Stragg...

引用

32nd European Signal Processing Conference (EUSIPCO)

作者： Li, Chengxi Skoglund, Mikael KTH Royal Inst Technol Sch Elect Engn & Comp Sci Stockholm Sweden

ISBN: (纸本)9789464593617;9798331519773

In this paper, we consider a decentralized learning problem in the presence of stragglers. Although gradient coding techniques have been developed for distributed learning to evade stragglers, where the devices send encoded gradients with redundant training data, it is difficult to apply those techniques directly to decentralized learning scenarios. To deal with this problem, we propose a new gossip-based decentralized learning method with gradient coding (GOCO). In the proposed method, to avoid the negative impact of stragglers, the parameter vectors are updated locally using encoded gradients based on the framework of stochastic gradient coding and then averaged in a gossip-based manner. We analyze the convergence performance of GOCO for strongly convex loss functions. And we also provide simulation results to demonstrate the superiority of the proposed method in terms of learning performance compared with the baseline methods.

关键词： decentralized learning gradient coding stragglers

来源：评论

学校读者我要写书评

暂无评论

Design and Optimization of Hierarchical gradient coding for Distributed Learning at Edge Devices

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2024年第12期72卷 7727-7741页

作者： Tang, Weiheng Li, Jingyi Chen, Lin Chen, Xu Sun Yat Sen Univ Sch Comp Sci & Engn Guangzhou 510275 Peoples R China Sun Yat Sen Univ Sch Comp Sci & Engn Guangdong Prov Key Lab Informat Secur Technol Guangzhou 510275 Peoples R China

Edge computing has recently emerged as a promising paradigm to boost the performance of distributed learning by leveraging the distributed resources at edge nodes. Architecturally, the introduction of edge nodes adds an additional intermediate layer between the master and workers in the original distributed learning systems, potentially leading to more severe straggler effect. Recently, coding theory-based approaches have been proposed for stragglers mitigation in distributed learning, but the majority focus on the conventional workers-master architecture. In this paper, along a different line, we investigate the problem of mitigating the straggler effect in hierarchical distributed learning systems with an additional layer composed of edge nodes. Technically, we first derive the fundamental trade-off between the computational loads of workers and the stragglers tolerance. Then, we propose a hierarchical gradient coding framework, which provides better stragglers mitigation, to achieve the derived computational trade-off. To further improve the performance of our framework in heterogeneous scenarios, we formulate an optimization problem with the objective of minimizing the expected execution time for each iteration in the learning process. We develop an efficient algorithm to mathematically solve the problem by outputting the optimum strategy. Extensive simulation results demonstrate the superiority of our schemes compared with conventional solutions.

关键词： Encoding Distance learning Computer aided instruction Computational modeling Task analysis Optimization Computer architecture Distributed learning hierarchical architecture stragglers tolerance gradient coding

来源：评论

学校读者我要写书评

暂无评论

Decentralized Learning Based on gradient coding With Compressed Communication

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2024年 72卷 4713-4729页

作者： Li, Chengxi Skoglund, Mikael KTH Royal Inst Technol Sch Elect Engn & Comp Sci Div Informat Sci & Engn Stockholm Sweden

This paper considers the problem of decentralized learning (DEL) with stragglers under the communication bottleneck. In the literature, various gradient coding techniques have been proposed for distributed learning with stragglers by letting the devices transmit encoded gradients based on redundant training data. However, those techniques can not be directly applied to fully decentralized scenarios as considered in this paper due to the lack of a global model in DEL. To overcome this shortcoming, we first propose a new gossip-based DEL method with gradient coding (GOCO). In GOCO, to mitigate the negative impact of stragglers, the devices update the parameter vectors with encoded gradients based on stochastic gradient coding before averaging in a gossip-based manner. To further reduce the communication overhead associated with GOCO, we propose an enhanced version of GOCO, namely GOCO with compressed communication (2-GOCO), where the devices transmit compressed messages instead of the raw parameter vectors. The convergence of the proposed methods is analyzed for strongly convex loss functions. Simulation results demonstrate that the proposed methods outperform the baseline methods, which attain better learning performance under the same communication overhead.

关键词： Communication bottleneck compression decentralized learning gradient coding stragglers Communication bottleneck compression decentralized learning gradient coding stragglers

来源：评论

学校读者我要写书评

暂无评论

Byzantine-Resilient gradient coding Through Local gradient Computations

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2025年第4期71卷 3142-3156页

作者： Hofmeister, Christoph Massny, Luis Yaakobi, Eitan Bitar, Rawad Tech Univ Munich Sch Computat Informat & Technol D-80333 Munich Germany Technion Israel Inst Technol CS Dept IL-3200003 Haifa Israel

We consider gradient coding in the presence of an adversary controlling so-called malicious workers trying to corrupt the computations. Previous works propose the use of MDS codes to treat the responses from malicious workers as errors and correct them using the error-correction properties of the code. This comes at the expense of increasing the replication, i.e., the number of workers each partial gradient is computed by. In this work, we propose a way to reduce the replication to s +1 instead of 2s +1 in the presence of s malicious workers. Our method detects erroneous inputs from the malicious workers, transforming them into erasures. This comes at the expense of s additional local computations at the main node and additional rounds of light communication between the main node and the workers. We define a general framework and give fundamental limits for fractional repetition data allocations. Our scheme is optimal in terms of replication and local computation and incurs a communication cost that is asymptotically, in the size of the dataset, a multiplicative factor away from the derived bound. We furthermore show how additional redundancy can be exploited to reduce the number of local computations and communication cost, or, alternatively, tolerate straggling workers.

关键词： Encoding Vectors Polynomials Redundancy Machine learning Games Costs Anomaly detection Training Optimization Byzantine errors gradient coding probabilistic error correction distributed gradient descent straggler mitigation

来源：评论

学校读者我要写书评

暂无评论

Optimization-Based Block Coordinate gradient coding for Mitigating Partial Stragglers in Distributed Learning

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2023年 71卷 1023-1038页

作者： Wang, Qi Cui, Ying Li, Chenglin Zou, Junni Xiong, Hongkai Shanghai Jiao Tong Univ Dept Elect Engn Shanghai 200240 Peoples R China Hong Kong Univ Sci & Technol Guangzhou IoT Thrust Guangzhou 511400 Peoples R China

gradient coding schemes effectively mitigate full stragglers in distributed learning by introducing identical redundancy in coded local partial derivatives corresponding to all model parameters. However, they are no longer effective for partial stragglers as they cannot utilize incomplete computation results from partial stragglers. This paper aims to design a new gradient coding scheme for mitigating partial stragglers in distributed learning. Specifically, we consider a distributed system consisting of one master and N workers, characterized by a general partial straggler model and focuses on solving a general large-scale machine learning problem with L model parameters using gradient coding. First, we propose a coordinate gradient coding scheme with L coding parameters representing L possibly different diversities for the L coordinates, which generates most gradient coding schemes. Then, we consider the minimization of the expected overall runtime and the maximization of the completion probability with respect to the L coding parameters for coordinates, which are challenging discrete optimization problems. To reduce computational complexity, we first transform each to an equivalent but much simpler discrete problem with N << L variables representing the partition of the L coordinates into N blocks, each with identical redundancy. This indicates an equivalent but more easily implemented block coordinate gradient coding scheme with N coding parameters for blocks. Then, we adopt continuous relaxation to further reduce computational complexity. For the resulting minimization of expected overall runtime, we develop an iterative algorithm of computational complexity O(N-2) to obtain an optimal solution and derive two closed-form approximate solutions both with computational complexity O(N). For the resultant maximization of the completion probability, we develop an iterative algorithm of computational complexity O(N-2) to obtain a stationary point and derive a closed-f

关键词： Big Data coded computation distributed learning gradient coding stochastic optimization

来源：评论

学校读者我要写书评

暂无评论

Tree gradient coding Considering Communication Delays and Partial Stragglers 59

Tree Gradient Coding Considering Communication Delays and Pa...

引用

59th Annual IEEE International Conference on Communications (IEEE ICC)

作者： Shah, Raj Tiwari, Utsav Thomas, Anoop Indian Inst Technol Bhubaneswar Sch Elect Sci Bhubaneswar India

ISBN: (纸本)9781728190549

There are two major problems while training large machine learning models using distributed gradient descent. The first is the problem of straggling workers, and the second is the communication delays in transmitting the computed gradient. In Tree gradient coding (TGC) architecture, the workers are arranged in a tree topology, and the data partitions are redundantly assigned to these workers, providing us resilience to straggling workers. In TGC the effect of the communication delays and the partial straggling behavior of the workers are not considered while distributing the computation load. In this paper, an expression for computation load in TGC considering the communication delays and the partial stragglers is derived. Moreover, the proposed technique is implemented on cloud-based VMs and experimental results are obtained. A speedup of up to 23.95% is observed compared to the traditional TGC scheme.

关键词： coding Theory Distributed gradient Descent gradient coding Tree gradient coding

来源：评论

学校读者我要写书评

暂无评论

Heterogeneity-Aware gradient coding for Tolerating and Leveraging Stragglers

引用

IEEE TRANSACTIONS ON COMPUTERS 2022年第4期71卷 779-794页

作者： Wang, Haozhao Guo, Song Tang, Bin Li, Ruixuan Yang, Yutong Qu, Zhihao Wang, Yi Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430074 Peoples R China Hong Kong Polytech Univ Dept Comp Hong Kong Peoples R China Hong Kong Polytech Univ Shenzhen Res Inst Shenzhen 518057 Peoples R China Hohai Univ Coll Comp & Informat Nanjing 211100 Peoples R China Peng Cheng Lab Shenzhen 518066 Peoples R China

Distributed gradient descent has been widely adopted in the machine learning field because considerable computing resources are available when facing the huge volume of data. Specifically, the gradient over the whole data is cooperatively computed by multiple workers. However, its performance can be severely affected by slow workers, namely stragglers. Recently, coding-based approaches have been introduced to mitigate the straggler problem, but they could hardly deal with the heterogeneity among workers. Besides, they always discard the results of stragglers causing huge resource waste. In this article, we first investigate how to tolerate stragglers by discarding their results and then seek to leverage the stragglers. For tolerating stragglers, we propose a heterogeneity-aware coding scheme that encodes gradients adaptive to the computing capability of workers. Theoretically, this scheme is optimal for stragglers tolerance. Relying on the scheme, we further propose an algorithm called DHeter-aware to exploit the gradients of stragglers which we called delayed gradients. Moreover, theoretical results characterized for DHeter-aware exhibits the same convergence rate as the gradient descent without delayed gradients. Experiments on various tasks and clusters demonstrate that our coding scheme outperforms all the state-of-the-art methods and the DHeter-aware further accelerates the coding scheme by achieving 25 percent time savings.

关键词： Encoding Task analysis Clustering algorithms Partitioning algorithms Machine learning Training Convergence Distributed architecture distributed systems gradient coding

来源：评论

学校读者我要写书评

暂无评论

Adaptive gradient coding

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2022年第2期30卷 717-734页

作者： Cao, Hankun Yan, Qifa Tang, Xiaohu Han, Guojun Southwest Jiaotong Univ Informat Secur & Natl Comp Grid Lab Chengdu 611756 Peoples R China Guangdong Univ Technol Sch Informat Engn Guangzhou 510006 Peoples R China

This paper focuses on mitigating the impact of stragglers in distributed learning system. Unlike the existing results designated for a fixed number of stragglers, we develop a new scheme called Adaptive gradient coding (AGC) with flexible communication cost for varying number of stragglers. Our scheme gives an optimal tradeoff between computation load, straggler tolerance and communication cost by allowing workers to send multiple signals sequentially to the master. In particular, it can minimize the communication cost according to the unknown real-time number of stragglers in practical environments. In addition, we present a Group AGC (G-AGC) by combining the group idea with AGC to resist more stragglers in some situations. The numerical and simulation results demonstrate that our adaptive schemes can achieve the smallest average running time.

关键词： Encoding Costs Codes Real-time systems Task analysis Optimization Adaptive systems gradient coding straggler adaptive distributed computing

来源：评论

学校读者我要写书评

暂无评论

Communication Optimization in Heterogeneous Edge Networks Using Dynamic Grouping and gradient coding 17th

Communication Optimization in Heterogeneous Edge Networks Us...

引用

17th International Conference on Wireless Algorithms, Systems, and Applications (WASA)

作者： Mao, Yingchi Wu, Jun He, Xiaoming Ping, Ping Huang, Jianxin Hohai Univ Minist Water Resources Key Lab Water Big Data Technol Nanjing 211100 Peoples R China Hohai Univ Sch Comp & Informat Nanjing 211100 Peoples R China Res & Dev Dept Suma Technol Co Ltd Suzhou Peoples R China

ISBN: (纸本)9783031192104;9783031192111

Communication load in heterogeneous edge networks is becoming heavier because of excessive computation and delay caused by straggler dropout, leading to high electricity cost and serious greenhouse gas emissions. To create a green edge environment, we focus on mitigating computation and straggler dropout to improve the communication efficiency during the distributed training. Therefore, we propose a novel scheme named Dynamic Grouping and Heterogeneity-aware gradient coding (DGHGC) to speed up average iteration time. The average iteration time is used as a metric reflecting the effect of mitigating computation and straggler dropout. Specifically, DGHGC firstly uses the static grouping to evenly distribute stragglers in each group. After the static grouping, considering the nonuniform distribution of nodes due to straggler dropout during the training process, a dynamic grouping depending on dropout frequency of stragglers is employed. The dynamic grouping tolerates more stragglers by examining the dropout threshold to improve the rationality of the static grouping for stragglers. In addition, DGHGC applies a heterogeneity-aware gradient coding to allocate reasonable data to stragglers based on their computing capacity and encode gradients to prevent stragglers from dropping out. Numerical results demonstrate that the average iteration time of DGHGC can be reduced largely compared to the state-of-art benchmark schemes.

关键词： Heterogeneous edge networks Communication efficiency Dynamic grouping gradient coding

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：