We are interested in the following question: suppose we generate a large graph according to the linear preferential attachment model---can we say anything about the initial (seed) graph? A precise answer to this question could lead to new insights for the diverse applications of the preferential attachment model. In this work we focus on the case of trees grown according to the preferential attachment model. We first show that the seed has no effect from a weak local limit point…

Given n vectors rj in n-space with all coefficients in one wants a vector x=(x1,...,xn) with all xi=+1 or −1 so that all dot products x⋅rj are at most Kn‾√ in absolute value, K an absolute constant. A random x would make x⋅rj roughly Gaussian but there would be outliers. The existence of such an x was first shown by the speaker, resolving a discrepancy question of Paul Erdős. However, the original argument did not give an effective algorithm. The…

Modern techniques in data accumulation and sensing have led to an explosion in both the volume and variety of data. Many of the resulting estimation problems are high-dimensional, meaning that the number of parameters to estimate can be far greater than the number of examples. A major focus of my work has been developing an understanding of how hidden low-complexity structure in large datasets can be used to develop computationally efficient estimation methods. I will discuss a framework for establishing…

In this talk we will introduce a new model of a growing sequence of random graphs where a new vertex is less likely to join to an existing vertex with high degree and more likely to join to a vertex with low degree. In contrast to the well studied model of preferential attachment random graphs where higher degree vertices are preferred, we will call our model de-preferential attachment random graph model. We will consider two types of de-preferential attachment models,…

In this talk we will consider inference with high dimensional data. We propose new methods for estimating and constructing confidence regions for a regression parameter of primary interest alpha_0, a parameter in front of the regressor of interest, such as the treatment variable or a policy variable. We show how to apply these methods to Z-estimators (for example, logistic regression and quantile regression). These methods allow to estimate alpha_0 at the root-n rate when the total number p of other…

Achieving balance between experimental groups is a cornerstone of causal inference. Without balance any observed difference may be attributed to a difference other than the treatment alone. In controlled/clinical trials, where the experimenter controls the administration of treatment, complete randomization of subjects has been the golden standard for achieving this balance because it allows for unbiased and consistent estimation and inference in the absence of any a priori knowledge or measurements. However, since estimator variance under complete randomization may be…

Superposition codes are asymptotically capacity achieving scheme for the Additive White Gaussian Noise channel. I will first show how a practical iterative decoder can be built based on a Belief Propagation type approach, closely related to the one performed in compressed sensing and sparse estimation problems. Secondly, I will show how the idea of spatial coupling in this context allows to built efficient and practical capacity achieving coding and decoding schemes. The links between the present problem, sparse estimations, and…

A central problem in analyzing networks is partitioning them into modules or communities, clusters with a statistically homogeneous pattern of links to each other or to the rest of the network. A principled approach to address this problem is to fit the network on a stochastic block model, this task is, however, intractable exactly. In this talk we discuss application of belief propagation algorithm to module detection. In the first part we present an asymptotically exact analysis of the stochastic…

While much attention has been paid recently to the construction of optimal algorithms that adaptively estimate low-dimensional parameters (described by sparsity, low-rank, or smoothness) in high-dimensional models, the theory of statistical inference and uncertainty quantification (in particular hypothesis tests & confidence sets) is much less well-developed. We will discuss some perhaps surprising impossibility results in the basic high-dimensional compressed sensing model, and some of the recently remerging positive results in the area.

We will discuss recent moment bounds and concentration inequalities for sample covariance operators based on a sample of n i.i.d. Gaussian random variables taking values in an infinite dimensional space. These bounds show that the size of the operator norm of the deviation of sample covariance from the true covariance can be completely characterized by two parameters: the operator norm of the true covariance and its so called "effective rank". These results rely on Talagrand's generic chaining bounds and on…