Непрерывная оптимизация (МОП)/2020 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показано 37 промежуточных версии 4 участников)
Строка 5: Строка 5:
  
 
{| class="wikitable"
 
{| class="wikitable"
  ! Группа !! Расписание !! Инвайт для anytask
+
  ! Группа !! Расписание !! Ссылка на zoom !! Инвайт для anytask
 
  |-
 
  |-
  | 171 || понедельник, лекция в 18:10, семинар в 19:40, ауд. см. в [https://ruz.hse.ru РУЗ] || align="center"|gQHw1vz
+
  | 171 || понедельник, лекция в 18:10, семинар в 19:40 || align="center"|https://zoom.us/j/531942418 || align="center"|gQHw1vz
 
  |-
 
  |-
  | 172 || понедельник, лекция в 18:10, семинар в 19:40, ауд. см. в [https://ruz.hse.ru РУЗ] || align="center"|0iPflMg
+
  | 172 || понедельник, лекция в 18:10, семинар в 19:40 || align="center"|https://zoom.us/j/531942418 || align="center"|0iPflMg
 
  |}
 
  |}
  
 
Группа в Telegram для вопросов по курсу: [https://t.me/joinchat/CHLEHhWx4Rzq5f1m8Cy6cQ ссылка]
 
Группа в Telegram для вопросов по курсу: [https://t.me/joinchat/CHLEHhWx4Rzq5f1m8Cy6cQ ссылка]
  
Таблица с оценками по курсу: ??
+
Таблица с оценками по курсу: [https://docs.google.com/spreadsheets/d/1JrxkcB19unvWXJ6ZOgmbJ3hUY3hABJqV5uLhAXspApA/edit?usp=sharing ссылка]
 +
 
 +
Записи занятий в zoom: [https://www.youtube.com/playlist?list=PLEwK9wdS5g0pRd8haE1NGph34yBUUHvUV ссылка]
 +
 
 +
== Экзамен ==
 +
 
 +
Процедура экзамена, а также список билетов/вопросов находится [https://drive.google.com/file/d/1zsRsu0-czj7MYGOGCI-oNEkQAEhy0Huz/view?usp=sharing здесь].
 +
 
 +
Примеры заданий что могут быть выданы на экзамене: [https://drive.google.com/file/d/1QnOEtC0LgqV5xrAYRxCsSXyPfp-IqF5p/view?usp=sharing link].
 +
 
 +
Распределение студентов по времени сдачи экзамена: [https://docs.google.com/spreadsheets/d/1U_uxwr1s_aCWFBkulwKKz8sSkrhFVrsoqChd8i8clZ8/edit?usp=sharing ссылка].
 +
 
 +
Консультация к экзамену, а также проверка технической готовности состоится 25 июня в 14-00. [https://youtu.be/s95mGMfxXQY видео]
  
 
== Система выставления оценок по курсу ==
 
== Система выставления оценок по курсу ==
Строка 24: Строка 36:
 
  |align="center"|>=8 || Сданы все задания, кроме одного теоретического задания (на оценку >=4), экзамен сдан на оценку >= 6
 
  |align="center"|>=8 || Сданы все задания, кроме одного теоретического задания (на оценку >=4), экзамен сдан на оценку >= 6
 
  |-
 
  |-
  |align="center"|>=6 || Сданы все задания, кроме трех (на оценку >=4), экзамен сдан на оценку >= 4
+
  |align="center"|>=6 || Сданы все задания, кроме двух (на оценку >=4), экзамен сдан на оценку >= 4
 
  |-
 
  |-
  |align="center"|>=4 || Сданы все задания, кроме пяти (на оценку >=4), экзамен сдан на оценку >= 4
+
  |align="center"|>=4 || Сданы все задания, кроме трех (на оценку >=4), экзамен сдан на оценку >= 4
 
  |-
 
  |-
 
  |}
 
  |}
Строка 36: Строка 48:
  
 
== Теоретические ДЗ ==  
 
== Теоретические ДЗ ==  
 +
 +
Задание 1. [https://drive.google.com/open?id=1wmwhCqFBjIfeMSS6VJJYHfDMBC_NGNzh Выпуклые множества и функции]. Срок сдачи - 14 марта (суббота), 23:59.
 +
 +
Задание 2. [https://drive.google.com/open?id=1VAJA_no969xvp5x7CkoZ9JXmg6u9W-jD Условия Каруша--Куна--Таккера. Двойственность.] Срок сдачи - 20 мая (среда), 23.59.
 +
 +
Дополнительное задание. [https://drive.google.com/file/d/1je4tv40idB3FqjcIU6QlwaXV7GGki6KR/view?usp=sharing Сопряжённые функции, субдифференциалы, проксимальные операторы]. Срок сдачи (мягкий=жёсткий) 23 июня (вторник), 23:59
 +
 
== Практические ДЗ ==
 
== Практические ДЗ ==
  
 
Задание 1. [https://github.com/JeanPaulShapo/hse20-opt-course/blob/d16d202bfa7b97ea82bcc44fe7d08464f2ad23ed/task1/practice1.pdf Методы градиентного спуска и Ньютона]. Срок сдачи - 3 марта (вторник), 23:59.
 
Задание 1. [https://github.com/JeanPaulShapo/hse20-opt-course/blob/d16d202bfa7b97ea82bcc44fe7d08464f2ad23ed/task1/practice1.pdf Методы градиентного спуска и Ньютона]. Срок сдачи - 3 марта (вторник), 23:59.
 +
 +
Задание 2. [https://github.com/JeanPaulShapo/hse20-opt-course/blob/016c3ee13b87c0178323272148e0cb2d4812e4b0/task2/practice2.pdf Продвинутые методы безусловной оптимизации]. Срок сдачи - 27 марта (пятница), 23:59.
 +
 +
Задание 3. [https://github.com/JeanPaulShapo/hse20-opt-course/blob/c50d4e4bfdd8b53648b26ef49956ee31b0bf718a/task3/practice3.pdf Метод барьеров]. Срок сдачи - 23 мая (суббота), 23:59.
 +
 +
Задание 4. [https://github.com/JeanPaulShapo/hse20-opt-course/blob/6d6ecdc59641113455d58068c56b49d3f4779371/task4/practice4.pdf Композитная оптимизация]. Срок сдачи - 9 июня (вторник) 23:59.
  
 
== Лекции ==
 
== Лекции ==
Строка 54: Строка 79:
 
| align="center"|2
 
| align="center"|2
 
| 20 января 2020
 
| 20 января 2020
| Одномерная оптимизация. ||  
+
| Одномерная оптимизация. || [http://www.machinelearning.ru/wiki/images/4/4d/MOMO16_min1d.pdf Конспект]
 
|-
 
|-
 
| align="center"|3
 
| align="center"|3
Строка 71: Строка 96:
 
| 17 февраля 2020
 
| 17 февраля 2020
 
| Безгессианный метод Ньютона. Разностное дифференцирование. ||  
 
| Безгессианный метод Ньютона. Разностное дифференцирование. ||  
 +
|-
 +
| align="center"|7
 +
| 2 марта 2020
 +
| Квазиньютоновские методы оптимизации ||
 +
|-
 +
| align="center"|8
 +
| 16 марта 2020
 +
| Условия Каруша-Куна-Таккера для условной оптимизации ||
 +
|-
 +
| align="center"|9
 +
| 6 апреля 2020
 +
| Двойственные задачи, симплекс-метод для линейного программирования || [https://youtu.be/J3ZFXVX0st4 видео]
 +
|-
 +
| align="center"|10
 +
| 13 апреля 2020
 +
| Метод Ньютона и логарифмических барьеров для выпуклых задач условной оптимизации || [https://youtu.be/1NyS4b61nQo видео]
 +
|-
 +
| align="center"|11
 +
| 20 апреля 2020
 +
| Негладкая оптимизация. Субградиентный метод. || [https://youtu.be/uxGcpOhLvpM видео]
 +
|-
 +
| align="center"|12
 +
| 27 апреля 2020
 +
| Проксимальный градиентный метод || [https://youtu.be/O6X46icwVUI видео]
 +
|-
 +
| align="center"|13
 +
| 18 мая 2020
 +
| Стохастическая оптимизация || [https://youtu.be/dTa55W-kgjc видео 1] [https://youtu.be/RmYcby79V3s видео 2]
 +
|-
 +
| align="center"|14
 +
| 25 мая 2020
 +
| Риманова оптимизация || [https://youtu.be/nT4FruWbjRI видео]
 +
|-
 +
| align="center"|15
 +
| 01 июня 2020
 +
| Решение задач оптимизации с помощью нейронных сетей || [https://youtu.be/x1BVFRZrs58 видео]<br> [https://arxiv.org/abs/1606.04474 Статья 1]<br> [https://arxiv.org/abs/1803.08475 Статья 2]
 
|-
 
|-
 
|}
 
|}
Строка 105: Строка 166:
 
| 17&nbsp;февраля&nbsp;2020
 
| 17&nbsp;февраля&nbsp;2020
 
| Выпуклые функции. || [https://drive.google.com/file/d/1m0IIMRwO-sIe-nhmys0B47ZjLHfIxZ98/view?usp=sharing Конспект]
 
| Выпуклые функции. || [https://drive.google.com/file/d/1m0IIMRwO-sIe-nhmys0B47ZjLHfIxZ98/view?usp=sharing Конспект]
 +
|-
 +
| align="center"|7
 +
| 2&nbsp;марта&nbsp;2020
 +
| Матричные преобразования в квазиньютоновских методах || [https://drive.google.com/file/d/1zlqaDmb84kfZ67BmiMinOKfYCeq68VKO/view?usp=sharing Конспект]
 +
|-
 +
| align="center"|8
 +
| 16&nbsp;марта&nbsp;2020
 +
| Задачи условной оптимизации || [https://yadi.sk/d/Op-nmGrl02lLnQ Конспекты]
 +
|-
 +
| align="center"|9
 +
| 6&nbsp;апреля&nbsp;2020
 +
| Двойственные задачи, эквивалентные преобразования задач || [https://youtu.be/lRaWpJ8bTok видео] [https://drive.google.com/file/d/1GXgex6RrwWv_wGBh4oYLpUcWD5-Yc3UM/view?usp=sharing Конспект]
 +
|-
 +
| align="center"|10
 +
| 13&nbsp;апреля&nbsp;2020
 +
| Преобразование задач к стандартному виду || [https://youtu.be/F0eOsHLqDAU видео] [https://drive.google.com/file/d/1GXgex6RrwWv_wGBh4oYLpUcWD5-Yc3UM/view?usp=sharing Конспект]
 +
|-
 +
| align="center"|11
 +
| 20&nbsp;апреля&nbsp;2020
 +
| Субдифференциальное исчисление || [https://youtu.be/vl2qJw5E95U видео] [https://drive.google.com/file/d/175GWh8qsMg6rVO_xkjDvWbmRG_ALzIbm/view?usp=sharing Конспект]
 +
|-
 +
| align="center"|12
 +
| 27&nbsp;апреля&nbsp;2020
 +
| Проекции и проксимальные операторы || [https://youtu.be/LDUj7gq8Ty0 видео] [https://drive.google.com/file/d/1U7HbVIoK4KlrZSlioERfJ1g8rvAGSxhS/view?usp=sharing Заметки с семинара]
 +
|-
 +
| align="center"|13
 +
| 18&nbsp;мая&nbsp;2020
 +
| Сопряженные функции и нормы || [https://youtu.be/LxsJxOt6xYk видео] [http://www.machinelearning.ru/wiki/images/c/cb/MOMO20_Conjugate.pdf Конспект]
 +
|-
 +
| align="center"|14
 +
| 1&nbsp;июня&nbsp;2020
 +
| Решение задач дискретной оптимизации непрерывными методами || [https://youtu.be/lCCdoEla_7s видео] <br>[https://drive.google.com/file/d/1iEXeHGZ-3gdCT7hcHreOGlBAc1tTZgE8/view?usp=sharing Презентация]
 
|-
 
|-
 
|}
 
|}

Текущая версия на 15:40, 25 июня 2020

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

Преподаватели: Кропотов Дмитрий Александрович, Гадецкий Артём, Шаповалов Никита, Таскынов Ануар, Гринберг Вадим, Бобров Евгений.

Группа Расписание Ссылка на zoom Инвайт для anytask
171 понедельник, лекция в 18:10, семинар в 19:40 https://zoom.us/j/531942418 gQHw1vz
172 понедельник, лекция в 18:10, семинар в 19:40 https://zoom.us/j/531942418 0iPflMg

Группа в Telegram для вопросов по курсу: ссылка

Таблица с оценками по курсу: ссылка

Записи занятий в zoom: ссылка

Экзамен

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

Примеры заданий что могут быть выданы на экзамене: link.

Распределение студентов по времени сдачи экзамена: ссылка.

Консультация к экзамену, а также проверка технической готовности состоится 25 июня в 14-00. видео

Система выставления оценок по курсу

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

Итоговая оценка Условия
>=8 Сданы все задания, кроме одного теоретического задания (на оценку >=4), экзамен сдан на оценку >= 6
>=6 Сданы все задания, кроме двух (на оценку >=4), экзамен сдан на оценку >= 4
>=4 Сданы все задания, кроме трех (на оценку >=4), экзамен сдан на оценку >= 4

Правила сдачи заданий

Теоретические и практические задания сдаются в систему anytask (инвайт см. выше). Эти задания могут быть присланы после срока сдачи, но с задержкой не более одной недели. При этом начисляется штраф из расчёта 0.5 балла в день. Все задания выполняются самостоятельно. Если задание выполнялось сообща или использовались какие-либо сторонние коды и материалы, то об этом должно быть написано в отчёте. В противном случае «похожие» решения считаются плагиатом и все задействованные студенты (в том числе те, у кого списали) будут сурово наказаны.

Теоретические задания сдаются в anytask в виде сканов или набранных в TeX pdf-файлов. ВАЖНО! Присылаемые сканы должны быть высокого качества, присылаться одним файлом, в котором все листы идут в правильном порядке. В случае плохого качества сканов или же сдачи в формате, отличном от pdf, проверяющий имеет право поставить за работу 0, не проверяя.

Теоретические ДЗ

Задание 1. Выпуклые множества и функции. Срок сдачи - 14 марта (суббота), 23:59.

Задание 2. Условия Каруша--Куна--Таккера. Двойственность. Срок сдачи - 20 мая (среда), 23.59.

Дополнительное задание. Сопряжённые функции, субдифференциалы, проксимальные операторы. Срок сдачи (мягкий=жёсткий) 23 июня (вторник), 23:59

Практические ДЗ

Задание 1. Методы градиентного спуска и Ньютона. Срок сдачи - 3 марта (вторник), 23:59.

Задание 2. Продвинутые методы безусловной оптимизации. Срок сдачи - 27 марта (пятница), 23:59.

Задание 3. Метод барьеров. Срок сдачи - 23 мая (суббота), 23:59.

Задание 4. Композитная оптимизация. Срок сдачи - 9 июня (вторник) 23:59.

Лекции

№ п/п Дата Занятие Материалы
1 15 января 2020 Введение в курс. Скорости сходимости итерационных процессов. Конспект
2 20 января 2020 Одномерная оптимизация. Конспект
3 27 января 2020 Метод градиентного спуска.
4 3 февраля 2020 Матричные разложения. Метод Ньютона.
5 10 февраля 2020 Метод сопряжённых градиентов для решения СЛАУ.
6 17 февраля 2020 Безгессианный метод Ньютона. Разностное дифференцирование.
7 2 марта 2020 Квазиньютоновские методы оптимизации
8 16 марта 2020 Условия Каруша-Куна-Таккера для условной оптимизации
9 6 апреля 2020 Двойственные задачи, симплекс-метод для линейного программирования видео
10 13 апреля 2020 Метод Ньютона и логарифмических барьеров для выпуклых задач условной оптимизации видео
11 20 апреля 2020 Негладкая оптимизация. Субградиентный метод. видео
12 27 апреля 2020 Проксимальный градиентный метод видео
13 18 мая 2020 Стохастическая оптимизация видео 1 видео 2
14 25 мая 2020 Риманова оптимизация видео
15 01 июня 2020 Решение задач оптимизации с помощью нейронных сетей видео
Статья 1
Статья 2

Семинары

№ п/п Дата Занятие Материалы
1 15 января 2020 Матрично-векторное дифференцирование. Конспект
2 20 января 2020 Неточная одномерная оптимизация. Классы функций для оптимизации.
3 27 января 2020 Метод градиентного спуска. ipynb
4 3 февраля 2020 Выпуклые множества. Конспект
5 10 февраля 2020 Нелинейный метод сопряжённых градиентов. Презентация
6 17 февраля 2020 Выпуклые функции. Конспект
7 2 марта 2020 Матричные преобразования в квазиньютоновских методах Конспект
8 16 марта 2020 Задачи условной оптимизации Конспекты
9 6 апреля 2020 Двойственные задачи, эквивалентные преобразования задач видео Конспект
10 13 апреля 2020 Преобразование задач к стандартному виду видео Конспект
11 20 апреля 2020 Субдифференциальное исчисление видео Конспект
12 27 апреля 2020 Проекции и проксимальные операторы видео Заметки с семинара
13 18 мая 2020 Сопряженные функции и нормы видео Конспект
14 1 июня 2020 Решение задач дискретной оптимизации непрерывными методами видео
Презентация

Дополнительный материал

  • Конспект по матрично-векторным скалярным произведениям и нормам.

Литература

  1. J. Nocedal, S. Wright. Numerical Optimization, Springer, 2006.
  2. A. Ben-Tal, A. Nemirovski. Optimization III. Lecture Notes, 2013.
  3. Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2003.
  4. Ю.Е. Нестеров. Методы выпуклой оптимизации, МЦНМО, 2010
  5. S. Boyd, L. Vandenberghe. Convex Optimization, Cambridge University Press, 2004.
  6. D. Bertsekas. Convex Analysis and Optimization, Athena Scientific, 2003.
  7. Б.Т. Поляк. Введение в оптимизацию, Наука, 1983.
  8. J. Duchi. Introductory Lectures on Stochastic Optimization, Graduate Summer School Lectures, 2016.
  9. S. Sra et al.. Optimization for Machine Learning, MIT Press, 2011.
  10. Y. Nesterov. Lectures on convex optimization, Springer, 2018.