Review for NeurIPS paper: From Boltzmann Machines to Neural Networks and Back Again

I am changing the score to 7. The paper gives a new algorithm for learning the structure Restricted Boltzmann Machines (formalized using Markov blankets), which is claimed to work for larger parameter regimes than the previous work. This is done by considering the problem of predicting the spin of a node given the spins of all other nodes. This dependence is shown to be given by a one-hidden layer neural net (with somewhat non-standard activations). An algorithm for learning this network is given based on polynomial approximation of the neural net and using regression on degree-D monomial feature map (with \ell_1 constraint). The algorithm works under L_\inf constraint on the input vector which is different from the past work. Given the above algorithm for learning the dependence of one node on the rest, under suitable non-degeneracy conditions, an algorithm is given for learning the structure (Markov blanket) of the RBM. Nearly matching lower bounds are provided (under hardness assumptions or in the SQ model). The reduction to neural networks is also used for learning supervised RBMs, which can be thought of as a neural network under distributional assumptions on the data (in terms of "sparsity and nonnegative correlations among the input features 307 conditional on the output label"). This distributional assumptions seems to be new.