在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2023, Vol. 40 ›› Issue (5): 833-842.doi: 10.3969/j.issn.1005-3085.2023.05.011

• • 上一篇    下一篇

R-线性收敛的重要样本抽样随机梯度下降算法

王福胜,  甄  娜,  李晓桐   

  1. 太原师范学院数学与统计学院，晋中 030619
  • 收稿日期:2022-08-04 接受日期:2023-02-06 出版日期:2023-10-15 发布日期:2023-12-15
  • 基金资助:
    山西省基础研究计划(自由探索类)面上项目(202103021224303)；山西省回国留学人员科研资助项目(2017-104).

R-linear Convergence of Importance Sampling Stochastic Gradient Decent Algorithm

WANG Fusheng,  ZHEN Na,  LI Xiaotong   

  1. School of Mathematics and Statistics, Taiyuan Normal University, Jinzhong 030619
  • Received:2022-08-04 Accepted:2023-02-06 Online:2023-10-15 Published:2023-12-15
  • Supported by:
    The Basic Research Plan (Free Exploration) of Shanxi Province (202103021224303); the Scientific Research Project for Returned Overseas Chinese in Shanxi Province (2017-104).

摘要：

针对机器学习中一类有限光滑凸函数和的最小化问题，提出一种新的随机方差约简梯度下降算法。新算法的特点是将随机方差约简梯度算法和一种谱梯度BB步长方法有机结合，从而可以充分发挥两种方法的优势。另外，初始步长可以任意选取，且步长在算法运行中可以自适应地计算更新。此外，新算法使用了重要样本抽样方法，可以大大减少计算工作量。最后，在通常的假设条件下证明了新算法具有R-线性收敛速度，并给出了复杂度分析。数值实验验证了新算法是可行有效的。

关键词: 机器学习, 随机梯度下降, 重要样本抽样, 线性收敛, BB步长

Abstract:

In this paper, we propose a new stochastic variance reduction gradient algorithm for minimizing the sum of a finite number of smooth convex functions in machine learning. The characteristic of the new algorithm is to combine the gradient algorithm of stochastic variance reduction and a method of spectral gradient BB step size, so that the advantages of the two methods can be fully utilized. In addition, the new algorithm uses the important sample sampling method, which can greatly reduce the computation workload. In the end, it is proved that the new algorithm has R-linear convergence rate under the usual assumptions, and the complexity analysis is given. Numerical experiments show that the new algorithm is feasible and effective.

Key words: machine learning, stochastic gradient decent, importance sampling, linear convergence, BB step size

中图分类号: