Decentralized Primal-Dual Optimization Without Global Lipschitz Continuity.

Abstract

Existing distributed optimization algorithms often rely on the Lipschitz continuity of the objective function's gradient, but in practice, the Lipschitz constant is difficult to estimate, and the global Lipschitz continuity assumption may not hold. In this article, we propose two novel decentralized (proximal) algorithms, adaptive decentralized proximal primal--dual (ADPPD) and adaptive decentralized primal--dual (ADPD), which incorporate specially designed adaptive stepsizes within an improved primal-dual framework for composite optimization problems. These algorithms only require local estimates of cocoercivity and the Lipschitz modulus, eliminating the need for global Lipschitz continuity and avoiding the overly conservative stepsizes associated with a large Lipschitz constant. Moreover, the adaptive stepsizes are independent of the network, making the algorithms highly scalable. We provide detailed theoretical analyses to prove that ADPPD shows an ergodic convergence rate $\mathcal {O}({\scriptstyle \text {}^{\scriptstyle 1}}\hspace {-0.224em}/\hspace {-0.112em}{\scriptstyle k})$ when the smooth term $f_{i}$ and the nonsmooth term $g_{i}$ are convex, and ADPD shows a linear convergence rate when $f_{i}$ is strongly convex. Numerical experiments on least-squares and logistic regression problems confirm our theoretical results, demonstrating that our algorithms achieve faster convergence due to the better utilization of local Lipschitz continuity.