2019/04/05 by A. El Alaoui, Andrea Montanari, Alaoui, Ahmed El +1
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR) #Random Matrices and Applications #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1904.03313
openalex publication_date 2019/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of estimating a vector of discrete variables\n(\θ1,\⋯,\θn), based on noisy observations Yuv of the pairs\n(\θu,\θv) on the edges of a graph G=([n],E). This setting\ncomprises a broad family of statistical estimation problems, including group\nsynchronization on graphs, community detection, and low-rank matrix estimation.\n A large body of theoretical work has established sharp thresholds for weak\nand exact recovery, and sharp characterizations of the optimal reconstruction\naccuracy in such models, focusing however on the special case of\nErd "os--R 'enyi-type random graphs. The single most important finding of this\nline of work is the ubiquity of an information-computation gap. Namely, for\nmany models of interest, a large gap is found between the optimal accuracy\nachievable by any statistical method, and the optimal accuracy achieved by\nknown polynomial-time algorithms. Moreover, this gap is generally believed to\nbe robust to small amounts of additional side information revealed about the\n\θi's.\n How does the structure of the graph G affect this picture? Is the\ninformation-computation gap a general phenomenon or does it only apply to\nspecific families of graphs?\n We prove that the picture is dramatically different for graph sequences\nconverging to amenable graphs (including, for instance, d-dimensional grids).\nWe consider a model in which an arbitrarily small fraction of the vertex labels\nis revealed, and show that a linear-time local algorithm can achieve\nreconstruction accuracy that is arbitrarily close to the information-theoretic\noptimum. We contrast this to the case of random graphs. Indeed, focusing on\ngroup synchronization on random regular graphs, we prove that the\ninformation-computation gap still persists even when a small amount of side\ninformation is revealed.\n