Введение в выпуклую оптимизацию

Программа курса: 

Разделы и темы лекционных занятий

Содержание

1

Элементы выпуклого анализа. Введение в выпуклую оптимизацию. Краткий обзор задач и методов. Примеры.

Введение: выпуклые множества и функции. Задача выпуклой оптимизации (в n-мерном пространстве). Примеры: машинное обучение, классификация с учителем, регрессия.

Элементы выпуклого анализа: теоремы о разделении, об опорной гиперплоскости, определение и существование субградиента. Условия оптимальности 1-го порядка.

Модель черного ящика. Понятия об оракуле, его сложности, о методе оптимизации и его сложности. Краткий обзор методов и результатов. 

2

Метод центров тяжести и метод эллипсоидов: свойства и сложность. Градиентный метод.

Метод центра тяжести. Доказательство верхней границы. Сложность метода.

Метод эллипсоидов, его свойства и сложность. Градиентный метод.

3

Прямо-двойственный подход и метод зеркального спуска (МЗС) для задач стохастической и детерминированной оптимизации.

Прямо-двойственный подход к задачам выпуклой оптимизации. Идея метода зеркального спуска (МЗС). Параметры метода: исходная и двойственная нормы, потенциал отображения сопряженного пространства и условие Липшица на градиент. Примеры (с доказательствами).

Задача выпуклой стохастической оптимизации на заданном компакте с оракулом 1-го порядка. МЗС и его анализ. Понятие прокси-функции, преобразование Лежандра-Фенхеля. Параметр сильной выпуклости. Связь МЗС с методом стохастической аппроксимации.

Частный случай параметров МЗС; полностью рекуррентный алгоритм ЗС (АЗС), его верхняя граница и сложность. Доказательства.

Адаптивный АЗС (по обобщенной температуре), его верхняя граница и сложность. Другие варианты прямо-двойственных методов. Обсуждение. МЗС с инерцией.

4

Верхние и нижние (информационные) границы методов оптимизации. Их вывод и обоснование.

Подробное изучение нижних и верхних границ методов зеркального спуска в задачах выпуклой оптимизации, в частности, для задачи о стохастическом многоруком бандите. 

5

Минимаксные выпукло-вогнутые задачи, их решение на основе МЗС.

Рассмотрение задачи PageRank как минимаксную выпукло-вогнутую задачу и ее решение на основе МЗС. Обобщение на выпукло-вогнутые стохастические задачи.

6

Применение МЗС к задачам о многоруком бандите, PageRank, бинарной классификации с учителем и др.

Задача о стохастическом многоруком бандите. Применение оптимизационного подхода и МЗС. Получение верхней границы. Сравнение с известной информационной  нижней границей. Задача PageRank как оценивание главного собственного вектора стохастической матрицы. Сведение к задаче выпуклой оптимизации и применение МЗС.

Задача бинарной классификации с учителем: применение МЗС для минимизации ошибки классификации на выпуклой оболочке «простых» правил разделения.

Перечень контрольных вопросов:

1. Определения выпуклого множества и выпуклой функции; строго выпуклые множества и функции; сильно выпуклые функции.

2. Задача выпуклой оптимизации на заданном множестве в конечномерном пространстве. Формулировка задач машинного обучения, бинарной классификации с учителем и линейной регрессии как задач выпуклой оптимизации. Возможные варианты этих задач: Support Vector Machines (SVM) и Hinge Loss в классификации, МНК, гребневая регрессия и LASSO для регрессии. 

3. Формулировка теоремы о разделении и теоремы об опорной гиперплоскости. Определение субградиента; соответствующая теорема о существовании и доказательство. Важность задач выпуклой оптимизации. Условия оптимальности 1-го порядка.

4. Понятие черного ящика и оракула. Порядок оракула. Понятие метода оптимизации. Сложность оракула и метода; понятие о дефекте метода (регрет). О структурной оптимизации. Краткий обзор методов и результатов выпуклой оптимизации.

5. Формулировка метода центров тяжести. Исходные предположения о задаче и оракуле. Теорема о дефекте метода (о верхней границе); доказательство с использованием леммы Грюнбаума. Сложность метода и его реализуемость.

6. Лемма об отсечении эллипсоида плоскостью, проходящей через его центр. Метод эллипсоидов, его свойства: сложность и трудоемкость.

7. Понятие о методе зеркального спуска (МЗС) в непрерывном времени. Исходное и сопряженное векторные пространства в R^n, исходная и двойственная нормы, потенциальное гладкое отображение сопряженного пространства grad W и условие Липшица (на градиент потенциала grad W). Пример с евклидовыми нормами и квадратичным потенциалом, приводящий МЗС к стандартному субградиентному методу.

8. Задача выпуклой стохастической оптимизации на заданном компакте с оракулом градиентного типа. МЗС в дискретном времени и его анализ.

9. Преобразование Лежандра-Фенхеля. Параметр обобщенной температуры.  Определение прокси-функции V, ее связь с потенциальным отображением сопряженного пространства на допустимое множество. Параметр сильной выпуклости прокси-функции и связь с условием Липшица на grad W.

10. Пример оптимизации на стандартном симплексе. Прокси-функция энтропийного типа, ее свойства выпуклости по отношению к норме в l_1; соответствующее преобразование Лежандра-Фенхеля (с параметром обобщенной температуры) и прямое обоснование условия Липшица на градиент.

11. Выбор последовательностей коэффициента усиления и обобщенной температуры: частный случай параметров МЗС; полностью рекуррентный алгоритм ЗС (АЗС), доказательство его верхней границы (дефекта), сложность и трудоемкость АЗС. Обобщение метода как прямо-двойственный. Пример оптимизации на заданном евклидовом шаре с квадратичной прокси-функцией: АЗС как алгоритм проекции субградиента.

12. Адаптивный АЗС (по обобщенной температуре и при постоянном коэффициенте усиления). Условие о равномерно ограниченной норме субградиента минимизируемой функции почти наверное. Теорема о верхней границе, доказательство. Сравнение с нижней границей Немировского-Юдина (без доказательства). Сложность АЗС. Другие варианты прямо-двойственных алгоритмов.

13. Стохастическая задача о многоруком бандите. Применение оптимизационного подхода и алгоритма ЗС с целью синтеза рандомизированной стратегии, минимизирующей функцию средних потерь. Получение верхней границы (дефекта функции потерь). Сравнение с известной информационной нижней границей (Auer et al., 2002) без доказательства.

14. Задача PageRank как задача оценивания главного собственного вектора стохастической матрицы. Сведение к задаче выпуклой стохастической оптимизации с оракулом градиентного типа. Применение МЗС с прокси функцией энтропийного типа. Рандомизированные АЗС.

15. Сведение PageRank к минимаксной выпукло-вогнутой стохастической задаче с оракулом градиентного типа. Применение МЗС.

16. Задача бинарной классификации с учителем, сведение к задаче выпуклой стохастической оптимизации на стандартном симплексе. Понятие и примеры функций фи-риска: экспоненциальные, используемые в SVM, и логит-потери. 

Перечень рекомендуемой литературы:

Основная литература:

1. Ю.Е. Нестеров. Введение в выпуклую оптимизацию. М.: МЦНМО, 2010.

2. А.С. Немировский. Методы зеркального спуска. Седьмая Традиционная молодежная школа "Управление, информация и оптимизация". 16 июня 2015 г. Солнечногорск (Московская область). http://www.mathnet.ru/php/presentation.phtml?option_lang=rus&presentid=11950

3. Б.Т. Поляк. Введение в оптимизацию. Изд. стереотип. URSS. 2019. - 392 с. ISBN 978-5-9710-6133-5.

Дополнительная литература:

4. Beck, A. and Teboulle, M., Mirror Descent and Nonlinear Projected Subgradient Methods for Convex Optimization, Oper. Research Letters, 2003, vol. 31, no. 3, pp. 167–175. 

5. Bubeck S., Convex Optimization: Algorithms and Complexity. Foundations and Trends ® in Machine Learning, vol. 8, no. 3-4, pp. 231–357, 2015. http://dx.doi.org/10.1561/2200000050

6. N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.

7. А. Б. Юдицкий, А. В. Назин, А. Б. Цыбаков, Н. Ваятис. Рекуррентное агрегирование оценок методом зеркального спуска с усреднением // Пробл. передачи информ., 41:4 (2005), c. 78–96.

8. А.В. Назин, Б.Т. Поляк. Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank // Автомат. и телемех., 2011, вып. 2, c. 131–141.

9. А. В. Назин. Алгоритмы инерционного зеркального спуска в выпуклых задачах стохастической оптимизации // Автомат. и телемех., 2018, вып. 1,  с. 100–112.