Increasingly complex datasets pose a number of challenges for Bayesianinference. Conventional posterior sampling based on Markov chain Monte Carlocan be too computationally intensive, is serial in nature and mixes poorlybetween posterior modes. Further, all models are misspecified, which bringsinto question the validity of the conventional Bayesian update. We present ascalable Bayesian nonparametric learning routine that enables posteriorsampling through the optimization of suitably randomized objective functions. ADirichlet process prior on the unknown data distribution accounts for modelmisspecification, and admits an embarrassingly parallel posterior bootstrapalgorithm that generates independent and exact samples from the nonparametricposterior distribution. Our method is particularly adept at sampling frommultimodal posterior distributions via a random restart mechanism. Wedemonstrate our method on Gaussian mixture model and sparse logistic regressionexamples.