Mismatched Monte Carlo Algorithms For The Planted Clique Problem
summary
Jerrum Monte Carlo on perfect cliques gets trapped at random clique sizes and empirically remains superpolynomial until k scales like n^0.91 rather than √n, so standard sampling fails. Introducing a mismatched temperature (beta < 1) yields a Metropolis chain whose optimal beta produces linear-time recovery once k > c √n, with data collapsing under k/√n and time ∝ n. A Jerrum Monte Carlo variant tied to the posterior matches this behavior, while parallel tempering empirically reaches the 2 log2 n information limit.
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:23Random clique problem
- 2:14Jerrum’s Monte Carlo algorithm
- 5:30Planted clique phases
- 6:58Monte Carlo algorithms
- 9:13Jerrum’s algorithm simulations
- 11:40Mismatched Bayesian approach
- 15:14Mismatched algorithm performance
- 18:37Glassy states and dynamics
- 21:29Summary and open questions
- 23:43Over-parameterization parallels
- 24:26Parallel tempering benefits
- 28:25Phase diagram and temperature
related talks
41mReducibility and Statistical-Computational Gaps from Secret Leakage
14mSequential Monte Carlo Program Synthesis with Refinement Proposals
34mSampling From the Random Cluster Model at All Temperatures on Random Graphs
25mLucky Talk: From Coding to Clustering
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
01h 11mStatistical Physics and Computation in High Dimension
20mNonparametric Involutive Markov Chain Monte Carlo
01h 06mNonparametric Bayesian Methods: Models, Algorithms, and Applications I