论文标题
通过乘法学习高斯图形模型
Learning Gaussian Graphical Models via Multiplicative Weights
论文作者
论文摘要
马尔可夫随机字段中的图形模型选择是统计和机器学习中的一个基本问题。两个特别突出的模型，即Ising模型和高斯模型，在很大程度上使用不同的（尽管经常相关的）技术并行开发，并且已经为每种技术建立了一些具有严格样本复杂性界限的实用算法。在本文中，我们根据乘积更新的方法，通过非平凡的修改到算法及其分析的方法，使Klivans and Meka最近提出的算法（FOCS，2017）调整了从ISING模型到高斯模型。该算法享有与文献中其他相似性相似的样本复杂性，在$ m $样本和$ p $节点的情况下，运行时$ O（MP^2）$较低，并且可以以在线方式实施。
Graphical model selection in Markov random fields is a fundamental problem in statistics and machine learning. Two particularly prominent models, the Ising model and Gaussian model, have largely developed in parallel using different (though often related) techniques, and several practical algorithms with rigorous sample complexity bounds have been established for each. In this paper, we adapt a recently proposed algorithm of Klivans and Meka (FOCS, 2017), based on the method of multiplicative weight updates, from the Ising model to the Gaussian model, via non-trivial modifications to both the algorithm and its analysis. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature, has a low runtime $O(mp^2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
