Аннотация:
Метод зеркального спуска (МЗС) известен с конца 70-х годов [1] как существенное обобщение стандартного градиентного метода. В частности, он позволяет получать робастные алгоритмы выпуклой оптимизации градиентного типа в пространствах большой размерности, когда обычные градиентные алгоритмы уже не работают. Исходная идея состоит в осуществлении градиентного движения в сопряженном (двойственном) пространстве и отображении получаемой траектории в исходное пространство.
Занятие построено по следующей схеме.
1. Краткое введение. Идея МЗС (в непрерывном времени) и некоторые его свойства.
Роль преобразования Лежандра, функции Ляпунова, дополнительное усреднение траектории исходного пространства. Оценка скорости сходимости по оптимизируемой функции. Некоторые выводы.
2. Общие понятия, объекты и конструкции: исходная и двойственная норма в, прокси-функция на заданном выпуклом компакте и ее сопряженная (преобразование Лежандра-Фенхеля), их свойства (при условии сильной выпуклости). Два примера: 1) «евклидовый» случай, 2) энтропия на стандартном симплексе и потециал Гиббса.
3. Выпуклая задача стохастической оптимизации (и ее детерминированный случай). Стохастический субградиент и алгоритм ЗС, его верхняя граница (скорость сходимости).
4. Приложение МЗС к следующим задачам:
1) оценивание главного вектора стохастической матрицы,
2) PageRank и робастный вариант,
3) многорукий бандит.
5. Заключение.
Обратная связь: