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

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».