Improving the Convergence of Distributed Gradient Descent via Inexact Average Consensus

It is observed that the inexact convergence of the well-known distributed gradient descent algorithm can be caused by inaccuracy of consensus procedures. Motivated by this, to achieve the improved convergence, we ensure the sufficiently accurate consensus via approximate consensus steps. The accuracy is controlled by a predefined sequence of consensus error bounds. It is shown that one can achieve exact convergence when the sequence decays to zero; furthermore, a linear convergence rate can be obtained when the sequence decays to zero linearly. To implement the approximate consensus step with given error bounds, an inexact average consensus scheme is proposed in a distributed manner. Due to the flexibility of choices of both consensus error bounds and consensus schemes, the proposed framework offers the potential to balance the communication and computation in distributed optimization.