CRII: CIF: Fast Algorithms for Learning Graphical Models from Scarce Data

图形模型（GM）是一个强大的框架，用于简洁地表示复杂的高维现象。变量之间的统计相关性通过图中的边组合表示，这允许模型可解释性和计算有效的推理。由于这些原因，GM是机器学习和人工智能的核心，并已被用于各种应用领域，包括金融，运筹学，生物学，信号处理和社交网络。对于具有非明显结构的大型复杂数据，中心问题是学习适当的模型。学习图形模型提出了计算和统计的挑战。这个问题的组合性质意味着有大量可能的模型需要探索。与此同时，现代应用程序的高维性质意味着数据点的数量往往比周围参数空间的维数小得多：因此，学习算法必须有效地利用数据，而这些数据相对于问题的大小来说是稀缺的。现有的学习图模型的方法要么达到统计效率，要么达到计算效率，但不能两者兼得。本研究的目的是两全其美：极端的计算和统计效率。虽然实际应用需要这样的效率，它是不可能达到的完全普遍性，所有的模型。问题是，现实世界系统的哪些特征允许易处理的学习？这项研究需要确定感兴趣的特定模型子类，并开发具有可证明性能保证的算法。具体来说，该研究提供了关于学习所需数据量的新的信息理论下限，并通过这些下限，给出了统计上接近最优的快速（计算效率高）算法。

Graphical models (GMs) are a powerful framework used to succinctly represent complex high-dimensional phenomena. Statistical dependence between variables is represented combinatorially via edges in a graph, and this allows both model interpretability and computationally efficient inference. For these reasons, GMs are at the core of machine learning and artificial intelligence and have been used in a variety of applied fields, including finance, operations research, biology, signal processing, and social networks. For large complex data with non-obvious structure, the central problem is that of learning an appropriate model. Learning a graphical model presents both a computational and statistical challenge. The combinatorial nature of the problem means that there are a huge number of possible models to explore. At the same time, the high-dimensional nature of modern applications means that the number of data-points is often much smaller than the dimension of the ambient parameter space: learning algorithms must therefore make efficient use of the data, which is scarce relative to the problem size. Existing approaches to learning graphical models achieve either statistical efficiency or computational efficiency, but not both.This research aims for the best of both worlds: extreme computational and statistical efficiency. While practical applications demand such efficiency, it is unlikely to be attainable in complete generality, for all models. The question is, what features of real-world systems allow for tractable learning? The research entails identifying specific model subclasses of interest and developing algorithms with provable performance guarantees. Concretely, the research provides new information-theoretic lower bounds on the amount of data required to learn, and informed by these lower bounds, gives fast (computationally efficient) algorithms that are statistically near optimal.