weakness even if true but worth discussing in detail since it
could guide future work.) [EDIT: I see now that this is *not* the case, see response below]
I also feel that the discussion of Chow-Liu is missing a very
important aspect. Chow-Liu doesn't just correctly recover the
true structure when run on data generated from a tree. Rather,
Chow-Lui finds the *maximum-likelihood* tree for data from an
*arbitrary* distribution. This is a property that almost all
follow-up work does not satisfy (Srebro showed bounds). The
discussion in this paper is all true, but doesn't mention that
"maximum likelihood" or "model robustness" issue at all, which
is hugely important in practice.
For reference: The basic result is that given a single node $u$,
and a hypothesized set of "separators" $S$ (neighbors of $u$) then
there will be some set of nodes $I$ with size at most $r-1$ such
that $u$ and $I$ have positive conditional mutual information.
The proof of the central result proceeds by setting up a
"game", which works as follows:
1) We pick a node $X_u$ to look at.
2) Alice draws two joint samples $X$ and $X'$.
3) Alice draws a random value $R$ (uniformly from the space of
possible values of $X_u$
4) Alice picks a random set of neighbors of $X_u$, call them $X_I$.
5) Alice tells Bob the values of $X_I$
6) Bob get's to wager on if $X_u=R$ or $X'_u=R$. Bob wins his
wager if $X_u=R$ an loses his wager if $X'_u=R$ and nothing
happens if both or neither are true.
Here I first felt like I *must* be missing something, since
this is just establishing that $X_u$ has mutual information
with it's neighbors. (There is no reference to the "separator"
set S in the main result.) However, it later appears that this
is just a warmup (regular mutual information) and can be
extended to the conditional setting.
Actually, couldn't the conditional setting itself be phrased
as a game, something like
1) We pick a node $X_u$ and a set of hypothesized "separators"
$X_S$ to look at.
2) Alice draws two joint samples $X$ and $X'$ Both are
conditioned on the some random value for $X_S$.
3) Alice draws a random value $R$ (uniformly from the space of
possible values of $X_u$
4) Alice picks a random set of nodes (not including $X_u$ or $X_S$, call them $X_I$.
5) Alice tells Bob the values of $X_I$
6) Bob get's to wager on if $X_u=R$ or $X'_u=R$. Bob wins his
wager if $X_u=R$ an loses his wager if $X'_u=R$ and nothing
happens if both or neither are true.
I don't think this adds anything to the final result, but is
an intuition for something closer to the final goal.
After all this, the paper discusses an algorithm for greedily
learning an MRF graph (in sort of the obvious way, by
exploiting the above result) There is some analysis of how
often you might go wrong estimating mutual information from
samples, which I appreciate.
Overall, as far as I can see, the result appears to be
true. However, I'm not sure that the purely theoretical result
is sufficiently interesting (at NIPS) to be published with no
experiments. As I mentioned above, Chow-Liu has the major
advantage of finding the maximum likelihood solution, which the current method
does not appear to have. (It would violate hardness results
due to Srebro.) Further, note that the bound given in Theorem
5.1, despite the high order, is only for correctly recovering
the structure of a single node, so there would need to be
another lever of applying the union bound to this result with
lower delta to get a correct full model.
EDIT AFTER REBUTTAL:
Thanks for the rebuttal. I see now that I should understand $r$ not as the maximum clique size, but rather as the maximum order of interactions. (E.g. if one has a fully-connected Ising model, you would have r=2 but the maximum clique size would be n). This answers the question I had about this being a generalization of Bressler's result. (That is, this paper's is a strict generalization.) This does slightly improve my estimation of this paper, though I thought this was a relatively small concern in any case. My more serious concerns are that a pure theoretical result is appropriate for NIPS.
3) Alice draws a random value $R$ (uniformly from the space of possible values of $X_u$ 4) Alice picks a random set of nodes (not including $X_u$ or $X_S$, call them $X_I$. 5) Alice tells Bob the values of $X_I$