Distributed optimization
An Analysis Tool for Push-Sum-Based Distributed Optimization
A Lyapunov-based analysis framework for push-sum algorithms over time-varying directed communication networks.
- Year
- 2025
- Status
- Published
- Topics
- Optimization · Directed graphs · Convergence analysis
A conceptual illustration of the mathematical idea, not a plot of measured experimental results.
The question
Can distributed gradient methods over changing, unbalanced directed graphs match centralized convergence rates?
Central insight
The ratio correction in push-sum hides a row-stochastic process. Making its absolute probability sequence explicit reveals the right time-varying quadratic energy for analysis.
Approach
- 01
Express the normalized push-sum states through an induced row-stochastic matrix sequence.
- 02
Identify the associated absolute probability sequence explicitly.
- 03
Build quadratic Lyapunov functions adapted to the evolving directed network.
- 04
Apply the tool to subgradient-push and stochastic gradient-push.
My contribution
- Helped construct the Lyapunov-based analysis framework.
- Established optimal convergence rates for two representative push-sum optimization algorithms.
- Connected the multi-agent rates to their centralized single-agent counterparts.
A closer look
Why two quantities are passed around the network
A directed network can distribute information unevenly: an agent may send to one set of neighbors and receive from another. Push-sum compensates by propagating both a numerator xᵢ and a positive weight yᵢ using the same communication weights. Their ratio zᵢ = xᵢ/yᵢ removes the distortion introduced by the network. For ordinary push-sum with initial weights equal to one, these ratios approach the initial average under the paper’s connectivity assumptions.
The key analytical step rewrites the ratio dynamics as a row-stochastic process. Its absolute probability sequence is explicit: πᵢ(t) = yᵢ(t)/n. This identifies the changing weights needed to construct a quadratic Lyapunov analysis compatible with the directed network.
zᵢ(t) = xᵢ(t) / yᵢ(t), πᵢ(t) = yᵢ(t) / n
What matching the centralized rate means
Applied to subgradient-push, the framework gives an O(1/√T) rate for general convex objectives with a constant stepsize chosen for a finite horizon. For strongly convex stochastic gradient-push, a diminishing stepsize gives O(1/t). These match the corresponding centralized rates in order, while network properties still affect constants.
The guarantees require the stated objective and noise assumptions, positive communication weights bounded away from zero, and uniform joint strong connectivity. They do not require every individual communication graph to be strongly connected, and they do not claim the same rates for arbitrary nonconvex learning problems.
Result
The analysis closes known rate gaps: O(1/sqrt(T)) for general convex subgradient-push and O(1/t) for strongly convex stochastic gradient-push.
What remains
Apply the framework to broader classes of push-sum-based learning and optimization algorithms.
Paper & resources
An Analysis Tool for Push-Sum-Based Distributed Optimization
Yixuan Lin, Zeru Zhu, and Ji Liu
IEEE Transactions on Automatic Control, 70(12), 8298–8305 · Published