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.