A primal-dual algorithm with optimal stepsizes and its application in decentralized consensus optimization
11 citations recorded by the source corpus.
We consider a primal-dual algorithm for minimizing $f(x)+h(Ax)$ with differentiable $f$. The primal-dual algorithm has two names in literature: Primal-Dual Fixed-Point algorithm based on the Proximity Operator (PDFP$^2$O) and Proximal Alternating Predictor-Corrector (PAPC). In this paper, we extend it to solve $f(x)+h\square l(Ax)$ with differentiable $l^*$ and prove its convergence under a weak condition (i.e., under a large dual stepsize). With additional assumptions, we show its linear convergence. In addition, we show that this condition is optimal and can not be weaken. This result recovers the recent proposed positive-indefinite linearized augmented Lagrangian method. Then we consider the application of this primal-dual algorithm in decentralized consensus optimization. We show that EXact firsT-ordeR Algorithm (EXTRA) and Proximal Gradient-EXTRA (PG-EXTRA) can be consider as the primal-dual algorithm applied on a problem in the form of $h\square l(Ax)$. Then, the optimal upper bound of the stepsize for EXTRA/PG-EXTRA is derived. It is larger than the existing work on EXTRA/PG-EXTRA. Furthermore, for the case with strongly convex functions, we proved linear convergence under the same condition for the stepsize.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
Citations in the corpus
- $\texttt{DeepSqueeze}$: Decentralization Meets Error-Compensated Compression (2019, background): “…2011, Recht et al., 2011], where all the workers are ensured to obtain information from all others; 2) decentralized parallel learning [Dvurechenskii et al., 2018, He et al., 2018, Li and Yan, 2017, Lian et al., 2017], where each worker can only gather information from a fraction of its neighbors.”
- D2: Decentralized Training over Decentralized Data (2018, methodology): “Recently, Li and Yan [2017] show that λ n > − 1/3 is optimal in the convergence of EXTRA.”
- A Decentralized Proximal-Gradient Method With Network Independent Step-Sizes and Separated Convergence Rates (2017, methodology): “The upper bound of step-size for EXTRA was recently improved to (5 + 3λn(W))/(4L) in [47].”