Convergence of Message-Passing for Distributed Convex Optimisation with Scaled Diagonal Dominance

2019/04/09 by Zhang, Zhaorong, Fu, Minyue
#FOS: Electrical engineering #FOS: Mathematics #Optimization and Control (math.OC) #Signal Processing (eess.SP) #electronic engineering #information engineering

paper · doi:10.48550/arxiv.1904.04465

Abstract

This paper studies the convergence properties the well-known message-passing algorithm for convex optimisation. Under the assumption of pairwise separability and scaled diagonal dominance, asymptotic convergence is established and a simple bound for the convergence rate is provided for message-passing. In comparison with previous results, our results do not require the given convex program to have known convex pairwise components and that our bound for the convergence rate is tighter and simpler. When specialised to quadratic optimisation, we generalise known results by providing a very simple bound for the convergence rate.

Related

• Convergence of the Min-Sum Algorithm for Convex Optimization
• Communication Lower Bounds for Distributed Convex Optimization: Partition Data on Features
• Convergence of Min-Sum Message Passing for Quadratic Optimization
• Communication Complexity of Distributed Convex Learning and Optimization
• Distributed Convex Optimization With Limited Communications