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.
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.
Moniqua improves SGD convergence with quantized communication.
problem Efficiently communicating in decentralized SGD with limited bandwidth.
method Modulo quantized communication in decentralized SGD.
result Moniqua converges at the same rate as full-precision communication with less bits.
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.
The paper provides Gaussian approximations for decentralized Federated Learning.
problem Lack of asymptotic statistical guarantees for local SGD in Federated Learning.
method Two generalized Gaussian approximation results for local SGD trajectories.
result Valid multiplier bootstrap procedures and Gaussian bootstrap-based tests for detecting adversarial attacks.
Recently, the technique of local updates is a powerful tool in centralized settings to improve communication efficiency via periodical communication. For decentralized settings, it is still unclear how to efficiently combine local updates and decentralized communication. In this work, we propose an algorithm named as L…
DE-SGD shows heavy-tailed behavior in decentralized settings.
problem Heavy-tailed behavior in decentralized SGD.
method Analyzes the emergence of heavy-tails in DE-SGD, considering both quadratic and twice continuously differentiable strongly convex loss functions.
result DE-SGD exhibits heavier tails than centralized SGD, and tail behavior depends on network parameters.
The paper analyzes stability and generalization of decentralized SGD.
problem Stability and generalization of decentralized stochastic gradient descent.
method Novel formulation of decentralized stochastic gradient descent combined with non/convex optimization theory.
result First stability and generalization guarantees for decentralized stochastic gradient descent.
Novel periodic momentum SGD method for decentralized training with linear speedup.
problem Lack of effective momentum schema in decentralized training methods.
method Proposes a novel periodic decentralized momentum SGD method.
result Achieves linear speedup in decentralized training.
New analysis shows D-SGD can generalize well regardless of graph connectivity.
problem Improving generalization of D-SGD in decentralized settings.
method Algorithmic stability analysis and optimization-dependent generalization bounds.
result D-SGD can achieve generalization bounds similar to classical SGD, independent of graph connectivity.
Single global merging boosts decentralized learning performance.
problem Limited communication in decentralized learning hinders performance.
method Scheduled communication, focusing on final step with global merging.
result Single global merging improves global test performance.
Paper analyzes D-SGD convergence with heterogeneous data and proposes topology learning.
problem Efficiently dealing with data heterogeneity in decentralized learning.
method Revisits D-SGD analysis, introduces neighborhood heterogeneity, and proposes topology learning.
result Formulates topology learning as a tractable optimization problem and demonstrates its effectiveness.
Enhances parallelism in decentralized learning for larger networks.
problem Scalability limitations in decentralized learning with increasing number of machines.
method Proposes Decentralized Anytime SGD, a novel algorithm that extends parallelism threshold.
result Establishes a theoretical upper bound on parallelism surpassing current state-of-the-art.
Stochastic Gradient Descent (SGD) is the most popular algorithm for training deep neural networks (DNNs). As larger networks and datasets cause longer training times, training on distributed systems is common and distributed SGD variants, mainly asynchronous and synchronous SGD, are widely used. Asynchronous SGD is com…
The paper proves D-SGD's stability and generalization bound, highlighting the importance of communication topology.
problem The stability and generalization of decentralized stochastic gradient descent (D-SGD).
method Theoretical analysis of D-SGD's stability and generalization bound, considering spectral gap and communication topology.
result D-SGD's generalization bound is positively correlated with the spectral gap of the communication topology.
Most commonly used distributed machine learning systems are either synchronous or centralized asynchronous. Synchronous algorithms like AllReduce-SGD perform poorly in a heterogeneous environment, while asynchronous algorithms using a parameter server suffer from 1) communication bottleneck at parameter servers when wo…
In this paper, we propose and analyze SPARQ-SGD, which is an event-triggered and compressed algorithm for decentralized training of large-scale machine learning models. Each node can locally compute a condition (event) which triggers a communication where quantized and sparsified local model parameters are sent. In SPA…
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.
Decentralized optimization is emerging as a viable alternative for scalable distributed machine learning, but also introduces new challenges in terms of synchronization costs. To this end, several communication-reduction techniques, such as non-blocking communication, quantization, and local steps, have been explored i…
This paper studies the problem of error-runtime trade-off, typically encountered in decentralized training based on stochastic gradient descent (SGD) using a given network. While a denser (sparser) network topology results in faster (slower) error convergence in terms of iterations, it incurs more (less) communication …
Improved SGD bounds for machine learning models with Markovian noise.
problem Uniform high-probability bounds for SGD under PL condition with Markovian noise.
method Combining Poisson equation for Markovian noise and probabilistic induction for almost-sure bounds.
result Matching 1/k decay rate for expected suboptimality. A(DP)2SGD improves federated learning privacy and efficiency.
problem Privacy and efficiency in federated learning with asynchronous decentralized parallel SGD.
method Differentially private asynchronous decentralized parallel SGD (A(DP)2SGD) using R{é}nyi differential privacy. result Achieves optimal convergence rate and comparable model accuracy to SSGD but faster.
This paper accelerates D-PSGD and AD-PSGD for large-scale deep learning tasks.
problem Decreasing spectral gap with increasing number of learners hampers convergence in D-PSGD and AD-PSGD.
method Improves spectral gap while minimizing communication cost through new techniques.
result Demonstrates faster training times and lower error rates on large-scale tasks.
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…
Decor protects decentralized learning models from curious users.
problem Privacy violation in decentralized learning.
method Decor uses correlated Gaussian noises to protect local models in decentralized SGD with differential privacy guarantees.
result Decor matches central DP optimal privacy-utility trade-off for arbitrary connected graphs.
While machine learning has achieved remarkable results in a wide variety of domains, the training of models often requires large datasets that may need to be collected from different individuals. As sensitive information may be contained in the individual's dataset, sharing training data may lead to severe privacy conc…
New method amplifies privacy in decentralized learning without centralized communication.
problem Privacy amplification in decentralized federated learning.
method Random check-in protocol for DP-SGD in FL.
result Privacy/accuracy trade-offs similar to subsampling/shuffling, but without server-initiated communication.
Improved convergence analysis for decentralized non-convex optimization.
problem Minimizing a sum of smooth non-convex functions over a network.
method Gradient tracking in decentralized stochastic gradient descent (GT-DSGD).
result GT-DSGD achieves network-independent performances matching centralized SGD under certain conditions.
This work bounds the run-time of nonconvex optimization with early stopping.
problem Bounding the expected run-time of nonconvex optimization with early stopping.
method Derives conditions for well-defined early stopping based on validation function norms and bounds the expected number of iterations and gradient evaluations.
result Guarantees the validity of early stopping and provides bounds on the expected run-time for various optimization algorithms.
DSGD with OAC-MAC scheme achieves better convergence in noisy wireless networks.
problem Performance of decentralized SGD in noisy wireless environments.
method Proposed OAC-MAC scheme for over-the-air computation in DSGD.
result OAC-MAC scheme converges faster with fewer communication rounds.
UD-SGD analysis shows efficient sampling by a few agents can outperform others.
problem Analyzing convergence speed and sampling strategies in UD-SGD.
method Asymptotic analysis of UD-SGD with various communication patterns and sampling strategies.
result Efficient sampling by a few agents can lead to better overall convergence.
Data parallelism has become the de facto standard for training Deep Neural Network on multiple processing units. In this work we propose DC-S3GD, a decentralized (without Parameter Server) stale-synchronous version of the Delay-Compensated Asynchronous Stochastic Gradient Descent (DC-ASGD) algorithm. In our approach, w…
This paper analyzes Local SGD for federated learning, achieving both statistical and communication efficiency.
problem Statistical estimation and inference in federated learning with decentralized data.
method Local SGD, a multi-round estimation procedure using intermittent communication.
result Local SGD achieves both statistical efficiency and communication efficiency.
A new topology improves decentralized learning efficiency and accuracy.
problem Finding efficient decentralized learning topologies with fast consensus and low maximum degree.
method Proposed the Base-(k+1) Graph topology for decentralized learning. result The Base-(k+1) Graph enables faster convergence and better communication efficiency than the exponential graph. There is significant recent interest to parallelize deep learning algorithms in order to handle the enormous growth in data and model sizes. While most advances focus on model parallelization and engaging multiple computing agents via using a central parameter server, aspect of data parallelization along with decentral…
Adaptive step-size method improves compressed SGD performance in machine learning.
problem Communication bottleneck in distributed and decentralized optimization.
method Developed an adaptive step-size method for compressed SGD.
result Order-optimal convergence rates for various objective functions.
Decentralized training of deep learning models is a key element for enabling data privacy and on-device learning over networks, as well as for efficient scaling to large compute clusters. As current approaches suffer from limited bandwidth of the network, we propose the use of communication compression in the decentral…
This paper studies a decentralized stochastic gradient tracking (DSGT) algorithm for non-convex empirical risk minimization problems over a peer-to-peer network of nodes, which is in sharp contrast to the existing DSGT only for convex problems. To ensure exact convergence and handle the variance among decentralized dat…
Unified framework for stability and generalization of Push-Sum in decentralized learning over directed graphs.
problem Understanding stability and generalization of Push-Sum in decentralized learning over directed networks.
method Developed a unified uniform-stability framework for SGP algorithm, incorporating imbalance-aware consistency bounds.
result Established finite-iteration stability and optimization guarantees for convex and non-convex objectives.
We consider decentralized stochastic optimization with the objective function (e.g. data samples for machine learning task) being distributed over n machines that can only communicate to their neighbors on a fixed communication graph. To reduce the communication bottleneck, the nodes compress (e.g. quantize or sparsi…
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…
Distributed training of deep nets is an important technique to address some of the present day computing challenges like memory consumption and computational demands. Classical distributed approaches, synchronous or asynchronous, are based on the parameter server architecture, i.e., worker nodes compute gradients which…
The paper proposes a fair and private decentralized deep learning framework.
problem Ensuring fairness and privacy in collaborative deep learning.
method A reputation system and differential privacy are used. FDPDDL framework is built with two stages: initialisation and update.
result FDPDDL achieves high fairness, comparable accuracy to centralised and distributed frameworks, and better accuracy than standalone.
This study compares decentralized banks and finds some lack decentralization.
problem Decentralized banks do not fully decentralize transactions as expected.
method Network analysis of transaction data from four banks using core-periphery features.
result MakerDao and Compound are more decentralized than Aave and Liquity.
Distributed optimization is essential for training large models on large datasets. Multiple approaches have been proposed to reduce the communication overhead in distributed training, such as synchronizing only after performing multiple local SGD steps, and decentralized methods (e.g., using gossip algorithms) to decou…
Systematizes blockchain decentralization taxonomy and metrics.
problem Lack of a unified definition for blockchain decentralization.
method Formulated a taxonomy of five facets and developed metrics.
result Provided comprehensive insights into blockchain decentralization.
Study finds Aave token network has core-periphery structure, with high decentralization predicting better returns.
problem Understanding the actual decentralization in DeFi token transactions on the Ethereum blockchain.
method Applied social network analysis to measure decentralization in Aave token transactions.
result A more decentralized Aave token network predicts higher returns and lower volatility.
MakerDAO's governance is centralized despite its decentralized claim.
problem Decentralization illusion in Decentralized Finance (DeFi) governance.
method Empirical analysis using financial, transaction, network, and sentiment indicators.
result Centralized governance impacts Maker protocol and voting power distribution.