КАРТОЧКА ПРОЕКТА,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ


Номер 18-11-00132

НазваниеАнализ случайных объектов высокой размерности и приложения к задачам обработки больших массивов данных

РуководительНаумов Алексей Александрович, Кандидат физико-математических наук

Организация финансирования, регионфедеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский университет "Высшая школа экономики", г Москва

Года выполнения при поддержке РНФ2018 - 2020

КонкурсКонкурс 2018 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами»

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах, 01-110 - Теория вероятностей и математическая статистика

Ключевые словаобнаружение сообществ, кластеризация, случайные матрицы, случайные графы, ковариационные матрицы, многомерные статистики

Код ГРНТИ27.43.00


 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ


Аннотация
Многие теоретические и прикладные задачи в математической физике, машинном обучении, компьютерных науках, теории передачи, хранения и обработки больших объемов информации естественным образом связаны с изучением свойств случайных объектов высокой размерности -- случайных матриц и случайных графов. Исследованию данных объектов посвящены исследования передовых научных групп во всем мире. Настоящий проект нацелен на разработку общих аналитических подходов и методов, позволяющих решать широкий круг важнейших теоретических и прикладных задач, среди которых: исследование спектральных статистик функций от случайных матриц высокой размерности и их приложения; оценивание высокоразмерных ковариационных матриц при наличии ошибок в наблюдениях; анализ динамики сообществ в графах и кластеризация. Полученные результаты могут быть применены для решения прикладных задач, в частности, при изучении сообществ в сетях, надежности прогнозов, полученных с помощью методов машинного обучения и глубинных сетей, а также для оценивания пространственных зависимостей в климатических данных.

Ожидаемые результаты
Проект направлен на создание единого подхода к широкому кругу теоретических и прикладных задач, возникающих при анализе случайных объектов высокой размерности. Разработка такого подхода актуальна для теоретической математики, а полученные результаты могут быть применены для решения прикладных задач, в частности, при изучении сообществ в сетях, надежности прогнозов, полученных с помощью методов машинного обучения и глубинных сетей, а также для оценивания пространственных зависимостей в климатических данных. Планируется получение следующих фундаментальных и прикладных результатов: - Исследование локального поведения спектра (собственного и сингулярного) и универсальности широкого класса функций от случайных матриц. Изучение концентрации нормы случайной матрицы вокруг среднего. Разработка методов оценивания скрытой клики . А также приложения к нахождению точности приближений асимптотическими разложениями для распределений многомерных статистик, которые записываются в терминах спектров случайных матриц большой размерности, в случае нелинейной зависимости статистик от элементов выборки при различных соотношениях между объемом выборки и размерностью наблюдений. - Разработка и имплементация алгоритма поиска сообществ в сетях, основанного на идее множественного статистического тестирования на зазор между каждыми двумя локальными сообществами. Планируется теоретическое обоснование работы алгоритма, а также применение к задачам и реальным данным в биологии, медицине, социальным и интернет сетям. Также планируется изучение динамики сообществ во времени и построение (с теоретическим обоснованием) алгоритма обнаружения разладки в структуре сообществ. - Разработка методов оценивания высокоразмерных разреженных ковариационных матриц при наличии ошибок в наблюдениях. Изучение асимптотических свойств полученных оценок и построение доверительных интервалов. Применение к оценивания пространственных зависимостей в климатических данных. Результаты, полученные по проекту, будут опубликованы в серии статей (не менее 11 за весь период работы) в ведущих отечественных и международных журналах из списков WoS и Scopus, представлены на российских и международных конференциях. Результаты также составят основу одной монографии. Кроме того, они будут включены в 1 кандидатскую диссертацию участников группы и ряд магистерских диссертаций. Все эти результаты будут соответствовать передовому уровню современных мировых исследований. Планируется, что большинство результатов составят основу для курсов, читаемых студентам бакалавриата, магистратуры и аспирантуры ведущих российских университетов и академических центров, в частности на магистерской программе "Статистическая теория обучения" (совместная магистерская программа Сколтеха и НИУ ВШЭ, академический руководитель В.Г. Спокойный).


 

ОТЧЁТНЫЕ МАТЕРИАЛЫ


Аннотация результатов, полученных в 2018 году
Коллектив гранта в 2018 году опубликовал следующие результаты: 1. Доказаны неравенство сравнения и анти-концентрации для квадратов норм центрированных гауссовских элементов в произвольном сепарабельном гильбертовом пространстве. Опубликована статья F. Gotze, A. Naumov, V. Spokoiny and V. Ulyanov. Nonasymptotic Estimates for the Closeness of Gaussian Measures on Balls, Doklady Mathematics, 98 (2), 490–493, 2018, https://link.springer.com/article/10.1134%2FS1064562418060248 2. Предложена процедура для построения доверительных множеств для спектральных проекторов ковариационной матрицы, основанная на Байесовском подходе. Доказаны теоретические оценки и проведены численные эксперименты, подтверждающие высокую точность алгоритма. Опубликована статья Silin, V. Spokoiny, Bayesian inference for spectral projectors of the covariance matrix, Electron. J. Statistics., 12, 1948–1987, 2018. DOI:10.1214/18-EJS1451, https://projecteuclid.org/euclid.ejs/1529308884 4. Разработан новый эффективный метод оценивания плотности решения многомерного стохастического дифференциального уравнения типа Маккина Власова при наличии разреженности в спектральном представлении коэффициентов разложения. Получены оптимальные порядки сходимости основанные. Опубликована статья Belomestny, D. and Schoenmakers, J., 2018. Projected Particle Methods for Solving McKean--Vlasov Stochastic Differential Equations. SIAM Journal on Numerical Analysis, 56(6), pp.3169-3195. https://epubs.siam.org/doi/abs/10.1137/17M1111024 4. Изучен вопрос снижения неопределенности в задаче вычисления математических ожиданий по высокоразмерным распределениям. Предложен новый метод снижения неопределенности основанный на минимизации эмпирической дисперсии по классу контрольных функционалов и проведен анализ его сложности. При этом получены новые концентрационные неравенства для квадратичных форм. Опубликована статья Belomestny, D.V., Iosipoi, L.S. and Zhivotovskiy, N.K., Variance Reduction in Monte Carlo Estimators via Empirical Variance Minimization. In Doklady Mathematics (Vol. 98, No. 2, pp. 494-497, 2018, https://link.springer.com/article/10.1134%2FS1064562418060261 Подготовил к публикации препринты: 1. Разработан новый алгоритм для оценивания разреженных ковариационных матриц и их собственных подпространств по последовательно приходящим по времени наблюдениям. Получены неасимптотические оценки скорости сходимости предложенного алгоритма. Опубликована препринт Belomestny, D. and Krymova, E., 2018. Sparse constrained projection approximation subspace tracking, arXiv preprint arXiv:1810.09298, https://arxiv.org/abs/1810.09298 . Статья представлена в журнал. 2. Доказана точная неасимптотическая оценка для отклонения спектральной нормы матрицы инцидентности случайного графа от своего математического ожидания. Доказана аналогичная равномерная оценка для графового процесса Ердеша-Реньи. Подготовлен препринт Lugosi G., Mendelson S., Zhivotovskiy N. Concentration of the spectral norm of Erdős-Rényi random graphs. arXiv preprint arXiv:1801.02157, https://arxiv.org/abs/1801.02157 . Статья представлена в журнал. 3. Доказан локальный закон для собственных значений произведения независимых случайных матриц из ансамбля Гирко-Жинибра в предположении, что существует момента порядка 4 + epsilon у распределений элементов матрицы. Опубликован препринт Goetze, F., Naumov, A., Tikhomirov, A. On Local laws for non-Hermitian random matrices and their products, ArXiV: 1708.06950v2https://arxiv.org/abs/1708.06950. Статья представлена в журнал. 4. Разработаны новые подходы, учитывающие тот факт, что размерность наблюдений p может расти одновременно с объемом выборки n таким образом, что отношение p/n стремится к некоторому числу на интервале (0,1). Предложенный метод позволил получить новые вычислимые оценки порядка log(n)/\sqrt(n) для ошибок приближения распределений многомерных статистик с нелинейной зависимостью от элементов выборки, в частности, для статистик, используемых в многомерном дисперсионном анализе, включая статистики Хотеллинга и Бартлетт-Нанда-Пиллай. На основе полученных результатов подготовлена работа, публикация которой ожидается в 2019 году. 5. Получено оптимальное неравенство, выражающее близость оценки к ковариационной матрице, не зависящее явным образом от размерности задачи. Подготовлен препринт Klochkov, E. Zhivotovskiy, N., Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method, arXiv preprint, arXiv:1812.03548, https://arxiv.org/abs/1812.03548

 

Публикации

1. Беломестный Д. В., Животовский Н. К, Иосипой Л. Снижение дисперсии оценки Монте-Карло методом минимизации эмпирической дисперсии Доклады Академии Наук. Математика., 98. № 2. С. 494-497, 2018 (год публикации - 2018).

2. Беломестный Д.В., Шоенмакерс Д. PROJECTED PARTICLE METHODS FOR SOLVING MCKEAN−VLASOV STOCHASTIC DIFFERENTIAL EQUATIONS SIAM Journal on Numerical Analysis, Vol. 56. No. 6. P. 3169-3195 (год публикации - 2018).

3. Наумов А.А., Спокойный В.Г., Тавыриков Ю.Е., Ульянов В.В. Nonasymptotic Estimates for the Closeness of Gaussian Measures on Balls Doklady Mathematics, 018, Vol. 98, No. 2, pp. 490–493 (год публикации - 2018).

4. Силин И.В., Спокойный В.Г. Bayesian inference for spectral projectors of the covariance matrix Electronic Journal of Statistics, Vol. 12 (2018) 1948-1987 (год публикации - 2018).