OxCSML : Projects : Bayesian Inference for Big Data with Stochastic Gradient Markov Chain Monte Carlo

This EPSRC project involving Yee Whye Teh (Oxford), Arnaud Doucet (Oxford), and Christophe Andrieu (Bristol) aims to develop both methodologies and theoretical foundations for scalable Markov chain Monte Carlo methods for big data. The starting point was stochastic gradient Langevin dynamics (SGLD) (Welling and Teh 2011), where we have provided theoretical analyses in terms of both asymptotic convergence (Teh et al 2016) as well as weak error expansion (Vollmer et al 2016). We have also developed a range of novel scalable Monte Carlo algorithms based on different techniques.

Publications

2017

L. Hasenclever , S. Webb , T. Lienart , S. Vollmer , B. Lakshminarayanan , C. Blundell , Y. W. Teh , Distributed Bayesian Learning with Stochastic Natural-gradient Expectation Propagation and the Posterior Server, Journal of Machine Learning Research (JMLR), Oct. 2017.
Project: sgmcmc

This paper makes two contributions to Bayesian machine learning algorithms. Firstly, we propose stochastic natural gradient expectation propagation (SNEP), a novel alternative to expectation propagation (EP), a popular variational inference algorithm. SNEP is a black box variational algorithm, in that it does not require any simplifying assumptions on the distribution of interest, beyond the existence of some Monte Carlo sampler for estimating the moments of the EP tilted distributions. Further, as opposed to EP which has no guarantee of convergence, SNEP can be shown to be convergent, even when using Monte Carlo moment estimates. Secondly, we propose a novel architecture for distributed Bayesian learning which we call the posterior server. The posterior server allows scalable and robust Bayesian learning in cases where a dataset is stored in a distributed manner across a cluster, with each compute node containing a disjoint subset of data. An independent Monte Carlo sampler is run on each compute node, with direct access only to the local data subset, but which targets an approximation to the global posterior distribution given all data across the whole cluster. This is achieved by using a distributed asynchronous implementation of SNEP to pass messages across the cluster. We demonstrate SNEP and the posterior server on distributed Bayesian learning of logistic regression and neural networks.
```
@article{HasWebLie2017a,
  author = {Hasenclever, L. and Webb, S. and Lienart, T. and Vollmer, S. and Lakshminarayanan, B. and Blundell, C. and Teh, Y. W.},
  note = {ArXiv e-prints: 1512.09327},
  title = {Distributed {B}ayesian Learning with Stochastic Natural-gradient Expectation Propagation and the Posterior Server},
  journal = {Journal of Machine Learning Research (JMLR)},
  month = oct,
  year = {2017},
  bdsk-url-1 = {https://arxiv.org/pdf/1512.09327.pdf}
}
```
L. Hasenclever , S. Webb , T. Lienart , S. Vollmer , B. Lakshminarayanan , C. Blundell , Y. W. Teh , Distributed Bayesian Learning with Stochastic Natural Gradient Expectation Propagation and the Posterior Server, Journal of Machine Learning Research, vol. 18, no. 106, 1–37, 2017.
Project: bigbayes sgmcmc

This paper makes two contributions to Bayesian machine learning algorithms. Firstly, we propose stochastic natural gradient expectation propagation (SNEP), a novel alternative to expectation propagation (EP), a popular variational inference algorithm. SNEP is a black box variational algorithm, in that it does not require any simplifying assumptions on the distribution of interest, beyond the existence of some Monte Carlo sampler for estimating the moments of the EP tilted distributions. Further, as opposed to EP which has no guarantee of convergence, SNEP can be shown to be convergent, even when using Monte Carlo moment estimates. Secondly, we propose a novel architecture for distributed Bayesian learning which we call the posterior server. The posterior server allows scalable and robust Bayesian learning in cases where a dataset is stored in a distributed manner across a cluster, with each compute node containing a disjoint subset of data. An independent Monte Carlo sampler is run on each compute node, with direct access only to the local data subset, but which targets an approximation to the global posterior distribution given all data across the whole cluster. This is achieved by using a distributed asynchronous implementation of SNEP to pass messages across the cluster. We demonstrate SNEP and the posterior server on distributed Bayesian learning of logistic regression and neural networks.
```
@article{HasWebLie2015a,
  author = {Hasenclever, Leonard and Webb, Stefan and Lienart, Thibaut and Vollmer, Sebastian and Lakshminarayanan, Balaji and Blundell, Charles and Teh, Yee Whye},
  title = {Distributed Bayesian Learning with Stochastic Natural Gradient Expectation Propagation and the Posterior Server},
  journal = {Journal of Machine Learning Research},
  year = {2017},
  volume = {18},
  number = {106},
  pages = {1-37}
}
```

2016

W. Herlands , A. Wilson , H. Nickisch , S. Flaxman , D. Neill , W. Van Panhuis , E. Xing , Scalable Gaussian Processes for Characterizing Multidimensional Change Surfaces, in Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 2016, 1013–1021.
Project: sgmcmc

We present a scalable Gaussian process model for identifying and characterizing smooth multidimensional changepoints, and automatically learning changes in expressive covariance structure. We use Random Kitchen Sink features to flexibly define a change surface in combination with expressive spectral mixture kernels to capture the complex statistical structure. Finally, through the use of novel methods for additive non-separable kernels, we can scale the model to large datasets. We demonstrate the model on numerical and real world data, including a large spatio-temporal disease dataset where we identify previously unknown heterogeneous changes in space and time.
```
@inproceedings{HerWilNicketal2016,
  author = {Herlands, William and Wilson, Andrew and Nickisch, Hannes and Flaxman, Seth and Neill, Daniel and Van Panhuis, Wilbert and Xing, Eric},
  title = {{Scalable Gaussian Processes} for Characterizing Multidimensional Change Surfaces},
  booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics},
  pages = {1013--1021},
  year = {2016}
}
```
Y. W. Teh , A. H. Thiéry , S. J. Vollmer , Consistency and Fluctuations for Stochastic Gradient Langevin Dynamics, Journal of Machine Learning Research, 2016.
Project: sgmcmc

Applying standard Markov chain Monte Carlo (MCMC) algorithms to large data sets is computationally expensive. Both the calculation of the acceptance probability and the creation of informed proposals usually require an iteration through the whole data set. The recently proposed stochastic gradient Langevin dynamics (SGLD) method circumvents this problem by generating proposals which are only based on a subset of the data, by skipping the accept-reject step and by using decreasing step-sizes sequence (δ_m)_m≥0. We provide in this article a rigorous mathematical framework for analysing this algorithm. We prove that, under verifiable assumptions, the algorithm is consistent, satisfies a central limit theorem (CLT) and its asymptotic bias-variance decomposition can be characterized by an explicit functional of the step-sizes sequence (δ_m)_m≥0. We leverage this analysis to give practical recommendations for the notoriously difficult tuning of this algorithm: it is asymptotically optimal to use a step-size sequence of the type δ_m≍m^−1/3, leading to an algorithm whose mean squared error (MSE) decreases at rate O(m^−1/3).
```
@article{TehThiVol2016a,
  author = {Teh, Y. W. and Thi\'ery, A. H. and Vollmer, S. J.},
  journal = {Journal of Machine Learning Research},
  title = {Consistency and Fluctuations for Stochastic Gradient {L}angevin Dynamics},
  year = {2016},
  bdsk-url-1 = {http://jmlr.org/papers/v17/teh16a.html},
  bdsk-url-2 = {http://www.jmlr.org/papers/volume17/teh16a/teh16a.pdf}
}
```
S. J. Vollmer , K. C. Zygalakis , Y. W. Teh , Exploration of the (Non-)asymptotic Bias and Variance of Stochastic Gradient Langevin Dynamics, Journal of Machine Learning Research (JMLR), 2016.
Project: sgmcmc

Applying standard Markov chain Monte Carlo (MCMC) algorithms to large data sets is computationally infeasible. The recently proposed stochastic gradient Langevin dynamics (SGLD) method circumvents this problem in three ways: it generates proposed moves using only a subset of the data, it skips the Metropolis- Hastings accept-reject step, and it uses sequences of decreasing step sizes. In Teh et al. (2014), we provided the mathematical foundations for the decreasing step size SGLD, including consistency and a central limit theorem. However, in practice the SGLD is run for a relatively small number of iterations, and its step size is not decreased to zero. The present article investigates the behaviour of the SGLD with fixed step size. In particular we characterise the asymptotic bias explicitly, along with its dependence on the step size and the variance of the stochastic gradient. On that basis a modified SGLD which removes the asymptotic bias due to the variance of the stochastic gradients up to first order in the step size is derived. Moreover, we are able to obtain bounds on the finite-time bias, variance and mean squared error (MSE). The theory is illustrated with a Gaussian toy model for which the bias and the MSE for the estimation of moments can be obtained explicitly. For this toy model we study the gain of the SGLD over the standard Euler method in the limit of large data sets.
```
@article{VolZygTeh2016a,
  author = {Vollmer, S. J. and Zygalakis, K. C. and Teh, Y. W.},
  journal = {Journal of Machine Learning Research (JMLR)},
  title = {Exploration of the (Non-)asymptotic Bias and Variance of Stochastic Gradient {L}angevin Dynamics},
  year = {2016},
  bdsk-url-1 = {http://jmlr.org/papers/v17/15-494.html},
  bdsk-url-2 = {http://www.jmlr.org/papers/volume17/15-494/15-494.pdf}
}
```

2015

T. Lienart , Y. W. Teh , A. Doucet , Expectation Particle Belief Propagation, in Advances in Neural Information Processing Systems (NeurIPS), 2015.
Project: sgmcmc

We propose an original particle-based implementation of the Loopy Belief Propagation (LPB) algorithm for pairwise Markov Random Fields (MRF) on a continuous state space. The algorithm constructs adaptively efficient proposal distributions approximating the local beliefs at each note of the MRF. This is achieved by considering proposal distributions in the exponential family whose parameters are updated iterately in an Expectation Propagation (EP) framework. The proposed particle scheme provides consistent estimation of the LBP marginals as the number of particles increases. We demonstrate that it provides more accurate results than the Particle Belief Propagation (PBP) algorithm of Ihler and McAllester (2009) at a fraction of the computational cost and is additionally more robust empirically. The computational complexity of our algorithm at each iteration is quadratic in the number of particles. We also propose an accelerated implementation with sub-quadratic computational complexity which still provides consistent estimates of the loopy BP marginal distributions and performs almost as well as the original procedure.
```
@inproceedings{LieTehDou2015a,
  author = {Lienart, T. and Teh, Y. W. and Doucet, A.},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  title = {Expectation Particle Belief Propagation},
  year = {2015},
  bdsk-url-1 = {http://papers.nips.cc/paper/5674-expectation-particle-belief-propagation},
  bdsk-url-2 = {http://papers.nips.cc/paper/5674-expectation-particle-belief-propagation.pdf},
  bdsk-url-3 = {http://papers.nips.cc/paper/5674-expectation-particle-belief-propagation-supplemental.zip}
}
```
B. Lakshminarayanan , D. M. Roy , Y. W. Teh , Particle Gibbs for Bayesian Additive Regression Trees, in Proceedings of the International Conference on Artificial Intelligence and Statistics, 2015.
Project: bigbayes sgmcmc

Additive regression trees are flexible non-parametric models and popular off-the-shelf tools for real-world non-linear regression. In application domains, such as bioinformatics, where there is also demand for probabilistic predictions with measures of uncertainty, the Bayesian additive regression trees (BART) model, introduced by Chipman et al. (2010), is increasingly popular. As data sets have grown in size, however, the standard Metropolis–Hastings algorithms used to per- form inference in BART are proving inadequate. In particular, these Markov chains make local changes to the trees and suffer from slow mixing when the data are high- dimensional or the best-fitting trees are more than a few layers deep. We present a novel sampler for BART based on the Particle Gibbs (PG) algorithm (Andrieu et al., 2010) and a top-down particle filtering algorithm for Bayesian decision trees (Lakshminarayanan et al., 2013). Rather than making local changes to individual trees, the PG sampler proposes a complete tree to fit the residual. Experiments show that the PG sampler outperforms existing samplers in many settings.
```
@inproceedings{LakRoyTeh2015b,
  author = {Lakshminarayanan, B. and Roy, D. M. and Teh, Y. W.},
  booktitle = {Proceedings of the International Conference on Artificial Intelligence and Statistics},
  title = {Particle {G}ibbs for {B}ayesian Additive Regression Trees},
  year = {2015},
  bdsk-url-1 = {http://jmlr.org/proceedings/papers/v38/lakshminarayanan15.html},
  bdsk-url-2 = {http://jmlr.org/proceedings/papers/v38/lakshminarayanan15.pdf},
  bdsk-url-3 = {http://jmlr.org/proceedings/papers/v38/lakshminarayanan15-supp.pdf}
}
```

2014

M. Xu , B. Lakshminarayanan , Y. W. Teh , J. Zhu , B. Zhang , Distributed Bayesian Posterior Sampling via Moment Sharing, in Advances in Neural Information Processing Systems, 2014.
Project: sgmcmc

We propose a distributed Markov chain Monte Carlo (MCMC) inference algorithm for large scale Bayesian posterior simulation. We assume that the dataset is partitioned and stored across nodes of a cluster. Our procedure involves an independent MCMC posterior sampler at each node based on its local partition of the data. Moment statistics of the local posteriors are collected from each sampler and propagated across the cluster using expectation propagation message passing with low communication costs. The moment sharing scheme improves posterior estimation quality by enforcing agreement among the samplers. We demonstrate the speed and inference quality of our method with empirical studies on Bayesian logistic regression and sparse linear regression with a spike-and-slab prior.
```
@inproceedings{XuLakTeh2014a,
  author = {Xu, M. and Lakshminarayanan, B. and Teh, Y. W. and Zhu, J. and Zhang, B.},
  booktitle = {Advances in Neural Information Processing Systems},
  title = {Distributed {B}ayesian Posterior Sampling via Moment Sharing},
  year = {2014},
  bdsk-url-1 = {http://papers.nips.cc/paper/5596-distributed-bayesian-posterior-sampling-via-moment-sharing},
  bdsk-url-2 = {http://papers.nips.cc/paper/5596-distributed-bayesian-posterior-sampling-via-moment-sharing.pdf},
  bdsk-url-3 = {https://github.com/BigBayes/SMS}
}
```
B. Paige , F. Wood , A. Doucet , Y. W. Teh , Asynchronous Anytime Sequential Monte Carlo, in Advances in Neural Information Processing Systems (NeurIPS), 2014.
Project: sgmcmc

We introduce a new sequential Monte Carlo algorithm we call the particle cascade. The particle cascade is an asynchronous, anytime alternative to traditional sequential Monte Carlo algorithms that is amenable to parallel and distributed implementations. It uses no barrier synchronizations which leads to improved particle throughput and memory efficiency. It is an anytime algorithm in the sense that it can be run forever to emit an unbounded number of particles while keeping within a fixed memory budget. We prove that the particle cascade provides an unbiased marginal likelihood estimator which can be straightforwardly plugged into existing pseudo-marginal methods.
```
@inproceedings{PaiWooDou2014a,
  author = {Paige, B. and Wood, F. and Doucet, A. and Teh, Y. W.},
  booktitle = {Advances in Neural Information Processing Systems (NeurIPS)},
  title = {Asynchronous Anytime Sequential {M}onte {C}arlo},
  year = {2014},
  bdsk-url-1 = {http://papers.nips.cc/paper/5450-asynchronous-anytime-sequential-monte-carlo},
  bdsk-url-2 = {http://papers.nips.cc/paper/5450-asynchronous-anytime-sequential-monte-carlo.pdf},
  bdsk-url-3 = {http://papers.nips.cc/paper/5450-asynchronous-anytime-sequential-monte-carlo-supplemental.zip}
}
```

Software

2016

L. Hasenclever , S. Webb , T. Lienart , S. Vollmer , B. Lakshminarayanan , C. Blundell , Y. W. Teh , Posterior Server. 2016.
Project: sgmcmc

This paper makes two contributions to Bayesian machine learning algorithms. Firstly, we propose stochastic natural gradient expectation propagation (SNEP), a novel alternative to expectation propagation (EP), a popular variational inference algorithm. SNEP is a black box variational algorithm, in that it does not require any simplifying assumptions on the distribution of interest, beyond the existence of some Monte Carlo sampler for estimating the moments of the EP tilted distributions. Further, as opposed to EP which has no guarantee of convergence, SNEP can be shown to be convergent, even when using Monte Carlo moment estimates. Secondly, we propose a novel architecture for distributed Bayesian learning which we call the posterior server. The posterior server allows scalable and robust Bayesian learning in cases where a dataset is stored in a distributed manner across a cluster, with each compute node containing a disjoint subset of data. An independent Monte Carlo sampler is run on each compute node, with direct access only to the local data subset, but which targets an approximation to the global posterior distribution given all data across the whole cluster. This is achieved by using a distributed asynchronous implementation of SNEP to pass messages across the cluster. We demonstrate SNEP and the posterior server on distributed Bayesian learning of logistic regression and neural networks.
```
@software{HasWebLie2016a,
  author = {Hasenclever, L. and Webb, S. and Lienart, T. and Vollmer, S. and Lakshminarayanan, B. and Blundell, C. and Teh, Y. W.},
  title = {Posterior Server},
  year = {2016},
  bdsk-url-1 = {https://github.com/BigBayes/PosteriorServer}
}
```

2015

B. Lakshminarayanan , D. M. Roy , Y. W. Teh , PGBart. 2015.

Project: bigbayes sgmcmc

@software{LakRoyTeh2015a,
  author = {Lakshminarayanan, B. and Roy, D. M. and Teh, Y. W.},
  title = {PGBart},
  year = {2015},
  bdsk-url-1 = {https://github.com/balajiln/pgbart}
}

2014

M. Xu , B. Lakshminarayanan , Y. W. Teh , J. Zhu , B. Zhang , SMS: Sampling via Moment Sharing, Advances in Neural Information Processing Systems. 2014.
Project: sgmcmc

We propose a distributed Markov chain Monte Carlo (MCMC) inference algorithm for large scale Bayesian posterior simulation. We assume that the dataset is partitioned and stored across nodes of a cluster. Our procedure involves an independent MCMC posterior sampler at each node based on its local partition of the data. Moment statistics of the local posteriors are collected from each sampler and propagated across the cluster using expectation propagation message passing with low communication costs. The moment sharing scheme improves posterior estimation quality by enforcing agreement among the samplers. We demonstrate the speed and inference quality of our method with empirical studies on Bayesian logistic regression and sparse linear regression with a spike-and-slab prior.
```
@software{XuLakTeh2014b,
  author = {Xu, M. and Lakshminarayanan, B. and Teh, Y. W. and Zhu, J. and Zhang, B.},
  booktitle = {Advances in Neural Information Processing Systems},
  title = {{SMS}: Sampling via Moment Sharing},
  year = {2014},
  bdsk-url-1 = {https://github.com/BigBayes/SMS}
}
```