Stopping Rules for the Stochastic Nested Partitions Method

We have recently developed a global optimization methodology for solving combinatorial problems with either deterministic or stochastic performance functions. This method, the Nested Partitions (NP) method has been shown to generate a Markov chain and with probability one to converge to a global optimum. In this paper, we study the rate of convergence of the method through the use of Markov Chain Monte Carlo (MCMC) methods, and use this to derive stopping rules that can be applied during simulation-based optimization. A numerical example serves to illustrate the feasibility of our approach.     

Two-Stage Nested Partitions Method for Stochastic Optimization

We address the problem of optimizing over a large but finite set when the objective function does not have an analytical expression and is evaluated using noisy estimation. Building on the recently proposed nested partitions method for stochastic optimization, we develop a new approach that combines this random search method and statistical selection for guiding the search. We prove asymptotic convergence and analyze the finite time behavior of the new approach. We also report extensive numerical results to illustrate the benefits of the new approach.     

A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation*

We present a new method, called the minimum cross-entropy (MCE) method for approximating the optimal solution of NP-hard combinatorial optimization problems and rare-event probability estimation, which can be viewed as an alternative to the standard cross entropy (CE) method. The MCE method presents a generic adaptive stochastic version of Kull-backs classic MinxEnt method. We discuss its similarities and differences with the standard cross-entropy (CE) method and prove its convergence. We show numerically that MCE is a little more accurate than CE, but at the same time a little slower than CE. We also present a new method for trajectory generation for TSP and some related problems. We finally give some numerical results using MCE for rare-events probability estimation for simple static models, the maximal cut problem and the TSP, and point out some new areas of possible applications.AMS 2000 Subject Classification: 65C05, 60C05, 68W20, 90C59*This reseach was supported by the Israel Science Foundation (grant no 191-565).     

Bayesian Filtering for Jump-Diffusions With Application to Stochastic Volatility

In this article, the problem of sequentially learning parameters governing discretely observed jump-diffusions is explored. The estimation framework involves the introduction of latent points between every pair of observations to allow a sufficiently accurate Euler–Maruyama approximation of the underlying (but unavailable) transition densities. Particle filtering algorithms are then implemented to sample the posterior distribution of the latent data and the model parameters online. The methodology is applied to the estimation of parameters governing a stochastic volatility (SV) model with jumps. As well as using S&P 500 Index data, a simulation study is provided. Supplemental materials for this article are available online.     

Implementable Algorithm for Stochastic Optimization Using Sample Average Approximations

We develop an implementable algorithm for stochastic optimization problems involving probability functions. Such problems arise in the design of structural and mechanical systems. The algorithm consists of a nonlinear optimization algorithm applied to sample average approximations and a precision-adjustment rule. The sample average approximations are constructed using Monte Carlo simulations or importance sampling techniques. We prove that the algorithm converges to a solution with probability one and illustrate its use by an example involving a reliability-based optimal design.     

Stochastic Optimization of Insurance Portfolios for Managing Exposure to Catastrophic Risks

A catastrophe may affect different locations and produce losses that are rare and highly correlated in space and time. It may ruin many insurers if their risk exposures are not properly diversified among locations. The multidimentional distribution of claims from different locations depends on decision variables such as the insurer's coverage at different locations, on spatial and temporal characteristics of possible catastrophes and the vulnerability of insured values. As this distribution is analytically intractable, the most promising approach for managing the exposure of insurance portfolios to catastrophic risks requires geographically explicit simulations of catastrophes. The straightforward use of so-called catastrophe modeling runs quickly into an extremely large number of what-if evaluations. The aim of this paper is to develop an approach that integrates catastrophe modeling with stochastic optimization techniques to support decision making on coverages of losses, profits, stability, and survival of insurers. We establish connections between ruin probability and the maximization of concave risk functions and we outline numerical experiments.     

Noisy Hamiltonian Monte Carlo for Doubly Intractable Distributions

Hamiltonian Monte Carlo (HMC) has been progressively incorporated within the statistician’s toolbox as an alternative sampling method in settings when standard Metropolis–Hastings is inefficient. HMC generates a Markov chain on an augmented state space with transitions based on a deterministic differential flow derived from Hamiltonian mechanics. In practice, the evolution of Hamiltonian systems cannot be solved analytically, requiring numerical integration schemes. Under numerical integration, the resulting approximate solution no longer preserves the measure of the target distribution, therefore an accept–reject step is used to correct the bias. For doubly intractable distributions—such as posterior distributions based on Gibbs random fields—HMC suffers from some computational difficulties: computation of gradients in the differential flow and computation of the accept–reject proposals poses difficulty. In this article, we study the behavior of HMC when these quantities are replaced by Monte Carlo estimates. Supplemental codes for implementing methods used in the article are available online.     

Adaptive Bayesian Nonstationary Modeling for Large Spatial Datasets Using Covariance Approximations

Gaussian process models have been widely used in spatial statistics but face tremendous modeling and computational challenges for very large nonstationary spatial datasets. To address these challenges, we develop a Bayesian modeling approach using a nonstationary covariance function constructed based on adaptively selected partitions. The partitioned nonstationary class allows one to knit together local covariance parameters into a valid global nonstationary covariance for prediction, where the local covariance parameters are allowed to be estimated within each partition to reduce computational cost. To further facilitate the computations in local covariance estimation and global prediction, we use the full-scale covariance approximation (FSA) approach for the Bayesian inference of our model. One of our contributions is to model the partitions stochastically by embedding a modified treed partitioning process into the hierarchical models that leads to automated partitioning and substantial computational benefits. We illustrate the utility of our method with simulation studies and the global Total Ozone Matrix Spectrometer (TOMS) data. Supplementary materials for this article are available online.     

General Methods for Monitoring Convergence of Iterative Simulations

Abstract

We generalize the method proposed by Gelman and Rubin (1992a) for monitoring the convergence of iterative simulations by comparing between and within variances of multiple chains, in order to obtain a family of tests for convergence. We review methods of inference from simulations in order to develop convergence-monitoring summaries that are relevant for the purposes for which the simulations are used. We recommend applying a battery of tests for mixing based on the comparison of inferences from individual sequences and from the mixture of sequences. Finally, we discuss multivariate analogues, for assessing convergence of several parameters simultaneously.     

The Cross-Entropy Method for Combinatorial and Continuous Optimization

We present a new and fast method, called the cross-entropy method, for finding the optimal solution of combinatorial and continuous nonconvex optimization problems with convex bounded domains. To find the optimal solution we solve a sequence of simple auxiliary smooth optimization problems based on Kullback-Leibler cross-entropy, importance sampling, Markov chain and Boltzmann distribution. We use importance sampling as an important ingredient for adaptive adjustment of the temperature in the Boltzmann distribution and use Kullback-Leibler cross-entropy to find the optimal solution. In fact, we use the mode of a unimodal importance sampling distribution, like the mode of beta distribution, as an estimate of the optimal solution for continuous optimization and Markov chains approach for combinatorial optimization. In the later case we show almost surely convergence of our algorithm to the optimal solution. Supporting numerical results for both continuous and combinatorial optimization problems are given as well. Our empirical studies suggest that the cross-entropy method has polynomial in the size of the problem running time complexity.     

Perturbation bounds for Monte Carlo within Metropolis via restricted approximations

The Monte Carlo within Metropolis (MCwM) algorithm, interpreted as a perturbed Metropolis–Hastings (MH) algorithm, provides an approach for approximate sampling when the target distribution is intractable. Assuming the unperturbed Markov chain is geometrically ergodic, we show explicit estimates of the difference between the $n$th step distributions of the perturbed MCwM and the unperturbed MH chains. These bounds are based on novel perturbation results for Markov chains which are of interest beyond the MCwM setting. To apply the bounds, we need to control the difference between the transition probabilities of the two chains and to verify stability of the perturbed chain.     

Pattern Hit-and-Run for sampling efficiently on polytopes

Pattern Hit-and-Run (PHR) is a Markov chain Monte Carlo sampler for a target distribution that was originally designed for general sets embedded in a box. A specific set of interest to many applications is a polytope intersected with discrete or mixed continuous/discrete lattices. PHR requires an acceptance/rejection mechanism along a bidirectional walk to guarantee feasibility. We remove this inefficiency by utilizing the linearity of the constraints defining the polytope, so each iteration of PHR can be efficiently implemented even though the variables are allowed to be integer valued. Moreover, PHR converges to a uniform distribution in polynomial time for a class of discrete polytopes.     

A Pivotal Allocation-Based Algorithm for Solving the Label-Switching Problem in Bayesian Mixture Models

In Bayesian analysis of mixture models, the label-switching problem occurs as a result of the posterior distribution being invariant to any permutation of cluster indices under symmetric priors. To solve this problem, we propose a novel relabeling algorithm and its variants by investigating an approximate posterior distribution of the latent allocation variables instead of dealing with the component parameters directly. We demonstrate that our relabeling algorithm can be formulated in a rigorous framework based on information theory. Under some circumstances, it is shown to resemble the classical Kullback-Leibler relabeling algorithm and include the recently proposed equivalence classes representatives relabeling algorithm as a special case. Using simulation studies and real data examples, we illustrate the efficiency of our algorithm in dealing with various label-switching phenomena. Supplemental materials for this article are available online.     

Path coupling without contraction

Path coupling is a useful technique for simplifying the analysis of a coupling of a Markov chain. Rather than defining and analysing the coupling on every pair in Ω×Ω, where Ω is the state space of the Markov chain, analysis is done on a smaller set SΩ×Ω. If the coefficient of contraction β is strictly less than one, no further analysis is needed in order to show rapid mixing. However, if β=1 then analysis (of the variance) is still required for all pairs in Ω×Ω. In this paper we present a new approach which shows rapid mixing in the case β=1 with a further condition which only needs to be checked for pairs in S, greatly simplifying the work involved. We also present a technique applicable when β=1 and our condition is not met.     

Extensions of Stochastic Optimization Results to Problems with System Failure Probability Functions

We derive an implementable algorithm for solving nonlinear stochastic optimization problems with failure probability constraints using sample average approximations. The paper extends prior results dealing with a failure probability expressed by a single measure to the case of failure probability expressed in terms of multiple performance measures. We also present a new formula for the failure probability gradient. A numerical example addressing the optimal design of a reinforced concrete highway bridge illustrates the algorithm. This work was sponsored by the Research Associateship Program, National Research Council. The authors are grateful for the valuable insight from Professors Alexander Shapiro, Evarist Gine, and Jon A. Wellner. The authors also thank Professor Tito Homem-de-Mello for commenting on an early draft of this paper.     

A markov chain sampler for contingency table exact inference

Summary  In the inference of contingency table, when the cell counts are not large enough for asymptotic approximation, conditioning exact method is used and often computationally impractical for large tables. Instead, various sampling methods can be used. Based on permutation, the Monte Carlo sampling may become again impractical for large tables. For this, existing the Markov chain method is to sample a few elements of the table at each iteration and is inefficient. Here we consider a Markov chain, in which a sub-table of user specified size is updated at each iteration, and it achieves high sampling efficiency. Some theoretical properties of the chain and its applications to some commonly used tables are discussed. As an illustration, this method is applied to the exact test of the Hardy-Weinberg equilibrium in the population genetics context.     

Automated Factor Slice Sampling

Markov chain Monte Carlo (MCMC) algorithms offer a very general approach for sampling from arbitrary distributions. However, designing and tuning MCMC algorithms for each new distribution can be challenging and time consuming. It is particularly difficult to create an efficient sampler when there is strong dependence among the variables in a multivariate distribution. We describe a two-pronged approach for constructing efficient, automated MCMC algorithms: (1) we propose the “factor slice sampler,” a generalization of the univariate slice sampler where we treat the selection of a coordinate basis (factors) as an additional tuning parameter, and (2) we develop an approach for automatically selecting tuning parameters to construct an efficient factor slice sampler. In addition to automating the factor slice sampler, our tuning approach also applies to the standard univariate slice samplers. We demonstrate the efficiency and general applicability of our automated MCMC algorithm with a number of illustrative examples. This article has online supplementary materials.     

Statistically Efficient Thinning of a Markov Chain Sampler

It is common to subsample Markov chain output to reduce the storage burden. Geyer shows that discarding k ? 1 out of every k observations will not improve statistical efficiency, as quantified through variance in a given computational budget. That observation is often taken to mean that thinning Markov chain Monte Carlo (MCMC) output cannot improve statistical efficiency. Here, we suppose that it costs one unit of time to advance a Markov chain and then θ > 0 units of time to compute a sampled quantity of interest. For a thinned process, that cost θ is incurred less often, so it can be advanced through more stages. Here, we provide examples to show that thinning will improve statistical efficiency if θ is large and the sample autocorrelations decay slowly enough. If the lag ? ? 1 autocorrelations of a scalar measurement satisfy ρ_? > ρ_{? + 1} > 0, then there is always a θ < ∞ at which thinning becomes more efficient for averages of that scalar. Many sample autocorrelation functions resemble first order AR(1) processes with ρ_? = ρ^|?| for some ? 1 < ρ < 1. For an AR(1) process, it is possible to compute the most efficient subsampling frequency k. The optimal k grows rapidly as ρ increases toward 1. The resulting efficiency gain depends primarily on θ, not ρ. Taking k = 1 (no thinning) is optimal when ρ ? 0. For ρ > 0, it is optimal if and only if θ ? (1 ? ρ)²/(2ρ). This efficiency gain never exceeds 1 + θ. This article also gives efficiency bounds for autocorrelations bounded between those of two AR(1) processes. Supplementary materials for this article are available online.     

Some characterizations of minimal Markov basis for sampling from discrete conditional distributions

In this paper we given some basic characterizations of minimal Markov basis for a connected Markov chain, which is used for performing exact tests in discrete exponential families given a sufficient statistic. We also give a necessary and sufficient condition for uniqueness of minimal Markov basis. A general algebraic algorithm for constructing a connected Markov chain was given by Diaconis and Sturmfels (1998,The Annals of Statistics,26, 363–397). Their algorithm is based on computing Gröbner basis for a certain ideal in a polynomial ring, which can be carried out by using available computer algebra packages. However structure and interpretation of Gröbner basis produced by the packages are sometimes not clear, due to the lack of symmetry and minimality in Gröbner basis computation. Our approach clarifies partially ordered structure of minimal Markov basis.     

Optimization algorithm with probabilistic estimation

In this paper, we present a stochastic optimization algorithm based on the idea of the gradient method which incorporates a new adaptive-precision technique. Because of this new technique, unlike recent methods, the proposed algorithm adaptively selects the precision without any need for prior knowledge on the speed of convergence of the generated sequence. With this new technique, the algorithm can avoid increasing the estimation precision unnecessarily, yet it retains its favorable convergence properties. In fact, it tries to maintain a nice balance between the requirements for computational accuracy and those for computational expediency. Furthermore, we present two types of convergence results delineating under what assumptions what kinds of convergence can be obtained for the proposed algorithm.The work reported here was supported in part by NSF Grant No. ECS-85-06249 and USAF Grant No. AFOSR-89-0518. The authors wish to thank the anonymous reviewers whose careful reading and criticism have helped them improve the paper considerably.