 Award ID(s):
 1854562
 NSFPAR ID:
 10233326
 Editor(s):
 Bae, KH; Feng, B; Kim, S; LazarovaMolnar, S; Zheng, Z; Roeder, T; Thiesing, R
 Date Published:
 Journal Name:
 Proceedings of the Winter Simulation Conference
 ISSN:
 15584305
 Page Range / eLocation ID:
 28872898
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Chaudhuri, Kamalika and (Ed.)Spikeandslab priors are commonly used for Bayesian variable selection, due to their interpretability and favorable statistical properties. However, existing samplers for spikeandslab posteriors incur prohibitive computational costs when the number of variables is large. In this article, we propose Scalable SpikeandSlab (S^3), a scalable Gibbs sampling implementation for highdimensional Bayesian regression with the continuous spikeandslab prior of George & McCulloch (1993). For a dataset with n observations and p covariates, S^3 has order max{n^2 p_t, np} computational cost at iteration t where p_t never exceeds the number of covariates switching spikeandslab states between iterations t and t1 of the Markov chain. This improves upon the order n^2 p periteration cost of stateoftheart implementations as, typically, p_t is substantially smaller than p. We apply S^3 on synthetic and realworld datasets, demonstrating orders of magnitude speedups over existing exact samplers and significant gains in inferential quality over approximate samplers with comparable cost.more » « less

Abstract We propose a very fast approximate Markov chain Monte Carlo sampling framework that is applicable to a large class of sparse Bayesian inference problems. The computational cost per iteration in several regression models is of order O(n(s+J)), where n is the sample size, s is the underlying sparsity of the model, and J is the size of a randomly selected subset of regressors. This cost can be further reduced by data subsampling when stochastic gradient Langevin dynamics are employed. The algorithm is an extension of the asynchronous Gibbs sampler of Johnson et al. [(2013). Analyzing Hogwild parallel Gaussian Gibbs sampling. In Proceedings of the 26th International Conference on Neural Information Processing Systems (NIPS’13) (Vol. 2, pp. 2715–2723)], but can be viewed from a statistical perspective as a form of Bayesian iterated sure independent screening [Fan, J., Samworth, R., & Wu, Y. (2009). Ultrahigh dimensional feature selection: Beyond the linear model. Journal of Machine Learning Research, 10, 2013–2038]. We show that in highdimensional linear regression problems, the Markov chain generated by the proposed algorithm admits an invariant distribution that recovers correctly the main signal with high probability under some statistical assumptions. Furthermore, we show that its mixing time is at most linear in the number of regressors. We illustrate the algorithm with several models.

Inferencebased optimization via simulation, which substitutes Gaussian process (GP) learning for the structural properties exploited in mathematical programming, is a powerful paradigm that has been shown to be remarkably effective in problems of modest feasibleregion size and decisionvariable dimension. The limitation to “modest” problems is a result of the computational overhead and numerical challenges encountered in computing the GP conditional (posterior) distribution on each iteration. In this paper, we substantially expand the size of discretedecisionvariable optimizationviasimulation problems that can be attacked in this way by exploiting a particular GP—discrete Gaussian Markov random fields—and carefully tailored computational methods. The result is the rapid Gaussian Markov Improvement Algorithm (rGMIA), an algorithm that delivers both a global convergence guarantee and finitesample optimalitygap inference for significantly larger problems. Between infrequent evaluations of the global conditional distribution, rGMIA applies the full power of GP learning to rapidly search smaller sets of promising feasible solutions that need not be spatially close. We carefully document the computational savings via complexity analysis and an extensive empirical study. Summary of Contribution: The broad topic of the paper is optimization via simulation, which means optimizing some performance measure of a system that may only be estimated by executing a stochastic, discreteevent simulation. Stochastic simulation is a core topic and method of operations research. The focus of this paper is on significantly speedingup the computations underlying an existing method that is based on Gaussian process learning, where the underlying Gaussian process is a discrete Gaussian Markov Random Field. This speedup is accomplished by employing smart computational linear algebra, stateoftheart algorithms, and a careful divideandconquer evaluation strategy. Problems of significantly greater size than any other existing algorithm with similar guarantees can solve are solved as illustrations.more » « less

Lawrence, Neil (Ed.)Recent research has shown the potential utility of deep Gaussian processes. These deep structures are probability distributions, designed through hierarchical construction, which are conditionally Gaussian. In this paper, the current published body of work is placed in a common framework and, through recursion, several classes of deep Gaussian processes are deﬁned. The resulting samples generated from a deep Gaussian process have a Markovian structure with respect to the depth parameter, and the eﬀective depth of the resulting process is interpreted in terms of the ergodicity, or nonergodicity, of the resulting Markov chain. For the classes of deep Gaussian processes introduced, we provide results concerning their ergodicity and hence their eﬀective depth. We also demonstrate how these processes may be used for inference; in particular we show how a MetropoliswithinGibbs construction across the levels of the hierarchy can be used to derive sampling tools which are robust to the level of resolution used to represent the functions on a computer. For illustration, we consider the eﬀect of ergodicity in some simple numerical examples.more » « less

Markov chain Monte Carlo (MCMC) is an established approach for uncertainty quantification and propagation in scientific applications. A key challenge in apply ing MCMC to scientific domains is computation: the target density of interest is often a function of expensive computations, such as a highfidelity physical simulation, an intractable integral, or a slowlyconverging iterative algorithm. Thus, using an MCMC algorithms with an expensive target density becomes impractical, as these expensive computations need to be evaluated at each iteration of the algorithm. In practice, these computations often approximated via a cheaper, low fidelity computation, leading to bias in the resulting target density. Multifidelity MCMC algorithms combine models of varying fidelities in order to obtain an ap proximate target density with lower computational cost. In this paper, we describe a class of asymptotically exact multifidelity MCMC algorithms for the setting where a sequence of models of increasing fidelity can be computed that approximates the expensive target density of interest. We take a pseudomarginal MCMC approach for multifidelity inference that utilizes a cheaper, randomizedfidelity unbiased estimator of the target fidelity constructed via random truncation of a telescoping series of the lowfidelity sequence of models. Finally, we discuss and evaluate the proposed multifidelity MCMC approach on several applications, including logGaussian Cox process modeling, Bayesian ODE system identification, PDEconstrained optimization, and Gaussian process parameter inference.more » « less