Structural Learning Seminar — семинар, объединяющий исследователей, аспирантов и студентов Сколтеха, Сектора №7 ИППИ РАН и НИУ ВШЭ. На семинаре обсуждаются задачи, которые находятся на стыке различных дисциплин математики и компьютерных наук: математической статистики, машинного обучения, теории случайных матриц, оптимизации, теории информации и других.

Академический руководитель семинара: Владимир Григорьевич Спокойный.
Организаторы: Никита Животовский, Леонид Иосипой, Алексей Наумов, Максим Панов.

Семинар проходит по четвергам в ИППИ РАН, ауд. 615, в 17:00 (если не указано иное).

Весна 2017

02.03.2017

Денис Беломестный (ВШЭ, Duisburg-Essen University):

Efficient simulation of Levy areas and related problems.

In this talk I review some known method for simulating Levy area which plays an important role in stochastic and numerical analysis.

Радомир Бритков (Сколтех)

Обзор работы: A. Carpentier, J. Eisert, D. Gross, R. Nickl "Uncertainty Quantification for Matrix Compressed Sensing and QuantumTomography Problems".

Осень 2016

15.12.2016

Никита Животовский (Сколтех, ИППИ РАН)

How to control empirical processes without using chaining?

The theory of empirical processes is well-developed for the worst-case deviations of sums of i.i.d random variables from their means. However, the general theory involving functions of independent random variables or certain cases of localized analysis are still an active area of research. In this short talk, we will discuss several preliminary steps in both directions, based on entropies with the bracketing.

08.12.2016

Владимир Васильевич Ульянов (ВМК МГУ)

Асимптотический и неасимптотический анализ для нелинейных форм от случайных элементов

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

Алексей Наумов (Сколтех)

Variations on the Berry-Esseen theorem by B. Klartag and S. Sodin

In this work the authors analyze the quality of the gaussian approximation to linear combinations of n independent, identically-distributed random variables with finite fourth moments. It turns out that there exist universal, simple linear combinations that perform better than the sum of the variables. We also investigate the case in which the random variables are independent, yet they are not necessarily identically distributed.

01.12.2016

Назарий Тупица (МФТИ)

Линейная регрессия со случайным дизайном

В докладе будут коротко рассмотрены теоремы Фишера и Вилкса, а также неравенство концентрации для score-вектора в случае известного шума, затем они будут обобщены на случай неизвестного шума. Для этого будет построена оценка ковариационной матрицы score-вектора с помощью бутсрепа. Будет рассмотрено качество этой оценки.

Евгений Маршаков (Сколтех)

Differential Geometry with Applications to Low-Rank Matrix Completion

We will tell a few words about Riemannian optimization for low-rank matrix completion problem, more precisely, about algorithm that minimizes the least-square distance on the sampling set over fixed-rank matrices manifold. During the talk we will discuss in detail differential geometry that appears in proposed algorithm.

24.11.2016

Андрей Купавский (EPFL, МФТИ)

Верхние и нижние оценки размера эпсилон-сетей

Пусть дано множество [n] из n элементов и некоторое семейство подмножеств этого множества. Подножество X в [n] называется эпсилон-сетью, если любое множество из семейства размера больше эпсилон n пересекается с X. В этом докладе я расскажу про последние результаты, касающиеся размера минимальных эпсилон-сетей для различных систем множеств. В частности, речь пойдет о верхней оценке Чана и др., основанной на так называемой shallow cell complexity, и о нижних оценках размера эпсилон-сетей для семейств множеств, заданных геометрически.

18.11.2016

Денис Беломестный (University of Duisburg-Essen)

Threshold estimation for sparse high-dimensional deconvolution

The problem of covariance estimation for a p-dimensional normal vector X ∼ N(0, Σ) observed with additional noise is studied. Only a very general non-parametric assumption is imposed on the distribution of the noise. In this semi-parametric deconvolution problem spectral thresholding estimators are constructed that adapt to sparsity in Σ. We prove that the minimax convergence rates logarithmic in (logp)/n with n being the sample size.

10.11.2016

Евгений Фролов (Сколтех)

Tensor Methods and Recommender Systems

Доклад посвящен применению тензорных методов в рекомендательных системах. Будут разобраны задачи построения моделей поведения пользователей на основе тензорных разложений, таких как каноническое разложение и разложение Такера. Области применения рассматриваемых подходов будут включать контекстно-зависимые рекомендации, рекомендации на основе ключевых слов или меток (тэгов), рекомендации с учетом трендов и изменений во времени. Будет также рассмотрена задача моделирования субъективной функции полезности и ряд концептуальных проблем, устраняемых с помощью тензорной формулировки.

03.11.2016

Павел Яськов (МИ РАН им. В.А. Стеклова)

Вокруг теоремы Марченко-Пастура

Доклад будет строиться вокруг теоремы Марченко-Пастура для выборочных ковариационных матриц и условия слабой концентрации для квадратичных форм. Будет продемонстрировано, что данное условие при некоторых дополнительных ограничениях является необходимым и достаточным для выполнимости теоремы Марченко-Пастура. Также будет рассказано, как данное условие приводит к глобальному анизотропному закону для резольвент выборочных ковариационных матриц.

Александр Подкопаев (Сколтех)

Dimension reduction in unsupervised learning via Non-Gaussian Component Analysis

The report will be focused on the dimension reduction topic. In this talk, we will discuss methods based on Non-gaussian component analysis (NGCA). It can be formulated as a problem of identifying a low-dimensional non-Gaussian component of the whole distribution in an iterative and structure adaptive way. In more details, we will mainly consider NGCA procedure of identification of the non-Gaussian subspace using Principle Component Analysis (PCA) method, sparse NGCA (SNGCA) which replaces the PCA-based procedure with an algorithm based on convex projection and approach for direct estimation of the projector on the target subspace based on semidefinite programming. Recovering the structure when its effective dimension is unknown will be also discussed.

27.10.2016

Quentin Paris (ФЭН ВШЭ)

Recent advances on the occupancy problem

From a classical point of view, the occupancy problem (also known as the urn scheme) is to describe the spread (or repartition) of a random sample over its support when it is drawn from a discrete distribution. In this talk we will start by briefly describing the problem and state a few well known results concerning the asymptotic behaviour and concentration of the so called occupancy probabilities. In the second part of the talk, we will present new results concerning finite sample (upper and lower) bounds for the occupancy probabilities. Finally, the third and last part of the talk will discuss some results and perspectives outside of the i.i.d. and discrete context: arbitrary distributions in a metric space and Markov chains.

Игорь Силин (Сколтех)

Dimension reduction in unsupervised learning via Non-Gaussian Component Analysis

В докладе рассматривается алгоритм восстановления графа по наблюдениям состояний системы в модели Изинга, которая так же известна как Markov Random Field. Последние годы данная тема представляет большой интерес в статистике, машинном обучении и статистической физике. В начале будет введена вероятностная модель, затем будут отмечены некоторые ее свойства и поставлена задача. Затем будет предложен алгоритм, решающий задачу. Наконец, будет дано теоретическое объяснение его корректности. Предлагаемый алгоритм не требует никаких сильных предположений, кроме идентифицируемости модели. В основе алгоритма лежат свойства такой величины как "условное влияние" одной вершины на другую.

20.10.2016

Алексей Зайцев (ИППИ РАН)

Минимаксно оптимальное отношение размеров выборок данных разной точности

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

13.10.2016

Любовь Маркович (ИПУ РАН)

Вероятностные, информационные и корреляционные характеристики квантовых систем

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

Никита Животовский (ИППИ РАН)

High probability upper bounds, online learning, and stability

In statistical learning, the guarantees for many learning algorithms are provided both in expectation and with high probability with respect to the learning sample. Usually, the concentration of measure inequalities provide sharp tails and reduce the problem to the analysis in expectation. But when considering some learning algorithms other than empirical risk minimization powerful concentration results are of no use and tight high probability bounds become an inaccessible dream. Simultaneously, tight results in expectation can be proven as a two line exercise via stability arguments. In this talk, we will discuss several successful approaches towards getting high probability bounds including the online to batch conversion and the analysis of monotonic learning rules.

06.10.2016

Massih-Reza Amini (Universite Grenoble Alpes)

Multi-class to Binary reduction of Large-scale classification Problems

In the context of large-scale problems, traditional multiclass classification approaches have to deal with class imbalancement and complexity issues which make them inoperative in some extreme cases. In this talk we present a transformation that reduces the initial multiclass classification of examples into a binary classification of pairs of examples and classes. We present generalization error bounds that exhibit the interdependency between the pairs of examples and which recover known results on binary classification with i.i.d. data. We show the efficiency of the deduced algorithm compared to state-of-the-art multiclass classification strategies on two large-scale document collections especially in the interesting case where the number of classes becomes very large.

Никита Пучкин (ФУПМ МФТИ)

Spatial aggregation of local likelyhood estimates with applications to classification (D. Belomestny, V. Spokoiny)

This paper presents a new method for spatially adaptive local (constant) likelihood estimation which applies to a broad class of nonparametric models, including the Gaussian, Poisson and binary response models. The main idea of the method is, given a sequence of local likelihood estimates (“weak” estimates), to construct a new aggregated estimate whose pointwise risk is of order of the smallest risk among all “weak” estimates. We also propose a new approach toward selecting the parameters of the procedure by providing the prescribed behavior of the resulting estimate in the simple parametric situation. We establish a number of important theoretical results concerning the optimality of the aggregated estimate. In particular, our “oracle” result claims that its risk is, up to some logarithmic multiplier, equal to the smallest risk for the given family of estimates. The performance of the procedure is illustrated by application to the classification problem. A numerical study demonstrates its reasonable performance in simulated and real-life examples.

Весна 2016

28.06.2016

Никита Животовский (ИППИ РАН)

Схемы сжатия выборок

23.06.2016

Алексей Наумов (ИППИ РАН)

Structured Random Matrices by Ramon van Handel (Часть II)

21.06.2016

Владимир Григорьевич Спокойный (институт им. Вейерштрасса, Берлин)

Bootstrap tuning in ordered model selection

14.06.2016

Валентин Сотсков (мехмат МГУ)

Roughness penalty for dimension reduction

07.06.2016

Александра Суворикова (университет им. Гумбольдта, Берлин)

Wasserstein barycenters of probability measures

24.05.2016

Никита Животовский (ИППИ РАН)

Равномерные законы больших чисел и локализация

17.05.2016

Назарий Тупица (ФРТК МФТИ)

Linear regression with random design

10.05.2016

Бекжан Керимкулов (ФКН ВШЭ)

User-friendly tail bounds for sums of random matrices by Joel A. Tropp

26.04.2016

Алексей Наумов (ИППИ РАН)

Structured Random Matrices by Ramon van Handel (Часть I)

19.04.2016

Максим Панов (ИППИ РАН)

Finite Sample Bernstein – von Mises Theorem for Semiparametric Problems

12.04.2016

Александра Дорофеева (ВМК МГУ)

Sharp deviation bounds for quadratic forms

05.04.2016

Леонид Иосипой (мехмат МГУ)

Parametric estimation. Fisher and Wilks Theorems