Thy Friend is My Friend: Iterative Collaborative Filtering for Sparse Matrix Estimation
The sparse matrix estimation problem consists of estimating the distribution of an n × n matrix Y , from a sparsely observed single instance of this matrix where the entries of Y are independent random variables. This captures a wide array of problems; special instances include matrix completion in the context of recommendation systems, graphon estimation, and community detection in (mixed membership) stochastic block models. Inspired by classical collaborative filtering for recommendation systems, we propose a novel iterative, collaborative filteringstyle algorithm for matrix estimation in this generic setting. We show that the mean squared error (MSE) of our estimator converges to 0 at the rate of O(d 2 (pn) −2/5 ) as long as ω(d 5 n) random entries from a total of n 2 entries of Y are observed (uniformly sampled), E[Y ] has rank d, and the entries of Y have bounded support. The maximum squared error across all entries converges to 0 with high probability as long as we observe a little more, Ω(d 5 n ln 5 (n)) entries. Our results are the best known sample complexity results in this generality.
This paper studies a rather generic form of sparse matrix estimation problem. Inspired by [1-3], it suggests an algorithm that is roughly based on averaging matrix elements that are r-hop common neighbours of the two of nodes for which the estimate is being computed. 
The authors then prove sample complexity bounds for the MSE to go to zero. 
While there is a lot of related work in this direction the present paper discussed this nicely and treats the many cases in a unified framework and allows for generic noise function and sparser matrices. The paper provides (as far as I know) best bounds that hold in this generality. I think this is a very good paper that should be accepted. 
Some comments suggesting improvements follow: 
While in the sparse regime treating the generality of the noise is interesting and as far as I know original. It might be worth mentioning that in the denser case results on universality with respect to the noise are known for the matrix estimation problem ("MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel" by Lesieur et al, and "Asymptotic mutual information for the two-groups stochastic block model" by Deshpande, Abbe, Montanari). 
The algorithm seems related to a spectral algorithms designed for sparse graphs, based on the non-backtracking matrix. While the introduction mentions in only one sentence relation to only standard spectral algorithm, the relation to belief propagation and non-backtracking operator is discussed on page 6. At the same time the original works suggesting and analyzing those approaches are not cited there (i.e. "Spectral redemption in clustering sparse networks" by Krzakala et al, or "Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs" by Bordenave et al.). This relation should perhaps be discussed in the section of related work or in the introduction and not in the section describing in details of the algorithm. 
The introduction discusses an unpublished work on mixed membership SBM, in particular a gap between information theoretical lower bound and a conjectures algorithmic threshold in that case. Perhaps it should be mentioned that such results originate from the normal SBM where both the information-theoretic threshold for detection, and the conjectured algorithmic threshold were studied in detail, e.g. in "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications" by Decelle et al.  Also in that case the gap between the two threshold is d (for large d). 
While the main contribution of the paper is theoretical, it would have been nice to see some practical demonstration of the algorithm, comparison to other algorithms (at the same time this should not be used as an argument for rejection). Evidence of the scalability of the algorithm should be presented. 
Minor points: 
While the o(), O(), \Omega() notations are rather standard I was not very familiar with the \omega() and had to look it up to be sure. Perhaps more of NIPS audience would not be familiar with those and the definition could be shortly reminded. 
I've read the author's feedback and took it into account in my score.