Optimizing Stochastic Gradient Push under Broadcast Communications

• URL: http://arxiv.org/abs/2604.15549v1
• Date: Thu, 16 Apr 2026 21:56:57 GMT
• Title: Optimizing Stochastic Gradient Push under Broadcast Communications
• Abstract summary: We consider the problem of minimizing the convergence time for decentralized federated learning (DFL) in wireless networks under broadcast communications.<n>We focus on mixing matrix design, which simultaneously controls the convergence rate across iterations and the communication demand per iteration.<n>Our evaluations show that the proposed solution can notably reduce the convergence time compared to the state of the art without compromising the quality of the trained model.
• Score: 5.019739507685787
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of minimizing the convergence time for decentralized federated learning (DFL) in wireless networks under broadcast communications, with focus on mixing matrix design. The mixing matrix is a critical hyperparameter for DFL that simultaneously controls the convergence rate across iterations and the communication demand per iteration, both strongly influencing the convergence time. Although the problem has been studied previously, existing solutions are mostly designed for decentralized parallel stochastic gradient descent (D-PSGD), which requires the mixing matrix to be symmetric and doubly stochastic. These constraints confine the activated communication graph to undirected (i.e., bidirected) graphs, which limits design flexibility. In contrast, we consider mixing matrix design for stochastic gradient push (SGP), which allows asymmetric mixing matrices and hence directed communication graphs. By analyzing how the convergence rate of SGP depends on the mixing matrices, we extract an objective function that explicitly depends on graph-theoretic parameters of the activated communication graph, based on which we develop an efficient design algorithm with performance guarantees. Our evaluations based on real data show that the proposed solution can notably reduce the convergence time compared to the state of the art without compromising the quality of the trained model.

Related papers

• Directed Graph Topology Inference via Graph Filter Identification [54.541275287889164]
  We address the problem of inferring a directed network from nodal measurements generated by a graph convolutional filter.<n>A joint graph filter and topology identification algorithm is also proposed, which alternates between the aforementioned steps to offer improved sample complexity.
  arXiv  Detail & Related papers  (2026-06-25T18:25:57Z)
• Bridging Graph Drawing and Dimensionality Reduction with Stochastic Stress Optimization [0.22940141855172028]
  Dimensionality Reduction (DR) and Graph Drawing (GD) aim to visualize abstract, non-linear structures, yet rely on different optimization paradigms.<n>We bridge these domains by adapting Gradient Descent (SGD) techniques from graph drawing to vector data embedding.
  arXiv  Detail & Related papers  (2026-05-01T13:22:56Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Balancing Symmetry and Efficiency in Graph Flow Matching [33.80974796363154]
  We study the trade-off for graph generative models between strict equivariance and controllable symmetry modulation.<n>We show that properly modulating the symmetry signal can delay overfitting while accelerating convergence.
  arXiv  Detail & Related papers  (2026-02-20T09:17:57Z)
• Time-varying Mixing Matrix Design for Energy-efficient Decentralized Federated Learning [6.831984901330601]
  We propose a theoretically-justified solution for mixing matrix design that aims at minimizing the maximum per-node energy consumption until convergence.<n>Our evaluations based on real data have validated the efficacy of the proposed solution in combining the low energy consumption of sparse mixing matrices and the fast convergence of dense mixing matrices.
  arXiv  Detail & Related papers  (2025-12-30T08:24:28Z)
• Learning Time-Varying Graphs from Incomplete Graph Signals [1.7430416823420511]
  We develop an efficient Alternating Direction Multiplier algorithm for solving the problem of imputing missing data from a graph.<n>We prove that the proposed ADMM scheme converges to and we derive a stationary point.
  arXiv  Detail & Related papers  (2025-10-19T11:12:13Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• GP-FL: Model-Based Hessian Estimation for Second-Order Over-the-Air Federated Learning [52.295563400314094]
  Second-order methods are widely adopted to improve the convergence rate of learning algorithms.<n>This paper introduces a novel second-order FL framework tailored for wireless channels.
  arXiv  Detail & Related papers  (2024-12-05T04:27:41Z)
• On Learning Gaussian Multi-index Models with Gradient Flow [57.170617397894404]
  We study gradient flow on the multi-index regression problem for high-dimensional Gaussian data. We consider a two-timescale algorithm, whereby the low-dimensional link function is learnt with a non-parametric model infinitely faster than the subspace parametrizing the low-rank projection.
  arXiv  Detail & Related papers  (2023-10-30T17:55:28Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  We characterize the dependence of convergence on the relationship between the mixing weights of the graph and the data heterogeneity across nodes. We propose a metric that quantifies the ability of a graph to mix the current gradients. Motivated by our analysis, we propose an approach that periodically and efficiently optimize the metric.
  arXiv  Detail & Related papers  (2022-04-13T15:54:35Z)

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.