We consider the problem of reconstructing the graph underlying an Ising model
from i.i.d. samples. Over the last fifteen years this problem has been of
significant interest in the statistics, machine learning, and statistical
physics communities, and much of the effort has been directed towards finding
algorithms with low computational cost for various restricted classes of
models. Nevertheless, for learning Ising models on general graphs with $p$
nodes of degree at most $d$, it is not known whether or not it is possible to
improve upon the $p^{d}$ computation needed to exhaustively search over all
possible neighborhoods for each node.
In this paper we show that a simple greedy procedure allows to learn the
structure of an Ising model on an arbitrary bounded-degree graph in time on the
order of $p^2$. We make no assumptions on the parameters except what is
necessary for identifiability of the model, and in particular the results hold
at low-temperatures as well as for highly non-uniform models. The proof rests
on a new structural property of Ising models: we show that for any node there
exists at least one neighbor with which it has a high mutual information. This
structural property may be of independent interest.

本文探讨了如何通过简单的贪心算法来学习任意边界度数的 Ising 模型，在保证模型可辨识度的情况下，仅需用时 O (p^2) 即可还原图结构，并且该结构性质可独立运用于其他相关研究。

在任意图上高效学习 Ising 模型

Efficiently learning Ising models on arbitrary graphs

The model averaging problem is to average multiple models to achieve a
prediction accuracy not much worse than that of the best single model in terms
of mean squared error. It is known that if the models are misspecified, model
averaging is superior to model selection. Specifically, let $n$ be the sample
size, then the worst case regret of the former decays at a rate of $O(1/n)$
while the worst case regret of the latter decays at a rate of $O(1/\sqrt{n})$.
The recently proposed $Q$-aggregation algorithm \citep{DaiRigZhang12} solves
the model averaging problem with the optimal regret of $O(1/n)$ both in
expectation and in deviation; however it suffers from two limitations: (1) for
continuous dictionary, the proposed greedy algorithm for solving
$Q$-aggregation is not applicable; (2) the formulation of $Q$-aggregation
appears ad hoc without clear intuition. This paper examines a different
approach to model averaging by considering a Bayes estimator for deviation
optimal model averaging by using exponentiated least squares loss. We establish
a primal-dual relationship of this estimator and that of $Q$-aggregation and
propose new greedy procedures that satisfactorily resolve the above mentioned
limitations of $Q$-aggregation.

本文探讨采用贝叶斯估计器与指数化最小二乘损失来进行偏差最优的模型平均，通过建立两种方法之间的原始对偶关系并提出新的贪心方法，规避了现有 $Q$- 聚合算法的局限性。