Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
arXiv:2106.05720 · doi:10.1088/1742-5468/ac3657
Abstract
Over-parametrization was a crucial ingredient for recent developments in inference and machine-learning fields. However a good theory explaining this success is still lacking. In this paper we study a very simple case of mismatched over-parametrized algorithm applied to one of the most studied inference problem: the planted clique problem. We analyze a Monte Carlo (MC) algorithm in the same class of the famous Jerrum algorithm. We show how this MC algorithm is in general suboptimal for the recovery of the planted clique. We show however how to enhance its performances by adding a (mismatched) parameter: the temperature; we numerically find that this over-parametrized version of the algorithm can reach the supposed algorithmic threshold for the planted clique problem.
References in corpus (16)
- Machine learning and the physical sciences
- The Bethe lattice spin glass revisited
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Statistical physics of inference: Thresholds and algorithms
- Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
- Focused Local Search for Random 3-Satisfiability
- Behavior of heuristics and state space structure near SAT/UNSAT transition
- Finding One Community in a Sparse Graph
- Typology of phase transitions in Bayesian inference problems
- Temperature chaos in 3D Ising Spin Glasses is driven by rare events
- Spurious Valleys in Two-layer Neural Network Optimization Landscapes
- Stochasticity helps to navigate rough landscapes: comparing gradient-descent-based algorithms in the phase retrieval problem
- Glassy nature of the hard phase in inference problems
- The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
- Parallel Tempering for the planted clique problem
- Who is Afraid of Big Bad Minima? Analysis of Gradient-Flow in a Spiked Matrix-Tensor Model