Revision as of 20:13, 15 April 2024

Современные численные методы оптимизации в обучении

Квалификация выпускника: бакалавр

Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”

Направленность (профиль) образовательной программы: Математические основы ИИ

Программу разработал(а): А.Н. Безносиков

1. Краткая характеристика дисциплины

Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области численных методов оптимизации, их применения для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают фундаментальные вопросы, необходимые современному исследователю или инженеру в области математического моделирования, оптимального управления, классического машинного и глубокого обучения. В частности, обучающиеся знакомятся с классическими формулировками задач оптимизации, возникающими в приложениях, базовыми методами оптимизации, а также способами их настройки, сравнения и выбора под конкретные задачи. Также в рамках курса рассматриваются специальные сюжеты, возникающие в обучении с подкреплением, оптимальном транспорте, распределенном и федеративном обучении.

2. Перечень планируемых результатов обучения

Целью освоения дисциплины является изучение современных численных методов оптимизации в приложении к задачам, возникающим в различных областях, в том числе в машинном обучении.

Задачами дисциплины являются:

изучение постановок задач оптимизации, возникающих в различных областях прикладной математики;
изучение понятий из теории выпуклого анализа и линейной алгебры, необходимых для построения теории численных методов оптимизации;
изучение теоретических и практических подходов к матрично-векторному дифференцированию;
изучение методов первого порядка (градиентный спуск, метод тяжелого шарика), а также их различных модификаций и практических улучшений;
изучение задач поиска седловой точки, их связи с задачами minmax оптимизации, а также прикладных примеров данных задач;
изучение методов негладкой оптимизации: субградиентного спуска, проксимального метода, примеров проксимальных операторов;
изучение адаптивных методов, популярных для задач обучения;
изучение постановки задачи оптимального транспорта с точки зрения оптимизации, а также методов решения данной задачи;
изучение постановки задачи обучения с подкреплением с точки зрения оптимизации, а также методов решения данной задачи;
изучение метода стохастического градиентного спуска, его практических модификаций для стабилизации и ускорения процесса сходимости;
изучение методов редукции дисперсии для задачи минимизации эмпирического риска;
изучение координатных и безградиентных методов;
изучение подходов к распределенному решению задач оптимизации: локальных методов, методов с сжатием;
изучение инженерных вопросов организации распределенного обучения;
изучение постановки задачи федеративного обучения, ее связи с задачей распределенного обучения

Общая характеристика результата обучения по дисциплине

Знания:

- постановки задач оптимизации, возникающие в приложениях, в том числе связанных с машинным обучением; - классические современные методы оптимизации, их теоретические и практические особенности работы; - способы модификации классических методов оптимизации под конкретные задачи;

Умения:

- дифференцирование функций (теоретическое и практическое), зависящих от многих переменных; - реализация на языке программирования Python классических методов оптимизации; - настройка параметров методов оптимизации под конкретные задачи; - выбор методов оптимизации в зависимости от задачи.

Навыки (владения):

- аналитическое дифференцирование функции многих переменных; - дифференцирование функции многих переменных с помощью специализированных библиотек; - реализация классических методов оптимизации на языке программирования Python с помощью библиотек дифференцирования; - сравнение качества работы методов оптимизации между собой; - оперирование оптимизационными постановками и методами их решения; - самостоятельное совершенствование оптимизационных постановок в зависимости от требований на получаемое решение задачи; - реализация специальных модификаций и дополнительных техник для усовершенствования методов оптимизации;

3. Структура и содержание дисциплины

№ п/п	Наименование раздела дисциплины	Содержание дисциплины по темам
1.	Связь оптимизации и машинного обучения. Основные понятия	- примеры задач оптимизации в машинном обучении - основы построения теории сходимости - элементы линейной алгебры - выпуклость, Липшицевость и гладкость
2.	Матрично-векторное дифференцирование	- теория матрично-векторного дифференцирования - граф вычислений - библиотеки матрично-векторного дифференцирования (autograd, pytorch, jax) - реализация методов оптимизации (градиентного спуска) с помощью библиотек дифференцирования
3.	Методы первого порядка	- градиентный спуск - момент инерции и ускорение, метод тяжелого шарика и метод Нестерова - теоретическая сходимость методов градиентного спуска, тяжелого шарика и Нестерова - теоретическая оптимальность метода Нестерова - способы настройки параметров методов - особенности работы методов первого порядка на практике
4.	Метод Ньютона	- метод Ньютона - квазиньютоновские методы: SR1, BFGS, L-BFGS - теоретическая сходимость метода Ньютона и квазиньютоновских методов - особенности реализации и настройки методов на практике - практические модификации метода Ньютона - особенности работы методов на практике
5.	Зеркальный спуск	- идея метода зеркального спуска - дивергенция Брэгмана - сходимость метода зеркального спуска - частные случаи метода зеркального спуска - зеркальный спуск и минимизация регрета - зеркальный спуск и теоретико-игровые задачи
6.	Седловые задачи	- связь поиска седловой точки и решения minmax - примеры седловых задач: Лагранжиан, теория игр - методы решения седловых задач: спуск-подъем, экстраградиент и MirrorProx - теория сходимости метод решения седловых задач
7.	Субградиентный методы и проксимальный оператор	- субградиентный метод - проксимальный оператор - примеры проксимальных операторов: проекция, l1 - регуляризация - l1 регуляризация и отбор признаков - градиентный спуск с проекцией и метод Франк-Вульфа на l1 шаре
8.	Методы со шкалированием (адаптивные методы)	- AdaGradNorm, адаптивный субградиентный метод - AdaGrad, адаптивность по компонентам - RMSProp, моментум при подсчете адаптивности - Adam, коррекция взвешивания - AdamW, адаптивные методы для регуляризованных задач - особенности реализации и настройки методов на практике - особенности работы методов на практике
9.	Оптимизация и оптимальный транспорт	- постановка задачи оптимального транспорта - выпуклая оптимизация в задачах оптимального транспорта - метод Синхорна
10.	Стохастический градиентный спуск	- различные постановки задачи стохастической оптимизации - сходимость метода стохастического градиентного спуска - батчирование - клиппирование - техника перемешивания данных в батчах (reshuffling) - выбор методов оптимизации под конкретные задачи машинного обучения
11.	Методы редукции дисперсии	- идея методов редукции дисперсии - SVRG, SAGA, SARAH - теоретическая сходимость методов редукции дисперсии - особенности реализации и настройки методов на практике - особенности работы методов на практике
12.	Оптимизация и обучение с подкреплением	- ростановка задачи обучения с подкреплением - выпуклая оптимизация в обучении с подкреплением - policy gradient
13.	Координатные и безградиентные методы	- координатные методы - способы решения задач оптимизации с помощью оракула нулевого порядка - связь координатных и безградиентных методов - выбор направления в безградиентных методах - особенности реализации и настройки методов на практике - особенности работы методов на практике
14.	Распределенное обучение. Локальные методы	- идея локальных методов - LocalSGD, FedProx, Scaffold, Scaffnew - теоретические особенности сходимости распределенных методов - инженерные и прикладные вопросы распределенного обучения с локальными шагами
15.	Распределенное обучение. Методы с сжатием	- идея методов с сжатием - несмещенные и смещенные оператора сжатия - техники памяти и компенсации ошибки - инженерные и прикладные вопросы распределенного обучения с сжатием
16.	Федеративное обучение	- постановка задачи федеративного обучения - разновидности федеративного обучения и особенности - асинхронные вычисления - персонализированность обучения - дифференциальная приватность - атаки и защиты - византийские атаки
17.	Проектная деятельность	- чтение, разбор и обзор научных статей - воспроизведение и представление результатов

4. Методические и оценочные материалы

Задания для практических занятий:

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
1.	Связь оптимизации и машинного обучения. Основные понятия	Постройте матричную норму, индуцированную некоторой векторной нормой. Исследуйте функцию на выпуклость, Липшицевость, гладкость.
2.	Матрично-векторное дифференцирование	Найдите градиент функции $f:R^{d}\to R$ Найдите гессиан функции: $f:R^{d}\to R$ Найдите первый дифференциал функции: $f:R^{d\times d}\to R$ Найдите второй дифференциал функции: $f:R^{d\times d}\to R$ По графу вычислений найдите производные по всем переменным Реализуйте дифференцирование функции c помощью библиотеки autograd Реализуйте дифференцирование функции c помощью библиотеки pytorch Реализуйте дифференцирование функции c помощью библиотеки jax Реализуйте метод градиентного спуска c помощью библиотеки autograd Реализуйте метод градиентного спуска c помощью библиотеки pytorch Реализуйте метод градиентного спуска c помощью библиотеки jax
3.	Методы первого порядка	Реализуйте метод тяжелого шарик Реализуйте метод Нестерова Охарактеризуйте сходимость методов на квадратичных задачах с различными числами обусловленности Реализуйте различные способы подбора шага в методе градиентного спуска (линейный поиск, адаптивность, правила Армихо/Вульф/Гольдстейн, Поляка) Сравните работу метод с различными настройками и способами подбора параметров на квадратичных задачах с различными числами обусловленности Сравните несколько методов между собой на квадратичных задачах с различными числами обусловленности
4.	Метод Ньютона	Реализуйте метод Ньютона Реализуйте метод BFGS Реализуйте метод L-BFGS. Обоснуйте эффективность реализации Охарактеризуйте сходимость методов Реализуйте различные модификации метода Ньютона (демпфированный Ньютон, кубический Ньютон)
5.	Зеркальный спуск	Выпишите итерацию метода зеркального спуска на симплекс с KL-дивергенцией Реализуйте итерацию метода зеркального спуска с KL-дивергенцией Решите с помощью метода зеркального спуска задачу минимизации регрета в онлайн обучении
6.	Седловые задачи	Решите с помощью метода зеркального спуска билинейную седловую задачу поиска оптимальных стратегиях в игре с нулевой суммой
7.	Субградиентный методы и проксимальный оператор	Выпишите аналитическое выражение проксимального оператора l1-нормы Выпишите аналитическое выражение проксимального оператора индикаторной функции множества Реализуйте проксимальный градиентный спуск Реализуйте метод градиентного спуска с проекцией Реализуйте оператор проекции на l1 шар Реализуйте метод Франк-Вульфа для оптимизации на l1 шаре Сравните работу метода проекции и метода Франк-Вульфа на задаче логистической регрессии Сравните с точки зрения машинного обучения подходы на основе l1 регуляризации и на основе l1 множества оптимизации
8.	Методы со шкалированием (адаптивные методы)	Реализуйте метод AdaGradNorm Реализуйте метод AdaGrad Реализуете метод RMSProp Реализуйте метод Adam Реализуйте метод AdamW Реализуйте метод OASIS Изучите работу методов Adam/RMSProp в зависимости от параметра $\beta _{2}$ (моментума шкалирования) на задаче логистической регрессии Сравните работу методов между собой на задаче логистической регрессии
9.	Оптимизация и оптимальный транспорт	Сформулируйте задачу поиска оптимального транспорта с точки зрения оптимизации Реализуйте метод Синхорна для задачи поиска оптимального транспорта Реализуйте метод зеркального спуска для задачи поиска оптимального транспорта Сравните работу методов на задаче оптимального транспорта датасета MNIST
10.	Стохастический градиентный спуск	Реализуйте метод стохастического градиентного спуска для задачи минимизации эмпирического риска Изучите сходимость метода в зависимости от стратегии подбора шага Реализуйте возможность использования батчирования в стохастическом градиентном спуске Реализуйте возможность использования клиппирования в стохастическом градиентном спуске Реализуйте технику reshuffling в стохастическом градиентном спуске Изучите, как работают данные техники на различных задачах машинного обучения Сравните сходимости методов SGD и Adam на различных задачах машинного обучения (CV, NLP)
11.	Методы редукции дисперсии	Реализуйте метод SVRG для задачи минимизации эмпирического риска Реализуйте метод SAGA для задачи минимизации эмпирического риска Реализуйте метод SARAH для задачи минимизации эмпирического риска Сравните сходимость методов на различных задачах машинного обучения
12.	Оптимизация и обучение с подкреплением	Сформулируйте задачу обучения с подкреплением с оптимизационной точки зрения Объясните, какие особенности могут возникнуть в обучении с подкреплением, которых не наблюдалось, например, в минимизации эмпирического риска Реализуйте метод стохастического (зеркального) спуска для задачи обучения с подкреплением. С помощью реализованного метода решите задачу построение стратегии агента (frozen lake)
13.	Координатные и безградиентные методы	Реализуйте координатный спуск Исследуйте его работу на квадратичных задачах разной размерности с разным числами обсусловленности Реализуйте безградиентный метод с техникой аппроксимации градиента через конечные разности С помощью реализованного метода решите задачу оптимальной настройки параметров метода тяжелого шарика Реализуйте безградиентный метод с трехточечным оракулом С помощью реализованного метода решите задачу настройки рекомендательной системы
14.	Распределенное обучение. Локальные методы	Реализуйте метод LocalSGD Реализуйте метод FedProx Реализуйте метод Scaffold Опишите различные постановки распределенной оптимизации, которые могут возникнуть на практике (с точки зрения организации коммуникаций, симметричности устройств и т.д.) Опишите, как эффективно организовать процесс общения в зависимости от распределенной постановки Воссоздайте распределенную постановку, добавьте возможность варьировать различные особенности среды Сравните и охарактеризуйте работу реализованных методов на различных постановках задачи распределенного обучения
15.	Распределенное обучение. Методы с сжатием	Реализуйте метод QSGD Реализуйте технику компенсации ошибки Реализуйте метод EF21 Реализуйте простейшие операторы сжатия: округление, случайный выбор координат, жадный выбор координат Сравните и охарактеризуйте работу методов с различными операторами сжатия
16.	Федеративное обучение	Реализуйте способ защиты приватности в федеративном обучении с помощью добавления шума к пересылаемым данным Реализуйте простейшую атаку на метки обучающей выборки на одном из устройств Проверьте защищает ли дифференциальная приватность от реализованной атаки Реализуйте способы борьбы с византийскими атаками (FL trust) Реализуйте простейшие византийские атаки (случайный вектор, смена меток) Проверьте защищает ли FL trust от реализованных атак
17.	Проектная деятельность	Изучите особенности постановки, которую рассматривают авторы статьи Опишите подход, предложенный в статье Выделите основные особенности данного подхода. Объясните, чем он отличается и как связан с теми подходами, что уже были предложены ранее в литературе Реализуйте подход из статьи, а также несколько подходов-конкурентов Сравните реализованные техники между собой. Сделайте вывод, насколько результаты статьи удалось воспроизвести Проведите дополнительные экспериментальные исследования изучаемого подхода

Текущий контроль успеваемости обучающихся по дисциплине:

№ п/п	Наименование раздела дисциплины	Форма текущего контроля	Материалы текущего контроля
1.	Связь оптимизации и машинного обучения. Основные понятия Матрично-векторное дифференцирование Методы первого порядка Метод Ньютона \|\| Домашние задание; Коллоквиум \|\| В домашнее задание включаются задачи, нерешенные во время семинарских занятий
2.	Зеркальный спуск Седловые задачи Субградиентный методы и проксимальный оператор \|\| Домашние задание; Коллоквиум \|\| В домашнее задание включаются задачи, нерешенные во время семинарских занятий
3.	Методы со шкалированием (адаптивные методы) Оптимизация и оптимальный транспорт Стохастический градиентный спуск Методы редукции дисперсии Оптимизация и обучение с подкреплением Координатные и безградиентные методы \|\| Домашние задание; Коллоквиум \|\| В домашнее задание включаются задачи, нерешенные во время семинарских занятий
4.	Распределенное обучение. Локальные методы Распределенное обучение. Методы с сжатием Федеративное обучение \|\| Домашние задание; Коллоквиум \|\| В домашнее задание включаются задачи, нерешенные во время семинарских занятий
5.	Проектная деятельность	Групповой проект	В качестве тем для проектов предоставляются широко цитируемые и известные научные публикации в области численных методов оптимизации. Проект выполняется группой из двух студентов

Контрольные вопросы для подготовки к промежуточной аттестации:

№ п/п	Наименование раздела дисциплины	Вопросы
1.	Связь оптимизации и машинного обучения. Основные понятия	Дайте определение матричной нормы, индуцированная векторной нормой и приведите примеры таких норм. Дайте определение выпуклого множества. Дайте определение выпуклой функции. Дайте определение Липшицевой функции. Дайте определение гладкой функции. Дайте определения скоростей сходимости методов: сублинейной, линейной, сверхлинейной, квадратичной.
2.	Матрично-векторное дифференцирование	Выпишите формулу подсчета градиента и гессиана для квадратичной задачи. Выпишите формулу подсчета градиента и гессиана для задачи логистической регрессии. Проверьте, что данные функции являются выпуклыми/гладкими.
3.	Методы первого порядка	Выпишите итерацию метода градиентного спуска/тяжелого шарика/метода Нестерова. Качественно сравните методы градиентного спуска, тяжелого шарика и Нестерова.
4.	Метод Ньютона	Выпишите итерацию метода Ньютона. Качественно сравните методы градиентного спуска и Ньютона. Выпишите квазиньютоновское уравнение. Выпишите общий вид записи квазиньютоновских методов.
5.	Зеркальный спуск	Дайте определение дивергенция Брэгмана и приведите примеры. Выпишите итерацию метода зеркального спуска. Как связан зеркальный спуск и градиентный спуск?
6.	Седловые задачи	Дайте определения седловой и minmax задач. Выпишите итерацию метода спуска-подъема. Выпишите итерацию метода экстраградиента.
7.	Субградиентный методы и проксимальный оператор	Выпишите итерацию метода субградиентного спуска. Качественно сравните метода субградиентного спуска для гладких и негладких задач. Дайте определение композитной задачи. Выпишите итерацию проксимального метода.
8.	Методы со шкалированием (адаптивные методы)	Выпишите итерации методов AdaGradNorm, AdaGrad, RMSProp, Adam, AdamW. Объясните, чем похожи и чем отличаются данные методы друг от друга.
9.	Оптимизация и оптимальный транспорт	Сформулируйте задачу оптимального транспорта. Выпишите итерацию алгоритма Синхорна.
10.	Стохастический градиентный спуск	Сформулируйте задачу онлайн обучения с точки зрения оптимизации. Сформулируйте задачу минимизации эмпирического риска. Как связаны эти две постановки? Выпишите итерацию метода SGD. Качественно сравните методы градиентного спуска и стохастического градиентного спуска. В чем заключается техника батчирования? В чем заключается техника клипирования? В чем заключается техника reshuffling?
11.	Методы редукции дисперсии	Выпишите итерацию методов SAGA, SVRG, SARAH. Качественно сравните методы стохастического градиентного спуск, SAGA, SVRG и SARAH.
12.	Оптимизация и обучение с подкреплением	Сформулируйте задачу обучения с подкреплением с точки зрения оптимизации. Объясните ключевые отличия задачи оптимизации в обучении с подкреплением от минимизации эмпирического риска. Выпишите итерацию метода policy gradient.
13.	Координатные и безградиентные методы	Выпишите итерацию метода координатного спуска. Качественно сравните методы градиентного спуска и координатного спуска. Выпишите итерацию метода безградиентной оптимизации, использующего аппроксимацию производной по направлению через конечные разности. Выпишите итерацию безградиентного метода трех точек.
14.	Распределенное обучение. Локальные методы	Выпишите итерацию метода Local SGD. Качественно сравните методы градиентного спуска и Local GD. Выпишите итерацию методов Scaffold и FedProx. Качественно сравните методы Local GD, FedProx и Scaffold.
15.	Распределенное обучение. Методы с сжатием	Дайте определение несмещенного и смещенного операторов сжатия и приведите примеры. Выпишите итерацию метода QSGD. Качественно сравните методы градиентного спуска и QSGD. В чем состоит техника компенсации ошибки? Выпишите итерацию QSGD с техникой компенсации ошибки. В чем состоит техника памяти? Выпишите итерацию метода EF21. Качественно сравните QSGD, QSGD с техникой компенсации ошибки и EF21.
16.	Федеративное обучение	Опишите постановку задачи федеративное обучение. Перечислите особенности и отличия федеративного обучения от классического распределенного обучения.

Вопросы/Задания к промежуточной аттестации в устной/письменной форме:

1. База: Определение выпуклого множества. Определение выпуклой функции для непрерывно дифференцируемой функции и произвольной функции. Скорости сходимости методов: сублинейная, линейная, сверхлинейная, квадратичная. Продвинутый: Формулировка условия локального минимума на $R^{d}$ для произвольной непрерывно дифференцируемой функции. Формулировка условия глобального минимума на $R^{d}$ для выпуклой непрерывно дифференцируемой функции.

Превосходный: Доказательство условия локального минимума на $R^{d}$ . Доказательство условия глобального минимума на $R^{d}$ выпуклой функции. Доказательство свойства гладкой непрерывно дифференцируемой функции. Доказательство свойства ограниченности субградиента выпуклой Липшицевой функции.

2. База: Итерация метода градиентного спуска. Интуиция: почему такой метод, зачем нужен параметр (шаг). Характер сходимости (линейная/сублинейная/… локальная/глобальная) градиентного спуска для гладких сильно выпуклых задач.

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

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

3. База: Итерации метода тяжелого шарика и ускоренного градиентного метода (метода Нестерова). Интуиция: почему может быть лучше, чем градиентный спуск, как подбирать моментнумный параметр. Характер сходимости для гладких сильно выпуклых задач. Особенности сходимости по сравнению с градиентным спуском.

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

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

4. База: Итерация метода Ньютона. Интуиция метода Ньютона: почему берется именно такая итерация. Характер сходимости для сильно выпуклых задач с Липшицевым гессианом. Квазиньютоновское уравнение. Интуиция квазиньютоновских методов.

Продвинутый: Формулировка оценки сходимости метода Ньютона для сильно выпуклых задач с Липшицевым гессианом. Способы получения глобальной сходимости для метода Ньютона. Правила обновления матриц H или B для SR1 и BFGS.

Превосходный: Доказательство сходимости метода Ньютона для сильно выпуклых задач с Липшицевым гессианом.

5. База: Итерация метода зеркального спуска. Интуиция метода. Характер сходимости для выпуклых гладких задач.

Продвинутый: Шаг зеркального спуска в случае симплекса и KL-дивергенции (с доказательством).

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

6. База: Седловая задача. Итерация метода экстраградиента. Интуиция метода: почему лучше, чем градиентный спуск-подъем. Характер сходимости для сильно выпуклых - сильно вогнутых гладких задач.

Продвинутый: Формулировка теорем о связь задачи поиска седловой точки и minmax задачи. Примеры седловых задач. Формулировка оценки сходимости метода экстраградиента для сильно выпуклых - сильно вогнутых гладких задач.

Превосходный: Доказательство сходимости метода экстраградиента для сильно выпуклых - сильно вогнутых гладких задач.

7. База: Итерация метода субградиентного спуска. Интуиция метода. Характер сходимости. Композитная задача. Итерация проксимального метода. Интуиция метода. Характер сходимости.

Продвинутый: Формулировка оценки сходимости субградиентного спуска для выпуклых задач с Липшицевой функцией. Формулировка свойств проксимального оператора.

Превосходный: Доказательство сходимости для выпуклых задач с Липшицевой функцией.

Доказательство сходимости проксимального метода для выпуклых композитных задач с гладким и проксимально дружественным слагаемыми (вместе с доказательствами свойств проксимального оператора).

8. База: Итерация методов AdaGradNorm, AdaGrad, RMSProp, Adam, AdamW. Интуиция методов и улучшения по сравнению с предшественником. Характер сходимости.

Продвинутый: Формулировка оценки сходимости для метода AdaGrad для выпуклых Липшицевых функций.

Превосходный: Доказательство оценки сходимости для метода AdaGrad для выпуклых Липшицевых функций.

9. База: Различные постановки задачи стохастической оптимизации. Итерация метода SGD. Интуиция метода. Характер сходимости в условиях ограниченной дисперсии стохастического градиента. Итерация методов SAGA, SVRG, SARAH. Интуиция методов. Характер сходимости. Батчирование.

Продвинутый: Техники клипирования и reshuffling. Формулировка оценки сходимости SGD для сильно выпуклых гладких задач в условиях ограниченной дисперсии стохастического градиента. Формулировка оценки сходимости SAGA для сильно выпуклых гладких задач вида конечной суммы.

Превосходный: Доказательство сходимости SGD. Доказательство сходимости SAGA.

10. База: Формулировка задачи оптимального транспорта с точки зрения оптимизации, формулировка задачи обучения с подкреплением с точки зрения оптимизации.

Продвинутый: Методы решения задачи оптимального транспорта: алгоритма Синхорна, зеркальный спуск. Ключевые отличия задачи оптимизации в обучении с подкреплением от минимизации эмпирического риска. Policy gradient.

11. База: Итерация метода координатного спуска. Идея метода. Итерация метода метода безградиентной оптимизации, использующего аппроксимацию производной по направлению через конечные разности. Итерация безградиентного метода трех точек.

Продвинутый: Выбор координат в координатном методе. Выбор направлений в безградиентном методе. Зависимость сходимости от выбора координат и направлений. Формулировка сходимости координантного метода для гладких сильно выпуклых задач. Формулировка сходимости метода трех точек для гладких сильно выпуклых задач.

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

12. База: Итерация метода Local SGD. Идея метода. Характер и особенности сходимости. Итерация методов FedProx и Scaffold. Идея методов. Характер сходимости. Сравнение с Local SGD.

Продвинутый: Теоретические особенности сходимости метода Local SGD.

13. База: Несмещенные и смещенные операторы сжатия. Примеры операторов сжатия. Итерация метода QSGD. Идея метода. Характер и особенности сходимости. Техника компенсации ошибки. Итерация QSGD с техникой компенсации ошибки. Характер и особенности сходимости. Техника памяти. Итерация метода EF21. Характер и особенности сходимости.

Продвинутый: Теоретические особенности сходимости QSGD для смещенных и несмещенных операторов сжатия. Теоретические особенности сходимости метода EF21. Способ организации коммуникаций и общения между собой в случае отсутствия координирующего сервера. AllReduce и AllGather процедуры.

14. База: Постановка задачи федеративное обучение. Особенности и отличия федеративного обучения от классического распределенного обучения.

Продвинутый: Способы персонализации результатов федеративного обучения. Способы защиты приватности в федеративном обучении. Способы атаки на приватность федеративного обучения.

Перечень учебно-методического обеспечения дисциплины

Список основной литературы:

1. Jorge Nocedal, Stephen J. Wright, Numerical Optimization (2nd edition) / ISBN: 978-0-387-40065-5

2. John C. Duchi, Introductory Lectures on Stochastic Optimization

3. Anatoly Zhigljavsky, Antanas Žilinskas, Stochastic Global Optimization/ ISBN: 978-0-387-74740-8

Список дополнительной литературы:

1. Stephen Boyd, Lieven Vandenberghe, Convex Optimization/ ISBN: 978-0-521-83378-3

2. Yurii Nesterov, Lectures on Convex Optimization (2nd edition)/ ISBN: 978-3-319-91578-4

3. Amir Beck, First-Order Methods in Optimization /ISBN: 978-1611974980

Методические указания для обучающихся по освоению дисциплины

Вид учебных занятий/деятельности	Деятельность обучающегося
Лекция	Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практическое (семинарское) занятие	При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его. Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
Устный/письменный опрос	Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
Подготовка к промежуточной аттестации	При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей. Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
Самостоятельная работа	Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
Дискуссия	Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
Контрольная работа	При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
Тестирование (устное/письменное)	При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.
Индивидуальная работа	При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
Выполнение домашних заданий и групповых проектов	Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.

Методы и технологии обучения, способствующие формированию компетенции

Методы и технологии обучения, способствующие формированию компетенции
Информационно – коммуникационная технология, Педагогика сотрудничества, Традиционные технологии, Модульная технология

Difference between revisions of "BSc: ModernMumericalMethodsForDistributedLearning"