Decentralized gradient methods: does topology matter?

• URL: http://arxiv.org/abs/2002.12688v1
• Date: Fri, 28 Feb 2020 12:59:25 GMT
• Title: Decentralized gradient methods: does topology matter?
• Authors: Giovanni Neglia and Chuan Xu and Don Towsley and Gianmarco Calbi
• Abstract summary: This paper shows how each worker maintains a local estimate of the optimal parameter vector and iteratively updates it by averaging the estimates obtained from its neighbors, and applying a correction on the basis of its local dataset. While theoretical results suggest that worker communication topology should have strong impact on the number of epochs needed to converge, previous experiments have shown the opposite conclusion. This paper sheds lights on this apparent contradiction and show how sparse topologies can lead to faster convergence even in the absence of communication delays.
• Score: 23.1803761184887
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consensus-based distributed optimization methods have recently been advocated as alternatives to parameter server and ring all-reduce paradigms for large scale training of machine learning models. In this case, each worker maintains a local estimate of the optimal parameter vector and iteratively updates it by averaging the estimates obtained from its neighbors, and applying a correction on the basis of its local dataset. While theoretical results suggest that worker communication topology should have strong impact on the number of epochs needed to converge, previous experiments have shown the opposite conclusion. This paper sheds lights on this apparent contradiction and show how sparse topologies can lead to faster convergence even in the absence of communication delays.

Related papers

• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture. Non-smooth regularization is often incorporated into machine learning tasks. We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Federated Learning as Variational Inference: A Scalable Expectation Propagation Approach [66.9033666087719]
  This paper extends the inference view and describes a variational inference formulation of federated learning. We apply FedEP on standard federated learning benchmarks and find that it outperforms strong baselines in terms of both convergence speed and accuracy.
  arXiv  Detail & Related papers  (2023-02-08T17:58:11Z)
• Straggler-Resilient Distributed Machine Learning with Dynamic Backup Workers [9.919012793724628]
  We propose a fully distributed algorithm to determine the number of backup workers for each worker. Our algorithm achieves a linear speedup for convergence (i.e., convergence performance increases linearly with respect to the number of workers)
  arXiv  Detail & Related papers  (2021-02-11T21:39:53Z)
• Numerical Comparison of Neighbourhood Topologies in Particle Swarm Optimization [0.0]
  This paper offers a comparison of the performances exhibited by five different neighbourhood topologies combined with four different coefficients' settings. Despite the optimum topology being problem-dependent, it appears that dynamic neighbourhoods with the number of interconnections should be preferred.
  arXiv  Detail & Related papers  (2021-01-25T09:23:55Z)
• Decentralized Deep Learning using Momentum-Accelerated Consensus [15.333413663982874]
  We consider the problem of decentralized deep learning where multiple agents collaborate to learn from a distributed dataset. We propose and analyze a novel decentralized deep learning algorithm where the agents interact over a fixed communication topology. Our algorithm is based on the heavy-ball acceleration method used in gradient-based protocol.
  arXiv  Detail & Related papers  (2020-10-21T17:39:52Z)
• A Partial Regularization Method for Network Compression [0.0]
  We propose an approach of partial regularization rather than the original form of penalizing all parameters, which is said to be full regularization, to conduct model compression at a higher speed. Experimental results show that as we expected, the computational complexity is reduced by observing less running time in almost all situations. Surprisingly, it helps to improve some important metrics such as regression fitting results and classification accuracy in both training and test phases on multiple datasets.
  arXiv  Detail & Related papers  (2020-09-03T00:38:27Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  Local features provide region-to-region rather than point-to-point correspondences. We propose guidelines for effective use of region-to-region matches in the course of a full model estimation pipeline. Experiments show that affine solvers can achieve accuracy comparable to point-based solvers at faster run-times.
  arXiv  Detail & Related papers  (2020-07-20T12:07:48Z)
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization [93.78811018928583]
  This paper provides a framework to analyze the convergence of federated heterogeneous optimization algorithms. We propose FedNova, a normalized averaging method that eliminates objective inconsistency while preserving fast error convergence.
  arXiv  Detail & Related papers  (2020-07-15T05:01:23Z)
• PushNet: Efficient and Adaptive Neural Message Passing [1.9121961872220468]
  Message passing neural networks have recently evolved into a state-of-the-art approach to representation learning on graphs. Existing methods perform synchronous message passing along all edges in multiple subsequent rounds. We consider a novel asynchronous message passing approach where information is pushed only along the most relevant edges until convergence.
  arXiv  Detail & Related papers  (2020-03-04T18:15:30Z)
• Support recovery and sup-norm convergence rates for sparse pivotal estimation [79.13844065776928]
  In high dimensional sparse regression, pivotal estimators are estimators for which the optimal regularization parameter is independent of the noise level. We show minimax sup-norm convergence rates for non smoothed and smoothed, single task and multitask square-root Lasso-type estimators.
  arXiv  Detail & Related papers  (2020-01-15T16:11:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.