Convergence Analysis of EXTRA in Non-convex Distributed Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908439153737728 |
|---|---|
| author | Qin, Lei Pu, Ye |
| author_facet | Qin, Lei Pu, Ye |
| contents | 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 \textbf{EXTRA} (decentralized exact first-order algorithm), have been proposed to address these challenges. In this paper, we analyze the convergence properties of \textbf{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) \textbf{EXTRA} converges to a consensual first-order stationary point of the global objective with a sublinear rate; and ii) \textbf{EXTRA} avoids convergence to consensual strict saddle points, offering second-order guarantees that ensure robustness. These findings provide a deeper understanding of \textbf{EXTRA} in a non-convex context. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_11104 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Convergence Analysis of EXTRA in Non-convex Distributed Optimization Qin, Lei Pu, Ye Optimization and Control 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 \textbf{EXTRA} (decentralized exact first-order algorithm), have been proposed to address these challenges. In this paper, we analyze the convergence properties of \textbf{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) \textbf{EXTRA} converges to a consensual first-order stationary point of the global objective with a sublinear rate; and ii) \textbf{EXTRA} avoids convergence to consensual strict saddle points, offering second-order guarantees that ensure robustness. These findings provide a deeper understanding of \textbf{EXTRA} in a non-convex context. |
| title | Convergence Analysis of EXTRA in Non-convex Distributed Optimization |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2503.11104 |