Beyond normality: Learning sparse probabilistic graphical models in the non-Gaussian setting
We present an algorithm to identify sparse dependence structure in continuous and non-Gaussian probability distributions, given a corresponding set of data. The conditional independence structure of an arbitrary distribution can be represented as an undirected graph (or Markov random field), but most algorithms for learning this structure are restricted to the discrete or Gaussian cases. Our new approach allows for more realistic and accurate descriptions of the distribution in question, and in turn better estimates of its sparse Markov structure. Sparsity in the graph is of interest as it can accelerate inference, improve sampling methods, and reveal important dependencies between variables. The algorithm relies on exploiting the connection between the sparsity of the graph and the sparsity of transport maps, which deterministically couple one probability measure to another.
This paper presents a method for identifying the independence structure of undirected probabilistic graphical models with continuous but non-Gaussian distributions, using SING, a novel iterative algorithm based on transport maps. The authors derive an estimate for the number of samples needed to recover the exact underlying graph structure with some probability and demonstrate empirically that SING can indeed recover this structure on two simple domains, where comparable methods that make invalid assumptions about the underlying data-generating process fail.
Quality.
The paper seems technically sound, with its claims and conclusions supported by existing and provided theoretical and empirical results. The authors mostly do a good job of justifying their approach, but do not discuss potential issues with the algorithm. For example, what is the complexity of SING? Since it has a variable-elimination-like aspect, is complexity exponential in the treewidth of the generated graph? If so, how is this approach feasible for non-sparse graphs? In that vein, I would like to see how SING fares empirically when applied to more realistic and higher-dimensional problems and in comparison to other standard MRF-learning approaches. The latter typically make overly strong assumptions, but can still perform well given that there are rarely enough data points for true structures to be recovered.
Clarity.
The writing is good, and each subsection is clear, but the authors should better define their notation and spend more time explaining the algorithm as a whole and gluing the pieces together. In particular, what exactly happens in subsequent iterations? A quick example or a brief high-level walk-through of the algorithm would be helpful here to assemble all of the pieces that have been described into a coherent whole. 
Also, is the amount of sparsity that is estimated monotonic over iterations? If SING over-estimates the amount of sparsity present in the data, can it then reduce the amount of sparsity it is estimating? The sparsity pattern identified on line 8 of Alg. 1 is used in line 2, correct? (Note that you use I_{S_{i+1}} and S^B_{I_{i}}, respectively, on these lines – is I_i the same as I_{S_{i+1}} from the previous iteration?) It’s not clear to me how this sparsity pattern gets used in the estimation of the transport map. You should more clearly define where the original and induced graphs come from. From what I can tell, the original graph is the result of the thresholded \Sigma (but no graph is discussed in Alg. 1), and the induced graph comes from some variable-elimination-like algorithm, but it’s not clear how this actually happens. Does Alg. 1 perform variable elimination? What are the factors? Why do you need to do this?
Originality.
The approach seems novel and original, although I am not that familiar with transport maps and their corresponding literature.
Significance.
The presented approach seems interesting and potentially useful, but lacks sufficient evaluation as the authors do not evaluate or discuss the complexity of their algorithm and only evaluate on two simple problems. It would also be useful to properly conclude section 5 by better explaining and contextualizing the result. In particular, is the number of samples needed high or low relative to other works that estimate similar types of graph structures, or is this completely novel analysis?
Overall.
With additional results, editing, and a more cohesive explanation of their approach, this could be a successful publication, but I do not think it has reached that threshold as it stands.
Detailed comments:
- Please define your notation. For example, in the introduction you should define the independence symbol and \bf{x}_{jk}. In section 2, you use both d_j d_k for (I think) partial derivatives, but then later use d_{jk} for (I assume) the same quantity, but define neither. You should define det() and the circle, which is typically used for function composition.  The V on line 154 should be defined. The projection (?) operator on the equation below line 162 should be defined. Etc.
- Line 75: inline citations should be Author (Year), instead of the number (use \citet instead of \citep if using natbib)
- There are a few typos and duplicated words (e.g., lines 86, 191).
- The font sizes on your figures are barely legible when printed – these should be increased.
- Alg 1., line 1, “DECREASING = TRUE” does not show when printed, perhaps due to font choice or embedding.
- Lines 156 and 173: These should be referred to as Equation (6) and Equation (7), not Line (6) and (7).
- Figure 3d shows SING(B=1), but the B=1 case has not been explained before this, so it looks like a failure case of the algorithm. Better would be to put the success case in Figure (3d) and then show the failure case in Figure (4) (separate from the others) and discuss the effect of B=1 there.
- Figure 5: it’s confusing to show the true graph (5a) as the ‘recovered’ graph. You should show the recovered adjacency matrix for SING as an added sub-figure of figure 5. Further, the x- and y- axis labels are just numbers, meaning that it’s not clear which numbers correspond to the hyperparameters, so lines 232-233 are confusing.
- Figures 3-6: would be useful to have a legend or explanation somewhere that blue means an edge and white means no edge.
---- 
After reading the author response, I have updated my score to 'weak accept' as I agree that the NIPS community will benefit from this work and my main concerns of complexity with respect to the use of variable elimination have been satisfied. However, the exact use of the variable elimination heuristics still remains somewhat unclear to me and the authors should clarify and be more explicit about how it is used in their algorithm.