Convergence Analysis of EXTRA in Non-convex Distributed Optimization

Optimization problems involving the minimization of a finite sum of smooth, possibly non-convex functions arise in numerous applications. To achieve a consensus solution over a network, distributed optimization algorithms, such as $\mathbf{\text{EXTRA}}$ (decentralized exact first-order algorithm), have been proposed to address these challenges. In this paper, we analyze the convergence properties of $\mathbf{\text{EXTRA}}$ in the context of smooth, non-convex optimization. By interpreting its updates as a nonlinear dynamical system, we show novel insights into its convergence properties. Specifically, i) $\mathbf{\text{EXTRA}}$ converges to a consensual first-order stationary point of the global objective with a sublinear rate; and ii) $\mathbf{\text{EXTRA}}$ avoids convergence to consensual strict saddle points, offering second-order guarantees that ensure robustness. These findings provide a deeper understanding of $\mathbf{\text{EXTRA}}$ in a non-convex context.