Convergence rate for distributed optimization methods: Novel bounds and distributed step size computation

We consider unconstrained multi-agent optimization problems where agents cooperatively minimize the sum of their local objective functions. By combining and extending recent results in [1] and [2], we determine an improved bound on the convergence rate of consensus based distributed subgradient methods with constant step size. In particular, we show that the convergence speed of the consensus based algorithm and the asymptotic optimization error are jointly decided by the step size and the spectral gap of the underlying network. Wave equation based algorithm [3] is utilized to rapidly and distributively compute the proposed bound, thus providing a way for the agents to estimate the instantaneous error as well as chose a suitable step size in a distributed fashion. Simulation results show how the bound compares to ground truth values for some relevant examples.