Stochastic Gradient Descent with Pre-Conditioned Polyak Step-Size

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

Stochastic Gradient Descent (SGD) is one of the many iterative optimization methods that are widely used in solving machine learning problems. These methods display valuable properties and attract researchers and industrial machine learning engineers with their simplicity. However, one of the weaknesses of this type of methods is the necessity to tune learning rate (step-size) for every loss function and dataset combination to solve an optimization problem and get an efficient performance in a given time budget. Stochastic Gradient Descent with Polyak Step-size (SPS) is a method that offers an update rule that alleviates the need of fine-tuning the learning rate of an optimizer. In this paper, we propose an extension of SPS that employs preconditioning techniques, such as Hutchinson’s method, Adam, and AdaGrad, to improve its performance on badly scaled and/or ill-conditioned datasets.

Full Text

Restricted Access

About the authors

F. Abdukhakimov

Mohamed bin Zayed University of Artificial Intelligence

Author for correspondence.
Email: farshed888@gmail.com
United Arab Emirates, Abu Dhabi

Ch. Xiang

Mohamed bin Zayed University of Artificial Intelligence

Email: chulu.xiang@mbzuai.ac.ae
United Arab Emirates, Abu Dhabi

D. Kamzolov

Mohamed bin Zayed University of Artificial Intelligence

Email: kamzolov.opt@gmail.com
United Arab Emirates, Abu Dhabi

M. Takáč

Mohamed bin Zayed University of Artificial Intelligence

Email: takac.mt@gmail.com
United Arab Emirates, Abu Dhabi

References

  1. Bekas C., Kokiopoulou E., Saad Y. An estimator for the diagonal of a matrix // Appl. Numer. Math. 2007. V. 57. № 11. P. 1214—1229.
  2. Berrada L., Zisserman A., Kumar M. P. Training neural networks for and by interpolation. In Hal Daum´e III and Aarti Singh, eds. // Proceed. 37th Inter. Conf. Mach. Learn. 2020. V. 119. P. 799—809.
  3. Boyd S., Xiao L., Mutapcic A. Subgradient methods. lecture notes of EE392o, Stanford Univer., Autumn Quarter. 2023. V. 2004. P. 2004—2005.
  4. Christianson B. Automatic Hessians by reverse accumulation // IMA J. Numer. Analys. 1992. V. 12. № 2. P. 135—150.
  5. Duchi J., Hazan E., Singer Y. Adaptive subgradient methods for online learning and stochastic optimization // J. Mach. Learn. Res. 2011. V. 12. № 61. P. 2121—2159.
  6. Garrigos G., Gower R. M., Schaipp F. Function value learning: Adaptive learning rates based on the polyak stepsize and function splitting in erm // arXiv preprint arXiv:2307.14528, 2023.
  7. Gower R.M., Blondel M., Gazagnadou N., Pedregosa F. Cutting some slack for sgd with adaptive polyak stepsizes // arXiv preprint arXiv:2202.12328, 2022.
  8. Hutchinson M.F. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines // Comm. in Statistics-Simulation and Computat. 1989. V. 18. № 3. P. 1059—1076.
  9. Jahani M., Rusakov S., Shi Zh., Richt´arik P., Mahoney M. W., Tak´aˇc M. Doubly adaptive scaled algorithm for machine learning using second-order information // In 10th Inter. Conf. Learn. Representat. (ICLR2022), 2022.
  10. Jiang X., Stich S. U. Adaptive sgd with polyak stepsize and line-search: Robust convergence and variance reduction // arXiv preprint arXiv:2308.06058, 2023.
  11. Kingma D., Ba J. Adam: A method for stochastic optimization // Inter. Conf. Learn. Representat. (ICLR), San Diego, CA, USA, 2015.
  12. Lan G. An optimal method for stochastic composite optimization // Math. Program. 2012. V. 133. P. 365—397.
  13. Li Sh., Swartworth W. J., Tak´aˇc M., Needell D., Gower R. M. SP2: A second order stochastic polyak method // 11th Inter. Conf. on Learn. Representat., 2023.
  14. Li X., Orabona F. On the convergence of stochastic gradient descent with adaptive stepsizes. In Kamalika Chaudhuri and Masashi Sugiyama, eds. // Proceed. 22nd Inter. Conf. Artific. Intelligence and Statistic. 2019. V. 89. P. 983—992.
  15. Loizou N., Vaswani Sh., Laradji I. H., Lacoste-Julien S. Stochastic polyak step-size for sgd: An adaptive learning rate for fast convergence. In Arindam Banerjee and Kenji Fukumizu, eds. // Proceed. 24th Inter. Conf. Artific. Intelligence and Statistic. 2021. V. 130. P. 1306—1314.
  16. Loshchilov I., Hutter F. Decoupled weight decay regularization // Inter. Conf. Learn. Representat., 2019.
  17. Nemirovski A., Juditsky A., Lan G., Shapiro A. Robust stochastic approximation approach to stochastic programming // SIAM J. Optimizat. 2009. V. 19. № 4. P. 1574—1609.
  18. Orvieto A., Lacoste-Julien S., Loizou N. Dynamics of sgd with stochastic polyak stepsizes: Truly adaptive variants and convergence to exact solution. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, eds. // Adv. Neural Informat. Proces. System. 2022. V. 35. P. 26943—26954.
  19. Polyak B.T., Juditsky A. B. Acceleration of stochastic approximation by averaging.
  20. SIAM J. Control and Optimizat. 1992. V. 30. № 4. P. 838—855.
  21. Polyak B. T. Minimization of unsmooth functionals // USSR Comput. Math. and Math. Phys. 1969. V. 9. P. 14—29.
  22. Polyak B. T. Introduction to optimization. Optimization Software, Inc., Publ. Division, 1987.
  23. Polyak B.T. A new method of stochastic approximation type // Avtomatika i Telemekhanika. 1990. V. 51. P. 98—107.
  24. Reddi S.J., Kale S., Kumar S. On the convergence of adam and beyond // Inter. Conf. Learn. Representat., 2018.
  25. Robbins H., Monro S. A stochastic approximation method // Ann. Math. Statistic. 1951. V. 22. P. 400—407.
  26. Sadiev A., Beznosikov A., Almansoori A. J., Kamzolov D., Tappenden R., Tak´aˇc M. Stochastic gradient methods with preconditioned updates // arXiv preprint arXiv:2206.00285, 2022.
  27. Schaipp F., Gower R. M., Ulbrich M. A stochastic proximal polyak step size // arXiv preprint arXiv:2301.04935, 2023.
  28. Schaipp F., Ohana R., Eickenberg M., Defazio A., Gower R. M. Momo: Momentum models for adaptive learning rates // arXiv preprint arXiv:2305.07583, 2023.
  29. Shi Zh., Sadiev A., Loizou N., Richt´arik P., Tak´aˇc M. AI-SARAH: Adaptive and implicit stochastic recursive gradient methods // Transact. Mach. Learn. Res., 2023.
  30. Tieleman T., Hinton G., et al. Lecture 6.5-rmsprop: Divide the gradient by a running average of its recent magnitude // COURSERA: Neural Networks for Machine Learn. 2012. V. 4. № 2. P. 26—31.
  31. Ward R., Wu X., Bottou L. Adagrad stepsizes: Sharp convergence over nonconvex landscapes // J. Mach. Learn. Res. 2020. V. 21. № 1. P. 9047—9076.
  32. Yao Zh., Gholami A., Shen Sh., Mustafa M., Keutzer K., Mahoney M. Adahessian: An adaptive second order optimizer for machine learning // Proceed. AAAI Conf. Artific. Intelligence. 2021. V. 35. P. 10665—10673.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download
2. Fig. 1. Adam vs PSPS method with different preconditioning for logistic regression on the mushrooms dataset

Download (151KB)
Indexing metadata
3. Fig. 2. AdaGrad vs PSPS methods with different preconditioning for logistic regression on the mushrooms dataset

Download (237KB)
Indexing metadata
4. Fig. 3. Adam vs PSPS methods with different preconditioning for logistic regression on the colon-cancer dataset

Download (565KB)
Indexing metadata
5. Fig. 4. Comparison of the performance of PSPSL1 and PSPSL2 with SPS, SGD and Adam for logistic regression on original and ill-conditioned versions of the colon-cancer dataset

Download (1MB)
Indexing metadata
6. Fig. 5. Performance comparison of PSPSL1 and PSPSL2 with SPS, SGD and Adam for logistic regression on original and ill-conditioned versions of the mushrooms dataset

Download (1MB)
Indexing metadata

Copyright (c) 2024 Russian Academy of Sciences