Публикации

Let X_1, ... ,X_n be i.i.d. sample in R^p with zero mean and the covariance matrix S. The problem of recovering the projector onto the eigenspace of S from these observations naturally arises in many applications. Recent technique from [Koltchinskii and Lounici, 2015b] helps to study the asymptotic distribution of the distance in the Frobenius norm between the true projector P_r on the subspace of the r-th eigenvalue and its empirical counterpart \hat{P}_r in terms of the effective trace of S. This paper offers a bootstrap procedure for building sharp confidence sets for the true projector P_r from the given data. This procedure does not rely on the asymptotic distribution of || P_r - \hat{P}_r ||_2 and its moments, it applies for small or moderate sample size n and large dimension p. The main result states the validity of the proposed procedure for finite samples with an explicit error bound on the error of bootstrap approximation. This bound involves some new sharp results on Gaussian comparison and Gaussian anti-concentration in high dimension. Numeric results confirm a nice performance of the method in realistic examples. 

We derive tight non-asymptotic bounds for the Kolmogorov distance between the probabilities of two Gaussian elements to hit a ball in a Hilbert space. The key property of these bounds is that they are dimension-free and depend on the nuclear (Schatten-one) norm of the difference between the covariance operators of the elements and on the norm of the mean shift. The obtained bounds significantly improve the bound based on Pinsker's inequality via the Kullback-Leibler divergence. We also establish an anti-concentration bound for a squared norm of a non-centered Gaussian element in Hilbert space. The paper presents a number of examples motivating our results and applications of the obtained bounds to statistical inference and to high-dimensional CLT.

Новый век кредитного скоринга и принятия решений

Currently, there are digital services that provide transactions between private contractors and their customers. A third party provides information, safety and security of transactions. The article is devoted to introduction of blockchain technology in business model of ‘People-to-People Economy’ (P2PE). Following the results of the work, an application for lease/rent lodgings for a short term was implemented. The paper describes the domain overview, choice of architectural solution and description of the application implementation.

В работе предлагается новая концепция (δ, L)-модели функции, которая обобщает концепцию (δ, L)-оракула Деволдера–Глинера–Нестерова. В рамках этой концепции строятся градиентный спуск, быстрый градиентный спуск и показывается, что многие известные ранее конструкции методов (композитные методы, методы уровней, метод условных градиентов, проксимальные методы) являются частными случаями предложенных в данной работе методов.

Книга содержит необходимые сведения из теории алгоритмов, теории графов, комбинаторики. Рассматриваются частично рекурсивные функции, машины Тьюринга, приводятся некоторые варианты алгоритмов (ассоциативные исчисления, системы подстановок, грамматики, продукции Поста, нормальные алгоритмы Маркова, операторные алгоритмы). Описываются основные типы графов (мультиграфы, псевдографы, эйлеровы графы, гамильтоновы графы, деревья, двудольные графы, паросочетания, сети Петри, планарные графы, транспортные сети). Приводятся некоторые часто используемые в практике алгоритмы на графах. Рассматриваются классические комбинаторные конфигурации и их производящие функции, рекуррентные последовательности. В основу книги положен многолетний опыт преподавания авторами дисциплины «Дискретная математика» на факультете бизнес-информатика, на факультете компьютерных наук Национального исследовательского университета Высшая школа экономики и на факультете автоматики и вычислительной техники Национального исследовательского университета  Московский энергетический институт. Книга предназначена для студентов бакалавриата, обучающихся по направлениям 09.03.01 «Информатика и вычислительная техника», 09.03.02 «Информационные системы и технологии», 09.03.03 «Прикладная информатика», 09.03.04 «Программная инженерия», а также для ИТ-специалистов и разработчиков программных продуктов.

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

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

Другая особенность учебника состоит в том, что в каждую главу включен и достаточно трудный материал. Это делает учебник интересным студентам разного уровня подготовки.

Изложение книги сопровождается задачами разного уровня сложности.

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