姜霞,孙健,陈杰等 | 求解非光滑优化问题的随机重排采样近似梯度算法
文摘
科技
2024-12-07 14:30
北京
![]()
![]()
研究团队
姜霞，房妍妍，曾宪琳，孙健：北京理工大学
陈杰：同济大学
文章下载
Xia JIANG, Yanyan FANG, Xianlin ZENG, Jian SUN & Jie CHEN. Inexact Proximal Gradient Algorithm with Random Reshuffling for Nonsmooth Optimization. Sci China Inf Sci, 2024, doi: 10.1007/s11432-023-4095-y
![]()
非光滑优化是信号处理和协同控制领域中的一个重要问题，传统的优化理论和方法基于优化问题函数可微的设定，并不适用于求解具有非连续可微目标函数或约束条件的优化问题。此外，许多非光滑优化问题涉及到大规模的数据样本，这导致全梯度的计算成本很高。因此，采用近似梯度的随机算法求解具有非光滑正则项的凸优化问题得到广泛关注。同时，由于在大规模数据梯度计算过程中可能存在的误差，针对非光滑正则项的近端算子的精确求解同样具有挑战性的。另一方面，针对大规模数据样本，传统的随机优化算法往往基于有放回的均匀采样建立算法的收敛保证，而实际应用中常采用的无放回的排列采样却少有理论研究，尤其缺乏针对复杂非光滑优化问题的算法收敛分析。为了解决上述问题，本文提出了一种高效的采用近似梯度的随机近端梯度下降算法，该算法引入随机重排采样机制来提高梯度计算效率，节省计算资源。与传统的近端算法不同，本文的算法避免了在每次随机梯度下降步骤后都进行近端算子的求解，而是在遍历完所有数据后才求解一次近端算子。此外，本文还证明了在无放回随机重排采样方案下的近端梯度算法的收敛性，并指出在梯度计算和近端算子求解中都存在计算误差时，所提出的非精确随机近端梯度算法能够收敛到最优解的邻域。最后，本文将所提出的算法应用于压缩感知领域，并与其他一些流行算法进行了效率比较。(1) 本文研究了无放回的随机重排采样机制，并分别提出了精确计算的随机近端梯度算法和基于非精确的近似梯度计算的随机近端梯度算法。(2) 基于无放回随机重排采样方案的精确计算的随机近端梯度算法以O(1/T)的收敛速度收敛到最优解的邻域。收敛分析利用目标函数的Bregman散度和前向遍历偏差来解决无放回重排采样方案固有的偏梯度问题。此外，最优解收敛邻域范围随着步长的衰减而缩小。 (3) 在近端算子和梯度计算不精确或受到干扰的情况下，基于非精确近似梯度与无放回重排采样方案下的随机近端梯度算法可以以同样的收敛速率收敛到最优解的邻域。本文还建立了不精确计算误差对收敛速度分析的影响。本文所提出的算法在MNIST数据集上进行了仿真验证。其中每个图像矩阵可以被向量化成一个高维的信号向量。单观测矩阵A下的稀疏信号恢复问题是具有等式约束的l_0-范数最小化模型，本文将其重写为一个无约束的l_1-范数最小化问题。为了验证所提出的随机算法的有效性，我们将所提出的算法（PG-RR）与现有的四种流行的优化算法进行了比较，包括近端梯度算法（PG）、随机近端梯度算法（SPG）、块近端梯度算法（B-PG）和乘子交替方向法（ADMM）。本文考虑了精确无误差、衰减误差和常数误差三种情况下不同算法的性能。最后，对所提出的算法获得的恢复信号与原始真实稀疏信号进行了比较，实验结果表明我们的算法能够成功地恢复原始稀疏信号。并将对比算法用到手写体稀疏图像恢复任务中，从手写体图像恢复效果可以看出，所提出的算法具有更好的稀疏图像恢复效果。![]()
![]()
