权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Algorithms, Dynamics and Connections with Phase Transitions

算法、动力学以及与相变的联系

基本信息

批准号：
EP/V050842/1
负责人：
Charilaos Efthymiou
金额：
$ 39.47万
依托单位：
University of Warwick
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2021
资助国家：
英国
起止时间：
2021 至无数据
项目状态：
未结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FV050842%2F1
关键词：
Algorithms Dynamics Connections Phase Transitions

项目摘要

The project focuses on an interplay between algorithms and phase transitions. We consider computational problems in the class NP. These are abstractions of a tremendous wealth of important practical problems in communication networks, biology, coding theory and many others. Here, we focus on random instances of problems in NP, rather than worst case ones. This approach is motivated in many ways. For example, dealing with random instances can be a part of the problem like in coding theory. In other cases, random instances give rise to what we call statistical - computational tradeoffs. That is, adjusting the parameters of the problem we generate families of instances whose tractability varies from efficiently solvable to (what is believed to be) computationally hard. Here we particularly consider instances of problems known as random Constraint Satisfaction Problems (rCSP). These are random instances of classical combinatorial, or algebraic problems such as the graph colouring, k-satisfiability etc. Physicists, have been studying rCSPs as models of disordered systems. They have developed ingenious alas mathematically non-rigorous ideas which over the past decade have grown into a toolkit called the Cavity Method. Cavity's predictions are related to the size and the geometry of the solution space of a rCSP. This allows us to understand and appreciate the challenges we have to deal in our algorithmic problems.In this project we plan to study sampling algorithms for Gibbs distributions in rCSPs. These distributions are defined over the solution space of the rCSP, e.g. for graph colourings this is the uniform distribution over the k-colourings of the underlying graph. We focus on two different approaches for sampling. The first one is based on the Markov Chain Monte Carlo (MCMC) method. The natural question there is how fast the MCMC dynamics mixes for a given set of the parameters. The MCMC algorithms are simple to implement Markov chains and usually they have a notable empirical performance. However, analysing them can be challenging.We also intend to study a non-MCMC approach to sampling. The plan is to use the approach introduced in [Efthymiou SODA2012]. This algorithm is very different than the MCMC ones. iIt is very simple to implement and describe, with a provably notable performance. There are a lot of very interesting directions that worth exploring with this approach.Furthermore, we plan to investigate the soundness of certain predictions from the Cavity method.Gibbs distributions: The natural way of studying Gibbs distributions is in terms of spatial correlation decay. There are several, different, notions of spatial mixing which arise naturally in the study. Some of these notions seem to be related to the performance of algorithms. We plan to study spatial mixing for non-symmetric distributions on random graphs with focus on the so-called reconstruction threshold. We also intend to study non-reconstruction problem for spin-glasses, e.g., the Edwards-Anderson model. We focus on non-reconstruction because the on-set of reconstruction signifies that sampling and search algorithms for rCSP stop being polynomial.Free Energy: Many natural inference and learning problems are cast naturally as rCSP, e.g., Stochastic Block Model (SBM) for networks inference, models of neurones like Ising Perceptron, the committee machine. It a natural to study these models in terms of their free energy. We intend to use the formalism of free energy to establish information lower bounds for inference algorithms for the non-symmetric SBM and study basic properties of physics' models of neural networks, including capacity estimates, or finding their energy landscape.

该项目侧重于算法和相变之间的相互作用。我们考虑NP类中的计算问题。这些是对通信网络、生物学、编码理论和许多其他领域中大量重要实际问题的抽象。这里，我们关注NP问题的随机实例，而不是最坏情况。这种方法的动机有很多。例如，处理随机实例可能是编码理论中问题的一部分。在其他情况下，随机实例会导致我们所说的统计计算权衡。也就是说，通过调整问题的参数，我们生成了一系列实例，这些实例的可处理性从有效可解决到（被认为是）计算困难不等。这里我们特别考虑随机约束满足问题（rCSP）的实例。这些是经典组合或代数问题的随机实例，如图着色，k-可满足性等。物理学家一直在研究rcsp作为无序系统的模型。在过去的十年里，他们发展出了一些巧妙的、数学上不严谨的想法，这些想法已经发展成为一种叫做空腔法的工具包。Cavity的预测与rCSP解空间的大小和几何形状有关。这使我们能够理解和欣赏我们在处理算法问题时所面临的挑战。在这个项目中，我们计划研究rcsp中Gibbs分布的抽样算法。这些分布是在rCSP的解空间上定义的，例如，对于图着色，这是底层图的k个着色上的均匀分布。我们关注两种不同的采样方法。第一种方法是基于马尔可夫链蒙特卡罗（MCMC）方法。自然的问题是，对于给定的一组参数，MCMC动力学混合的速度有多快。MCMC算法易于实现马尔可夫链，通常具有显著的经验性能。然而，分析它们可能具有挑战性。我们还打算研究一种非mcmc采样方法。计划采用[Efthymiou SODA2012]中介绍的方法。这个算法与MCMC算法有很大的不同。它的实现和描述非常简单，性能也非常显著。有很多非常有趣的方向值得用这种方法去探索。此外，我们计划研究从空腔法某些预测的合理性。吉布斯分布：研究吉布斯分布的自然方法是根据空间相关衰减。在研究中自然产生了几种不同的空间混合概念。其中一些概念似乎与算法的性能有关。我们计划研究随机图上非对称分布的空间混合，重点研究所谓的重建阈值。我们还打算研究自旋玻璃的非重构问题，例如Edwards-Anderson模型。我们之所以关注非重构，是因为重构的on-set意味着rCSP的采样和搜索算法不再是多项式。自由能：许多自然推理和学习问题被自然地转换为rCSP，例如，用于网络推理的随机块模型（SBM），像Ising Perceptron这样的神经元模型，委员会机。从自由能的角度来研究这些模型是很自然的。我们打算使用自由能的形式来建立非对称SBM推理算法的信息下界，并研究神经网络物理模型的基本性质，包括容量估计，或找到它们的能量景观。