An Explicit Convergence Rate for Nesterov's Method from SDP
An Explicit Convergence Rate for Nesterov's Method from SDP
复制标题
基于SDP的Nesterov方法的显式收敛率
DOI：
10.1109/isit.2018.8437794
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
José Bento
中科院分区：
文献类型：
--
作者：
S. Safavi;Bikash Joshi;G. França;José Bento
Lessard等人（2014）引入的积分二次约束（IQC）框架将几种优化算法收敛速度的上限计算减少到半定规划（SDP）。特别是，这种技术被应用于Nesterov的加速方法（NAM）。对于二次函数，这个SDP被显式求解，从而导致NAM收敛速度的新界，对于任意强凸函数，数值表明IQC可以改进Nesterov（2004）的界。不幸的是，没有提供SDP的显式解析解。在本文中，我们提供了这样一个解析解，获得了一个新的一般和明确的上界的收敛速度NAM，我们进一步优化其参数。据我们所知，这是强凸函数NAM收敛速度的最佳且明确的上界。
The framework of Integral Quadratic Constraints (IQC) introduced by Lessard et al. (2014) reduces the computation of upper bounds on the convergence rate of several optimization algorithms to semi-definite programming (SDP). In particular, this technique was applied to Nesterov's accelerated method (NAM). For quadratic functions, this SDP was explicitly solved leading to a new bound on the convergence rate of NAM, and for arbitrary strongly convex functions it was shown numerically that IQC can improve bounds from Nesterov (2004). Unfortunately, an explicit analytic solution to the SDP was not provided. In this paper, we provide such an analytical solution, obtaining a new general and explicit upper bound on the convergence rate of NAM, which we further optimize over its parameters. To the best of our knowledge, this is the best, and explicit, upper bound on the convergence rate of NAM for strongly convex functions.