求解一类非光滑凸优化问题的相对加速SGD算法

Relatively accelerated stochastic gradient algorithm for a class of non-smooth convex optimization problem

一阶优化算法由于其计算简单、代价小,被广泛应用于机器学习、大数据科学、计算机视觉等领域,然而,现有的一阶算法大多要求目标函数具有Lipschitz连续梯度,而实际中的很多应用问题不满足该要求。在经典的梯度下降算法基础上,引入随机和加速,提出一种相对加速随机梯度下降算法。该算法不要求目标函数具有Lipschitz连续梯度,而是通过将欧氏距离推广为Bregman距离,从而将Lipschitz连续梯度条件减弱为相对光滑性条件。相对加速随机梯度下降算法的收敛性与一致三角尺度指数有关,为避免调节最优一致三角尺度指数参数的工作量,给出一种自适应相对加速随机梯度下降算法。该算法可自适应地选取一致三角尺度指数参数。对算法收敛性的理论分析表明,算法迭代序列的目标函数值收敛于最优目标函数值。针对Possion反问题和目标函数的Hessian阵算子范数随变量范数多项式增长的极小化问题的数值实验表明,自适应相对加速随机梯度下降算法和相对加速随机梯度下降算法的收敛性能优于相对随机梯度下降算法。

The first order method is widely used in the fields such as machine learning,big data science,computer vision,etc.A crucial and standard assumption for almost all first order methods is that the gradient of the objective function has to be globally Lipschitz continuous,which,however,can’t be satisfied by a lot of practical problems.By introducing stochasticity and acceleration to the vanilla GD(Gradient Descent)algorithm,a RASGD(Relatively Accelerated Stochastic Gradient Descent)algorithm is developed,and a wild relatively smooth condition rather than the gradient Lipschitz is needed to be satisfied by the objective function.The convergence of the RASGD is related to the UTSE(Uniformly Triangle Scaling Exponent).To avoid the cost of tuning this parameter,a ARASGD(Adaptively Relatively Accelerated Stochastic Gradient Descent)algorithm is further proposed.The theoretical convergence analysis shows that the objective function values of the iterates converge to the optimal value.Numerical experiments are conducted on the Poisson inverse problem and the minimization problem with the operator norm of Hessian of the objective function growing as a polynomial in variable norm,and the results show that the convergence performance of the ARASGD method and RASGD method is better than that of the RSGD method.