Distributed implementations of gradient-based methods, wherein a server distributes gradient computations across worker machines, suffer from slow running machines, called 'stragglers'. Gradient coding is a coding-theoretic framework to mitigate stragglers by enabling the server to recover the gradient sum in the prese…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “straggler mitigation”
Gradient codes adapt to varying straggler counts in distributed learning.
problem Mitigating slow worker nodes (stragglers) in distributed machine learning.
method Proposes a flexible gradient coding scheme that concatenates codes for different straggler tolerances, adapting to actual straggler counts.
result Significantly lower latency compared to fixed-tolerance gradient codes.
Gradient Codingstat.ML
We propose a novel coding theoretic framework for mitigating stragglers in distributed learning. We show how carefully replicating data blocks and coding across gradients can provide tolerance to failures and stragglers for Synchronous Gradient Descent. We implement our schemes in python (using MPI) to run on Amazon EC…
A new framework for federated learning tackles challenges with horizontally partitioned labels and stragglers.
problem Challenges with horizontally partitioned labels and stragglers in federated learning.
method Proposes a novel vertical federated learning framework named Cascade Vertical Federated Learning (CVFL) to fully utilize all horizontally partitioned labels and mitigate stragglers.
result Demonstrates comparable performance to centralized training and mitigates stragglers.
Slow running or straggler tasks can significantly reduce computation speed in distributed computation. Recently, coding-theory-inspired approaches have been applied to mitigate the effect of straggling, through embedding redundancy in certain linear computational steps of the optimization algorithm, thus completing the…
Distributed algorithms are often beset by the straggler effect, where the slowest compute nodes in the system dictate the overall running time. Coding-theoretic techniques have been recently proposed to mitigate stragglers via algorithmic redundancy. Prior work in coded computation and gradient coding has mainly focuse…
Gradient descent and its many variants, including mini-batch stochastic gradient descent, form the algorithmic foundation of modern large-scale machine learning. Due to the size and scale of modern data, gradient computations are often distributed across multiple compute nodes. Unfortunately, such distributed implement…
Anytime MiniBatch speeds up online distributed optimization by handling slow nodes.
problem Mitigating the impact of slow nodes (stragglers) in distributed optimization.
method Proposes an online distributed optimization method that averages minibatch gradients via consensus rounds.
result Prevents stragglers from slowing progress without wasting work.
Dealing with the shear size and complexity of today's massive data sets requires computational platforms that can analyze data in a parallelized and distributed fashion. A major bottleneck that arises in such modern distributed computing environments is that some of the worker nodes may run slow. These nodes a.k.a.~str…
This paper considers the problem of implementing large-scale gradient descent algorithms in a distributed computing setting in the presence of {\em straggling} processors. To mitigate the effect of the stragglers, it has been previously proposed to encode the data with an erasure-correcting code and decode at the maste…
Improves distributed SGD convergence speed with reduced computation load.
problem Mitigating stragglers in distributed SGD to speed up convergence.
method Modeling communication and computation times, adapting number of workers and computation load dynamically.
result Significantly reduces computation load while improving convergence speed.
Overlap-Local-SGD improves distributed SGD by overlapping communication and computation.
problem High communication delay and node slowdown in distributed SGD.
method Adding an anchor model to synchronize local updates and pull them towards the anchor model.
result Overlap-Local-SGD speeds up distributed training and mitigates straggler effects.
Performance of distributed optimization and learning systems is bottlenecked by "straggler" nodes and slow communication links, which significantly delay computation. We propose a distributed optimization framework where the dataset is "encoded" to have an over-complete representation with built-in redundancy, and the …
This work improves federated learning privacy and accuracy with non-private data sharing and approximate gradient coding.
problem Challenges of non-IID data and stragglers in federated learning.
method Data-driven strategy combining offline data sharing and approximate gradient coding.
result Achieves a trade-off between privacy and utility, leading to improved model convergence and accuracy.
A new algorithm reduces training time for distributed machine learning by dynamically assigning backup workers.
problem Time-consuming synchronization phase due to slow workers (stragglers).
method Dynamic allocation of backup workers to minimize waiting time.
result Achieves linear speedup in convergence performance with more workers.
Secure aggregation for buffered asynchronous federated learning without TEEs.
problem Privacy and convergence in buffered asynchronous federated learning.
method Developed a new protocol (BASecAgg) that ensures privacy without TEEs by carefully designing masks.
result BASecAgg achieves similar convergence guarantees as FedBuff without TEEs.
Gradient coding is a technique for straggler mitigation in distributed learning. In this paper we design novel gradient codes using tools from classical coding theory, namely, cyclic MDS codes, which compare favorably with existing solutions, both in the applicable range of parameters and in the complexity of the invol…
In this paper, we focus on approaches to parallelizing stochastic gradient descent (SGD) wherein data is farmed out to a set of workers, the results of which, after a number of updates, are then combined at a central master node. Although such synchronized SGD approaches parallelize well in idealized computing environm…
We focus on the commonly used synchronous Gradient Descent paradigm for large-scale distributed learning, for which there has been a growing interest to develop efficient and robust gradient aggregation strategies that overcome two key system bottlenecks: communication bandwidth and stragglers' delays. In particular, R…
Coded Federated Learning speeds up model convergence by preemptively computing on parity data.
problem Federated learning's convergence is slow on heterogeneous platforms due to stragglers.
method Develops CFL scheme where clients generate parity data and share it once, allowing the server to compute redundantly.
result CFL allows global model to converge nearly four times faster than uncoded federated learning.
Distributed Stochastic Gradient Descent (SGD) when run in a synchronous manner, suffers from delays in waiting for the slowest learners (stragglers). Asynchronous methods can alleviate stragglers, but cause gradient staleness that can adversely affect convergence. In this work we present a novel theoretical characteriz…
Cloud computing is becoming increasingly popular as a platform for distributed training of deep neural networks. Synchronous stochastic gradient descent (SSGD) suffers from substantial slowdowns due to stragglers if the environment is non-dedicated, as is common in cloud computing. Asynchronous SGD (ASGD) methods are i…
A new federated learning method speeds up training by selecting faster nodes first.
problem System heterogeneity and stragglers slow down federated learning.
method Adaptive selection of nodes based on data statistical characteristics.
result Significant speedup in wall-clock time compared to standard federated learning.
Recently, reducing communication time between machines becomes the main focus of distributed data mining. Previous methods propose to make workers do more computation locally before aggregating local solutions in the server such that fewer communication rounds between server and workers are required. However, these met…
New gradient coding schemes reduce decoding error in both random and adversarial straggler settings.
problem Creating efficient approximate gradient coding schemes for distributed optimization.
method Introduced novel approximate gradient codes based on expander graphs, achieving optimal decoding coefficients.
result Achieved nearly optimal error in random setting and nearly half the error in adversarial setting compared to existing codes.
Asynchronous SGD can speed up training with a trade-off of gradient staleness.
problem Asynchronous SGD suffers from gradient staleness, affecting convergence error.
method Theoretical analysis of the error-runtime trade-off considering random straggling delays.
result A method of gradually varying synchronicity in distributed SGD is proposed and demonstrated.
CodedFedL speeds up federated learning in MEC networks by 15x.
problem Slow convergence in federated learning due to heterogeneity and stochastic fluctuations.
method Injects structured coding redundancy into federated learning to mitigate stragglers and speed up training.
result CodedFedL speeds up the training procedure by up to 15x compared to benchmark schemes.
Adaptive Distributed Stochastic Gradient Descent for Minimizing Delay in the Presence of Stragglerscs.LG
Adaptive distributed SGD reduces delay in slow workers.
problem Minimizing delay in distributed SGD with stragglers.
method Adaptive policy for varying to optimize error-runtime trade-off.
result Numerical simulations confirm the effectiveness of the adaptive approach.
This paper develops coding techniques to reduce the running time of distributed learning tasks. It characterizes the fundamental tradeoff to compute gradients (and more generally vector summations) in terms of three parameters: computation load, straggler tolerance and communication cost. It further gives an explicit c…
New asynchronous algorithms improve speed in decentralized optimization networks.
problem Hard convergence analysis for asynchronous decentralized optimization.
method Continuized framework to analyze heterogeneous delays in event-driven updates.
result Achieves asynchronous speedup with convergence rate controlled by eigengap weighted by local delays.
DASA speeds up SA with delayed agents, achieving N-fold speedup.
problem Speeding up Stochastic Approximation with asynchronous delays.
method DASA: Delay-Adaptive Multi-Agent Stochastic Approximation algorithm.
result First algorithm with convergence rate dependent on mixing time and average delay.
Triadic-OCD detects changes in data streams robustly and optimally, even in asynchronous settings.
problem Online change detection in data streams with practical constraints.
method Triadic-OCD framework for asynchronous online change detection with provable robustness, optimality, and convergence.
result The proposed triadic-OCD algorithm achieves optimal performance and convergence in asynchronous settings.
Coded Federated Learning speeds up training in edge computing networks.
problem Slow convergence in Federated Learning due to heterogeneity and stochastic fluctuations.
method Exploiting statistical properties of compute and communication delays, distributed kernel embedding, and random Fourier features.
result Significant performance gains for CodedFedL in distributed non-linear regression and classification problems.
Paper proposes new gradient codes for robust distributed machine learning.
problem Robustness against slow machines (stragglers) in distributed machine learning.
method Constructs gradient codes based on probabilistic and Kronecker product methods.
result Gradient codes exist for a wide range of system parameters with comparable error performance.
Unified approach to federated learning improves robustness and personalization.
problem Real-world federated learning challenges like non-IID data and outliers.
method Fed+ methods that unify federated learning algorithms for better robustness and personalization.
result Convergence guarantees for Fed+ on convex and non-convex loss functions under various aggregation methods.
Federated Learning (FL) enables learning a shared model across many clients without violating the privacy requirements. One of the key attributes in FL is the heterogeneity that exists in both resource and data due to the differences in computation and communication capacity, as well as the quantity and content of data…
Freya PAGE optimizes nonconvex optimization with heterogeneous, asynchronous workers.
problem Optimizing nonconvex finite-sum problems with varying worker processing times.
method Freya PAGE, a parallel method robust to stragglers and adaptive to slow computations.
result Freya PAGE offers improved time complexity guarantees compared to previous methods.
A new method for efficient online federated learning reduces communication overhead.
problem Real-world limitations in online federated learning, such as heterogeneous client participation and communication delays.
method Proposes a communication-efficient asynchronous online federated learning (PAO-Fed) strategy.
result Achieves the same convergence properties as online federated stochastic gradient while reducing communication overhead by 98 percent.
Federated learning poses new statistical and systems challenges in training machine learning models over distributed networks of devices. In this work, we show that multi-task learning is naturally suited to handle the statistical challenges of this setting, and propose a novel systems-aware optimization method, MOCHA,…
We develop parallel and distributed Frank-Wolfe algorithms; the former on shared memory machines with mini-batching, and the latter in a delayed update framework. Whenever possible, we perform computations asynchronously, which helps attain speedups on multicore machines as well as in distributed environments. Moreover…
Distributed data-parallel algorithms aim to accelerate the training of deep neural networks by parallelizing the computation of large mini-batch gradient updates across multiple nodes. Approaches that synchronize nodes using exact distributed averaging (e.g., via AllReduce) are sensitive to stragglers and communication…
Training the deep convolutional neural network for computer vision problems is slow and inefficient, especially when it is large and distributed across multiple devices. The inefficiency is caused by the backpropagation algorithm's forward locking, backward locking, and update locking problems. Existing solutions for a…
Mobile edge learning is an emerging technique that enables distributed edge devices to collaborate in training shared machine learning models by exploiting their local data samples and communication and computation resources. To deal with the straggler dilemma issue faced in this technique, this paper proposes a new de…
Matrix multiplication is a fundamental building block for large scale computations arising in various applications, including machine learning. There has been significant recent interest in using coding to speed up distributed matrix multiplication, that are robust to stragglers (i.e., machines that may perform slower …
UBM transfers bias mitigation from upstream to downstream tasks efficiently.
problem Bias in fine-tuned language models across various tasks.
method Apply bias mitigation to an upstream model, then fine-tune a downstream model on this mitigated model.
result UBM effects transfer to new downstream tasks, creating less biased models.
The bulk synchronous parallel (BSP) is a celebrated synchronization model for general-purpose parallel computing that has successfully been employed for distributed training of machine learning models. A prevalent shortcoming of the BSP is that it requires workers to wait for the straggler at every iteration. To amelio…
This paper examines fairness and arbitrariness in bias mitigation methods.
problem Understanding how different bias mitigation strategies affect individual predictions and whether they introduce arbitrariness.
method FRAME framework to evaluate bias mitigation through five dimensions: Impact Size, Change Direction, Decision Rates, Affected Subpopulations, and Neglected Subpopulations.
result Significant differences in the behaviors of debiasing methods were exhibited, highlighting the limitations of current fairness criteria and the inherent arbitrariness in the debiasing process.
Study evaluates fairness of machine learning models on Kaggle and finds some optimization techniques can induce unfairness.
problem Ensuring fairness of machine learning models used in important decisions.
method Empirical evaluation of 40 top-rated models from Kaggle on 5 tasks, applying 7 mitigation techniques.
result Some model optimization techniques induce unfairness; mitigation in pre-processing is preferred.