مجله مدل‌سازی پیشرفته ریاضی

مجله مدل‌سازی پیشرفته ریاضی

ارائه ی یک روش بهینه سازی شبه نیوتون با حافظه ی محدود و قابلیت اجرا به صورت موازی

نوع مقاله : مقاله پژوهشی

نویسندگان
1 گروه مهندسی کامپیوتر، دانشکده مهندسی، دانشگاه فردوسی مشهد، مشهد
2 گروه مهندسی کامپیوتر، دانشکده مهندسی، دانشگاه فردوسی مشهد، مشهد، ایران
چکیده
روش نیوتن به‌دلیل دقت بالاتر نسبت به روش‌های مرتبه اول در تقریب تابع هدف، گزینه‌ای مطلوب محسوب می‌شود؛ با این حال، نیاز به محاسبه صریح ماتریس هسی دارد. در مقابل، روش‌های شبه‌نیوتن به‌دلیل بی‌نیازی از محاسبه صریح ماتریس هسی همواره مورد توجه پژوهشگران بوده‌اند.
هدف ما در اینجا ارائه یک روش شبه نیوتن است به طوری که بتواند در عین تقریب هسی به صورت مناسب، سرعت بالایی هم داشته باشد. روش ما از دید عملگری به ماتریس هسی نگاه می‌کند. طبق دیدگاه عملگری، ماتریس مانند یک عملگر خطی است که یک بردار ورودی دریافت و یک بردار در خروجی به دست می‌دهد. هسی نیز طبق این دیدگاه یک بردار گرادیان را دریافت و یک بردار در خروجی به دست می‌دهد. در روش ما هسی نه به صورت صریح، بلکه به‌صورت تقریب رتبه پایین و به‌وسیله‌ی یک سری بردار و عدد نمایش داده می‌شود. روش ما قابلیت انجام محاسبات به صورت موازی را دارد و به همین دلیل سرعت اجرای بالایی دارد. علاوه بر این، روش ما توانایی کار با حافظه محدود را دارد. نتایج به دست آمده نیز نشان می‌دهد که روش ارائه شده، نسبت به روش شبه نیوتن L-BFGS سرعت بیشتری دارد. همچنین در مسائلی که تعداد زیادی متغیر دارند، روش ما نسبت به BFGS از کارایی محاسباتی بیشتری برخوردار است.
کلیدواژه‌ها
موضوعات

عنوان مقاله English

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

نویسندگان English

Ashkan Sadeghi-Lotfabadi 1
Kamaledin Ghiasi-Shirazi 2
1 Computer Engineering Department,, Engineering Faculty, Ferdowsi University of Mashhad, Mashhad
2 Department of Computer Engineering, Engineering Faculty, Ferdowsi University of Mashhad, Mashhad, Iran
چکیده English

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.

کلیدواژه‌ها English

Quasi-Newton
L-BFGS
operator
low-rank approximation
[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.

فایل‌های تکمیلی/اضافی

  • تاریخ دریافت 27 آبان 1403
  • تاریخ بازنگری 01 اردیبهشت 1404
  • تاریخ پذیرش 07 خرداد 1404