Title | ||
---|---|---|
Linear Convergence of First- and Zeroth-Order Primal–Dual Algorithms for Distributed Nonconvex Optimization |
Abstract | ||
---|---|---|
This article considers the distributed nonconvex optimization problem of minimizing a global cost function formed by a sum of local cost functions by using local information exchange. We first consider a distributed first-order primal–dual algorithm. We show that it converges sublinearly to a stationary point if each local cost function is smooth and linearly to a global optimum under an additional condition that the global cost function satisfies the Polyak–Łojasiewicz condition. This condition is weaker than strong convexity, which is a standard condition for proving linear convergence of distributed optimization algorithms, and the global minimizer is not necessarily unique. Motivated by the situations where the gradients are unavailable, we then propose a distributed zeroth-order algorithm, derived from the considered first-order algorithm by using a deterministic gradient estimator, and show that it has the same convergence properties as the considered first-order algorithm under the same conditions. The theoretical results are illustrated by numerical simulations. |
Year | DOI | Venue |
---|---|---|
2022 | 10.1109/TAC.2021.3108501 | IEEE Transactions on Automatic Control |
Keywords | DocType | Volume |
Distributed nonconvex optimization,first-order algorithm,linear convergence,primal–dual algorithm,zeroth-order algorithm | Journal | 67 |
Issue | ISSN | Citations |
8 | 0018-9286 | 1 |
PageRank | References | Authors |
0.36 | 33 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xinlei Yi | 1 | 116 | 9.37 |
Shengjun Zhang | 2 | 1 | 0.36 |
Tao Yang | 3 | 160 | 76.32 |
Tianyou Chai | 4 | 13 | 5.59 |
Karl Henrik Johansson | 5 | 3996 | 322.75 |