Communication costs, resulting from synchronization requirements during learning, can greatly slow down many parallel machine learning algorithms. In this paper, we present a parallel Markov chain Monte Carlo (MCMC) algorithm in which subsets of data are processed independently, with very little communication. First, we arbitrarily partition data onto multiple machines. Then, on each machine, any classical MCMC method (e.g., Gibbs sampling) may be used to draw samples from a posterior distribution given the data subset. Finally, the samples from each machine are combined to form samples from the full posterior. This embarrassingly parallel algorithm allows each machine to act independently on a subset of the data (without communication) until the final combination stage. We prove that our algorithm generates asymptotically exact samples and empirically demonstrate its ability to parallelize burn-in and sampling in several models.
Consensus Monte Carlo @cite_12 is perhaps the most relevant work to ours. In this algorithm, data is also portioned into different machines and MCMC is performed independently on each machine. Thus, it roughly has the same time complexity as our algorithm. However, the prior is not explicitly reweighted during sampling as we do in Eq , and final samples for the full posterior are generated by averaging subposterior samples. Furthermore, this algorithm has few theoretical guarantees. We find that this algorithm can be viewed as a relaxation of our nonparametric, asymptotically exact sampling procedure, where samples are generated from an evenly weighted mixture (instead of each component having weight @math ) and where each sample is set to @math instead of being drawn from @math . This algorithm is one of our experimental baselines.
@cite_12
2305001871
The class of species sampling mixture models is introduced as an exten- sion of semiparametric models based on the Dirichlet process to models based on the general class of species sampling priors, or equivalently the class of all exchangeable urn distributions. Using Fubini calculus in conjunction with Pitman (1995, 1996), we derive characterizations of the posterior distribution in terms of a posterior par- tition distribution that extend the results of Lo (1984) for the Dirichlet process. These results provide a better understanding of models and have both theoretical and practical applications. To facilitate the use of our models we generalize the work in Brunner, Chan, James and Lo (2001) by extending their weighted Chinese restaurant (WCR) Monte Carlo procedure, an i.i.d. sequential importance sampling (SIS) procedure for approximating posterior mean functionals based on the Dirich- let process, to the case of approximation of mean functionals and additionally their posterior laws in species sampling mixture models. We also discuss collapsed Gibbs sampling, Polya urn Gibbs sampling and a Polya urn SIS scheme. Our framework allows for numerous applications, including multiplicative counting process models subject to weighted gamma processes, as well as nonparametric and semiparamet- ric hierarchical models based on the Dirichlet process, its two-parameter extension, the Pitman-Yor process and finite dimensional Dirichlet priors. Importance sampling methods can be iterated like MCMC algorithms, while being more robust against dependence and starting values. The population Monte Carlo principle consists of iterated generations of importance samples, with importance functions depending on the previously generated importance samples. The advantage over MCMC algorithms is that the scheme is unbiased at any iteration and can thus be stopped at any time, while iterations improve the performances of the importance function, thus leading to an adaptive importance sampling. We illustrate this method on a mixture example with multiscale importance functions. A second example reanalyzes the ion channel model using an importance sampling scheme based on a hidden Markov representation, and compares population Monte Carlo with a corresponding MCMC algorithm. Statistical and machine-learning algorithms are frequently applied to high-dimensional data. In many of these applications data is scarce, and often much more costly than computation time. We provide the first sample-efficient polynomial-time estimator for high-dimensional spherical Gaussian mixtures. For mixtures of any @math @math -dimensional spherical Gaussians, we derive an intuitive spectral-estimator that uses @math samples and runs in time @math , both significantly lower than previously known. The constant factor @math is polynomial for sample complexity and is exponential for the time complexity, again much smaller than what was previously known. We also show that @math samples are needed for any algorithm. Hence the sample complexity is near-optimal in the number of dimensions. We also derive a simple estimator for one-dimensional mixtures that uses @math samples and runs in time @math . Our other technical contributions include a faster algorithm for choosing a density estimate from a set of distributions, that minimizes the @math distance to an unknown underlying distribution. A @math -modal probability distribution over the discrete domain @math is one whose histogram has at most @math "peaks" and "valleys." Such distributions are natural generalizations of monotone ( @math ) and unimodal ( @math ) probability distributions, which have been intensively studied in probability theory and statistics. In this paper we consider the problem of (i.e., performing density estimation of) an unknown @math -modal distribution with respect to the @math distance. The learning algorithm is given access to independent samples drawn from an unknown @math -modal distribution @math , and it must output a hypothesis distribution @math such that with high probability the total variation distance between @math and @math is at most @math Our main goal is to obtain algorithms for this problem that use (close to) an information-theoretically optimal number of samples. We give an efficient algorithm for this problem that runs in time @math . For @math , the number of samples used by our algorithm is very close (within an @math factor) to being information-theoretically optimal. Prior to this work computationally efficient algorithms were known only for the cases @math Birge:87b,Birge:97 . A novel feature of our approach is that our learning algorithm crucially uses a new algorithm for as a key subroutine. The learning algorithm uses the property tester to efficiently decompose the @math -modal distribution into @math (near-)monotone distributions, which are easier to learn.