关键词: 随机梯度下降, 方差缩减, 凸优化, 非凸优化, 收敛速率

Abstract: The stochastic gradient descent (SGD) algorithms have been applied to machine learning and deep learning due to their superior performance. However, SGD requires the stochastic gradient of a single sample to approximate the full gradient of all samples, introducing additional variance in each iteration. This makes the convergence curve of SGD oscillate or even diverge. Therefore, effectively reducing variance becomes a key challenge at present. To address the above challenge, a variance reduction optimization algorithm, DM-SRG (double mini-batch stochastic recursive gradient), based on mini-batch random sampling is proposed and applied to solving convex and non-convex optimization problems. The main feature of the algorithm including an inner and outer double loop structure is designed: the outer loop structure uses a mini-batch random samples to calculate the gradient, approximating the full gradient and reducing the gradient calculation cost; the inter loop structure also uses a mini-batch random samples to calculate the gradient, and replacing the single sample random gradient and improving convergence stability of the algorithm. In this paper, a sublinear convergence rate of DM-SRG algorithm is theoretically guaranteed for both non-convex and convex objective functions. The effectiveness of the algorithm is evaluated via numerical simulation experiments on real datasets of varying sizes. The experimental results show that the loss function of the DM-SRG algorithm is reduced by 18.1%, and the average time of the algorithm is reduced by 8.22%.

Key words: stochastic gradient descent, variance reduction, convex optimization, non-convex optimization, convergence rate