Математика больших данных, осень 2023

По средам с 17:00 до 19:30, с 6 сентября

Аудитория 113 ГК

О курсе

Альтернативный курс для студентов 4-5 курса ПМФ ФПМИ. Проводится совместно с Независимым московским университетом (НМУ) и будет зачитываться также в НМУ.

Программа курса:

1 лекция (6 сентября) Вводная. В частности, схема испытаний Бернулли с точки зрения современного анализа данных. Задача PageRank. Обсуждение плана на семестр.

2 лекция (13 сентября) Вокруг энтропии. Элементы теории макросистем (принцип максимума энтропии): в частности, Задача 19 (теорема Гордона–Ньюэлла и PageRank). Кинетика социального неравенства. Модель хищник-жертва. Парадокс Эренфестов. Теорема Шеннона об энтропии текста; А.М. Яглом, «Вероятность и информация».

3 лекция (20 сентября) Алексей Фролов (tg: @frolov_alexey) Теоретико-информационные границы для задачи приближенного восстановления носителя. Лекция А. Фролова Approximate Support Recovery на Youtube.

Аннотация:

В рамках лекции мы рассмотрим задачу восстановление носителя неизвестного разреженного вектора по небольшому количеству зашумленных линейных измерений. Рассматривается случай большой размерности. С помощью вероятностного метода (или метода случайного кодирования) будут выведены две границы существования. В обоих случаях используется аддитивная граница, но для ее уточнения применяются методы Фано и Галлагера.

4 лекция (27 сентября) Эргодическая теорема для динамических систем. Примеры поворот окружности, цепные дроби. Модель Блэка-Шоулса-Мертона, диффузионный скейлинг. Введение в диффузионные процессы. Иммитация отжига.

5 лекция (4 октября) MCMC. Явление концентрации меры и различные примеры приложений. Теорема Джонсона-Линденштраусса.

Blum A., Hopcroft J., Kannan R. Foundations of data science. – Cambridge University Press, 2020.

6 лекция (11 октября) Сергей Самсонов (tg: @ssamsonov). Неравенства концентрации меры и приложения к статистической теории обучения. Оценки переобучения. Лекция С. Самсонова «Многорукие бандиты/Субгауссовские и экспоненциальные величины» на Youtube.

7 лекция (18 октября) Андрей Соболевский (tg: @sobolevski). Большие отклонения. Метод перевала и его использование в исследовании различных асимптотик. Лекция А. Соболевского «Введение в мультифрактальный анализ» на Youtube.

8 лекция (25 октября) Стохастический градиентный спуск и окрестности. Рандомизированные методы. Батчирование. Сходимость в условиях перепараметризации. Многорукие бандиты.

9 лекция (1 ноября) Распределенная оптимизация для решения задач огромных размеров. Компрессии. Федеративное обучение.

10 лекция (8 ноября) Максим Рахуба (tg: @mrakhuba). Матричные разложения. Лекция М.Рахубы о малоранговой аппроксимации матриц. Презентация к лекции на Youtube.

Скелетное и сингулярное разложение матриц. Псевдоскелетная аппроксимация. Оптимизационные методы: ALS, риманова оптимизация.

11 лекция (15 ноября) Максим Рахуба (tg: @mrakhuba). Тензорные разложения. Лекция М. Рахубы о тензорных разложениях, сети, а также оптимизационные методы для тензорных разложений на Youtube.

Каноническое разложение, разложение Таккера, тензорные сети. Оптимизационные методы для тензорных разложений.

12 лекция (22 ноября) Никита Пучкин (tg: @nikita_puchkin). Алгоритмическая устойчивость. Оценки на обобщающую способность равномерно устойчивых алгоритмов. Лекция Н. Пучкина о неравенстве Пуанкаре, логарифмическом неравенстве Соболева и концентрации меры на Youtube.

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

1) J. Cheeger, “A lower bound for the smallest eigenvalue of the Laplacian”, Problems in Analysis, Symposium in honor of S. Bochner, Princeton Univ. Press, Princeton, NJ, 1970, pp. 195-199.

2) M. Ledoux, “A simple analytic proof of an inequality by P. Buser”, Proceedings of the American Mathematical Society, 121(3), pp. 951-959, 1994.

3) M. Talagrand, “New concentration inequalities in product spaces”, Inventiones mathematicae, 126, pp. 505-563, 1996.

4) O. Bousquet, “A Bennett concentration inequality and its application to suprema of empirical processes”, Comptes Rendus Mathematique, 334(6), pp. 495-500, 2002.

5) T. Klein, E. Rio, “Concentration around the mean for maxima of empirical processes”, The Annals of Probability, 33(3), pp. 1060-1077, 2005.

6) M. Ledoux, “Four Talagrand inequalities under the same umbrella”, preprint, arXiv:1909.00363, 2019.

7) Y. Klochkov, N. Zhivotovskiy, “Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)”, Advances in Neural Information Processing Systems 34 (NeurIPS), 2021.

8) S. Bobkov, M. Ledoux, “Poincare ’s inequalities and Talagrand’s concentration phenomenon for
the exponential distribution”, Probability Theory and Related Fields, 107, pp. 383-400, 1997.

9) D. Bakry, F. Barthe, P. Cattiaux, A. Guillin, “A simple proof of the Poincare inequality for a large class of probability measures including the log-concave case”, Electronic Communications in Probability, 13, pp. 60-66, 2008.

10) S. Bobkov, M. Ledoux, “From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities”, Geometric and Functional Analysis (GAFA), 10, pp. 1028-1062, 2000.

13 лекция (29 ноября) Обучение с подкреплением с точки зрения линейнонго программирования. Уравнения Вальда-Беллмана. Индексы Гиттинса. DMDP, AMDP, HMDP и SOTA результаты.

Литература к лекции.

1) Лекции по случайным процессам под редакцией А. В. Гасникова.

2) Reinforcement Learning: Theory and Algorithms.

3) С.М.Гусейн-Заде. Разборчивая невеста.

4) Richard Weber. Multi-armed Bandits and the Gittins Index Theorem.