Стохастический градиентный спуск с предобусловленным размером шага им. Б. Т. Поляка

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Стохастический градиентный спуск (SGD) является одним из множества методов оптимизации, используемых для решения задач машинного обучения. Практичность и простота подобных методов привлекают не только исследователей, но и инженеров машинного обучения из индустрии. Однако одна из главных слабостей таких методов заключается в необходимости ручной настройки размера шага для эффективного решения каждой конкретной оптимизационной задачи, функции потерь и данных. Стохастический градиентный спуск с размером шага им. Б.Т. Поляка (SPS) – это метод, который предлагает правило обновления, не требующее точной ручной настройки размера шага для решения задачи. Цель настоящей работы – расширить SPS с помощью таких приемов предобуславливания, как методы Хатчинсона, Adam и AdaGrad, что, в свою очередь, улучшит эффективность SPS в случае с плохой обусловленностью задачи и данных. Библ. 31. Фиг. 5.

Полный текст

Доступ закрыт

Об авторах

Ф. Абдухакимов

Университет искусственного интеллекта им. Мохамеда бин Заеда

Автор, ответственный за переписку.
Email: farshed888@gmail.com
ОАЭ, Абу-Даби

Ч. Сян

Университет искусственного интеллекта им. Мохамеда бин Заеда

Email: chulu.xiang@mbzuai.ac.ae
ОАЭ, Абу-Даби

Д. Камзолов

Университет искусственного интеллекта им. Мохамеда бин Заеда

Email: kamzolov.opt@gmail.com
ОАЭ, Абу-Даби

М. Такач

Университет искусственного интеллекта им. Мохамеда бин Заеда

Email: takac.mt@gmail.com
ОАЭ, Абу-Даби

Список литературы

  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.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
2. Фиг. 1. Метод Adam vs PSPS с разным предобуславливанием для логистической регрессии на датасете mushrooms

Скачать (151KB)
3. Фиг. 2. Методы AdaGrad vs PSPS с разным предобуславливанием для логистической регрессии на датасет mushrooms

Скачать (237KB)
4. Фиг. 3. Методы Adam vs PSPS с разным предобуславливанием для логистической регрессии на датасете colon-cancer

Скачать (565KB)
5. Фиг. 4. Сравнение эффективности PSPSL1 и PSPSL2 с SPS, SGD и Adam для логистической регрессии на оригинальных и плохо обусловленных версиях датасета colon-cancer

6. Фиг. 5. Сравнение эффективности PSPSL1 и PSPSL2 с SPS, SGD и Adam для логистической регрессии на оригинальных и плохо обусловленных версиях датасета mushrooms


© Российская академия наук, 2024