Все выпуски

[ Switch to English ]

Метод эллипсоидов для задач выпуклой стохастической оптимизации малой размерности

Гладин Е.Л., Зайнуллина К.Э.
 pdf (229K)

В статье рассматривается задача минимизации математического ожидания выпуклой функции. Задачи такого вида повсеместны в машинном обучении, а также часто возникают в ряде других приложений. На практике для их решения обычно используются процедуры типа стохастического градиентного спуска (SGD). В нашей работе предлагается решать такие задачи с использованием метода эллипсоидов с мини-батчингом. Алгоритм имеет линейную скорость сходимости и может оказаться эффективнее SGD в ряде задач. Это подтверждается в наших экспериментах, исходный код которых находится в открытом доступе. Для получения линейной скорости сходимости метода не требуется ни гладкость, ни сильная выпуклость целевой функции. Таким образом, сложность алгоритма не зависит от обусловленности задачи. В работе доказывается, что метод эллипсоидов с наперед заданной вероятностью находит решение с желаемой точностью при использовании мини-батчей, размер которых пропорционален точности в степени -2. Это позволяет выполнять алгоритм параллельно на большом числе процессоров, тогда как возможности для батчараллелизации процедур типа стохастического градиентного спуска весьма ограничены. Несмотря на быструю сходимость, общее количество вычислений градиента для метода эллипсоидов может получиться больше, чем для SGD, который неплохо сходится и при маленьком размере батча. Количество итераций метода эллипсоидов квадратично зависит от размерности задачи, поэтому метод подойдет для относительно небольших размерностей.

Ключевые слова: стохастическая оптимизация, выпуклая оптимизация, метод эллипсоидов, мини-батчинг
Цитата: Гладин Е.Л., Зайнуллина К.Э. Метод эллипсоидов для задач выпуклой стохастической оптимизации малой размерности // Компьютерные исследования и моделирование, 2021, т. 13, № 6, с. 1137-1147
Citation in English: Gladin E.L., Zainullina K.E. Ellipsoid method for convex stochastic optimization in small dimension // Computer Research and Modeling, 2021, vol. 13, no. 6, pp. 1137-1147
DOI: 10.20537/2076-7633-2021-13-6-1137-1147
URL: http://crm.ics.org.ru/journal/article/3147/
Creative Commons License Статья доступна по лицензии Creative Commons Attribution-NoDerivs 3.0 Unported License.

Журнал индексируется в Scopus

Полнотекстовая версия журнала доступна также на сайте научной электронной библиотеки eLIBRARY.RU

Журнал входит в систему  Российского индекса научного цитирования.

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Международная Междисциплинарная Конференция "Математика. Компьютер. Образование"

Международная Междисциплинарная Конференция МАТЕМАТИКА. КОМПЬЮТЕР. ОБРАЗОВАНИЕ.

Copyright © 2009–2024 Институт компьютерных исследований