Schedule for: 21w5108 - Random Graphs and Statistical Inference: New Methods and Applications (Online)

A brief introduction to BIRS with important logistical information, technology instruction, and opportunity for participants to ask questions.

In this paper, we present a polynomial time algorithm for approximate sampling from symmetric Gibbs distributions on the sparse random graph and hypergraph. The examples include (but are not restricted to) some important distributions on spin-systems and spin-glasses. We consider the $q$ state antiferromagnetic Potts model for $q\geq 2$, including the (hyper)graph colourings. We also consider the uniform distribution over the Not-All-Equal solutions of a random $k$-SAT instance. Finally, we consider sampling from the {\em spin-glass} distribution called the $k$-spin model. The $k$-spin model is essentially a diluted version of the well-known Sherrington-Kirkpatrick model. To our knowledge, this is the first rigorously analysed efficient algorithm for spin-glasses which operates in a non trivial range of the parameters of the distribution. We make a major progress regarding the impressive predictions of physicists relating phase-transitions of Gibbs distributions with the efficiency of the corresponding sampling algorithms. We present, what we believe to be, an elegant sampling algorithm for symmetric Gibbs distributions. Our algorithm is unique in its approach and does not belong to any of the well-known families of sampling algorithms. We derive this algorithm by investigating the power and the limits of the the approach that was introduced in [Efthymiou: SODA 2012]. For the cases we consider here, our algorithm outperforms by far all other sampling algorithms in terms of the permitted range of the parameters of the Gibbs distributions. For the graph case, we show that our algorithm operates in a range of the parameters that coincides with the (in many cases conjectured) tree-uniqueness region, parametrised w.r.t. the {\em expected degree} of the graph. For the hypergraph case, where uniqueness is less restrictive for algorithmic purposes, it operates beyond the uniqueness region. For a symmetric Gibbs distribution $\mu$ on the random (hyper)graph whose parameters are within an appropriate range, our sampling algorithm has the following properties: with probability $1-o(1)$ over the instances of the input (hyper)graph, it generates a configuration which is distributed within total variation distance $n^{-\Omega(1)}$ from $\mu$. The time complexity is $O((n\log n)^2)$, where $n$ is the size of the input (hyper)graph. We give a new insight to the problem by exploiting phenomena of the Gibbs distributions that were not previously used by sampling algorithms. Our approach allows us to utilise the notion of {\em contiguity} between Gibbs distributions and the so-called {\em teacher-student model}, with the later distribution also known in various contexts as the {\em planted model}. This brings together tools and notions from sampling and statistical inference algorithms.

We analyse when community structure of an underlying graph can be determined from an observed subset of the graph. Modularity is a function on graphs which is used in algorithms for community detection. For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The (max) modularity q*(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0≤q*(G)≤1. In a natural model where we suppose edges in an underlying graph G appear independently with some probability in our observed graph G' we describe how high a sampling probability we need to infer the modularity of the underlying graph from the modularity of the observed graph. Joint work with Colin McDiarmid.

In a seminal paper, Chatterjee and Varadhan derived an LDP for the dense Erd˝os-R´enyi random graph, viewed as a random graphon. This directly provides LDPs for continuous functionals such as subgraph counts, spectral norms, etc. In contrast, very little is understood about this problem if the underlying random graph is inhomogeneous or constrained. In this talk, we will explore large deviations for dense random graphs, beyond the “mean-field” setting. In particular, we will study large deviations for uniform random graphs with given degrees, and a family of dense block model random graphs. We will establish the LDP in each case, and identify the rate function. In the block model setting, we will use this LDP to study the upper tail problem for homomorphism densities of regular sub-graphs. Our results establish that this problem exhibits a symmetry/symmetry-breaking transition, similar to one observed for Erd˝os-R´enyi random graphs. Based on joint works with Christian Borgs, Jennifer Chayes, Souvik Dhara, Julia Gaudio and Samantha Petti

We consider the model of random trees introduced by Devroye (1998), the so-called random split trees. The model encompasses many important randomized algorithms and data structures. We then perform supercritical Bernoulli bond-percolation on those trees and obtain the asymptotic distribution for the sizes of the largest clusters. Joint work with Gabriel Berzunza, University of Liverpool

As in the case of the binomial random graph, it is known that the behaviour of a random subgraph of a d-dimensional hypercube, where we include each edge independently with probability p, undergoes a phase transition when p is around 1/d. More precisely, answering a question of Erdős and Spencer, it was shown by Ajtai, Komlós and Szemerédi that significantly above this value of p, in the supercritical regime, whp this random subgraph has a unique 'giant' component, whose order is linear in the order of the hypercube. In the binomial random graph much more is known about the complex structure of this giant component, a lot of which can be deduced from more recent results about the likely expansion properties of the giant component. We show that whp the giant component L of a supercritical random subgraph of the d-dimensional hypercube has reasonably good expansion properties, and use this to deduce some structural information about L. In particular this leads to polynomial (in d) bounds on the diameter of L and the mixing times of a random walk on L, answering questions of Pete, and Bollobás, Kohayakawa, and Łuczak. This is a joint work with Mihyun Kang and Michael Krivelevich.

In this talk, we will discuss about a relatively new sharp statistical phase transition, known as the all-or-nothing (AoN) phenomenon. The AoN phenomenon concerns the fact that in certain sparse inference models the asymptotic minimum mean squared error exhibits a sharp phase transition at some critical threshold; below the threshold, it is “trivial” (i.e. not beating the random guess), and above it, it is zero. This is in sharp contrast with multiple well-studied dense inference models such as Wigner PCA or the stochastic block model where the transition is either believed or proven to be continuous. In this talk, we will primarily focus on the details of AoN phenomenon in the specific context of sparse tensor PCA. This is joint work with Jonathan Niles-Weed.

This talk will mix a completed work with an open direction. The completed work will focus on sequential estimation of convex divergences and functionals, by proving that convex functionals are reverse submartingales with respect to the "exchangeable filtration" https://arxiv.org/abs/2103.09267. The open direction is whether such techniques are useful in any way for sequences of random graphs, where the graph structure (forgetting order of nodes) plays the role of the aforementioned filtration. This is joint work with a PhD student at CMU, Tudor Manole, and the abstract of the above paper is presented below for completeness. We present a unified technique for sequential estimation of convex divergences between distributions, including integral probability metrics like the kernel maximum mean discrepancy, f-divergences like the Kullback-Leibler divergence, and optimal transport costs, such as powers of Wasserstein distances. The technical underpinnings of our approach lie in the observation that empirical convex divergences are (partially ordered) reverse submartingales with respect to the exchangeable filtration, coupled with maximal inequalities for such processes. These techniques appear to be powerful additions to the existing literature on both confidence sequences and convex divergences. We construct an offline-to-sequential device that converts a wide array of existing offline concentration inequalities into time-uniform confidence sequences that can be continuously monitored, providing valid inference at arbitrary stopping times. The resulting sequential bounds pay only an iterated logarithmic price over the corresponding fixed-time bounds, retaining the same dependence on problem parameters (like dimension or alphabet size if applicable).

In the pooled data problem, one tries to recover a signal x ∈{0, 1, 2, . . . ,d}^n from a measurement matrix A and the results of joint measurements Ax=y. It is therefore a special case of the famous compressed sensing problem with a discrete signal and a generalisation of the frequently studied quantitative group testing problem (d=1). The task becomes explicitly interesting if the signal is sparse (||x||_0=k << n). It is a well known fact that there are exponential time constructions to recover x from (A,y) with no more than O(k) measurements but all known efficient (polynomial time) constructions require at least Ω(k ln(n)) measurements and it was believed that closing this gap is hard. We show that this additional ln(n) factor is actually artificial by providing a randomised efficient construction A_{SC} coming with an efficient decoding algorithm that recovers x from (A_{SC},y) with high probability with no more than O(k) measurements. This is based on joint work with Noela Müller.

There are by now many proofs of combinatorial results for random discrete structures which, in one form or another, follow a common scheme: 1. Run an appropriate recursive algorithm for a large, bounded number of steps; 2. Show that subsequently few further changes will be made before the algorithm terminates. Examples include analysis of the k-core of random graphs and hypergraphs, as well as random constraint satisfaction problems. The second step typically involves showing that the propagation of subsequent changes can be modelled by some subcritical process which quickly dies out, and has so far been carried out on a case by case basis. We approach the problem from a very general point of view using the Warning Propagation message passing scheme, and show that under mild assumptions, this behaviour is indeed universal. This work was motivated by our study of the sparse parity matrix, but it generalises and unifies many previous approaches and we anticipate that it will prove useful as a tool in future applications of the method. This is based on joint work with Joon Lee and Jean Bernoulli Ravelomanana

In high-dimensional statistical problems (including planted clique, sparse PCA, community detection, etc.), the class of "low-degree polynomial algorithms" captures many leading algorithmic paradigms such as spectral methods, approximate message passing, and local algorithms on sparse graphs. As such, lower bounds against low-degree algorithms constitute concrete evidence for average-case hardness of statistical problems. This method has been widely successful at explaining and predicting statistical-to-computational gaps in these settings. While prior work has understood the power of low-degree algorithms for problems with a "planted" signal, we consider here the setting of "random optimization problems" (with no planted signal), including the problem of finding a large independent set in a sparse random graph, as well as the problem of optimizing the Hamiltonian of mean-field spin glass models. Focusing on the independent set problem, we show that low-degree algorithms can find independent sets of "half-optimal" size (log d/d)n but no larger, which explains the failure of all known poly-time algorithms beyond this threshold. The proof of the lower bound leverages stability properties of low-degree polynomials along with a variant of the so-called "ensemble multi-overlap gap property", which is a structural property of the solution space. Based on arXiv:2004.12063 (joint with David Gamarnik and Aukosh Jagannath) and arXiv:2010.06563

Let A be an n×n-matrix over F2 whose every entry equals 1 with probability d/n independently for a fixed d > 0. Draw a vector y randomly from the column space of A. It is a simple observation that the entries of a random solution x to Ax=y are asymptotically pairwise independent, i.e.,􏰈i e the overlap concentrates on a single value once we condition on the matrix A, while over the probability space of A its conditional expectation vacillates between two different values α∗(d) < α∗(d), either of which occurs with probability 1/2+o(1). This anti-concentration result provides an instructive contribution to both the theory of random constraint satisfaction problems and of inference problems on random structures.