Subgradient-Push Is of the Optimal Convergence Rate

2022/03/30 by Lin, Yixuan, Liu, Ji
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2203.16623

Abstract

The push-sum based subgradient is an important method for distributed convex optimization over unbalanced directed graphs, which is known to converge at a rate of O(ln t/√(t)). This paper shows that the subgradient-push algorithm actually converges at a rate of O(1/√(t)), which is the same as that of the single-agent subgradient and thus optimal. The proposed tool for analyzing push-sum based algorithms is of independent interest.

Related

• An Analysis Tool for Push-Sum Based Distributed Optimization
• Heterogeneous Distributed Subgradient
• Distributed optimization over time-varying directed graphs
• Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying\n Directed Graphs
• Convergence result for the gradient-push algorithm and its application to boost up the Push-DIging algorithm