|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
ЧИСЛЕННЫЕ МЕТОДЫ И ОСНОВЫ ИХ РЕАЛИЗАЦИИ
Метод эллипсоидов для задач выпуклой стохастической оптимизации малой размерности
Е. Л. Гладинabc, К. Э. Зайнуллинаa a Национальный исследовательский университет «Московский физико-технический институт»,
Россия, 141701, Московская облаcть, г. Долгопрудный, Институтский пер., д. 9
b Институт проблем передачи информации РАН,
Россия, 127051, г. Москва, Б. Каретный пер., д. 9
c Сколковский институт науки и технологий,
Россия, 121205, г. Москва, Большой бульвар, д. 30, с. 1
Аннотация:
В статье рассматривается задача минимизации математического ожидания выпуклой функции. Задачи такого вида повсеместны в машинном обучении, а также часто возникают в ряде других приложений. На практике для их решения обычно используются процедуры типа стохастического градиентного спуска(SGD). В нашей работе предлагается решать такие задачи с использованием метода эллипсоидов с мини-батчингом. Алгоритм имеет линейную скорость сходимости и может оказаться эффективнее SGD в ряде задач. Это подтверждается в наших экспериментах, исходный код которых находится в открытом доступе. Для получения линейной скорости сходимости метода не требуется ни гладкость, ни сильная выпуклость целевой функции. Таким образом, сложность алгоритма не зависит от обусловленности задачи. В работе доказывается, что метод эллипсоидов с наперед заданной вероятностью находит решение с желаемой точностью при использовании мини-батчей, размер которых пропорционален точности в степени -2. Это позволяет выполнять алгоритм параллельно на большом числе процессоров, тогда как возможности для батч-параллелизации процедур типа стохастического градиентного спуска весьма ограничены. Несмотря на быструю сходимость, общее количество вычислений градиента для метода эллипсоидов может получиться больше, чем для SGD, который неплохо сходится и при маленьком размере батча. Количество итераций метода эллипсоидов квадратично зависит от размерности задачи, поэтому метод подойдет для относительно небольших размерностей.
Ключевые слова:
стохастическая оптимизация, выпуклая оптимизация, метод эллипсоидов, мини-батчинг.
Поступила в редакцию: 09.11.2020 Исправленный вариант: 15.11.2021 Принята в печать: 16.11.2021
Образец цитирования:
Е. Л. Гладин, К. Э. Зайнуллина, “Метод эллипсоидов для задач выпуклой стохастической оптимизации малой размерности”, Компьютерные исследования и моделирование, 13:6 (2021), 1137–1147
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/crm940 https://www.mathnet.ru/rus/crm/v13/i6/p1137
|
Статистика просмотров: |
Страница аннотации: | 103 | PDF полного текста: | 35 | Список литературы: | 28 |
|