An official website of the United States government
Summary Sequential Monte Carlo algorithms are widely accepted as powerful computational tools for making inference with dynamical systems. A key step in sequential Monte Carlo is resampling, which plays the role of steering the algorithm towards the future dynamics. Several strategies have been used in practice, including multinomial resampling, residual resampling, optimal resampling, stratified resampling and optimal transport resampling. In one-dimensional cases, we show that optimal transport resampling is equivalent to stratified resampling on the sorted particles, and both strategies minimize the resampling variance as well as the expected squared energy distance between the original and resampled empirical distributions. For general $$d$$-dimensional cases, we show that if the particles are first sorted using the Hilbert curve, the variance of stratified resampling is $$O(m^{-(1+2/d)})$$, an improvement over the best previously known rate of $$O(m^{-(1+1/d)})$$, where $$m$$ is the number of resampled particles. We show that this improved rate is optimal for ordered stratified resampling schemes, as conjectured in Gerber et al. (2019). We also present an almost-sure bound on the Wasserstein distance between the original and Hilbert-curve-resampled empirical distributions. In light of these results, we show that for dimension $d>1$ the mean square error of sequential quasi-Monte Carlo with $$n$$ particles can be $$O(n^{-1-4/\{d(d+4)\}})$$ if Hilbert curve resampling is used and a specific low-discrepancy set is chosen. To our knowledge, this is the first known convergence rate lower than $$o(n^{-1})$$.
more »
« less
Emergence of pseudo-time during optimal Monte Carlo sampling and temporal aspects of symmetry breaking and restoration
We argue that one can associate a pseudo-time with sequences of configurations generated in the course of classical Monte Carlo simulations for a single-minimum bound state if the sampling is optimal. Hereby, the sampling rates can be, under special circumstances, calibrated against the relaxation rate and frequency of motion of an actual physical system. The latter possibility is linked to the optimal sampling regime being a universal crossover separating two distinct suboptimal sampling regimes analogous to the physical phenomena of diffusion and effusion, respectively. Bound states break symmetry; one may thus regard the pseudo-time as a quantity emerging together with the bound state. Conversely, when transport among distinct bound states takes place—thus restoring symmetry—a pseudo-time can no longer be defined. One can still quantify activation barriers if the latter barriers are smooth, but simulation becomes impractically slow and pertains to overdamped transport only. Specially designed Monte Carlo moves that bypass activation barriers—so as to accelerate sampling of the thermodynamics—amount to effusive transport and lead to severe under-sampling of transition-state configurations that separate distinct bound states while destroying the said universality. Implications of the present findings for simulations of glassy liquids are discussed.
more »
« less
- Award ID(s):
- 1956389
- PAR ID:
- 10403693
- Publisher / Repository:
- American Institute of Physics
- Date Published:
- Journal Name:
- The Journal of Chemical Physics
- Volume:
- 158
- Issue:
- 12
- ISSN:
- 0021-9606
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Sequential decision-making under uncertainty is present in many important problems. Two popular approaches for tackling such problems are reinforcement learning and online search (e.g., Monte Carlo tree search). While the former learns a policy by interacting with the environment (typically done before execution), the latter uses a generative model of the environment to sample promising action trajectories at decision time. Decision-making is particularly challenging in non-stationary environments, where the environment in which an agent operates can change over time. Both approaches have shortcomings in such settings -- on the one hand, policies learned before execution become stale when the environment changes and relearning takes both time and computational effort. Online search, on the other hand, can return sub-optimal actions when there are limitations on allowed runtime. In this paper, we introduce \textit{Policy-Augmented Monte Carlo tree search} (PA-MCTS), which combines action-value estimates from an out-of-date policy with an online search using an up-to-date model of the environment. We prove theoretical results showing conditions under which PA-MCTS selects the one-step optimal action and also bound the error accrued while following PA-MCTS as a policy. We compare and contrast our approach with AlphaZero, another hybrid planning approach, and Deep Q Learning on several OpenAI Gym environments. Through extensive experiments, we show that under non-stationary settings with limited time constraints, PA-MCTS outperforms these baselines.more » « less
-
A novel approach to computationally enhance the sampling of molecular crystal structures is proposed and tested. This method is based on the use of extended variables coupled to a Monte Carlo based crystal polymorph generator. Inspired by the established technique of quasi-random sampling of polymorphs using the rigid molecule constraint, this approach represents molecular clusters as extended variables within a thermal reservoir. Polymorph unit-cell variables are generated using pseudo-random sampling. Within this framework, a harmonic coupling between the extended variables and polymorph configurations is established. The extended variables remain fixed during the inner loop dedicated to polymorph sampling, enforcing a stepwise propagation of the extended variables to maintain system exploration. The final processing step results in a polymorph energy landscape, where the raw structures sampled to create the extended variable trajectory are re-optimized without the thermal coupling term. The foundational principles of this approach are described and its effectiveness using both a Metropolis Monte Carlo type algorithm and modifications that incorporate replica exchange is demonstrated. A comparison is provided with pseudo-random sampling of polymorphs for the molecule coumarin. The choice to test a design of this algorithm as relevant for enhanced sampling of crystal structures was due to the obvious relation between molecular structure variables and corresponding crystal polymorphs as representative of the inherent vapor to crystal transitions that exist in nature. Additionally, it is shown that the trajectories of extended variables can be harnessed to extract fluctuation properties that can lead to valuable insights. A novel thermodynamic variable is introduced: the free energy difference between ensembles ofZ′ = 1 andZ′ = 2 crystal polymorphs.more » « less
-
We present efficient algorithms for using selected configuration interaction (sCI) trial wave functions in phaseless auxiliary field quantum Monte Carlo (ph-AFQMC). These advances, geared toward optimizing computational performance for longer configuration interaction expansions, allow us to use up to a million configurations in the trial state for ph-AFQMC. In one example, we found the cost of ph-AFQMC per sample to increase only by a factor of about 3 for a calculation with 10 4 configurations compared to that with a single one, demonstrating the tiny computational overhead due to a longer expansion. This favorable scaling allows us to study the systematic convergence of the phaseless bias in auxiliary field quantum Monte Carlo calculations with an increasing number of configurations and provides a means to gauge the accuracy of ph-AFQMC with other trial states. We also show how the scalability issues of sCI trial states for large system sizes could be mitigated by restricting them to a moderately sized orbital active space and leveraging the near-cancellation of out of active space phaseless errors.more » « less
-
Abstract Monte Carlo simulations for photon transport are commonly used to predict the spectral response, including reflectance, absorptance, and transmittance in nanoparticle laden media, while the computational cost could be high. In this study, we demonstrate a general purpose fully connected neural network approach, trained with Monte Carlo simulations, to accurately predict the spectral response while dramatically accelerating the computational speed. Monte Carlo simulations are first used to generate a training set with a wide range of optical properties covering dielectrics, semiconductors, and metals. Each input is normalized, with the scattering and absorption coefficients normalized on a logarithmic scale to accelerate the training process and reduce error. A deep neural network with ReLU activation is trained on this dataset with the optical properties and medium thickness as the inputs, and diffuse reflectance, absorptance, and transmittance as the outputs. The neural network is validated on a validation set with randomized optical properties, as well as nanoparticle medium examples including barium sulfate, aluminum, and silicon. The error in the spectral response predictions is within 1% which is sufficient for many applications, while the speedup is 1–3 orders of magnitude. This machine learning accelerated approach can allow for high throughput screening, optimization, or real-time monitoring of nanoparticle media's spectral response.more » « less
