# Distributed Normal Map-based Stochastic Proximal Gradient Methods over Networks

arXiv: https://arxiv.org/abs/2412.13054 · HTML: https://mlsanity.com/paper/2412.13054/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2024.

## Built on by (most cited first, 1 of 1)

- [Achieving Linear Speedup for Composite Federated Learning](https://mlsanity.com/paper/2602.03357/) (2026)

## Abstract (arXiv)

Consider n agents connected over a network collaborating to minimize the average of their local cost functions combined with a common nonsmooth function. This paper introduces a unified algorithmic framework for solving such a problem through distributed stochastic proximal gradient methods, leveraging the normal map update scheme. Within this framework, we propose two new algorithms, termed Normal Map-based Distributed Stochastic Gradient Tracking (norM-DSGT) and Normal Map-based Exact Diffusion (norM-ED). We demonstrate that both methods can asymptotically achieve comparable convergence rates to the centralized stochastic proximal gradient descent method under a general variance condition on the stochastic gradients. Additionally, the number of iterations required for norM-ED to achieve such a rate (i.e., the transient time) behaves as O(n3/(1-λ)2) for minimizing composite objective functions, matching the performance of the non-proximal ED algorithm. Here 1-λ denotes the spectral gap of the mixing matrix related to the underlying network topology. To our knowledge, such a convergence result is state-of-the-art for the considered composite problem. Under the same condition, norM-DSGT enjoys a transient time of O(maxn3/(1-λ)2, n/(1-λ)3), which matches that of the non-proximal DSGT algorithm and norM-ED under the condition (1-λ)-1=O(n2).