Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
View through CrossRef
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.
Title: Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
Description:
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.
Related Results
Sobre grafos clique críticos
Sobre grafos clique críticos
Se llama completo de un grafo a un conjunto de vértices adyacentes entre si; si un completo es maximal con respecto a la inclusión, se dice que es un clique del grafo. Los cliques ...
Rank-sparsity decomposition for planted quasi clique recovery
Rank-sparsity decomposition for planted quasi clique recovery
Abstract
In this paper, we apply the Rank-Sparsity Matrix Decomposition to the planted Maximum Quasi-Clique Problem (MQCP). This problem has ...
Monte Carlo methods: barrier option pricing with stable Greeks and multilevel Monte Carlo learning
Monte Carlo methods: barrier option pricing with stable Greeks and multilevel Monte Carlo learning
For discretely observed barrier options, there exists no closed solution under the Black-Scholes model. Thus, it is often helpful to use Monte Carlo simulations, which are easily a...
Research on Multi-Group Monte Carlo Calculations Based on Group Constants Generated by RMC
Research on Multi-Group Monte Carlo Calculations Based on Group Constants Generated by RMC
Abstract
Nowadays, deterministic two-step or Monte Carlo methods are commonly used in core physics calculations. However, with the development of reactor core design, tradi...
Optimising tool wear and workpiece condition monitoring via cyber-physical systems for smart manufacturing
Optimising tool wear and workpiece condition monitoring via cyber-physical systems for smart manufacturing
Smart manufacturing has been developed since the introduction of Industry 4.0. It consists of resource sharing and networking, predictive engineering, and material and data analyti...
Evaluation of Thermoelectric Generators under Mismatching Conditions
Evaluation of Thermoelectric Generators under Mismatching Conditions
Due to the wide usability of thermoelectric generators (TEG) in the industry and research fields, it is plausible that mismatching conditions are present on the thermal surfaces of...
Evaluating View Factors Using a Hybrid Monte-Carlo Method
Evaluating View Factors Using a Hybrid Monte-Carlo Method
AbstractThis paper demonstrates that the well-known method for calculating view factors, the Monte Carlo method, combined with ray tracing is not necessarily the most efficient str...
Automation of the Monte Carlo simulation of medical linear accelerators
Automation of the Monte Carlo simulation of medical linear accelerators
The main result of this thesis is a software system, called PRIMO, which simulates clinical linear accelerators and the subsequent dose distributions using the Monte Carlo method. ...