论文标题
ISTA和FISTA的近端亚级别标准最小化
Proximal Subgradient Norm Minimization of ISTA and FISTA
论文作者
论文摘要
为了进行一阶光滑优化，对加速现象的研究具有长期的历史。直到最近，导致加速度的机制还没有成功地被梯度校正项及其等效隐式形式所揭示。此外，基于具有相应的新出现技术，相位空间表示和Lyapunov函数的高分辨率微分方程框架，在发现逆立方速率下，Nesterov加速梯度下降（\ texttt {NAG}）方法的Nesterov加速梯度下降的平方梯度标准。但是，该结果不能直接概括为在实践中广泛使用的复合优化，例如，线性反向问题具有稀疏表示。在本文中，我们精心观察到有关步骤尺寸$ s $和Lipschitz Constant $ l $的复合优化中使用的关键不平等，并发现它可以更紧密地改善。我们应用了在结构良好的Lyapunov函数中发现的更严格的不等式，然后通过相位空间表示，无论梯度校正或隐式差异如何，都可以通过相位空间表示近端的亚级别规范最小化。 Furthermore, we demonstrate that the squared proximal subgradient norm for the class of iterative shrinkage-thresholding algorithms (ISTA) converges at an inverse square rate, and the squared proximal subgradient norm for the class of faster iterative shrinkage-thresholding algorithms (FISTA) is accelerated to convergence at an inverse cubic rate.
For first-order smooth optimization, the research on the acceleration phenomenon has a long-time history. Until recently, the mechanism leading to acceleration was not successfully uncovered by the gradient correction term and its equivalent implicit-velocity form. Furthermore, based on the high-resolution differential equation framework with the corresponding emerging techniques, phase-space representation and Lyapunov function, the squared gradient norm of Nesterov's accelerated gradient descent (\texttt{NAG}) method at an inverse cubic rate is discovered. However, this result cannot be directly generalized to composite optimization widely used in practice, e.g., the linear inverse problem with sparse representation. In this paper, we meticulously observe a pivotal inequality used in composite optimization about the step size $s$ and the Lipschitz constant $L$ and find that it can be improved tighter. We apply the tighter inequality discovered in the well-constructed Lyapunov function and then obtain the proximal subgradient norm minimization by the phase-space representation, regardless of gradient-correction or implicit-velocity. Furthermore, we demonstrate that the squared proximal subgradient norm for the class of iterative shrinkage-thresholding algorithms (ISTA) converges at an inverse square rate, and the squared proximal subgradient norm for the class of faster iterative shrinkage-thresholding algorithms (FISTA) is accelerated to convergence at an inverse cubic rate.
