О курсе
Программа курса:
1 лекция (4 сентября) Александр Гасников (МФТИ, Университет Иннополис)
Эргодическая теорема для марковских процессов. Примеры применения: введению в теорию макросистем (парадокс Эренфестов, кинетика социального неравенства, принцип максимума энтропии), PageRank, введение в MCMC (алгоритм Метрополиса-Хастингса).
Видео с Анонсом совместного с МФТИ спецкурса Математика больших данных от А.В.Гасникова.
Видео с лекции Александра Гасникова.
2 лекция (11 сентября) Никита Пучкин (ВШЭ, МФТИ)
Неравенства концентрации меры. Субгауссовские и субэкпоненциальные случайные величины и их примеры. Лемма Хеффдинга. Теорема Хеффдинга и неравенство концентрации субэкспоненциальных случайных величин. Применение неравенства концентрации субэкспоненциальных случайных величин к линейному снижению размерности, лемма Джонсона-Линденштраусса.
3 лекция (18 сентября) Алексей Фролов (Сколтех)
Введение в теорию информации и ее приложения. Энтропия и ее аксиоматическое определение. Взаимная информация. Неравенство Фано. Неравенство обработки данных. Применение энтропии Шеннона в комбинаторных задачах.
Презентация Introduction to Information Theory.
Проекты по теме теоретико-информационных подходов в машинном обучении.
4 лекция (25 сентября) Иван Бутаков (Сколтех, МФТИ)
Теоретико-информационные подходы в анализе данных. Взаимная информация как универсальная и инвариантная мера зависимости. Оценка взаимной информации. Отбор признаков. InfoMax-самообучение. Распутывание представлений. Информационная плоскость и информационные потоки в нейронных сетях, принцип бутылочного горлышка.
Репозитории, упоминавшиеся на занятии:
Стохастический градиентный спуск (SGD). Asynchronous SGD. Оптимальные методы асинхронной и параллельной оптимизации (Rennala SGD и Malenia SGD). Доказательство нижних оценок времени решения задач с помощью метода Чернова.
Репозиторий для полного погружения в Machine Learning
6 лекция (9 октября) Сергей Самсонов (ВШЭ)
Задача о многоруком бандите. Основные понятия в задаче о многоруком бандите. Кумулятивные потери (регрет) алгоритма и его оценки. Дилемма исследования среды и использования текущей информации (exploration-exploitation trade-off). Напоминание: неравенство Хеффдинга. Алгоритм Explore-first, оценки регрета для него. Принцип оптимизма перед лицом неопределенности и алгоритм UCB.
7 лекция (9 октября) Сергей Самсонов (ВШЭ)
Стохастическая аппроксимация. Неравенства Розенталя и Бернштейна для линейных статистик от независимых случайных величин. Их обобщения на случай цепей Маркова. Приложения для получения оценок ошибки линейной стохастической аппроксимации и стохастического градиентного спуска.
8 лекция (16 октября) Никита Пучкин (ВШЭ)
PAC-байесовский подход к задачам многомерной статистики. PAC-байесовское вариационное неравенство и его применение к доказательству верхних оценок на вероятности больших уклонений. Матричное неравенство концентрации в пространстве высокой размерности, эффективный ранг. Применение к оценке ковариационной матрицы.
9 лекция (23 октября) Петр Мокров (Сколтех)
Оптимальный транспорт в современных генеративных моделях. Задача об оптимальной транспортировки (Монже и Канторовича). Прямая, двойственная и полудвойственная постановки. Частные случаи:
Wasserstein-1 расстояние: Теорема Канторовича-Рубинштейна. Приложения: Wasserstein GAN.
Wasserstein-2 расстояние: Теорема Бренье. Генеративные модели на основе выпуклых нейронных сетей
Обобщения: слабая задача оптимального транспорта. Max-min алгоритм нейронного оптимального транспорта (NOT) и его теоретические гарантии.
Энтропийный оптимальный транспорт, задача о мосте Шрёдингера (SB) . Точное решение этой задачи в некоторых частных случаях, приложения. Связь задачи SB с диффузионными генеративными моделями.
10 лекция (30 октября) Максим Рахуба (ВШЭ)
Методы малоранговой аппроксимации матриц. Матричные нормы, теорема Эккарта-Янга-Мирского. Рандомизированный алгоритм построение малорангового приближения, его улучшенная версия с помощью степенного метода. Методы римановой оптимизации.
11 лекция (6 ноября) Максим Рахуба (ВШЭ)
Тензорные разложения. Кронекерово произведение, векторизация и матрицизация тензоров. Разложения Таккера, разложение тензорного поезда. Алгоритмы построения тензорных разложений.
12 лекция (13 ноября) Александр Безносиков (МФТИ)
Локальные методы распределенного обучения. Локальный (стохастический) градиентный спуск: особенности сходимости, нижние и верхние оценки. Понятие о похожести локальных функций: похожесть градиентов и похожесть гессианов. Лемма Хеффдинга для оценки похожести гессианов. Метод зеркального спуска для распределенной задачи в условиях похожести. Зеркальный спуск, как техника слайдинга/скольжения. Модификации и обобщения зеркального спуска для распределенной задачи в условиях похожести.
13 лекция (20 ноября) Александр Безносиков (МФТИ)
Сжатие в распределенном обучении. Несмещенные операторы сжатия. QSGD: метод, особенности сходимости. Смещенные операторы сжатия. Техника компенсации ошибки. Сходимость QSGD с техникой компенсации ошибки. Техника памяти: EF21 и DIANA. Сходимость до точного решения с помощью техники памяти.
14 лекция (27 ноября) Андрей Соболевский (МФТИ)
Фракталы и мультифрактальный формализм I
Обобщение понятия размерности, которое приписывает некоторым множествам в евклидовом пространстве дробную размерность (сохраняя при этом для гладких кривых размерность 1, для гладких поверхностей размерность 2 и т.д.) — хорошо известная идея, но математически она может быть формализована по-разному. Множества, размерность которых в каком-то смысле является дробной и превышает их топологическую размерность (которая всегда выражается целым числом), принято называть фракталами.
Мы начнем с аккуратных определений двух формализаций понятия дробной размерности: боксовой размерности (box-counting dimension) и размерности Хаусдорфа (Hausdorff dimension; заодно будет определена еще и мера Хаусдорфа, которая является обобщением длины, площади и объема на дробные размерности).
Из простых примеров будет видно, что в терминах боксовой размерности фрактальность может оказываться артефактом: дробную боксовую размерность могут иметь множества, по существу не обладающие нетривиальной тонкой структурой фрактала. Хаусдорфова размерность свободна от этого недостатка, но ее аккуратное вычисление существенно труднее. Мы покажем, как с помощью леммы Фростмана можно строго вычислить хаусдорфову размерность канторова множества средних третей.
15 лекция (4 декабря) Андрей Соболевский (МФТИ)
Фракталы и мультифрактальный формализм II
Вторая часть рассказа о фракталах будет касаться мультифрактальности, т.е. фрактальных свойств мер: грубо говоря, мы будем смотреть не на геометрические объекты — множества, расположенные в пространстве, а на непрерывно распределенную по этим множествам массу (выражаясь строго, положительную счетно-аддитивную меру).
Мы увидим, что такое мультифрактальный спектр меры и в чем заключается «мультифрактальный формализм» — изобретенный физиками Дж. Паризи и У. Фришем способ вычисления мультифрактального спектра. Если хватит времени, обсудим некоторые модельные механизмы, порождающие мультифрактальные меры.