Adaptive importance sampling via minimization of estimators of cross-entropy, mean square, and inefficiency constant

Abstract

The inefficiency of using an unbiased estimator in a Monte Carlo procedure can be quantified using an inefficiency constant, equal to the product of the variance of the estimator and its mean computational cost. We develop methods for obtaining the parameters of the importance sampling (IS) change of measure via single- and multi-stage minimization of well-known estimators of cross- entropy and the mean square of the IS estimator, as well as of new estimators of such a mean square and inefficiency constant. We prove the convergence and asymptotic properties of the minimization results in our methods. We show that if a zero-variance IS parameter exists, then, under appropriate assumptions, minimization results of the new estimators converge to such a parameter at a faster rate than such results of the well-known estimators, and a positive definite asymptotic covariance matrix of the minimization results of the cross-entropy estimators is four times such a matrix for the well-known mean square estimators. We introduce criteria for comparing the asymptotic efficiency of stochastic optimization methods, applicable to the minimization methods of estimators considered in this work. In our numerical experiments for computing expectations of functionals of an Euler scheme, the minimization of the new estimators led to the lowest inefficiency constants and variances of the IS estimators, followed by the minimization of the well-known mean square estimators, and the cross-entropy ones.

Die Ineffizienz der Verwendung einer erwartungstreuen Schätzfunktion in einer Monte-Carlo-Methode (MC-Methode) kann durch eine Ineffizienz-Konstante quantifiziert werden, die gleich dem Produkt der Varianz der Schätzfunktion und ihrem mittleren Rechenaufwand ist. In dieser Arbeit entwickeln wir Verfahren, um gute Parameter für einen Maßwechsel beim adaptiven Importance Sampling (IS) zu berechnen durch ein- und mehrstufigen Minimierung der bekannten Schätzer der Kreuzentropie (engl: cross entropy) und des mittleren Quadrats der IS-Schätzfunktion, sowie neuartiger Schätzer des mittleren Quadrats und der Ineffizienz-Konstante. Wir beweisen dass die Ergebnisse unseren Verfahren geeignete starke Konvergenz und asymptotischen Eigenschaften genießen. Wir zeigen, dass, wenn ein Null-Varianz-IS-Parameter existiert, die Minimierungsverfahren für die neuen Schätzer unter geeigneten Annahmen schneller gegen diesen Parameter konvergieren als für die bekannten Schätzer und die positiv definite asymptotische Kovarianzmatrix des minimierten Kreuzentropie-Schätzer ist das Vierfache der Kovarianzmatrix im Falle des bekannten Schätzers mittleres Quadrats. Wir stellen Kriterien für den Vergleich der asymptotischen Effizienz der stochastischen Optimierungsverfahren, anwendbar auf die Minimierung Methoden der Schätzer die in dieser Arbeit betrachtet sind. In unseren numerischen Experimenten zur Berechnung von Erwartungswerten von Funktionalen eines Euler-diskretisierten Diffusionsprozesses führte die Minimierung der neuen Schätzer zu den niedrigsten Ineffizienz-Konstanten und Varianzen, gefolgt von den bekannten Schätzfunktionen des mittleren Quadrats und der Kreuzentropie.