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.

Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model / Angelini, Maria Chiara; Fachin, Paolo; de Feo, Simone. - In: JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT. - ISSN 1742-5468. - (2021).

Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model

Maria Chiara Angelini
Primo
;
Paolo Fachin;
2021

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.
2021
Physics - Statistical Mechanics; Physics - Statistical Mechanics; Physics - Disordered Systems and Neural Networks; Computer Science - Data Structures and Algorithms; cs.SI
01 Pubblicazione su rivista::01a Articolo in rivista
Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model / Angelini, Maria Chiara; Fachin, Paolo; de Feo, Simone. - In: JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT. - ISSN 1742-5468. - (2021).
File allegati a questo prodotto
File Dimensione Formato  
Angelini_Mismatching_2021.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.5 MB
Formato Adobe PDF
1.5 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1586239
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 5
social impact