A Large Deviation Principle for Block Models

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=r-4yXTodRPQ


Duration: 38:31
310 views
4

Julia Gaudio (Northwestern University)
https://simons.berkeley.edu/node/22592
Graph Limits, Nonparametric Models, and Estimation

We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee and Varadhan (2011), we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we study upper tail large deviations for homomorphism densities of regular graphs. We identify the existence of a "symmetric'' phase, where the graph, conditioned on the rare event, looks like a block model with the same block sizes as the generating graphon. In specific examples, we also identify the existence of a "symmetry breaking'' regime, where the conditional structure is not a block model with compatible dimensions. This identifies a "reentrant phase transition'' phenomenon for this problem---analogous to one established for Erdős–Rényi random graphs (Chatterjee and Dey (2010), Charrerjee and Varadhan (2011)). Finally, extending the analysis of Lubetzky and Zhao (2015), we identify the precise boundary between the symmetry and symmetry breaking regimes for homomorphism densities of regular graphs and the operator norm on Erdős–Rényi bipartite graphs.

Joint work with Christian Borgs, Jennifer Chayes, Subhabrata Sen, and Samantha Petti



Other Videos By Simons Institute for the Theory of Computing


2022-09-28Recent Developments on Graph Norms
2022-09-28The Degree-Restricted Random Process Is Far From Uniform
2022-09-28On the Second Kahn-Kalai Conjecture
2022-09-28Sparse Random Graphs with Many Triangles
2022-09-28Efficiently Exploiting Model Structure in Network Causal Inference with and without...
2022-09-28Symmetry and Convergence
2022-09-28Higher Order Fluctuations in Dense Random Graph Models
2022-09-27A Deterministic Theory of Low Rank Matrix Completion
2022-09-27Common Graphs with Arbitrary Chromatic Number
2022-09-27Higher-Order Graphon Theory: Fluctuations, Inference, and Degeneracies
2022-09-27A Large Deviation Principle for Block Models
2022-09-27Mean-field approximations for high-dimensional Bayesian Regression
2022-09-27Response of Graphs to Competing Constraints
2022-09-27Sparse Random Graphs: Interplay of Local and Global Structure
2022-09-26Analytic Approach to Guasirandomness
2022-09-26Random Cluster Model on Regular Graphs
2022-09-17Generalization and Robustness in Offline Reinforcement Learning
2022-09-17Adaptivity and Confounding in Multi-armed Bandit Experiments
2022-09-16When Can We Use Weak Function Approximation to Solve Large Scale Planning Problems in MDPs?
2022-09-16Dynamic Regret Minimization for Bandits without Prior Knowledge
2022-09-16Oracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust Learning


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Graph Limits Nonparametric Models and Estimation
Péter Csikvári