Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's
We present an algorithm for recovering planted solutions in two well-known models, the stochastic block model and planted constraint satisfaction problems (CSP), via a common generalization in terms of random bipartite graphs. Our algorithm matches up to a constant factor the best-known bounds for the number of edges (or constraints) needed for perfect recovery and its running time is linear in the number of edges used. The time complexity is significantly better than both spectral and SDP-based approaches. The main contribution of the algorithm is in the case of unequal sizes in the bipartition that arises in our reduction from the planted CSP. Here our algorithm succeeds at a significantly lower density than the spectral approaches, surpassing a barrier based on the spectral norm of a random matrix. Other significant features of the algorithm and analysis include (i) the critical use of power iteration with subsampling, which might be of independent interest; its analysis requires keeping track of multiple norms of an evolving solution (ii) the algorithm can be implemented statistically, i.e., with very limited access to the input distribution (iii) the algorithm is extremely simple to implement and runs in linear time, and thus is practical even for very large instances.
This paper gives a new, simple algorithm for block models (especially when the graph is bipartite and the two sides are highly imbalanced), and show that the problem of planted CSP can be reduced to this case. As a result this paper gives simple "spectral"-like algorithms for planted CSPs for all k, where previously for odd k the only known results require SDP or more complicated spectral analysis.This is a very interesting paper. The new algorithm is clean and efficient. The reviewer feels this gives significant better understanding to planted k-CSPs when k is odd. The main algorithmic technique is based on simple power iteration, but the subsampling idea is important (as otherwise it becomes the spectral approach which we know will not work in certain cases). The proof relies on careful induction on the mean and variance of the entries.Minor points: Definition 3: In order for this to be useful there must also be a distance to r-wise independent (or in other words lowerbound in the fourier coefficient), would be nice to discuss how that appears in Theorem 2 below.Section 5 explained why spectral algorithms cannot work, it would be nice to also explain why subsampling helps, as it still looks very much like power method that computes the top singular vectors. The induction proof does not give much intuition.Overall I think this paper is very nice and should be accepted.