Distributed Optimization via Energy Conservation Laws in Dilated Coordinates
This provides a theoretical framework for analyzing distributed optimization algorithms, which is incremental but offers improved convergence rates for systems with multiple agents and private data.
The paper tackles the lack of a unified method for analyzing convergence rates in distributed optimization by introducing an energy conservation approach in dilated coordinates, resulting in a novel second-order distributed accelerated gradient flow with a convergence rate of O(1/t^{2-ε}) and a discretized algorithm achieving O(1/k^{2-ε}), claimed as the most favorable rate for smooth convex optimization.
Optimizing problems in a distributed manner is critical for systems involving multiple agents with private data. Despite substantial interest, a unified method for analyzing the convergence rates of distributed optimization algorithms is lacking. This paper introduces an energy conservation approach for analyzing continuous-time dynamical systems in dilated coordinates. Instead of directly analyzing dynamics in the original coordinate system, we establish a conserved quantity, akin to physical energy, in the dilated coordinate system. Consequently, convergence rates can be explicitly expressed in terms of the inverse time-dilation factor. Leveraging this generalized approach, we formulate a novel second-order distributed accelerated gradient flow with a convergence rate of $O\left(1/t^{2-ε}\right)$ in time $t$ for $ε>0$. We then employ a semi second-order symplectic Euler discretization to derive a rate-matching algorithm with a convergence rate of $O\left(1/k^{2-ε}\right)$ in $k$ iterations. To the best of our knowledge, this represents the most favorable convergence rate for any distributed optimization algorithm designed for smooth convex optimization. Its accelerated convergence behavior is benchmarked against various state-of-the-art distributed optimization algorithms on practical, large-scale problems.