Complexity Bounds for Dirichlet Process Slice Samplers

Slice sampling is a standard Monte Carlo technique for Dirichlet process (DP)-based models, widely used in posterior simulation. However, formal assessments of the scalability of posterior slice samplers have remained largely unexplored, primarily because the computational cost of a slice-sampling iteration is random and potentially unbounded. In this work, we obtain high-probability bounds on the computational complexity of DP slice samplers. Our main results show that, uniformly across posterior cluster-growth regimes, the overhead induced by slice variables, relatively to the number of clusters supported by the posterior, is $O_{\mathbb P}(\log n)$. As a consequence, even in worst-case configurations, superlinear blow-ups in per-iteration computational cost occur with vanishing probability. Our analysis applies broadly to DP--based models without any likelihood-specific assumptions, still providing complexity guarantees for posterior sampling on arbitrary datasets. These results establish a theoretical foundation for assessing the practical scalability of slice sampling in DP-based models.

Many machine learning methods try to discover latent groups in data, such as communities in a network, repeated patterns in observations, or clusters of similar individuals. Many Bayesian approaches allow the number of these latent groups to grow automatically with the data rather than being fixed in advance. This flexibility is useful, but it makes computation harder: algorithms must decide, at each step, how many possible groups to consider, and in principle, this number can become very large, making the algorithm unpredictably slow. We study one such algorithm, called slice sampling, and ask whether these occasional expensive steps are a real obstacle. We prove that, with high probability, the algorithm only needs to consider a small extra number of possible groups beyond those currently used by the data. More precisely, this extra cost grows only logarithmically with the sample size. This helps explain why slice sampling often works well in practice, despite having no fixed computational limit per iteration. Our results give researchers stronger theoretical confidence in using exact Bayesian nonparametric methods without relying on arbitrary truncation rules.