AitF: Collaborative Research: Efficient High-Dimensional Integration using Error-Correcting Codes

有效地估计高维函数的积分是一个基本的和很大程度上未解决的计算问题，表现在从生物学和物理学到经济学的科学领域。特别是在人工智能和机器学习中，大量的方法在计算上受到限制，因为它们需要计算高维积分。虽然精确计算这样的积分是非常棘手的，但近似值足以满足许多应用。目前，近似尝试使用两个主要类别的算法：马尔可夫链蒙特卡罗（MCMC）抽样方法和变分推理技术。前者是渐近准确的，但他们的计算预算是不灵活的，往往令人望而却步。后者具有可管理的计算预算，但通常没有准确性保证。该项目将研究一种新的计算效率高的近似方法，将集成任务减少到更好地研究优化任务，从而利用数十年的研究和工程组合优化方法和技术。该项目的一个关键目标是开发一个包含用于高维集成的高效工具的开源软件库。将集成简化为优化的基础是将决策问题的概率简化为80年代中期开发的唯一性承诺问题。具体来说，这个想法是使用随机奇偶方程系统，以指定函数域的随机子集，并将积分与这些子集的优化任务联系起来。一般来说，有效优化的能力从根本上源于将域的大部分概括为不感兴趣的能力。该项目要解决的关键问题是，是否有可能定义随机子集，在这些子集上，优化既易于处理，又能为集成提供信息。为此，该项目将采用与低密度奇偶校验（LDPC）矩阵相对应的随机线性方程组作为纠错码。能源前景，即，这种系统的违反方程的数量远比作为原始80年代中期技术基础的线性方程的一般（密集）随机系统的数量平滑，因此远更易于优化。该项目还将建立在过去二十年对通信领域LDPC码的深入理解的基础上，目标是将有关能源前景的先验知识整合到优化策略中。这将为纠错码提供一个全新的用途，在优化和信息论领域之间架起一座桥梁。

Efficiently estimating integrals of high-dimensional functions is a fundamental and largely unsolved computational problem, manifesting in scientific areas from biology and physics to economics. In particular, in Artificial Intelligence and Machine Learning, a wide array of methods are computationally limited precisely because they require the computation of high-dimensional integrals. While computing such integrals exactly is highly intractable, approximations suffice for many applications. Currently, approximation is attempted using two main classes of algorithms: Markov Chain Monte Carlo (MCMC) sampling methods and variational inference techniques. The former are asymptotically accurate, but their computational budget is inflexible and often prohibitive. The latter have manageable computational budget, but typically come with no accuracy guarantees. This project will investigate a new family of computationally efficient approximation methods which reduce the task of integration to the much better studied task of optimization, thus leveraging decades of research and engineering in combinatorial optimization methods and technology. A key goal of the project is to develop an open-source software library of efficient tools for high-dimensional integration.The reduction of integration to optimization builds on the probabilistic reduction of decision problems to uniqueness promise problems developed in the mid-80s. Specifically, the idea is to use systems of random parity equations in order to specify random subsets of the function's domain, and relate integration to the task of optimization over these subsets. In general, the capacity for efficient optimization fundamentally stems from the capacity to summarily dispense large parts of the domain as uninteresting. The key question to be addressed by the project is whether it is possible to define random subsets over which optimization is both tractable and informative for integration. To that end, the project will employ random systems of linear equations corresponding to Low Density Parity Check (LDPC) matrices for error-correcting codes. The energy landscape, i.e., the number of violated equations, of such systems is far smoother than that of the generic (dense) random systems of linear equations that underlie the original mid-80s technique, thus being far more amenable to optimization. The project will also build upon the deep understanding gained in the last two decades for LDPC codes in the field of communications, with the goal of integrating a priori knowledge about the energy landscape in the optimization strategy. This will provide a fundamentally new use for error-correcting codes, creating a bridge between the areas of optimization and information theory.