  The distributed optimization problem is set up in a collection of nodes
interconnected via a communication network. The goal is to find the minimizer
of a global function formed by the addition of partial functions locally known
at each node. A number of methods are available for addressing this problem,
having different advantages. The goal of this work is to achieve the maximum
possible convergence rate. As a first step towards this end, we propose a new
method which we show converges faster than other available options. We then
carry out a theoretical analysis which yields guarantees for convergence in a
neighborhood of a local optimum and quantifies its asymptotic convergence rate.
As with most distributed optimization methods, this rate depends on a step size
parameter. Our second step toward our goal consists in choosing the optimal
step size in the sense of maximizing the convergence rate. Since this optimal
value depends on the unknown global function, we tackle the problem by
proposing a fully distributed method for estimating it. We present numerical
experiments showing that, for the same step size, our method converges
significantly faster than its rivals. Experiments also show that the
distributed step size estimation method achieves the theoretically maximum
asymptotic convergence rate.
