Introduction
Nonparametric Bayesian models, such as Dirichlet Process Mixture Models, offer a flexible framework for discovering latent structures in data without pre-specifying the number of clusters or features. However, these models face significant scalability challenges. Standard inference techniques like Gibbs sampling often become trapped in local optima due to high "energy barriers" in the posterior distribution. In large-scale datasets, moving between high-probability configurations requires coordinated changes across many data points, making the mixing time of standard MCMC algorithms prohibitively long.
The Subsample-Annealing Framework
To address these limitations, we introduce Subsample-Annealing, a method that leverages data subsampling as a form of simulated annealing. In classical simulated annealing, a temperature parameter is used to vertically compress the energy landscape, lowering barriers and allowing the sampler to explore the state space more freely. Subsample-annealing extends this by treating the size of the data subsample as the inverse temperature.
As shown in the figure above, while standard simulated annealing only reduces the height of energy barriers (vertical compression), subsampling also reduces the "distance" between modes in the latent space (horizontal compression). By working with a smaller "sketch" of the data, the algorithm can navigate the latent space much faster, discovering global structures before the full dataset is introduced.
Implementation and Annealing Schedule
The algorithm operates by gradually increasing the size of the active data subsample according to a predefined schedule. A key component of this process is data churning: instead of simply adding points, the algorithm decouples the removal and addition of data points. In each step, a random point is removed from the current subsample, and a different point is selected from the unassigned pool to replace it.
This schedule naturally facilitates hyperparameter learning. During the early stages of the schedule, when the data is churning rapidly and the landscape is highly compressed, the algorithm performs hyperparameter updates more frequently. This allows the model to settle into a robust global structure before entering the "fine-tuning" phase as the subsample size approaches the full dataset size $N$.
Key Insights and Results
The theoretical analysis of subsample-annealing reveals significant efficiency gains. For simple clustering models, the method reduces mixing time from $O(N^2)$ to $O(N)$. Empirically, the method was evaluated on diverse datasets, including US Census data and KDD Cup network logs with up to $10^6$ rows.
Key findings include:
- Efficiency: Subsample-annealing consistently outperforms naive Gibbs sampling and sequential initialization in accuracy-per-wallclock-time.
- Robustness: The method exhibits lower variance in cross-validation scores, avoiding the poor local optima that often plague standard MCMC runs.
- Scalability: Successful inference on million-row datasets demonstrates the method's capability where standard MCMC typically fails to converge.
Conclusion and Future Directions
Subsample-annealing provides a powerful mechanism for scaling nonparametric Bayesian inference by combining vertical and horizontal landscape compression. While highly effective, the method can be sensitive to rare outliers if they are not included in early subsamples. Future work may explore stratified subsampling techniques to ensure early representation of diverse data points and further investigate the performance of this approach on more complex energy landscapes.
Summary updated