In this paper, we study large-scale unconstrained nonconvex stochastic optimization problems, in which only noisy gradient information is accessible through a stochastic first-order oracle. We develop a stochastic quasi-Newton framework that combines modified secant curvature pairs with a damping strategy and limited-memory Broyden–Fletcher–Goldfarb–Shanno (BFGS) updates. To further enhance both convergence behavior and empirical performance, the proposed method incorporates variance reduction together with a momentum acceleration mechanism, yielding an efficient stochastic quasi-Newton algorithm suitable for large-scale learning tasks. Under standard smoothness and sampling assumptions, we establish convergence to an $ \varepsilon $-first-order stationary point and show that the method attains a stochastic first-order oracle complexity of $ O\!\left(n^{2/3} \varepsilon^{-2}\right) $. Numerical experiments on several large-scale datasets corroborate the effectiveness of our approach, showing that the proposed algorithm performs well on classification problems relative to representative stochastic first-order methods and typical stochastic second-order methods.
Citation: Runmin Wang, Jing Gao, Yuchang Zhang, Xiaoyu Fu, Wenwen Wang. A variance-reduced stochastic quasi-Newton method with momentum for large-scale nonconvex stochastic optimization[J]. AIMS Mathematics, 2026, 11(11): 37548-37584. doi: 10.3934/math.20261453
In this paper, we study large-scale unconstrained nonconvex stochastic optimization problems, in which only noisy gradient information is accessible through a stochastic first-order oracle. We develop a stochastic quasi-Newton framework that combines modified secant curvature pairs with a damping strategy and limited-memory Broyden–Fletcher–Goldfarb–Shanno (BFGS) updates. To further enhance both convergence behavior and empirical performance, the proposed method incorporates variance reduction together with a momentum acceleration mechanism, yielding an efficient stochastic quasi-Newton algorithm suitable for large-scale learning tasks. Under standard smoothness and sampling assumptions, we establish convergence to an $ \varepsilon $-first-order stationary point and show that the method attains a stochastic first-order oracle complexity of $ O\!\left(n^{2/3} \varepsilon^{-2}\right) $. Numerical experiments on several large-scale datasets corroborate the effectiveness of our approach, showing that the proposed algorithm performs well on classification problems relative to representative stochastic first-order methods and typical stochastic second-order methods.
| [1] |
X. Tian, Z. Tian, S. F. A. Khatib, Y. Wang, Machine learning in internet financial risk management: A systematic literature review, PLoS ONE, 19 (2024), e0300195. https://doi.org/10.1371/journal.pone.0300195 doi: 10.1371/journal.pone.0300195
|
| [2] |
L. Wang, E. Demeulemeester, Simulation optimization in healthcare resource planning: A literature review, IISE Trans., 55 (2023), 985–1007. https://doi.org/10.1080/24725854.2022.2147606 doi: 10.1080/24725854.2022.2147606
|
| [3] |
X. Sui, H. Yan, S. Pan, X. Li, X. Gu, Bus system optimization for timetables, routes, charging, and facilities: A summary, Digit. Transp. Saf., 4 (2025), 1–9. https://doi.org/10.48130/dts-0024-0024 doi: 10.48130/dts-0024-0024
|
| [4] |
H. Robbins, S. Monro, A stochastic approximation method, Ann. Math. Statist., 22 (1951), 400–407. |
| [5] |
S. Ghadimi, G. Lan, Stochastic first- and zeroth-order methods for nonconvex stochastic programming, SIAM J. Optim., 23 (2013), 2341–2368. https://doi.org/10.1137/120880811 doi: 10.1137/120880811
|
| [6] |
B. T. Polyak, A. B. Juditsky, Acceleration of stochastic approximation by averaging, SIAM J. Control Optim., 30 (1992), 838–855. https://doi.org/10.1137/0330046 doi: 10.1137/0330046
|
| [7] |
T. Xiao, G. Yang, A convergence study of SGD-type methods for stochastic optimization, Numer. Math. Theory Methods Appl., 16 (2023), 914–930. https://doi.org/10.4208/nmtma.oa-2022-0179 doi: 10.4208/nmtma.oa-2022-0179
|
| [8] |
L. Bottou, F. E. Curtis, J. Nocedal, Optimization methods for large-scale machine learning, SIAM Rev., 60 (2018), 223–311. https://doi.org/10.1137/16M1080173 doi: 10.1137/16M1080173
|
| [9] |
L. Bottou, Stochastic gradient descent tricks, In: Neural Networks: Tricks of the Trade, 2 Eds., Berlin, Heidelberg: Springer, 2012. http://doi.org/10.1007/978-3-642-35289-8_25 |
| [10] |
A. Nemirovski, A. Juditsky, G. Lan, A. Shapiro, Robust stochastic approximation approach to stochastic programming, SIAM J. Optim., 19 (2009), 1574–1609. https://doi.org/10.1137/070704277 doi: 10.1137/070704277
|
| [11] |
R. L. Karandikar, M. Vidyasagar, Convergence rates for stochastic approximation: Biased noise with unbounded variance, and applications, J. Optim. Theory Appl., 203 (2024), 2412–2450. https://doi.org/10.1007/s10957-024-02547-7 doi: 10.1007/s10957-024-02547-7
|
| [12] |
L. Madden, E. Dall'Anese, S. Becker, High probability convergence bounds for non-convex stochastic gradient descent with sub-Weibull noise, J. Mach. Learn. Res., 25 (2024), 1–36. |
| [13] |
B. T. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math. Phys., 4 (1964), 1–17. https://doi.org/10.1016/0041-5553(64)90137-5 doi: 10.1016/0041-5553(64)90137-5
|
| [14] |
I. Sutskever, J. Martens, G. E. Dahl, G. E. Hinton, On the importance of initialization and momentum in deep learning, In: International Conference on Machine Learning, 2013, 1139–1147. |
| [15] |
X. Li, Z. Yang, Y. Wang, Stochastic gradient accelerated by negative momentum for training deep neural networks, Appl. Intell., 55 (2025), 970. https://doi.org/10.1007/s10489-025-06900-9 doi: 10.1007/s10489-025-06900-9
|
| [16] |
J. Duchi, E. Hazan, Y. Singer, Adaptive subgradient methods for online learning and stochastic optimization, J. Mach. Learn. Res., 12 (2011), 2121–2159. |
| [17] |
D. P. Kingma, J. Ba, Adam: A method for stochastic optimization, In: 3rd International Conference on Learning Representations, San Diego, USA, Conference Track Proceedings, 2015. https://doi.org/10.48550/arXiv.1412.6980 |
| [18] |
C. Fang, C. J. Li, Z. Lin, T. Zhang, SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator, In: Advances in Neural Information Processing Systems, 31 (2018), 689–699. |
| [19] |
R. Johnson, T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction, In: Neural Information Processing Systems, 26 (2013), 315–323. |
| [20] |
L. M. Nguyen, J. Liu, K. Scheinberg, M. Takáč, SARAH: A novel method for machine learning problems using stochastic recursive gradient, In: Proceedings of the 34th International Conference on Machine Learning, 70 (2017), 2613–2621. |
| [21] |
C. Traoré, V. Apidopoulos, S. Salzo, S. Villa, Variance reduction techniques for stochastic proximal point algorithms, J. Optim. Theory Appl., 203 (2024), 1910–1939. https://doi.org/10.1007/s10957-024-02502-6 doi: 10.1007/s10957-024-02502-6
|
| [22] |
B. Recht, C. Ré, S. J. Wright, F. Niu, HOGWILD!: A lock-free approach to parallelizing stochastic gradient descent, In: Neural Information Processing Systems, 2011. |
| [23] |
J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, et al., Large scale distributed deep networks, In: Neural Information Processing Systems, 2012. |
| [24] |
R. H. Byrd, S. L. Hansen, J. Nocedal, Y. Singer, A stochastic quasi-Newton method for large-scale optimization, SIAM J. Optim., 26 (2016), 1008–1031. https://doi.org/10.1137/140954362 doi: 10.1137/140954362
|
| [25] |
P. Moritz, R. Nishihara, M. I. Jordan, A linearly-convergent stochastic L-BFGS algorithm, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 51 (2016), 249–258. |
| [26] |
R. Bollapragada, J. Nocedal, D. Mudigere, H. J. M. Shi, P. T. P. Tang, A progressive batching L-BFGS method for machine learning, In: Proceedings of the 35th International Conference on Machine Learning, 80 (2018), 620–629. |
| [27] |
A. Mokhtari, A. Ribeiro, RES: Regularized stochastic BFGS algorithm, IEEE Trans. Signal Process., 62 (2014), 6089–6104. https://doi.org/10.1109/tsp.2014.2357775 doi: 10.1109/tsp.2014.2357775
|
| [28] |
D. Goldfarb, Y. Ren, A. Bahamou, Practical quasi-Newton methods for training deep neural networks, In: Advances in Neural Information Processing Systems, 2020. |
| [29] |
H. J. Mao, S. Xie, Y. Xie, R. Byrd, J. Nocedal, A noise-tolerant quasi-Newton algorithm for unconstrained optimization, SIAM J. Optim., 32 (2022), 29–55. https://doi.org/10.1137/20m1373190 doi: 10.1137/20m1373190
|
| [30] |
X. Wang, S. Ma, D. Goldfarb, W. Liu, Stochastic quasi-Newton methods for nonconvex stochastic optimization, SIAM J. Optim., 27 (2017), 927–956. https://doi.org/10.1137/15M1053141 doi: 10.1137/15M1053141
|
| [31] |
H. Chen, H. C. Wu, S. C. Chan, W. H. Lam, A stochastic quasi-Newton method for large-scale nonconvex optimization with applications, IEEE Trans. Neural Netw. Learn. Syst., 31 (2020), 4776–4790. https://doi.org/10.1109/TNNLS.2019.2957843 doi: 10.1109/TNNLS.2019.2957843
|
| [32] |
Q. Zhang, F. Huang, C. Deng, H. Huang, Faster stochastic quasi-Newton methods, IEEE Trans. Neural Netw. Learn. Syst., 33 (2022), 4388–4397. https://doi.org/10.1109/TNNLS.2021.3056947 doi: 10.1109/TNNLS.2021.3056947
|
| [33] |
Y. Cheng, J. Gao, An efficient augmented memoryless quasi-Newton method for solving large-scale unconstrained optimization problems, AIMS Math., 9 (2024), 25232–25252. https://doi.org./10.3934/math.20241231 doi: 10.3934/math.20241231
|
| [34] |
D. Makmuang, S. Suppalap, R. Wangkeeree, The regularized stochastic Nesterov's accelerated quasi-Newton method with applications, J. Comput. Appl. Math., 428 (2023), 115190. https://doi.org/10.1016/j.cam.2023.115190 doi: 10.1016/j.cam.2023.115190
|
| [35] |
C. J. Hillar, L. H. Lim, Most tensor problems are NP-hard, J. ACM, 60 (2013), 45. https://doi.org/10.1145/2512329 doi: 10.1145/2512329
|
| [36] |
S. J. Reddi, A. Hefny, S. Sra, B. Póczos, A. Smola, Stochastic variance reduction for nonconvex optimization, In: Proceedings of The 33rd International Conference on Machine Learning, 48 (2016), 314–323. |
| [37] |
C. G. Broyden, The convergence of a class of double-rank minimization algorithms, IMA J. Appl. Math., 6 (1970), 76–90. https://doi.org/10.1093/imamat/6.1.76 doi: 10.1093/imamat/6.1.76
|
| [38] |
R. Fletcher, A new approach to variable metric algorithms, Comput. J., 13 (1970), 317–322. https://doi.org/10.1093/comjnl/13.3.317 doi: 10.1093/comjnl/13.3.317
|
| [39] |
D. Goldfarb, A family of variable-metric methods derived by variational means, Math. Comp., 24 (1970), 23–26. |
| [40] |
D. F. Shanno, Conditioning of quasi-Newton methods for function minimization, Math. Comp., 24 (1970), 647–656. |
| [41] |
Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, New York, NY: Springer, 2013. http://doi.org/10.1007/978-1-4419-8853-9 |
| [42] |
Z. Allen-Zhu, Katyusha: The first direct acceleration of stochastic gradient methods, J. Mach. Learn. Res., 18 (2018), 1–51. |
| [43] |
S. J. Reddi, S. Sra, B. Póczos, A. Smola, Fast incremental method for smooth nonconvex optimization, In: 2016 IEEE 55th Conference on Decision and Control (CDC), IEEE, 2016, 1971–1977. https://doi.org/10.1109/CDC.2016.7798553 |
Parameter sensitivity of M-SMdLBFGS-VR on the a6a and a7a data sets
Parameter sensitivity of M-SMdLBFGS-VR on the w8a and realsim data sets
Parameter sensitivity of M-SMdLBFGS-VR on the covtype and Synthetic data sets
Comparison of the five algorithms on the a6a and a7a data sets
Comparison of the five algorithms on the w8a and realsim data sets
Comparison of the five algorithms on the covtype and Synthetic data sets
Performance of the four variants on the a6a and a7a data sets
Performance of the four variants on the w8a and realsim data sets
Performance of the four variants on the covtype and Synthetic data sets
Parameter sensitivity of M-SMdLBFGS-VR on the a6a and a7a data sets
Parameter sensitivity of M-SMdLBFGS-VR on the w8a and realsim data sets
Parameter sensitivity of M-SMdLBFGS-VR on the covtype and Synthetic data sets
Comparison of the five algorithms on the a6a and a7a data sets
Comparison of the five algorithms on the w8a and realsim data sets
Comparison of the five algorithms on the covtype and Synthetic data sets
Comparison of the algorithms on the a6a and a7a data sets
Comparison of the algorithms on the w8a and realsim data sets
Comparison of the algorithms on the covtype and Synthetic data sets