无需全局利普希茨连续性的去中心化原始-对偶优化

《IEEE Transactions on Neural Networks and Learning Systems》：Decentralized Primal–Dual Optimization Without Global Lipschitz Continuity

针对现有分布式优化算法依赖全局Lipschitz连续性的问题，提出ADPPD和ADPD算法，通过局部自适应步长设计，仅需局部cocoercivity和Lipschitz模估计，避免保守步长，提升可扩展性，理论证明其收敛率，数值实验验证效果。

　　

摘要：

现有的分布式优化算法通常依赖于目标函数梯度的Lipschitz连续性，但在实践中，Lipschitz常数难以估计，且全局Lipschitz连续性的假设可能不成立。在本文中，我们提出了两种新型的分布式（近端）算法：自适应分布式近端原始-对偶（ADPPD）和自适应分布式原始-对偶（ADPD）。这些算法在改进的原始-对偶框架内融入了特别设计的自适应步长，适用于复合优化问题。这些算法仅需要局部估计的共轭性和Lipschitz模数，从而无需全局Lipschitz连续性，并避免了因Lipschitz常数过大而导致的过于保守的步长。此外，自适应步长与网络无关，使得算法具有高度的可扩展性。我们提供了详细的理论分析，证明了当平滑项和非平滑项分别为凸函数时，ADPPD的收敛速率为O(1/k)；当平滑项为强凸函数时，ADPPD的收敛速率为线性。通过对最小二乘法和逻辑回归问题的数值实验验证，我们的算法由于更好地利用了局部Lipschitz连续性，因此收敛速度更快。