Convergence Analysis of Stochastic Kriging-Assisted Simulation with Random Covariates

Cheng Li, Siyang Gao, Jianzhong Du

Introduction

In modern decision-making environments—ranging from personalized medicine to real-time supply chain management—decisions often depend on covariates. These are external input factors, such as a patient's specific biometrics or fluctuating market demands, that influence system performance but are not under the direct control of the decision-maker.

Traditionally, simulation-based decision-making follows an "online" approach: practitioners wait for covariate values to be revealed, then run simulations to identify the optimal design. However, high-fidelity simulations are often too computationally expensive for real-time applications. To address this, a new framework—simulation with covariates—shifts the heavy lifting offline. By running simulations across a distribution of possible covariate values beforehand, practitioners can build a metamodel (a predictive surrogate). When the actual covariate values are revealed online, the metamodel provides near-instantaneous predictions.

While practically efficient, this framework previously lacked a rigorous theoretical foundation regarding its accuracy. This paper provides the first comprehensive convergence analysis for Stochastic Kriging (SK) metamodels in this context, establishing the "speed limit" for how fast prediction errors diminish as offline simulation effort increases.

Methodology: Stochastic Kriging and RKHS

The study utilizes Stochastic Kriging (SK), a Gaussian Process regression variant tailored for stochastic simulations where observations are subject to inherent noise. The goal is to predict the system performance of a finite set of designs across a covariate space.

To derive convergence rates, the authors leverage Reproducing Kernel Hilbert Space (RKHS) theory and Mercer’s theorem. The convergence behavior is fundamentally tied to the decay of the eigenvalues of the covariance kernel, which represents the smoothness of the system's response. The paper categorizes kernels into three classes:

  1. Finite-rank kernels: Representing systems that can be described by a finite set of basis functions (e.g., polynomials).
  2. Exponentially decaying kernels: Representing highly smooth systems (e.g., Squared Exponential kernels).
  3. Polynomially decaying kernels: Representing rougher systems with varying degrees of differentiability (e.g., Matérn kernels).

Performance Metrics

The analysis focuses on two primary error measures to quantify the relationship between offline effort and online accuracy:

  • Maximal Integrated Mean Squared Error (IMSE): Quantifies the worst-case average prediction error for system performance across all designs.
  • Integrated Probability of False Selection (IPFS): Quantifies the likelihood of selecting a sub-optimal design based on the metamodel's predictions.

Theoretical Convergence Rates

The core contribution of this research is the establishment of concrete convergence rates ($R$) as the number of sampled covariate points ($m$) increases:

  • Finite-rank: $R \approx 1/m$.
  • Exponentially decaying: $R \approx (\log m)^d / m$, where $d$ is the dimension of the covariate.
  • Polynomially decaying: $R \approx m^{-2\nu / (2\nu + d)}$, where $\nu$ represents the smoothness parameter.

A significant insight from this analysis is that selection is often easier than estimation. The IPFS can converge at an exponential rate even when the IMSE (estimation error) only converges at a polynomial rate. This is encouraging for optimization-focused tasks where identifying the best design is more critical than knowing the exact performance value.

Numerical Validation

The theoretical rates were validated using three distinct benchmarks:

  • De Jong’s Function: A smooth parabolic surface used to test basic estimation.
  • Griewank’s Function: A complex, oscillatory surface that serves as a stress test for the metamodel under high non-linearity.
  • M/M/1 Queue Model: A classic operations research problem where arrival rates serve as the covariate.

The experiments confirmed that for a fixed simulation budget, it is generally more effective to sample more distinct covariate points ($m$) with fewer replications ($n$) per point, rather than focusing on high-precision samples at fewer locations. This "spreads the net" wider to better capture the response surface.

Conclusion and Future Directions

This work provides the necessary theoretical guarantees for using SK-assisted simulation in real-time decision-making. However, several avenues for future research remain. Currently, the model treats system designs as independent; incorporating spatial correlations between continuous designs could further accelerate convergence. Additionally, while this study focuses on static sampling, exploring the convergence of adaptive sampling strategies—which prioritize regions of high uncertainty—remains a promising frontier. Finally, addressing the $O(m^3)$ computational complexity of SK will be essential for scaling this framework to massive datasets.

Summary updated

Abstract

We consider performing simulation experiments in the presence of covariates. Here, covariates refer to some input information other than system designs to the simulation model that can also affect the system performance. To make decisions, decision makers need to know the covariate values of the problem. Traditionally in simulation-based decision making, simulation samples are collected after the covariate values are known; in contrast, as a new framework, simulation with covariates starts the simulation before the covariate values are revealed, and collects samples on covariate values that might appear later. Then, when the covariate values are revealed, the collected simulation samples are directly used to predict the desired results. This framework significantly reduces the decision time compared to the traditional way of simulation. In this paper, we follow this framework and suppose there are a finite number of system designs. We adopt the metamodel of stochastic kriging (SK) and use it to predict the system performance of each design and the best design. The goal is to study how fast the prediction errors diminish with the number of covariate points sampled. This is a fundamental problem in simulation with covariates and helps quantify the relationship between the offline simulation efforts and the online prediction accuracy. Particularly, we adopt measures of the maximal integrated mean squared error (IMSE) and integrated probability of false selection (IPFS) for assessing errors of the system performance and the best design predictions. Then, we establish convergence rates for the two measures under mild conditions. Last, these convergence behaviors are illustrated numerically using test examples.
BibTeX
@article{li2024convergence,
  author = {Cheng Li and Siyang Gao and Jianzhong Du},
  title = {{Convergence Analysis of Stochastic Kriging-Assisted Simulation with Random Covariates}},
  journal = {INFORMS Journal on Computing},
  year = {2024},
  url = {https://openreview.net/forum?id=xFNXQp4TeR},
}
Figure