Course description
The main goal of the course is to introduce students to the relevant mathematics, which should subsequently help them in studying specialized sections of data analysis (machine learning, statistics, reinforcement learning, numerical optimization methods, large network modeling, etc.).
The course is held jointly with the Independent University of Moscow.
An incomplete list of what we included in this course:
The phenomenon of concentration of measure. Starting with the classical results of Gauss, Maxwell, Poincare, Levy, Milman, it is planned to gradually move to modern results and applications, including those arising in various data analysis tasks.
Numerical methods for solving problems of (convex) stochastic optimization in large spaces. Such tasks often arise in a variety of applications, including data analysis — the principle of maximum likelihood in statistics, risk minimization in machine learning.
The classical SVD decomposition theorem and its various generalizations will be demonstrated in applications to data stored in multidimensional arrays.
Videos of all lectures with a description are available at the link
Instructors
Alexander Gasnikov (MIPT)
Maxim Rakhuba (HSE)
Alexey Frolov (Skoltech)
Daniil Tyapkin (Higher School of Economics)
Course materials
Main literature
Blum A., Hopcroft J., Kannan R. Fundamentals of data science. – Cambridge University Press, 2020.
Bach F. The study of theory based on first principles. – 2021.
Tyrtyshnikov E. E. Methods of numerical analysis. – 2007.
Zorich V. Mathematical analysis of problems of natural science. – Litres, 2018.
Additional literature
1. Gidelloy Ya., Benjio I., Kirville A. Deep research. 2nd ed., corrected by M.: DMK-Press, 2018.
2. Shapiro A., Dencheva D., Ruschinsky A. Lectures on stochastic programming: modeling and theory. – Society of Industrial and Applied Mathematics, 2014.
3. Shalev-Schwartz S., Ben-David S. Understanding machine learning: from theory to algorithms. – Cambridge University Press, 2014.
4. Bubek S. Convex optimization: algorithms and complexity // Fundamentals and trends® in machine learning, Volume 8, issue 3-411, pp. 231-357. – 2015.
5. Duchi J. S. Introductory lectures on stochastic optimization // Mathematics of data. – 2018. – Vol. 25. – pp. 99-185.
6. Hazan E. Lecture notes: Optimization for machine learning // Preprint arXiv arXiv:1909.03550. – 2019.
7. Lan G. Methods of first-order optimization and stochastic optimization for machine learning. – Spring nature, 2020.
8. Milman V. D. P. Levy's legacy in geometric functional analysis //Asterisk. – 1988. – Vol. 157. – No. 158. – pp. 273-301.
9. Shen A., Romashchenko A., Rumyantsev A. Yu. Notes on coding theory. – 2017.
10. Vershinin R. Multidimensional probability: an introduction to applications in the field of data science. – Cambridge University Press, 2018. – vol. 47.
Projects
Результаты работы студентов по некоторым проектам частично вошли в спецвыпуск журнала Компьютерные исследования и моделирование
Проект 1. Reinforcement Learning / AMDP (теоретический)
В современном обучении с подкреплением в плане теории уже довольно много сделано. Однако для average-reward (AMDP) постановок в теории есть зазор между нижними и верхними оценками. Предлагается в целом изучить RL сквозь призму современной стох. оптимизации (см. в этой связи презентацию, прикрепленную у описанию и цитированную литературу) и сконцентрироваться именно на AMDP. Итогом здесь должно быть написание некоторого небольшого (7-10 страниц) текста-отчета (лучше всего, сделанного в оверлифе), в котором описывается state-of-the-art результаты (теоретические) по AMDP постановкам. Отмечу, что в презентации содержатся не все нужные ссылки (например, нет вот этой), и отчасти работа заключается в поиске таких теоретических работ, в которых есть интересные продвижения.
Проект 2. Поиск вектора Page Rank
Изучите статьи Вокруг степенного закона распределения компонент вектора PageRank, Efficient Numerical Methods to Solve Sparse Linear Equations with Application to PageRank (тут есть пример, откуда можно брать данные). Попробуйте реализовать метод MCMC и еще парочку приглянувшихся методов для задачи поиска вектора PageRank. Определите, какой метод и в каком смысле лучше работает. Итогом здесь должен быть colab ноутбук с кодом и хорошими комментариями, поясняющими полученные результаты.
Проект 3. Градиентный клиппинг
Посмотрите вот это видео. В различных моделях обучения возникают задачи стохастической оптимизации, в которых у градиентов имеются тяжелые хвосты. Для лучшей практической работы стандартных методов типа SGD и их моментных вариантов используется клиппирование (пробатченного) стохастического градиента. Такой проект мы делали летом 2022 года со школьниками в Сириусе. В результате было сделано следующее (стоит делать поправку, что это делали школьники 8-10 классов):
Оказывается, для выпуклых задач есть довольно симпатичная математика, стоящая за всем этим: Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise, Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise (совсем идейно это описано в самом начале презентации, прикрепленной к описанию).
Проект практический и заключается в подборе новых примеров (классов) задач обучения (в том числе состязательного обучения), на которых клиппированные методы работают лучше неклипированных. На самом деле, чтобы не заниматься перебором, как раз важно понять, какой эффект дает клипирование и в каких ситуациях это все может себя проявить. Естественно, на практике размер клипа и батча, возможно, придется подбирать не совсем так как в теории, но в целом, некоторые общие закономерности теоретические результаты дают, по-видимому, правильные, и разумно это использовать, чтобы сократить перебор в подборе этих параметров.
Проект 4. Предельные формы
В цикле статей Вершика-Синая-Арнольда исследуются различные предельные формы (например, диаграмм Юнга, выпуклых ломаных и т.п.). Вообще, все это очень красиво, и в своей основе имеет целый ряд фундаментальных законов природы, проявляющихся и в целом ряде других областей. Например, в статистической физике. Для погружения в данную проблематику можно рекомендовать мини-курс А.М. Вершка из трех лекций. Некоторые такие примеры разобраны в книге (см. также цитированную там литературу). Искать можно как раз по фамилиям (Вершик, Синай). Целью данного проекта является разбор того, почему имеет место наблюдение, описанное в скрине. В результате работы над проектом должен появиться текст, обосновывающий результат со скрина.
Проект 5. Как зародилась жизнь? Генетические алгоритмы, Мир РНК
Вопрос «как зародилась жизнь?» давно привлекает к себе внимание ученых из разных областей. Текущее понимание этого вопроса изложено в замечательной книге А.А. Маркова «Рождение сложности». Хотя до сих пор нет одной какой-то общепринятой точки зрения, но все же наиболее популярна гипотеза о том, что жизнь могла зародиться из самокопирующихся молекул РНК (гипотеза РНК мира). Обоснование гипотезы требует проработки разных (в том числе чисто математических) вопросов. Замечательно здесь и то, что можно пойти и в обратном направлении (а именно, эволюция/естественный отбор может подсказать способ решения той или иной сложной задачи оптимизации, функционал которой интерпретируется как приспособленность). Собственно, это и предлагается сделать. Решите задачу 16 на стр. 175-176. Требуется математически строго обосновать решение и подкрепить теорию результатами численных экспериментов.
Проект 6 (вокруг методов Монте-Карло, в том числе с приложениями к финансовой математике) Посмотрите часть 1 и часть 2 видео «В окрестностях Монте-Карло» и попробуйте на базе прослушанного предложить какие-то свои вариации классических методов. Проект очень неопределенный. Это сделано специально, чтобы дать больше свободы творчества. Также было бы здорово обратить внимание, что для целого ряда вещей совсем не нужна первозданно случайная последовательность. В частности, на практике эффективными оказываются так называемы квази Монте-Карловские методы, под которые есть хорошая теория.
Цель данного проекта — знакомство с современными приложениями методов Монте-Карло. В частности, для тех, кто хочет посмотреть в сторону финансовой математике можно рекомендовать в качестве проекта выбрать Multi-level Monte Carlo. А именно, проект заключается в том, чтобы аккуратно обосновать (с нужной теорией и желательно демонстрацией на практике) то, что написано в условиях задачи 22 на стр. 204-205. Для погружения в финансовую математику есть очень доступный курс.
Проект 7. Ранняя остановка или регуляризация
Одной из главных проблем машинного обучения является переобучение. Это давно и хорошо известно, и много чего в этой связи было сделано. Если совсем кратко резюмировать, то для задач обучения с выпуклым целевым функционалом (логистическая регрессия, SVM, LASSO, …) основные способы борьбы с переобучением — это регуляризация или ранняя остановка процедур типа SGD. На базе первой главы книги по Алгоритмической стох. оптимизации (ссылка здесь дублируется - имеется в прикрепленном сообщении) попробуйте сделать обзор описанных двух подходов и продемонстрируйте как все это работает на практике. В чем преимущества и недостатки этих двух подходов друг перед другом? Итогом работы по проекту должен стать текст + эксперименты. То есть в этом проекте важны обе составляющие (практическая и теоретическая).
Проект 8. Модели распространения эпидемий, в частности, ковид как модель стохастической химической кинетики
Изучите главу 6. В частности, модель Эренфестов, модель хищник-жертва и ее распределенные варианты. Попробуйте на базе похожего формализма получить систему дифференциальных уравнений SIR-типа моделей и предложите свои обобщения. Для дополнительной мотивации можно посмотреть мультфильмы:
Результатом работы по проекту может быть описание микроскопической динамики, которая в макромасштабе описывается чем-то типа SIR-моделей или их обобщений. При этом обоснование должно быть как теоретическое, так и практическое.
Проект 9. Почему зависимости частот катастроф от их масштабов имеют степенной закон?
Изучите задачу Д. Кьялво (задача 12 на стр. 170-171). Попробуйте не только экспериментально проверить то о чем написано в задаче (естественно, в большем масштабе, чем было в эксперименте, который делал Д. Кьялво над своими студентами), но и обосновать это теоретически. Проект также включает в себя текст, с теоретической проработкой, и эксперименты.
Проект 10. Почему большинство крупных мегаполисов живут в режиме пробок, фазовый переход в сетях массового обслуживания
Этот проект совершенно реален (то есть идею этого проекта воплотили в жизнь при планировании развития сети общественного транспорта в г. Москве за последние 10-15 лет). Вот краткое описание проблематики (ключевой тут рис. 1). Немного есть про это вот в этом видео (в концовке как раз об этом, впрочем, начало тоже интересное, но не об этом). Речь идет о том, что большинство крупных мегаполисов живут в режимах, когда есть и много пробок. Почему это так? Математическое объяснение есть в книге (см. приложение Малышева-Замятина). Собственно, эта тема дальше развивается в Исследовательской задаче (такой раздел есть в книге) «Задача о критическом числе автомобилей для заданного города». Предложите свой вариант такого типа задачи и получите практическое подтверждение наличия фазового перехода. Проект практический.
Проект 11. Четыре рукопожатия и как это посчитать?
В замечательной книге Райгородского-Литвак совсем по-простому рассказано о том, как современные социальные сети решают различные задачи подсчета (см. сюжет из Главы 7 Счетчики с короткой памятью и в частности Четыре виртуальных рукопожатия). Попробуйте разобрать пример из статьи Себастьяна Виньи на более продвинутом уровне чем в популярной книге Райгородского-Литвак. В частности, помочь может вот эта книга. Цель проекта продемонстрировать математику, которая есть вокруг этого сюжета (в частности, хеширование). Проект теоретический, но чтобы получить по нему хорошую оценку нужно либо довольно тонко освоить теорию, либо провести достаточно понятные эксперименты, подтверждающие теорию...
Проект 12. Межгрупповая вражда способствует внутригрупповому сотрудничеству
В другой интересной книге А.А. Маркова в главе 5 есть параграф, который называется так как этот проект. Прочитайте параграф, постарайтесь понять о чем идет речь. В параграфе описывается некоторое равновесие макросистемы. Попробуйте придумать каку-то разумную динамику, которая бы приводила к такому равновесию (соответствующие заготовки могут быть почерпнуты из 6 главы книги). Нужно не только придумать, подтвердить экспериментально, но и попробовать математически обосновать, что предложенная динамика, действительно, выходит на нужное равновесие…
P.S. В целом, очень рекомендую эту книгу Маркова, если есть желание получше разобраться как устроены люди. Кажется, в этой книге есть и много других интересных сюжетов (например, парадокс Симпсона, теория Гамильтона — родственного отбора, и многое другое), которые, по-видимому, качественно улавливают какие-то закономерности, управляющие поведением людей.
По итогам этого проекта появилась статья.
Проект 13. Кинетика социального неравенства
Решите задачу 4 на стр. 154-162. Решение требуется привести математическое. Это один вариант сдачи проекта. Второй вариант — предложить свои вариации модели обмена монетками, которые приводят к более интересным асимптотикам. В этом случае обоснование формы предельных кривых может быть схематичным, но желательно тогда подтверждение численными экспериментами.
Проект 14. Двойной спуск, сложный проект!
В последние годы в задачах обучения наблюдается довольно интересный эффект, что если модель сильно переобучена, то U-образная кривая снова начинает убывать. Математика этого эффекта еще далека от своего окончательного объяснения, но все же попытки это объяснить имеются. В том числе довольно компактные. Более того, все эти вопросы оказываются завязанными на так называемое условие Поляка-Лоясиевича (градиентного доминирования). К сожалению, на данный момент неизвестны нижние оценки для гладких задач оптимизации в условиях Поляка-Лоясиевича. При том, что много интересных результатов о сходимости градиентного типа методов (в том числе и их стохастических вариантов) есть. Проект, по-видимому, достаточно сложный. Целью проекта является продвинуться в понимание, какие нижние оценки имеют место для методов типа градиентного спуска в условиях Поляка-Лоясиевича. Гипотеза, что имеющиеся верхние оценки оптимальны. То есть ускорения в условиях Поляка-Лоясиевича нет. Проблема тут с использованием стандартной техники получения нижних оценок упражнения 1.3 и 2.1. Нужно найти подобную плохую функцию, удовлетворяющую условию Поляка-Лоясиевича. Ну или как-то еще посмотреть на эту задачу.
Проект 15. Гамильтоновы пути и концентрация меры
Хорошо известно, что задача поиска гамильтонова пути — NP-трудна. А именно, трудной является задача почтальона: в каком порядке надо обойти дома на своем участке и вернуться в отделение почты (откуда и стартует маршрут), чтобы суммарная длина пути была бы минимальна? Конечно, метрический коммивояжер уже немного попроще (веса ребер графа отвечают некоторой топологии реальной дорожной сети, скажем на плоскости), чем общая задача. Все равно эта задача остается сложной и улучшается у нее только различные аппроксимационные характеристики. Представим себе, что теперь у нас город — это квадрат со стороной 1. В городе n домов. Все дома случайно и независимо построены (дом - это точка в квадрате, обе координаты которой выбираются независимо и из равномерного распределения). Обозначим длину кратчайшего (гамильтонового) пути в таком графе через TSP(n). Это будет случайная величина. Покажите, что TSP(n) экспоненциально концентрируется около своего математического ожидания, пропорционального \sqrt{n}. Указание: Используйте книгу.
Проект 16. Устойчивые системы большой размерности
Попробуйте решить задачу
Проект 17. О типично худшем накоплении ошибки в линейных итерационных методах
Попробуйте решить задачу
Проект 17 от Максима Рахубы. Использование тензорных сетей для сжатия и восстановления изображений
В этом проекте предлагается познакомиться с тензорными сетями (обобщение матричных факторизаций на многомерный случай и их приложением для задач восстановления изображения по значениям в небольшом числе пикселей (tensor completion), а также для сжатия изображений. Для конкретики можно рассмотреть тензорные сети PEPS, тензорное кольцо и/или тензорный поезд. Для решения задач минимизации можете использовать несколько методов оптимизации на свой выбор, а также реализовать метод попеременных наименьших квадратов (ALS) (только для задачи сжатия). Для более детального ознакомления с постановкой задачи и одним из возможных алгоритмов прочитайте статью и ознакомьтесь с сайтом. В качестве фреймворка для написания проекта можно воспользоваться пакетом или альтернативными вариантами. Результатом работы по проекту должна стать jupyter тетрадка (можно ссылкой в colab), с кодом, кратким описанием используемых алгоритмов, а также графиками ошибки и значений PSNR от числа параметров в тензорных сетях для нескольких изображений.
По поводу вопросов пишите в ТГ @mrakhuba.
Проект 18 от Максима Рахубы. Методы римановой оптимизации и их приложение для рекомендательных систем
Известно, что множество матриц фиксированного ранга является римановым многообразием. Эту информацию можно использовать для построения эффективных методов поиска малоранговых приближений матриц. В этом проекте предлагается познакомиться с методами римановой оптимизации, реализовать риманов метод сопряженных градиентов, а также воспользоваться им для минимизации l1 нормы ошибки. В качестве приложения предлагается построить рекомендательную систему. Результатом работы по проекту должна стать jupyter тетрадка (можно ссылкой в colab), с кодом, кратким описанием используемых алгоритмов, а также графиками зависимости RMSE и одной из релевантных для рекомендательных систем метрик в зависимости от ранга.
По поводу вопросов пишите в ТГ @mrakhuba.
Проект 19 от Алексея Фролова. Граница случайного кодирования для задачи сжатия измерений массового некоординированного множественного доступа
В работе [1] введена теоретико-информационная модель массового некоординированного множественного доступа и получена граница случайного кодирования, которую можно применять как в асимптотическом, так и неасимптотическом режимах. Улучшение для асимптотического режима предложено в работе [2] с использованием леммы Гордона (Gordon’s lemma) о минимуме гауссовского процесса. Задача данного проекта заключается в получении неасимптотической версии границы из [2]. Также разрешается применять любые другие методы уточнения аддитивной границы из [1], например, предложенную на лекции локальную лемму Ловаша.
1. Y. Polyanskiy, “A perspective on massive random-access,” IEEE Information Theory (ISIT), 2017.
2. I. Zadik, Y. Polyanskiy, and C. Thrampoulidis, “Improved bounds on Gaussian MAC and sparse regression via Gaussian inequalities,” IEEE International Symposium on Information Theory (ISIT), 2019
Exam program
A test paper is available for review