Recursive rounding of sample size estimation for multi-fidelity Monte Carlo

Abstract

In multifidelity Monte Carlo (MFMC), optimal sample allocations are typically derived from a continuous relaxation of a variance minimization problem, with integer solutions obtained through post hoc rounding. Such rounding procedures may fail to fully exploit the available cost budget, particularly under tight cost budgets or when model costs vary significantly. In this work, we reformulate the MFMC allocation problem as a variance-constrained cost minimization problem that is equivalent to the standard budget-constrained formulation at the continuous level. This reformulation admits a recursive structure that enables the construction of an integer allocation strategy based on Bellman's principle of optimality. Since the resulting MFMC allocation has a mathematical structure similar to the optimal multilevel Monte Carlo (MLMC) allocation, the proposed strategy naturally extends to MLMC. The resulting algorithm constructs integer-valued sample allocations that more closely follow the continuous variance--cost tradeoff while using the prescribed variance tolerance more efficiently. Numerical experiments demonstrate that the proposed approach satisfies the prescribed variance tolerance with less computational overhead than standard rounding strategies.