Abstract
We discuss recent theorems on both smooth and singular responses of large dense graphs to changes in edge and triangle density constraints. Smoothness requires control over typical (exponentially most) graphs with given sharp values of those two densities.
In particular we prove the existence of a connected open set S in the plane of edge and triangle densities, cut into two pieces S' and S" by the curve C corresponding to graphs with independent edges. For typical graphs G with given edge and triangle densities, every subgraph density of G is real analytic on S' and S" as a function of the edge and triangle densities. However these subgraph densities are not analytic, or even differentiable, on C.
Joint work with Joe Neeman and Lorenzo Sadun.
Abstract
In the theory of random graphs the giant component has remained a guiding theme since the seminal paper of Erdos and Renyi. It has long been observed that the emergence of the giant component is analogous to the survival of a Galton-Watson branching process. This analogy crystallises the interplay between the local and the global structure of a sparse random graph. In fact, the notion that the Galton-Watson tree is the limiting object of the 'local structure' of the Erdos and Renyi random graph can be formalised nicely in the language of 'local weak convergence' introduced by Benjamini and Schramm and by Aldous and Steele. The local structure and local weak limits found their applications also in message passing algorithms, such as Belief Propagation and Warning Propagation, to mention a few.
Turning our attention to a random graph with a topological constraint (e.g., a random planar graph) where the independence of edges is lost, we will show that the planarity constraint affects the global component structure substantially, which in turn affects the local structure.
Abstract
A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. The notion of quasirandom graphs, developed in the work of Rödl, Thomason, Chung, Graham and Wilson in 1980s, is particularly robust as several different properties of truly random graphs, e.g., subgraph density, edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is. We will discuss recent results on quasirandomness of various kinds of combinatorial structures (in particular, directed graphs, permutations and Latin squares) obtained using analytic tools provided by the theory of combinatorial limits.
Abstract
In this talk we study the random cluster model on essentially large girth and random regular graphs. We give explicit formula for the limiting free entropy of the random cluster model. Our result extends the work of Dembo, Montanari, Sly and Sun for the Potts model, and we prove a conjecture of Helmuth, Jenssen and Perkins about the phase transition of the random cluster model. This is joint work with Ferenc Bencs and Márton Borbényi.
The design of experiments involves an inescapable compromise between covariate balance and robustness. In this talk, we describe a formalization of this trade-off and introduce a new style of experimental design that allows experimenters to navigate it. The design is specified by a robustness parameter that bounds the worst-case mean squared error of an estimator of the average treatment effect. Subject to the experimenter’s desired level of robustness, the design aims to simultaneously balance all linear functions of potentially many covariates. The achieved level of balance is better than previously known possible, considerably better than what a fully random assignment would produce, and close to optimal given the desired level of robustness. We show that the mean squared error of the estimator is bounded by the minimum of the loss function of an implicit ridge regression of the potential outcomes on the covariates. The estimator does not itself conduct covariate adjustment, so one can interpret the approach as regression adjustment by design. Finally, we provide non-asymptotic tail bounds for the estimator, which facilitate the construction of conservative confidence intervals.
A well-known limitation of modeling causal systems via DAGs is their inability to encode context-specific information. Among the several proposed representations for context-specific causal information are the staged tree models, which are colored probability trees capable of expressing highly diverse context-specific information. The expressive power of staged trees comes at the cost of easy interpretability and the admittance of desirable properties useful in the development of causal discovery algorithms. In this talk, we consider a subfamily of staged trees, which we call CStrees, that admit an alternative representation via a sequence of DAGs. This alternate representation allows us to prove a Verma-Pearl-type characterization of model equivalence for CStrees which extends to the interventional setting, providing a graphical characterization of interventional CStree model equivalence. We will discuss these results and their potential applications to causal discovery algorithms for context-specific models based on interventional and observational data.
We consider testing and learning problems on causal Bayesian networks where the variables take values from a bounded domain. We address two problems: (i) Given access to observations and experiments on two unknown environments X and Y, test whether X=Y or X is far from Y. Here, two environments are equal if no intervention can distinguish between them. (ii) Given access to observations and experiments on an unknown environment X, learn a DAG that admits a causal model M such that X is close to M. For problem (i), we show that under natural sparsity assumptions on the underlying DAG, only O(log n) interventions and O~(n) samples/intervention is sufficient. This is joint work with Jayadev Acharya, Constantinos Daskalakis and Saravanan Kandasamy. For problem (ii), we consider the setting where there are two variables, and the goal is to learn whether X causes Y, Y causes X, or there is a hidden variable confounding the two. Under natural assumptions, we obtain a nearly tight characterization of the sample complexity that is sublinear in k. Moreover, there is a tradeoff between the number of observational samples and interventional samples. This is joint work with Jayadev Acharya, Sourbh Bhadane, Saravanan Kandasamy, and Ziteng Sun.
Data-driven design is making headway into a number of application areas, including protein, small-molecule, and materials engineering. The design goal is to construct an object with desired properties, such as a protein that binds to a target more tightly than previously observed. To that end, costly experimental measurements are being replaced with calls to a high-capacity regression model trained on labeled data, which can be leveraged in an in silico search for promising design candidates. The aim then is to discover designs that are better than the best design in the observed data. This goal puts machine-learning based design in a much more difficult spot than traditional applications of predictive modelling, since successful design requires, by definition, some degree of extrapolation---a pushing of the predictive models to its unknown limits, in parts of the design space that are a priori unknown. In this talk, I will discuss our methodological approaches to this problem, as well as report on some recent success in designing gene therapy delivery (AAV) libraries, useful for general downstream directed evolution selections.
Identifying which genetic variants influence medically relevant phenotypes is an important task both for therapeutic development and for risk prediction. In the last decade, genome wide association studies have been the most widely-used instrument to tackle this question. One challenge that they encounter is in the interplay between genetic variability and the structure of human populations. In this talk, we will focus on some opportunities that arise when one collects data from diverse populations and present statistical methods that allow us to leverage them. The presentation will be based on joint work with M. Sesia, S. Li, Z. Ren, Y. Romano and E. Candes.
Complete randomization allows for consistent estimation of the average treatment effect based on the difference in means of the outcomes without strong modeling assumptions on the outcome-generating process. Appropriate use of the pretreatment covariates can further improve the estimation efficiency. However, missingness in covariates is common in experiments and raises an important question: should we adjust for covariates subject to missingness, and if so, how? The unadjusted difference in means is always unbiased. The complete-covariate analysis adjusts for all completely observed covariates and improves the efficiency of the difference in means if at least one completely observed covariate is predictive of the outcome. Then what is the additional gain of adjusting for covariates subject to missingness? A key insight is that the missingness indicators act as fully observed pretreatment covariates as long as missingness is not affected by the treatment, and can thus be used in covariate adjustment to bring additional estimation efficiency. This motivates adding the missingness indicators to the regression adjustment, yielding the missingness-indicator method as a well-known but not so popular strategy in the literature of missing data. We recommend it due to its many advantages. We also propose modifications to the missingness-indicator method based on asymptotic and finite-sample considerations. To reconcile the conflicting recommendations in the missing data literature, we analyze and compare various strategies for analyzing randomized experiments with missing covariates under the design-based framework. This framework treats randomization as the basis for inference and does not impose any modeling assumptions on the outcome-generating process and missing-data mechanism.