ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 4, с. 582-598
удк 519.658
ОБ ЭФФЕКТИВНОСТИ ОДНОГО МЕТОДА РАНДОМИЗАЦИИ ЗЕРКАЛЬНОГО СПУСКА В ЗАДАЧАХ ОНЛАЙН ОПТИМИЗАЦИИ^
© 2015 г. А. В. Гасников, Ю. Е. Нестеров, В. Г. Спокойный
(141000Долгопрудный, М.о., Институтский пер., 9, МФТИ; 127051 Москва, Большой каретный пер., 19, стр. 1, ИППИ РАН; 101000 Москва, ул. Мясницкая, 20, НИУВШЭ) e-mail:gasnikov@yandex.ru; yurii.nesterov@uclouvain.be; spokoiny@wias-berlin.de Поступила в редакцию 03.09.2014 г. Переработанный вариант 29.10.2014 г.
Предлагается рандомизированная онлайн версия метода зеркального спуска. Отличие от имеющихся версий заключается в способе рандомизации. Рандомизация выводится не на этапе вычисления субградиента функции, как это повсеместно принято, а на этапе проектирования на единичный симплекс. В результате получается покомпонентный субградиентный спуск со случайным выбором компоненты, допускающий онлайн интерпретацию. Это наблюдение, например, позволило единообразно проинтерпретировать результаты о взвешивании экспертных решений и предложить наиболее эффективный способ поиска равновесия в антагонистической матричной игре с разреженной матрицей. Библ. 34.
Ключевые слова: метод зеркального спуска, метод двойственных усреднений, онлайн оптимизация, экспоненциальное взвешивание, многорукие бандиты, взвешивание экспертов, стохастическая оптимизация, рандомизация.
DOI: 10.7868/S0044466915040043
1. ВВЕДЕНИЕ
В конце 70-х годов А.С. Немировским и Д.Б. Юдиным был предложен итерационный метод решения негладких выпуклых задач оптимизации [1], который можно интерпретировать как разновидность метода проекции субградиента, когда проектирование понимается, например, в смысле расстояния Брэгмана (Кульбака—Лейблера) [2], или как прямодвойственный метод (см. [3]). Этот метод, получивший название метода зеркального спуска (МЗС), позволяет хорошо учитывать структуру множества, на котором происходит оптимизация (например, симплекса). Как и многие другие методы решения негладких выпуклых оптимизационных задач, этот метод тре-2 2 2
бует O(M R /е ) итераций, где s — точность найденного решения по функции, что соответствует нижним оценкам по s (см. [1]). Однако константа M, равномерно ограничивающая норму субградиента оптимизируемой функции, и размер множества R зависят от выбора нормы в пространстве, в котором ведется оптимизация. Так, если мы выбрали норму в нашем пространстве lp, 1 < p < да, то M есть сопряженная 1?-норма субградиента (1/p + 1/q = 1), а R2 есть "размер" множества в "метрике", сильно выпуклой относительно lp, с константой сильной выпуклости а > 1.
Замечание 1. Слово "размер" взято в кавычки, потому что в действительности то, что задается, мы интерпретируем в данном контексте как квадрат размера (физически правильнее квадратом размера назы-
2
вать R /а), поскольку "метрика" сильно выпуклая относительно нашей "рабочей" нормы в этом пространстве. Слово "метрика" взято в кавычки, потому что может быть не выполнено одно из свойств метрики — нет симметричности, например, для расстояния (дивергенции) Брэгмана.
При таких предположениях говорят, что выбранная "метрика" порождает прокс-структуру на множестве. Например, когда множество, на котором происходит оптимизация, является сим-
1) Работа выполнена при финансовой поддержке РФФИ (код проекта 14-01-00722-а), Лаборатории структурных ме-
тодов анализа данных в предсказательном моделировании МФТИ грант правительства РФ дог. 11.G34.31.0073, гранта Президента РФ № МК-5285.2013.9, исследование приложений МЗС (см. разд. 4) выполнено за счет гранта РНФ (проект № 14-50-00150).
плексом, то, как правило, выбирают p = 1, а "метрику" задают расстоянием Брэгмана (Кульба-ка—Лейблера). При этом "проекция" на симплекс согласно такому расстоянию считается по явным формулам (экспоненциальное взвешивание). В [4] была выдвинута гипотеза о том, что применительно к задачам стохастической оптимизации на единичном симплексе (не онлайн) такой
выбор нормы и расстояния являются наилучшими с точки зрения зависимости M 2R2 от размера пространства n (в типичных приложениях эта зависимость ~ln n). Однако в определенных ситу-
2 2
ациях (в задачах о многоруких бандитах, когда M R ~ n ln n) удается выиграть логарифмический по n фактор (см. ниже пример 1), более подходящим образом выбирая расстояние (см. [5]). При этом теряется возможность явного вычисления проекции.
В работах [3]—[8] исследовались стохастические (рандомизированные) версии МЗС. В том числе и онлайн (см. [5]). При этом анализировалась ситуация, когда именно градиент функции выдается оракулом со случайными шумами, но несмещенным образом. Такая релаксация детерминированного МЗС оказалась весьма полезной применительно к задачам адаптивного агрегирования оценок [4], оптимизации в пространствах огромных размеров [7], [8], задачах о многоруких бандитах и т.п. (см. [5], [9]—[11]).
В [1] была также отмечена возможность онлайн интерпретации МЗС. У разных авторов можно найти заметки на эту тему (см. [3], [5], [9], [11]—[14]). Наблюдение состоит в том, что ничего не изменится с точки зрения изучения сходимости метода (и его стохастической версии), если на каждом шаге допускать, что функция меняется, причем, возможно, враждебным образом (при этом оставаясь в классе выпуклых функций с ограниченной нормой субградиента).
В данной работе приводятся две версии стохастического онлайн МЗС. Первая версия близка к классической. Приблизительно в таком же виде ее уже можно было встретить в литературе (см. [3]—[5], [7]—[14]). Точнее говоря, предложенная версия аккумулирует в себе в виде частных случаев многие известные ранее версии МЗС. Вторая неявно была предложена в [6] применительно к поиску равновесия в антагонистической матричной игре (онлайн модификация в [6] не была затронута, равно как и связь предложенного метода с МЗС). Согласно [6], мы рандомизи-руем не на этапе вычисления субградиента функции, как это общепринято (см. [7], [8]), а на этапе проектирования на симплекс. В результате получается покомпонентный субградиентный спуск со случайным выбором компоненты, который, как будет ниже показано, допускает онлайн интерпретацию. Получив такой метод, мы расширяем множество тех задач онлайн оптимизации, к которым можно применять МЗС.
2. ОНЛАЙН МЗС СО СТОХАСТИЧЕСКИМ СУБГРАДИЕНТОМ
Рассмотрим задачу стохастической онлайн оптимизации (запись E.k[fk(x;£k)] означает, что математическое ожидание берется по £k, т.е. х и fk понимаются в такой записи не случайными)
N i n Л
1X Efx; %k)] ^ min, Sn (1) = \x > 0: £ x, = iL (1)
Nk=i xeS"(1) l ,=1 J
при следующих условиях.
Условие 1. E.^k[fk( x; £k)] — выпуклые функции (по х), для этого достаточно выпуклости по x функций fk(x; £k) и независимости распределения £k от х.
Условие 2. Существует такой вектор V xfk(x; £k), который для компактности будем называть субградиентом, хотя последнее верно не всегда (см. ниже пример 1), что
(V xfk(x; % k) - V Efx; % k)]| E k-1) = 0,
где Ek-1 есть ст-алгебра, порожденная случайными величинами 2,1,..., £k-1. Ниже везде будем использовать обозначения обычного градиента для векторов, которые мы назвали здесь субградиентами. В частности, если мы имеем дело с обычным субградиентом, то запись V xfk(x; £k) в вычислительном контексте (например, в итерационной процедуре МЗС, описанной ниже) означает какой-то его элемент (не важно какой именно), а если в контексте проверки условий
(например, ниже в условии 3), то V xfk(x; £k) пробегает все элементы субградиента (говорят также, субдифференциала).
Условие 3. |Ух/к(х;Е ) < М — (равномерно, с вероятностью 1) ограниченный субградиент.
Для справедливости части утверждений достаточно требовать одно из следующих (более слабых) условий:
а) Е..
|У х/к(х^%
< М2, б) Е.
ехр
||у /(х;^) м2
-к -1
< ехр(1).
Задача (1) является лишь компактной (и далеко не полной) записью настоящей постановки задачи стохастической онлайн оптимизации. В действительности, требуется подобрать последовательность {хк} (в разд. 2 {хк} е £„(1), а в разд. 3 и ряде примеров разд. 4 при дополнительном ограничении, что {хк} выбираются с возможными повторениями среди вершин симплекса Бп (1)) исходя из доступной исторической информации (хк может зависеть только от (х1,^1, /(•);...; хк-1,£,к-1, /к_1(-)}) так, чтобы минимизировать псевдо регрет
N N
1XЕе[/к(хк;$к)] - ш1п-1 XЕ/х;$к)]
N
к=1
или регрет
ш1п-1 Х(Л(х* ;%к) - /к (х-Лк))
В данном разделе мы сосредоточимся на минимизации псевдо регрета на основе информации (у/1(х1;%1);...; У/к _1(хк-1;^к_1)} при расчете хк. Онлайновость постановки задачи допускает, что на каждом шаге функция / может подбираться из рассматриваемого класса функций враждебно по отношению к используемому нами методу генерации последовательности {хк}. В частности, здесь / к может зависеть от (х1,^1,/(•);...;хк-1,£,к-1,/к-1( •);хк}.
В целом в данной статье мы ограничиваемся рассмотрением задач минимизации псевдо ре-грета, когда на каждом шаге мы можем получить независимую реализацию стохастического субградиента в одной указанной нами (допустимой) точке. Приведенные в статье результаты можно распространить на случай, когда градиент выдается не точно (с не случайной ошибкой), выдается не полностью (скажем, вместо градиента выдается производная по выбранному направлению) или вместо градиента выдается только значение функции (см. [14]). Немного об этом написано далее (см. ниже пример 1). Другим способом релаксации исходной постановки является возможность несколько раз обращаться на одном шаге за значением градиента функции и(или) значением самой функции и взвешивать / к(х,2,к) в (1) разными весами (см. [14], [15]). Результаты статьи также можно распространить и на случай, когда функции Е к[/к(х; ^к)] равномерно сильно выпуклые по х с константой ц (см. [5], [11], [13]). При этом выбирается евклидова прокс-структура, поскольку в сильно выпуклом случае (в стохастическом и не стохастическом) игра на выборе прокс-структуры не может дать выгоды. Неулучшаемая и достижимая оценка в этом случае будет
и
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.