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

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

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, и логит-потери.