  This article establishes the performance of stochastic blockmodels in
addressing the co-clustering problem of partitioning a binary array into
subsets, assuming only that the data are generated by a nonparametric process
satisfying the condition of separate exchangeability. We provide oracle
inequalities with rate of convergence $\mathcal{O}_P(n^{-1/4})$ corresponding
to profile likelihood maximization and mean-square error minimization, and show
that the blockmodel can be interpreted in this setting as an optimal
piecewise-constant approximation to the generative nonparametric model. We also
show for large sample sizes that the detection of co-clusters in such data
indicates with high probability the existence of co-clusters of equal size and
asymptotically equivalent connectivity in the underlying generative process.
