Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods
Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods
复制标题
DOI：
10.1287/moor.2017.0889
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
D. Drusvyatskiy;A. Lewis
中科院分区：
文献类型：
--
作者：
D. Drusvyatskiy;A. Lewis
最小化光滑与非光滑凸函数之和的近似梯度算法即使没有强凸性也经常线性收敛。一个常见的原因是，每次迭代时步长的倍数可以线性地限制“误差”--到解集的距离。我们直观地解释所观察到的线性收敛证明了这样的错误绑定到一个自然的二次增长条件的等价性。我们的方法推广到线性收敛性分析的近似方法（高斯-牛顿型）最小化的非光滑函数与光滑映射的组合物。我们顺便观察到，在算法中的短步长表示近平稳性，这表明一个可靠的终止标准。
The proximal gradient algorithm for minimizing the sum of a smooth and a nonsmooth convex function often converges linearly even without strong convexity. One common reason is that a multiple of the step length at each iteration may linearly bound the "error" -- the distance to the solution set. We explain the observed linear convergence intuitively by proving the equivalence of such an error bound to a natural quadratic growth condition. Our approach generalizes to linear convergence analysis for proximal methods (of Gauss-Newton type) for minimizing compositions of nonsmooth functions with smooth mappings. We observe incidentally that short step-lengths in the algorithm indicate near-stationarity, suggesting a reliable termination criterion.