An Analysis Tool for Push-Sum-Based Distributed Optimization
Yixuan Lin, Zeru Zhu, Ji yin Liu · IEEE Transactions on Automatic Control · 2025
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$T$steps converges at a rate of$O(1/\sqrt{T})$for general convex functions, and the stochastic gradient-push algorithm with a time$t$-dependent diminishing stepsize converges at a rate of$O(1/t)$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.