# Asymptotic Properties of Primal-Dual Algorithm for Distributed Stochastic Optimization Over Random Networks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jul 2016.

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

- [Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization](https://mlsanity.com/paper/2111.03820/) (2021)
- [Distributed gradient-based optimization in the presence of dependent aperiodic communication](https://mlsanity.com/paper/2201.11343/) (2022)
- [A Stochastic Approximation Approach for Efficient Decentralized Optimization on Random Networks](https://mlsanity.com/paper/2410.18774/) (2024)

## Abstract (arXiv)

This paper studies a distributed stochastic optimization problem over random networks with imperfect communications subject to a global constraint, which is the intersection of local constraint sets assigned to agents. The global cost function is the sum of local cost functions, each of which is the expectation of a random cost function. By incorporating the augmented Lagrange technique with the projection method, a stochastic approximation based distributed primal-dual algorithm is proposed to solve the problem. Each agent updates its estimate by using the local observations and the information derived from neighbors. For the constrained problem, the estimates are first shown to be bounded almost surely (a.s.), and then are proved to converge to the optimal solution set a.s. Furthermore, the asymptotic normality and efficiency of the algorithm are addressed for the unconstrained case. The results demonstrate the influence of random networks, communication noises, and gradient errors on the performance of the algorithm. Finally, numerical simulations demonstrate the theoretic results.