A Limited-Memory Quasi-Newton Optimization Method with Parallel Computing Capability

Sadeghi-Lotfabadi, Ashkan; Ghiasi-Shirazi, Kamaledin

doi:10.22055/jamm.2025.48314.2330

A Limited-Memory Quasi-Newton Optimization Method with Parallel Computing Capability

Document Type : Original Paper

Authors

Ashkan Sadeghi-Lotfabadi ¹

Kamaledin Ghiasi-Shirazi ²

¹ Computer Engineering Department,, Engineering Faculty, Ferdowsi University of Mashhad, Mashhad

² Department of Computer Engineering, Engineering Faculty, Ferdowsi University of Mashhad, Mashhad, Iran

10.22055/jamm.2025.48314.2330

Abstract

Newton's method is considered preferable due to its higher accuracy compared to first-order methods in approximating the target function; however, it requires the explicit computation of the Hessian matrix. On the other hand, quasi-Newton methods are popular among researchers because they don't require directly calculating the Hessian matrix.
Here, we propose a quasi-Newton method designed to achieve high computational speed while accurately approximating the Hessian. Our approach views the Hessian matrix from an operational perspective.
From the operational perspective, a matrix acts as an operator that transforms an input vector into an output vector. Following this approach, the Hessian matrix takes a gradient vector as input and generates an output vector accordingly. Our method is designed to perform calculations in parallel, enabling high execution speed. Moreover, our method is specifically designed to operate efficiently with limited memory, making it well-suited for large-scale problems. Our experimental results indicate that the proposed method is faster than the quasi-Newton L-BFGS method. For instance, in applications such as quadratic optimization problems, our method demonstrates a significant performance improvement, executing approximately ten times faster than L-BFGS. Furthermore, in problems involving a large number of variables, our method is more computationally efficient than BFGS.

Keywords

Quasi-Newton

L-BFGS

operator

low-rank approximation

Subjects

Control and Optimization

[1] Nocedal, J. and Wright, S. J., 2006. Numerical optimization. 2nd ed. New York: Springer. doi:
10.1007/978-0-387-40065-5
[2] Broyden, C. G., 1970. The convergence of a class of double-rank minimization algorithms 1. general
considerations. IMA Journal of Applied Mathematics, 6(1), pp. 76-90. doi: 10.1093/imamat/6.1.76
[3] Fletcher, R., 1970. A new approach to variable metric algorithms. The Computer Journal, 13(3), pp.
317-322. doi: 10.1093/comjnl/13.3.317
[4] Goldfarb, D., 1970. A family of variable-metric methods derived by variational means. Mathematics
of Computation, 24(109), pp. 23-26. doi: 10.2307/2004873
[5] Shanno, D. F., 1970. Conditioning of quasi-Newton methods for function minimization. Mathematics
of Computation, 24(111), pp. 647-656. doi: 10.2307/2004840
[6] Nocedal, J., 1980. Updating quasi-Newton matrices with limited storage. Mathematics of Computation, 35(151), pp. 773-782. doi: 10.2307/2006193
[7] Liu, D. C. and Nocedal, J., 1989. On the limited memory BFGS method for large scale optimization.
Mathematical Programming, 45(1), pp. 503-528. doi: 10.1007/BF01589116
[8] Mokhtari, A. and Ribeiro, A., 2020. Stochastic Quasi-Newton Methods. Proceedings of The IEEE,
108(11), pp. 1906-1922. doi: 10.1109/JPROC.2020.3023660
[9] Moritz, P., Nishihara, R. and Jordan, M., 2016. A linearly-convergent stochastic L-BFGS algorithm.
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, pp. 249-258.

[10] Xie, Y., Byrd, R. H. and Nocedal, J., 2020. Analysis of the BFGS method with errors. SIAM Journal
on Optimization, 30(1), pp. 182-209. doi: 10.1137/19M1240794
[11] Bordes, A., Bottou, L. and Gallinari, P., 2009. SGD-QN: Careful quasi-Newton stochastic gradient
descent. Journal of Machine Learning Research, 10, pp. 1737-1754. doi: 10.5555/1577069.1755842
[12] Mokhtari, A. and Ribeiro, A., 2014. RES: Regularized stochastic BFGS algorithm. IEEE Transactions on Signal Processing, 62(23), pp. 6089-6104. doi: 10.1109/TSP.2014.2357775
[13] Gao, W. and Goldfarb, D., 2019. Quasi-Newton methods: superlinear convergence without line
searches for self-concordant functions. Optimization Methods and Software, 34(1), pp. 194-217. doi:
10.1080/10556788.2018.1510927
[14] Rodomanov, A. and Nesterov, Y., 2021. Greedy quasi-Newton methods with explicit superlinear
convergence. SIAM Journal on Optimization, 31(1), pp. 785-811. doi: 10.1137/20M1320651
[15] Rodomanov, A. and Nesterov, Y., 2022. Rates of superlinear convergence for classical quasi-Newton
methods. Mathematical Programming, pp. 1-32. doi: 10.1007/s10107-021-01622-5
[16] Schraudolph, N. N., Yu, J. and Günter, S., 2007, March. A stochastic quasi-Newton method for online
convex optimization. Proceedings of the 11th International Conference on Artificial Intelligence and
Statistics, (pp. 436-443).
[17] Mokhtari, A., Gurbuzbalaban, M. and Ribeiro, A., 2018. Surpassing gradient descent provably: A
cyclic incremental method with linear convergence rate. SIAM Journal on Optimization, 28(2), pp.
1420-1447. doi: 10.1137/16M1101702
[18] Johnson, R. and Zhang, T., 2013. Accelerating stochastic gradient descent using predictive variance
reduction. Advances in Neural Information Processing Systems, 26, pp. 315-323.
[19] Schmidt, M., Le roux, N. and Bach, F., 2017. Minimizing finite sums with the stochastic average
gradient. Mathematical Programming, 162, pp. 83-112. doi: 10.1007/s10107-016-1030-6
[20] Chang, D., Sun, S. and Zhang, C., 2019. An Accelerated Linearly Convergent Stochastic L-BFGS
Algorithm. IEEE Transactions on Neural Networks and Learning Systems, 30(11), pp. 3338-3346. doi:
10.1109/TNNLS.2019.2891088
[21] Wang, X., Ma, S., Goldfarb, D. and Liu, W., 2017. Stochastic quasi-Newton methods for
nonconvex stochastic optimization. SIAM Journal on Optimization, 27(2), pp. 927-956. doi:
10.1137/15M1053141
[22] Chen, H., Wu, H. C., Chan, S. C. and Lam, W. H., 2020. A Stochastic Quasi-Newton Method for
Large-Scale Nonconvex Optimization with Applications. IEEE Transactions on Neural Networks and
Learning Systems, 31(11), pp. 4776-4790. doi: 10.1109/TNNLS.2019.2957843
[23] Mokhtari, A., Eisen, M. and Ribeiro, A., 2018a. IQN: An incremental quasi-Newton method
with local superlinear convergence rate. SIAM Journal on Optimization, 28(2), pp. 1670-1698. doi:
10.1137/17M1122943
[24] Javad ebadi, M., Fahs, A., Fahs, H. and Dehghani, R., 2023. Competitive secant (BFGS) methods
based on modified secant relations for unconstrained optimization. Optimization, 72(7), pp. 1691-
1706. doi: 10.1080/02331934.2022.2048381

[25] Gao, Z., Koppel, A. and Ribeiro, A., 2020. Incremental greedy BFGS: An incremental quasi-Newton
method with explicit superlinear rate. Proceedings of the 12th OPT Workshop on Optimization for
Machine Learning, Advances in Neural Information Processing Systems, (p. 47).
[26] Gower, R., Goldfarb, D. and Richtárik, P., 2016, June. Stochastic block BFGS: Squeezing more
curvature out of data. In Proceedings of the 33rd International Conference on Machine Learning, (pp.
1869-1878).
[27] Brust, J. J., Marcia, R. F., Petra, C. G. and Saunders, M. A., 2022. Large-scale optimization with linear
equality constraints using reduced compact representation. SIAM Journal on Scientific Computing,
44(1), pp. A103-A127. doi: 10.1137/21M1393819
[28] Jalilzadeh, A., Nedić, A., Shanbhag, U. V. and Yousefian, F., 2022. A variable sample-size stochastic quasi-Newton method for smooth and nonsmooth stochastic convex optimization. Mathematics of
Operations Research, 47(1), pp. 690-719. doi: 10.1109/CDC.2018.8619209
[29] Rafati, J. and Marica, R. F., 2020. Quasi-Newton Optimization Methods for Deep Learning Applications. Deep Learning Applications, pp. 9-38. doi: 10.1007/978-981-15-1816-4_2
[30] Goldfarb, D., Ren, Y. and Bahamou, A., 2020. Practical quasi-Newton methods for training deep
neural networks. Advances in Neural Information Processing Systems, 33, pp. 2386-2396.
[31] Berahas, A. S., Nocedal, J. and Takac, M., 2016. A multi-batch L-BFGS method for machine learning.
Advances in Neural Information Processing Systems, 29, pp. 1063-1071.
[32] Yang, M., Milzarek, A., Wen, Z. and Zhang, T., 2022. A stochastic extra-step quasi-Newton method
for nonsmooth nonconvex optimization. Mathematical Programming, pp. 1-47. doi: 10.1007/s10107-
021-01629-y
[33] Indrapriyadarsini, S., Mahboubi, S., Ninomiya, H. and Asai, H., 2019, September. A Stochastic Quasi-Newton Method with Nesterov’s Accelerated Gradient. In Joint European Conference on
Machine Learning and Knowledge Discovery in Databases (pp. 743-760). doi: 10.1007/978-3-030-
46150-8_43
[34] Yousefian, F., Nedic, A. and Shanbhag, U. V., 2020. On stochastic and deterministic quasi-Newton
methods for nonstrongly convex optimization: Asymptotic convergence and rate analysis. SIAM Journal on Optimization, 30(2), pp. 1144-1172. doi: 10.1137/17M1152474
[35] Boggs, P. T. and Byrd, R. H., 2019. Adaptive, limited-memory BFGS algorithms for unconstrained
optimization.SIAM Journal on Optimization, 29(2), pp. 1282-1299. doi: 10.1137/16M1065100
[36] Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga,
L. and Lerer, A., 2017. Automatic differentiation in pytorch. Advances in Neural Information Processing Systems, pp. 8024–8035.