More Like this

1. Dispersion‐enhanced sequential batch sampling for adaptive contour estimation

   https://doi.org/10.1002/qre.3245  

   Che, Yiming; Müller, Juliane; Cheng, Changqing (February 2024, Quality and Reliability Engineering International)

   In computer simulation and optimal design, sequential batch sampling offers an appealing way to iteratively stipulate optimal sampling points based upon existing selections and efficiently construct surrogate modeling. Nonetheless, the issue of near duplicates poses tremendous quandary for sequential learning. It refers to the situation that selected critical points cluster together in each sampling batch, which are individually but not collectively informative towards the optimal design. Near duplicates severely diminish the computational efficiency as they barely contribute extra information towards update of the surrogate. To address this issue, we impose a dispersion criterion on concurrent selection of sampling points, which essentially forces a sparse distribution of critical points in each batch, and demonstrate the effectiveness of this approach in adaptive contour estimation. Specifically, we adopt Gaussian process surrogate to emulate the simulator, acquire variance reduction of the critical region from new sampling points as a dispersion criterion, and combine it with the modified expected improvement (EI) function for critical batch selection. The critical region here is the proximity of the contour of interest. This proposed approach is vindicated in numerical examples of a two‐dimensional four‐branch function, a four‐dimensional function with a disjoint contour of interest and a time‐delay dynamic system. 

   more » « less
2. SMART LINEAR ALGEBRAIC OPERATIONS FOR EFFICIENT GAUSSIAN MARKOV IMPROVEMENT ALGORITHM

   Li, X; Song, S (December 2020, Proceedings of the Winter Simulation Conference)

   Bae, K-H; Feng, B; Kim, S; Lazarova-Molnar, S; Zheng, Z; Roeder, T; Thiesing, R (Ed.)

   This paper studies computational improvement of the Gaussian Markov improvement algorithm (GMIA) whose underlying response surface model is a Gaussian Markov random field (GMRF). GMIA’s computational bottleneck lies in the sampling decision, which requires factorizing and inverting a sparse, but large precision matrix of the GMRF at every iteration. We propose smart GMIA (sGMIA) that performs expensive linear algebraic operations intermittently, while recursively updating the vectors and matrices necessary to make sampling decisions for several iterations in between. The latter iterations are much cheaper than the former at the beginning, but their costs increase as the recursion continues and ultimately surpass the cost of the former. sGMIA adaptively decides how long to continue the recursion by minimizing the average per-iteration cost. We perform a floating-point operation analysis to demonstrate the computational benefit of sGMIA. Experiment results show that sGMIA enjoys computational efficiency while achieving the same search effectiveness as GMIA. 

   more » « less
3. Projected Gaussian Markov Improvement Algorithm for High-Dimensional Discrete Optimization via Simulation

   https://doi.org/10.1145/3649463  

   Li, Xinru; Song, Eunhye (May 2024, ACM Transactions on Modeling and Computer Simulation)

   This article considers a discrete optimization via simulation (DOvS) problem defined on a graph embedded in the high-dimensional integer grid. Several DOvS algorithms that model the responses at the solutions as a realization of a Gaussian Markov random field (GMRF) have been proposed exploiting its inferential power and computational benefits. However, the computational cost of inference increases exponentially in dimension. We propose the projected Gaussian Markov improvement algorithm (pGMIA), which projects the solution space onto a lower-dimensional space creating the region-layer graph to reduce the cost of inference. Each node on the region-layer graph can be mapped to a set of solutions projected to the node; these solutions form a lower-dimensional solution-layer graph. We define the response at each region-layer node to be the average of the responses within the corresponding solution-layer graph. From this relation, we derive the region-layer GMRF to model the region-layer responses. The pGMIA alternates between the two layers to make a sampling decision at each iteration. It first selects a region-layer node based on the lower-resolution inference provided by the region-layer GMRF, then makes a sampling decision among the solutions within the solution-layer graph of the node based on the higher-resolution inference from the solution-layer GMRF. To solve even higher-dimensional problems (e.g., 100 dimensions), we also propose the pGMIA+: a multi-layer extension of the pGMIA. We show that both pGMIA and pGMIA+ converge to the optimum almost surely asymptotically and empirically demonstrate their competitiveness against state-of-the-art high-dimensional Bayesian optimization algorithms. 

   more » « less
4. Double coset Markov chains

   https://doi.org/10.1017/fms.2022.106  

   Diaconis, Persi; Ram, Arun; Simper, Mackenzie (January 2023, Forum of Mathematics, Sigma)

   Abstract Let G be a finite group. Let $H, K$ be subgroups of G and $$H \backslash G / K$$ the double coset space. If Q is a probability on G which is constant on conjugacy classes ( $$Q(s^{-1} t s) = Q(t)$$ ), then the random walk driven by Q on G projects to a Markov chain on $$H \backslash G /K$$ . This allows analysis of the lumped chain using the representation theory of G . Examples include coagulation-fragmentation processes and natural Markov chains on contingency tables. Our main example projects the random transvections walk on $$GL_n(q)$$ onto a Markov chain on $$S_n$$ via the Bruhat decomposition. The chain on $$S_n$$ has a Mallows stationary distribution and interesting mixing time behavior. The projection illuminates the combinatorics of Gaussian elimination. Along the way, we give a representation of the sum of transvections in the Hecke algebra of double cosets, which describes the Markov chain as a mixture of Metropolis chains. Some extensions and examples of double coset Markov chains with G a compact group are discussed. 

   more » « less
5. Provable Policy Gradient Methods for Average-Reward Markov Potential Games

   Cheng, Min; Zhou, Ruida; Kumar, P R; Tian, Chao (May 2024, Proceedings of the 27th International Conference on Artificial Intelligence and Statistics (AISTATS) 2024)

   We study Markov potential games under the infinite horizon average reward criterion. Most previous studies have been for discounted rewards. We prove that both algorithms based on independent policy gradient and independent natural policy gradient converge globally to a Nash equilibrium for the average reward criterion. To set the stage for gradient-based methods, we first establish that the average reward is a smooth function of policies and provide sensitivity bounds for the differential value functions, under certain conditions on ergodicity and the second largest eigenvalue of the underlying Markov decision process (MDP). We prove that three algorithms, policy gradient, proximal-Q, and natural policy gradient (NPG), converge to an ϵ-Nash equilibrium with time complexity O(1ϵ2), given a gradient/differential Q function oracle. When policy gradients have to be estimated, we propose an algorithm with ~O(1mins,aπ(a|s)δ) sample complexity to achieve δ approximation error w.r.t~the ℓ2 norm. Equipped with the estimator, we derive the first sample complexity analysis for a policy gradient ascent algorithm, featuring a sample complexity of ~O(1/ϵ5). Simulation studies are presented. 

   more » « less