Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum

Yuan Zhou, Xinli Shi, Xuelong Li, Jiachen Zhong, Guanghui Wen, Jinde Cao

TL;DR

This paper introduces DEPOSITUM, a novel algorithm for decentralized federated learning (DFL) that tackles complex, non-convex optimization problems with non-smooth components. By combining gradient tracking with momentum, DEPOSITUM effectively handles data heterogeneity, reduces communication overhead through local updates, and achieves theoretical guarantees for convergence and linear speedup, outperforming existing methods in experiments.

What Problem Does This Paper Address?

Traditional federated learning (FL) relies on a central server to coordinate model training across clients. This creates a single point of failure and a potential communication bottleneck. Decentralized FL (DFL) aims to overcome these limitations by allowing clients to communicate directly with their neighbors. However, many real-world machine learning tasks involve objective functions that are not only non-convex but also include non-smooth regularization terms (e.g., for sparsity). Solving these "non-convex composite optimization problems" in a decentralized setting (DNCFL) is a challenging and underexplored area. Existing DFL methods often struggle with data heterogeneity (where client data distributions differ significantly), leading to "client drift" and slower convergence.

Methods

DEPOSITUM builds upon proximal stochastic gradient tracking (DSGT) to address DNCFL. Key innovations include:

  • Gradient Tracking: Clients use a tracking variable to approximate the global gradient, mitigating the impact of data heterogeneity without requiring strong assumptions about data distribution.
  • Momentum Integration: The algorithm incorporates momentum (either Polyak's or Nesterov's) into the proximal gradient descent step. This helps reduce the variance introduced by stochastic gradients, leading to faster convergence and improved stability.
  • Local Updates: DEPOSITUM supports multiple local client updates between communication rounds. This significantly reduces the communication burden, a critical factor in large-scale distributed systems.
  • Proximal Operator: The algorithm is designed to handle non-smooth, weakly convex regularization terms by leveraging their proximal operators.

The theoretical analysis shows that DEPOSITUM can achieve an expected $\epsilon$-stationary point with $\mathcal{O}(1/\epsilon^2)$ iteration complexity and that consensus and gradient estimation errors decrease at a sublinear rate of $\mathcal{O}(1/T)$. Crucially, with appropriate parameter tuning, it can achieve network-independent linear speedup.

Datasets

The paper evaluates DEPOSITUM on several standard datasets:

  • A9A
  • MNIST
  • Extended MNIST (EMNIST)
  • Fashion MNIST (FMNIST)
  • CIFAR-10

These datasets cover various data formats, including tabular, grayscale images, and color images, and are used with different model architectures.

Key Insights and Ideas

  • DFL for Non-Convex Composite Problems is Crucial: The paper highlights that many practical ML problems fall into the DNCFL category, making this research highly relevant.
  • Momentum and Gradient Tracking are a Powerful Combination: By synergistically combining these two techniques, DEPOSITUM effectively tackles both data heterogeneity and the variance of stochastic gradients.
  • Local Updates are Key for Efficiency: The ability to perform multiple local updates before communication is essential for reducing communication costs in decentralized settings.
  • Theoretical Guarantees are Achievable: The paper provides strong theoretical backing for DEPOSITUM's convergence and speedup, which is vital for practical deployment.
  • Network Topology Matters, but Less Than Expected: While a complete graph offers theoretical advantages, the experimental results suggest that DEPOSITUM performs well across different topologies, demonstrating robustness.

Key Results

  • Convergence: DEPOSITUM achieves an expected $\epsilon$-stationary point with $\mathcal{O}(1/\epsilon^2)$ iteration complexity. Consensus and gradient estimation errors decrease at a sublinear rate of $\mathcal{O}(1/T)$.
  • Linear Speedup: With proper parameter selection, DEPOSITUM can achieve network-independent linear speedup, meaning convergence improves proportionally with the number of clients.
  • Experimental Performance: DEPOSITUM consistently outperforms baseline decentralized FL algorithms (FedMiD, FedDR, FedADMM) across various datasets, models, and data distributions, achieving higher accuracy. The paper demonstrates the impact of hyperparameters like step size and momentum, showing that momentum generally improves performance.

Limitations and Future Work

  • Theoretical Assumptions: While DEPOSITUM relaxes assumptions on data heterogeneity compared to some prior work, it still relies on L-smoothness for local functions and p-weakly convexity for the non-smooth term.
  • Parameter Tuning: Achieving optimal performance, particularly linear speedup, requires careful tuning of parameters like step sizes ($\alpha$, $\beta$) and momentum coefficients ($\gamma$).
  • Future Work: The authors suggest integrating advanced security mechanisms and developing privacy-preserving and Byzantine-resilient variants of the algorithm. Exploring more general non-convexity conditions and asynchronous updates could also be promising directions.

Summary updated

Abstract

Decentralized Federated Learning (DFL) eliminates the reliance on the server-client architecture inherent in traditional federated learning, attracting significant research interest in recent years. Simultaneously, the objective functions in machine learning tasks are often nonconvex and frequently incorporate additional, potentially nonsmooth regularization terms to satisfy practical requirements, thereby forming nonconvex composite optimization problems. Employing DFL methods to solve such general optimization problems leads to the formulation of Decentralized Nonconvex Composite Federated Learning (DNCFL), a topic that remains largely underexplored. In this paper, we propose a novel DNCFL algorithm, termed \bf{DEPOSITUM}. Built upon proximal stochastic gradient tracking, DEPOSITUM mitigates the impact of data heterogeneity by enabling clients to approximate the global gradient. The introduction of momentums in the proximal gradient descent step, replacing tracking variables, reduces the variance introduced by stochastic gradients. Additionally, DEPOSITUM supports local updates of client variables, significantly reducing communication costs. Theoretical analysis demonstrates that DEPOSITUM achieves an expected $\epsilon$-stationary point with an iteration complexity of $\mathcal{O}(1/\epsilon^2)$. The proximal gradient, consensus errors, and gradient estimation errors decrease at a sublinear rate of $\mathcal{O}(1/T)$. With appropriate parameter selection, the algorithm achieves network-independent linear speedup without requiring mega-batch sampling. Finally, we apply DEPOSITUM to the training of neural networks on real-world datasets, systematically examining the influence of various hyperparameters on its performance. Comparisons with other federated composite optimization algorithms validate the effectiveness of the proposed method.
BibTeX
@misc{zhou2025decentralized,
  author = {Yuan Zhou and Xinli Shi and Xuelong Li and Jiachen Zhong and Guanghui Wen and Jinde Cao},
  title = {{Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum}},
  year = {2025},
  eprint = {2504.12742},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.12742},
}
Figure