An Analysis Tool for Push-Sum-Based Distributed Optimization

• 成果类型: Article
• 署名作者: Lin, Yixuan; Zhu, Zeru; Liu, Ji
• 署名单位: State University of New York (SUNY) System; Stony Brook University; State University of New York (SUNY) System; Stony Brook University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2025.3596669
• 发表日期: 2025
• 关键词: time; CONVERGENCE; algorithms; consensus

摘要

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/root 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.