Delivered at:: Big Data and Information Retrieval School

Course type:: Compulsory course

When:: 3 year, 3, 4 module

Instructors

Gadetsky, Artyom

Kodryan, Maxim

Kropotov, Dmitry

Полная версия программы учебной дисциплины

Аннотация

Методы оптимизации лежат в основе решения многих задач компьютерных наук. Например, в машинном обучении задачу оптимизации необходимо решать каждый раз при настройке какой-то модели алгоритмов по данным, причём от эффективности решения соответствующей задачи оптимизации зависит практическая применимость самого метода машинного обучения. Данный курс посвящен изучению классических и современных методов решения задач непрерывной оптимизации (в том числе невыпуклых), а также особенностям применения этих методов в задачах оптимизации, возникающих в машинном обучении. Основной акцент в изложении делается на практические аспекты реализации и использования методов. Целью курса является выработка у слушателей навыков по подбору подходящего метода для своей задачи, наиболее полно учитывающего её особенности.

Цель освоения дисциплины

Освоение классических и современных численных методов решения задач непрерывной оптимизации
Освоение основных математических результатов из теории непрерывной оптимизации
Выработка практических навыков реализации численных методов оптимизации

Содержание учебной дисциплины

Понятие о численных методах оптимизации
Понятие о численных методах оптимизации. Метод градиентного спуска. Сложность задач оптимизации. Сильно выпуклые задачи, выпуклые (вырожденные) задачи, невыпуклые задачи. Гладкие, негладкие задачи. Регуляризация и рестарты. О возможности вычислять градиент и автоматическом дифференцировании. Приложение к задаче оптимального управления.
Невыпуклая оптимизация
Невыпуклая оптимизация. Условие Поляка-Лоясиевича (ПЛ) и глобальная сходимость градиентного спуска. Пример: сведение решение системы нелинейных уравнений к задаче оптимизации с условием ПЛ. Сходимость градиентного спуска к локальному экстремуму. Принцип множителей Лагранжа и теорема о неявной функции. Выпуклая оптимизация. Принцип множителей Лагранжа и теорема об отделимости точки от выпуклого множества гиперплоскостью (без доказательства).
Унимодальные функции одной переменной
Унимодальные функции одной переменной. Методы одномерной минимизации (метод дихотомии, метод золотого сечения, метод Фибоначчи). Задача о распределении ресурсов. Методы маломерной оптимизации: метод центров тяжести, метод эллипсоидов.
Слабая и сильная двойственность для задач выпуклой оптимизации
Двойственная задача. Слабая и сильная двойственность для задач выпуклой оптимизации. Теорема о минмаксе (Фон Неймана, Сион-Какутани) (без доказательства). Седловые задачи. Коническая двойственность. Теоремы об альтернативах (Фаркаш) и их следствия (основная теорема финансовой математики об отсутствии арбитража; робастная оптимизация). Понятие о прямо-двойственных методах на примере решение задачи минимизации выпуклого сепарабельного функционала с аффинными ограничениями с помощью перехода к двойственной задаче и ее решения методом градиентного спуска.
Задачи оптимизации на множествах простой структуры
Задачи оптимизации на множествах простой структуры. Дивергенция Брэгмана. Метод проекции (суб-)градиента, метод зеркального спуска. Метод условного градиента (Франк-Вульфа). Пример задачи минимизации квадратичной формы с разреженной положительно определенной матрицей на единичном симплексе.
Способы выбора шага в методах
Способы выбора шага в методах. Наискорейший спуск. Правило Армихо и правило Голдстейна. Адаптивный способ выбора шага. Сопряженные направления. Метод сопряженных градиентов для минимизации квадратичных функций. Метод сопряженных градиентов для решения задач выпуклой оптимизации. Метод тяжелого шарика Поляка. Ускоренный градиентный метод (в разных вариантах: линейный каплинг, метод подобных треугольников). Новый ускоренный градиентный метод (на базе метода линейного каплинга) с одномерными минимизациями.
Концепция (неточной) модели функции
Концепция (неточной) модели функции. Композитная оптимизация. Универсальный градиентный спуск и его ускоренный вариант. Проксимальный градиентный спуск. Ускоренный проксимальный метод (в варианте Монтейро-Свайтера). Каталист - общий способ ускорения различных неускоренных методов.
Метод Ньютона
Метод Ньютона. Квазиньютоновские методы (LBFGS). Метод Ньютона с кубической регуляризацией. Тензорные методы. Ускоренные тензорные методы.
Стохастическая оптимизация
Стохастическая оптимизация. Минибатчинг и распараллеливание. Рандомизированные методы на примере покомпонентных и безградиентных методов. Задача минимизации суммы функций.
Общая схема метода штрафных функций
Общая схема метода штрафных функций. Метод модифицированной функции Лагранжа. Методы внутренней точки. Понятие самосогласованного барьера. Методы параметризации целевых функций. Методы отслеживания центральной траектории.
Распределенная оптимизация
Распределенная оптимизация на примере решения задач выпуклой оптимизации функционалов вида суммы функций.

Элементы контроля

Самостоятельные работы
СР
Домашние задания
ДЗ
Экзамен
Письменный экзамен (Э) на 90 минут.
Контрольная работа
КР
Проект
ПР

Промежуточная аттестация

Промежуточная аттестация (4 модуль)
Общая оценка за курс вычисляется по правилу Округление_вверх(0.7*<Оценка_за_семестр> + 0.3*<Оценка_за_экзамен>). <Оценка_за_семестр> = min(10, <Суммарная_оценка_за_задания>*10 / <Максимальная_суммарная_оценка_за_задания_без_бонусов>). Итоговая оценка за курс совпадает с общей оценкой при соблюдении следующих дополнительных условий: >=8 — Сданы все задания, кроме одного (на оценку >=4), экзамен сдан на оценку >= 6 >=6 — Сданы все задания, кроме двух (на оценку >=4), экзамен сдан на оценку >= 4 >=4 — Сданы все задания, кроме трех (на оценку >=4), экзамен сдан на оценку >= 4

Bachelor’s Programme 'Applied Mathematics and Information Science'

Optimization in Machine Learning

Instructors

Программа дисциплины

Аннотация

Цель освоения дисциплины

Содержание учебной дисциплины

Элементы контроля

Промежуточная аттестация

Список литературы

Рекомендуемая основная литература

Рекомендуемая дополнительная литература