Proximal Subgradient Norm Minimization of ISTA and FISTA
Proximal Subgradient Norm Minimization of ISTA and FISTA
复制标题
ISTA 和 FISTA 的近端次梯度范数最小化
DOI：
10.48550/arxiv.2211.01610
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Ya
中科院分区：
文献类型：
--
作者：
Bowen Li;Bin Shi;Ya
对于一阶光滑优化，加速现象的研究有着悠久的历史。直到最近，梯度修正项及其等效的隐式速度形式还没有成功揭示导致加速的机制。此外，基于高分辨率微分方程框架以及相应的新兴技术、相空间表示和Lyapunov函数，发现了Nesterov加速梯度下降（\texttt{NAG}）方法在反立方速率下的平方梯度范数。然而，这个结果不能直接推广到实践中广泛使用的复合优化，例如稀疏表示的线性逆问题。在本文中，我们仔细观察了复合优化中使用的关于步长 $s$ 和 Lipschitz 常数 $L$ 的关键不等式，并发现它可以进一步改进。我们应用在构造良好的李亚普诺夫函数中发现的更严格的不等式，然后通过相空间表示获得近端次梯度范数最小化，无论梯度校正或隐式速度如何。此外，我们证明了迭代收缩阈值算法（ISTA）类的平方近端次梯度范数以平方反比速率收敛，并且更快迭代收缩阈值算法（FISTA）类的平方近端次梯度范数以反立方速率加速收敛。
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.