.png){kind=icon}
.png){kind=icon}
Return
An Analysis Tool for Push-Sum-Based Distributed Optimization
.png){kind=icon}
PRE
AI
DOI：10.1109/TAC.2025.3596669.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This article establishes the explicit absolute probability sequence for the push-sum algorithm, and based on which, and constructs quadratic Lyapunov functions for push-sum-based distributed optimization algorithms. As illustrative examples, the proposed novel analysis tool can establish optimal convergence rates for the subgradient-push and stochastic gradient-push, two important algorithms for distributed convex optimization over directed graphs. Specifically, this article proves that the subgradient-push algorithm with a constant stepsize for finite <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$T$</tex-math></inline-formula> steps converges at a rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(1/\sqrt{T})$</tex-math></inline-formula> for general convex functions, and the stochastic gradient-push algorithm with a time <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$t$</tex-math></inline-formula>-dependent diminishing stepsize converges at a rate of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(1/t)$</tex-math></inline-formula> for strongly convex functions over time-varying directed graphs. Both rates are, respectively, the same as the state-of-the-art rates of their single-agent counterparts and thus optimal.
Keywords:
Multi-agent systems
collaborative control
distributed optimization
Journal
IF:
7
Papers:
1.3W
Citations:
6.7W