Scaling Nonparametric Bayesian Inference via Subsample-Annealing
This addresses scalability issues in nonparametric clustering for large datasets, offering a method to handle million-row data more efficiently, though it is an incremental improvement over existing Gibbs sampling techniques.
The paper tackles the problem of slow mixing times in nonparametric Bayesian inference by introducing subsample-annealing, which adapts simulated annealing to use growing subsamples as an inverse temperature schedule. It proves speedups from N^2 to N and exp(N) to N in mixing times, and empirically shows improved accuracy-per-wallclock time on datasets like US Census and hospital ratings.
We describe an adaptation of the simulated annealing algorithm to nonparametric clustering and related probabilistic models. This new algorithm learns nonparametric latent structure over a growing and constantly churning subsample of training data, where the portion of data subsampled can be interpreted as the inverse temperature beta(t) in an annealing schedule. Gibbs sampling at high temperature (i.e., with a very small subsample) can more quickly explore sketches of the final latent state by (a) making longer jumps around latent space (as in block Gibbs) and (b) lowering energy barriers (as in simulated annealing). We prove subsample annealing speeds up mixing time N^2 -> N in a simple clustering model and exp(N) -> N in another class of models, where N is data size. Empirically subsample-annealing outperforms naive Gibbs sampling in accuracy-per-wallclock time, and can scale to larger datasets and deeper hierarchical models. We demonstrate improved inference on million-row subsamples of US Census data and network log data and a 307-row hospital rating dataset, using a Pitman-Yor generalization of the Cross Categorization model.