Decentralized Primal-Dual Optimization Without Global Lipschitz Continuity.

Area of Science:

• Optimization Theory
• Distributed Systems
• Machine Learning

Background:

• Existing distributed optimization algorithms often require global Lipschitz continuity, which is impractical to estimate and may not hold.
• The need for accurate Lipschitz constant estimation and global assumptions limits the applicability and performance of current methods.

Purpose of the Study:

• To propose novel decentralized algorithms, adaptive decentralized proximal primal-dual (ADPPD) and adaptive decentralized primal-dual (ADPD), for composite optimization problems.
• To overcome the limitations of existing methods by eliminating the need for global Lipschitz continuity and overly conservative stepsizes.

Main Methods:

• Developed two new algorithms, ADPPD and ADPD, featuring adaptive stepsizes within an improved primal-dual framework.
• Algorithms utilize local estimates of cocoercivity and Lipschitz modulus, avoiding global assumptions.
• Theoretical analysis to establish convergence rates for convex and strongly convex scenarios.

Main Results:

• ADPPD achieves an ergodic convergence rate of $\mathcal {O}(1/k)$ for convex functions.
• ADPD demonstrates a linear convergence rate when the smooth term is strongly convex.
• Numerical experiments on least-squares and logistic regression confirm faster convergence compared to existing methods.

Conclusions:

• The proposed adaptive decentralized algorithms (ADPPD and ADPD) are effective for composite optimization problems.
• These algorithms offer improved scalability and faster convergence by leveraging local Lipschitz continuity estimates.
• The methods eliminate the need for global Lipschitz continuity, enhancing practical applicability.