Elastic Gossip distributes neural network training using gossip-like protocols.
problem Distributing neural network training across heterogeneous environments.
method Pairwise-communication using Gossip-like protocols, building on Elastic Averaging SGD.
result Elastic Gossip performs better than Gossiping SGD in experiments, but hyper-parameter search may yield better configurations.
Novel gossip algorithms reduce communication in decentralized stochastic optimization with compressed updates.
problem Decentralized stochastic optimization with limited communication.
method Proposed CHOCO-SGD and CHOCO-GOSSIP algorithms for unbiased and biased compression, achieving linear convergence.
result Both algorithms outperform state-of-the-art, reducing communication by at least two orders of magnitude.
Asynchronous decentralized SGD with quantized and local updates converges in gossip model.
problem Scalable distributed machine learning challenges in decentralized optimization.
method Asynchronous decentralized SGD with quantization and local steps in gossip model.
result Decentralized optimization with quantization and local steps converges in asynchronous gossip model.
We address the issue of speeding up the training of convolutional networks. Here we study a distributed method adapted to stochastic gradient descent (SGD). The parallel optimization setup uses several threads, each applying individual gradient descents on a local variable. We propose a new way to share information bet…
Unified analysis for decentralized SGD across various topologies and updates.
problem Analysis of decentralized SGD methods with changing topologies and local updates.
method Unified convergence analysis covering local SGD updates and adaptive network topology.
result Universal convergence rates for smooth problems, interpolating between heterogeneous and iid-data settings.
Floating Gossip improves continuous machine learning in a decentralized manner.
problem Continuous learning in infrastructure-less environments.
method Mean field approach to analyze the impact of communication and computing in Floating Gossip.
result Floating Gossip can effectively incorporate large amounts of data into machine learning models.
Paper proposes robust gossip algorithms for mean and trimmed mean estimation.
problem Vulnerability of mean-based gossip algorithms to malicious nodes.
method Developed extsc{GoRank} for rank estimation and extsc{GoTrim} for trimmed mean estimation.
result Established convergence rates for rank and trimmed mean estimation.
The paper gives bounds for how long it takes for gossip protocols to spread information in networks.
problem Understanding the diffusion time in asynchronous gossip protocols.
method Provides non-asymptotic bounds for the number of messages needed for consensus in asynchronous gossip protocols.
result Explicit formula and approximation for the number of messages needed for consensus in different types of graphs.
AsylADMM improves gossip-based learning for non-smooth objectives.
problem Efficient and robust decentralized learning on edge devices.
method Asynchronous gossip algorithm for non-smooth optimization.
result AsylADMM converges faster on non-smooth problems.
New gossip algorithms improve robustness of rank-based statistics in decentralized systems.
problem Ensuring robustness in decentralized AI and edge intelligence systems, especially in the presence of corrupted or adversarial data.
method Developed asynchronous gossip algorithms for computing rank-based statistics.
result First convergence rate bound for asynchronous gossip-based rank estimation.
Multiple gossip steps improve decentralized optimization convergence.
problem Efficiently optimizing large-scale machine learning models with limited communication.
method Integrates multiple gossip steps between gradient descent iterations in compressed decentralized optimization.
result Convergence to within ε of the optimal value for smooth non-convex objectives.
SlowMo improves distributed SGD by periodically synchronizing and using momentum, leading to better accuracy.
problem Reducing communication overhead in distributed training while maintaining model accuracy.
method Periodically synchronizing workers and using momentum after multiple iterations of a base optimization algorithm.
result SlowMo consistently yields improvements in optimization and generalization performance relative to the base optimizer.
Gossip-based actor-learner architectures improve deep reinforcement learning efficiency and scalability.
problem Stabilizing and scaling deep reinforcement learning through multi-simulator training.
method Gossip-based communication among actor-learners in a peer-to-peer topology, reducing synchronization.
result Gossip-based architectures outperform A2C in terms of robustness and sample efficiency.
Continuized Nesterov acceleration accelerates stochastic gradient descent and gossip algorithms.
problem Improving the convergence rate of stochastic gradient descent and gossip algorithms.
method Introducing a continuized variant of Nesterov acceleration, which mixes variables continuously and takes gradient steps at random times.
result The continuized Nesterov acceleration achieves convergence rates similar to Nesterov's original acceleration but with random parameters.
Improves decentralized learning by teleporting active nodes for better convergence.
problem Decentralized learning's convergence rate degrades with large node numbers.
method Activates a subset of nodes, fetches parameters from previous active nodes, updates, and performs gossip averaging on a small topology.
result Teleportation completely alleviates convergence rate degradation with proper node activation.
GADGET SVM uses gossip-based distributed learning for scalable SVMs.
problem Scalability issues in traditional SVM algorithms for large datasets.
method Gossip-based distributed learning for the primal SVM formulation.
result Performance comparable to centralized and online SVM algorithms.
Decentralized ranking consensus via gossip for robust and scalable systems.
problem Achieving reliable and resilient consensus on collective rankings in a decentralized setting.
method Random gossip communication for decentralized computation of global rankings.
result Robust and scalable consensus on collective rankings achieved through decentralized, local interactions.
Algorithm reduces regret in multi-agent bandits through gossiping.
problem Minimizing cumulative regret in decentralized multi-agent bandits.
method Insert-Eliminate algorithm with gossip communication.
result Regret significantly reduced with minimal collaboration.
Consider a network of agents connected by communication links, where each agent holds a real value. The gossip problem consists in estimating the average of the values diffused in the network in a distributed manner. We develop a method solving the gossip problem that depends only on the spectral dimension of the netwo…
This paper proposes a gossip-based algorithm for distributed bilevel optimization over networks.
problem Distributed bilevel optimization over networks with limited communication.
method Gossip-based distributed bilevel learning algorithm.
result Achieves optimal sample complexities for general and strongly convex objectives.
We address the issue of speeding up the training of convolutional neural networks by studying a distributed method adapted to stochastic gradient descent. Our parallel optimization setup uses several threads, each applying individual gradient descents on a local variable. We propose a new way of sharing information bet…
SGP combines PushSum with stochastic gradient updates for robust distributed deep learning.
problem Synchronization issues in distributed deep learning.
method Stochastic Gradient Push (SGP) using PushSum for approximate distributed averaging.
result SGP converges to a stationary point at the same rate as SGD and achieves consensus.
Unified framework for Byzantine robust gossip algorithms with guaranteed performance.
problem Vulnerability of decentralized machine learning to misbehaving devices.
method Introduces F-RG framework and CS+ robust aggregation rule for Byzantine resilience.
result CS+-RG has near-optimal breakdown tolerance and outperforms existing methods.
A new decentralized federated learning approach tackles network capacity challenges.
problem Efficiently utilizing network capacities between nodes in federated learning.
method Proposes a segmented gossip approach for decentralized federated learning.
result Demonstrates significant reduction in training time compared to centralized federated learning.
Paper tightens lower bounds on decentralized training complexity.
problem Understanding and optimizing iteration complexity in decentralized training.
method Proved a tight lower bound on iteration complexity and proposed DeTAG algorithm.
result DeTAG achieves the theoretical lower bound with only a logarithmic gap.
GOAT learns multiple node representations from graph structure alone.
problem Context-free graph representation learning limits model performance.
method Inspired by gossip and mutual attention, GOAT learns multiple node representations.
result GOAT outperforms 12 SOTA baselines on link prediction and clustering tasks.
Efficient and robust algorithms for decentralized estimation in networks are essential to many distributed systems. Whereas distributed estimation of sample mean statistics has been the subject of a good deal of attention, computation of U-statistics, relying on more expensive averaging over pairs of observations, is…
In decentralized networks (of sensors, connected objects, etc.), there is an important need for efficient algorithms to optimize a global cost function, for instance to learn a global model from the local data collected by each computing unit. In this paper, we address the problem of decentralized minimization of pairw…
A new approach corrects bias in federated learning due to varying communication links.
problem Bias in federated learning due to non-uniform and time-varying communication links.
method Proposes Federated Postponed Broadcast (FedPBC) to correct bias in Federated Average (FedAvg).
result FedPBC converges to a stationary point of the global objective, overcoming bias caused by varying communication links.
A novel algorithm reduces regret in multi-agent multi-armed bandits through gossip-based communication.
problem Minimizing average cumulative regret in a large number of agents solving the same MAB problem.
method A gossip-based protocol for decentralized decision-making and communication among agents.
result Achieves significant reduction in per-agent regret and communication complexity.
In this paper, we determine the optimal convergence rates for strongly convex and smooth distributed optimization in two settings: centralized and decentralized communications over a network. For centralized (i.e. master/slave) algorithms, we show that distributing Nesterov's accelerated gradient descent is optimal and…
Novel algorithm for decentralized optimization in time-varying networks with delays.
problem Decentralized optimization in networks with communication delays.
method DT-GO algorithm, applicable to general directed graphs, converges to same complexity as centralized SGD.
result Algorithm DT-GO achieves convergence rates for convex and non-convex objectives, similar to centralized SGD.
RelaySum improves decentralized deep learning by uniformly distributing data across workers.
problem Handling data heterogeneity in decentralized deep learning.
method RelaySum uses spanning trees to distribute information exactly uniformly across all workers with finite delays.
result RelaySum is independent of data heterogeneity and scales to many workers, enabling highly accurate decentralized deep learning.
This paper examines ADMM for network averaging, revealing its convergence rates and network topology impacts.
problem Efficiently averaging local information over a network using ADMM.
method Comparative analysis of ADMM and other algorithms on a canonical distributed averaging problem.
result Characterization of ADMM convergence and optimal parameter tuning based on network spectral properties.
Local SGD outperforms minibatch SGD for quadratic objectives.
problem Theoretical foundations of local SGD are lacking.
method Proved local SGD strictly dominates minibatch SGD for quadratic objectives and accelerated local SGD is minimax optimal.
result Local SGD does not dominate minibatch SGD in general convex objectives.
Minibatch SGD outperforms Local SGD in heterogeneous distributed learning.
problem Optimizing a combined convex objective with stochastic gradient estimates from different machines.
method Analysis of Minibatch SGD and Local SGD in a heterogeneous distributed setting.
result Minibatch SGD dominates Local SGD in the heterogeneous distributed setting.
Stochastic gradient descent is a simple approach to find the local minima of a cost function whose evaluations are corrupted by noise. In this paper, we develop a procedure extending stochastic gradient descent algorithms to the case where the function is defined on a Riemannian manifold. We prove that, as in the Eucli…
Stochastic gradient descent (SGD) is a popular stochastic optimization method in machine learning. Traditional parallel SGD algorithms, e.g., SimuParallel SGD, often require all nodes to have the same performance or to consume equal quantities of data. However, these requirements are difficult to satisfy when the paral…
SQuARM-SGD improves decentralized SGD efficiency with momentum.
problem Efficient decentralized training of large-scale models over networks.
method Fixed local SGD steps with Nesterov's momentum, sparsified and quantized updates, locally computed triggering criterion.
result Convergence rate matches vanilla SGD, momentum improves test performance.
STL-SGD accelerates Local SGD by gradually increasing communication periods.
problem Reducing communication complexity in distributed SGD.
method Gradually increasing communication periods while decreasing learning rate.
result Significant reduction in communication complexity with improved convergence rates.
Nesterov SGD doesn't accelerate over SGD in over-parameterized learning.
problem Theoretical and practical acceleration of SGD with momentum in over-parameterized learning.
method Introducing a compensation term to Nesterov SGD, resulting in MaSS algorithm.
result MaSS converges for same step sizes as SGD and achieves accelerated convergence rates over SGD.
Communication-efficient SGD algorithms, which allow nodes to perform local updates and periodically synchronize local models, are highly effective in improving the speed and scalability of distributed SGD. However, a rigorous convergence analysis and comparative study of different communication-reduction strategies rem…
Paper shows local SGD outperforms mini-batch SGD under certain conditions.
problem Proving local SGD's superiority in distributed learning with heterogeneous data.
method New lower and upper bounds for local SGD under first-order heterogeneity assumptions.
result Local SGD is min-max optimal under certain conditions, resolving understanding of distributed optimization.
LSGD improves deep learning training efficiency by synchronizing and decentralizing SGD.
problem Asynchronous SGD's accuracy issues and synchronous SGD's communication inefficiency.
method LSGD divides nodes into subgroups with centralized communication and decentralized computation.
result LSGD achieves better accuracy and efficiency than synchronous and asynchronous SGD.
Homogenized SGD explains SGD dynamics in high dimensions.
problem Understanding SGD dynamics in high-dimensional settings.
method Developed a homogenized SGD model to analyze high-dimensional SGD.
result Convergent high-dimensional SGD to homogenized SGD for quadratic statistics.
MindFlayer SGD improves parallel SGD for heterogeneous, random compute times.
problem Minimizing nonconvex functions with heterogeneous, random compute times.
method MindFlayer SGD, designed for stochastic and heterogeneous delays.
result MindFlayer SGD outperforms existing methods in environments with heavy-tailed noise.
Large batch training with DP-SGD reduces model performance due to implicit bias.
problem Large batch training with DP-SGD reduces model performance.
method The study analyzes the phenomenon of implicit bias in Noisy-SGD (DP-SGD without clipping) and its theoretical solutions for linear models.
result The implicit bias in large batch training with DP-SGD is amplified by additional noise, similar to SGD.
New proof shows D-SGD and SAM are equivalent, revealing advantages of decentralization.
problem The generalization benefits of decentralized learning.
method Proved D-SGD implicitly minimizes SAM's loss function.
result Decentralized SGD and Average-direction SAM are asymptotically equivalent.