A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization
A Linearly Convergent Proximal Gradient Algorithm for Decentralized Optimization
复制标题
DOI：
--
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Sulaiman A. Alghunaim;K. Yuan;A. H. Sayed
中科院分区：
文献类型：
--
作者：
Sulaiman A. Alghunaim;K. Yuan;A. H. Sayed
分散优化是一种强大的范例，可以在工程和学习设计中找到应用。本文研究具有非光滑正则化项的分散复合优化问题。已知大多数现有的基于梯度的近端分散方法以次线性速率收敛到最优解，并且尚不清楚这类方法是否能够实现全局线性收敛。为了解决这个问题，这项工作假设非平滑正则化项在所有网络代理中都是通用的，这是许多机器学习问题的情况。在这种情况下，我们设计了一种不动点与期望最小值重合的近端梯度分散算法。然后给出了一个简洁的证明，证明了它的线性收敛性。在没有非光滑项的情况下，我们的分析技术涵盖了众所周知的EXTRA算法，并提供了有用的收敛速度和步长界限。
Decentralized optimization is a powerful paradigm that finds applications in engineering and learning design. This work studies decentralized composite optimization problems with non-smooth regularization terms. Most existing gradient-based proximal decentralized methods are known to converge to the optimal solution with sublinear rates, and it remains unclear whether this family of methods can achieve global linear convergence. To tackle this problem, this work assumes the non-smooth regularization term is common across all networked agents, which is the case for many machine learning problems. Under this condition, we design a proximal gradient decentralized algorithm whose fixed point coincides with the desired minimizer. We then provide a concise proof that establishes its linear convergence. In the absence of the non-smooth term, our analysis technique covers the well known EXTRA algorithm and provides useful bounds on the convergence rate and step-size.