Параллельные алгоритмы и оценки вероятностей больших уклонений в задачах стохастической выпуклой оптимизации
П.Е. Двуреченский1,2, А.В. Гасников2,3, А.А. Лагуновская3
1Институт прикладного анализа и стохастики им. К. Вейерштрасса, Моренштрассе, 39, Берлин, Германия, 10117
pavel.dvurechensky@wias-berlin.de
2Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, Большой Каретный пер., 19, строение 1, Москва, 127051
gasnikov.av@mipt.ru
3Московский физико-технический институт, Институтский пер., 9, Долгопрудный, Московская обл., 141700
a.lagunovskaya@phystech.edu
Ключевые слова: стохастическая выпуклая оптимизация, оценки вероятностей больших уклонений, метод зеркального спуска, параллельные алгоритмы, stochastic convex optimization, probability of large deviation, mirror descent, parallel algorithm
Страницы: 47-53
Аннотация
В этом коротком сообщении рассматриваются задачи выпуклой стохастической оптимизации при различных предположениях о свойствах стохастических субградиентов. Известно, что если вычислителю доступно значение целевой функции задачи, то можно параллельно вычислить несколько независимых приближений к решению задачи в терминах сходимости по математическому ожиданию. Выбрав приближение с наименьшим значением функции, можно контролировать вероятности больших уклонений невязки по значению функции. В данной работе рассматривается случай, когда значение целевой функции недоступно или требует большого объема вычислений. В предположении субгауссовости распределения стохастических субградиентов, а также в общем случае при умеренном уровне вероятности больших уклонений показано, что параллельное вычисление нескольких приближенных решений с последующим усреднением дает те же оценки вероятностей больших уклонений невязки по функции, что и вычисление одного приближенного решения, но с большим числом итераций. Тем самым в рассматриваемом случае параллельные вычисления позволяют получить решение того же качества, но за меньшее время.
DOI: 10.15372/SJNM20180103 |
