On Centralized and Distributed Mirror Descent: Convergence Analysis Using Quadratic Constraints
On Centralized and Distributed Mirror Descent: Convergence Analysis Using Quadratic Constraints
复制标题
DOI：
10.1109/tac.2022.3230767
复制
发表时间：
2021-05
影响因子：
6.8
通讯作者：
Youbang Sun;Mahyar Fazlyab;Shahin Shahrampour
中科院分区：
文献类型：
--
作者：
Youbang Sun;Mahyar Fazlyab;Shahin Shahrampour
镜像下降（MD）是一种功能强大的一阶优化技术，它包含了包括梯度下降（GD）在内的几种优化算法。在这项工作中，我们利用二次约束和李雅普诺夫函数分析的稳定性和特征的MD算法的收敛速度，以及它的分布式变体使用半定规划（SDP）。对于这两个算法，我们考虑强凸和非强凸的假设。对于集中式MD和强凸问题，我们构造了一个SDP，证明指数收敛速度，并推导出一个封闭形式的可行解的SDP，恢复GD的最优速率作为一个特殊情况。我们补充我们的分析，提供了一个明确的O（1/k）$凸问题的收敛速度。接下来，我们分析了分布式MD的收敛性，并使用其维度与网络大小无关的SDP数值表征速率。据我们所知，分布MD的数值速率以前没有在文献中报道。我们进一步证明了$O（1/k）$的收敛速度分布MD在凸设置。我们的强凸问题的数值实验表明，我们的框架证明优越的上级收敛速度相比，现有的分布式GD率。
Mirror descent (MD) is a powerful first-order optimization technique that subsumes several optimization algorithms including gradient descent (GD). In this work, we leverage quadratic constraints and Lyapunov functions to analyze the stability and characterize the convergence rate of the MD algorithm as well as its distributed variant using semidefinite programming (SDP). For both algorithms, we consider both strongly convex and nonstrongly convex assumptions. For centralized MD and strongly convex problems, we construct an SDP that certifies exponential convergence rates and derive a closed-form feasible solution to the SDP that recovers the optimal rate of GD as a special case. We complement our analysis by providing an explicit $O(1/k)$ convergence rate for convex problems. Next, we analyze the convergence of distributed MD and characterize the rate numerically using an SDP whose dimensions are independent of the network size. To the best of our knowledge, the numerical rate of distributed MD has not been previously reported in the literature. We further prove an $O(1/k)$ convergence rate for distributed MD in the convex setting. Our numerical experiments on strongly convex problems indicate that our framework certifies superior convergence rates compared to the existing rates for distributed GD.