3rd International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Control Variates as Screening Functions

Download611 downloads
  • @INPROCEEDINGS{10.4108/ICST.VALUETOOLS2008.4242,
        author={S. Kyriazopoulou-Panagiotopoulou and I. Kontoyiannis and S. P. Meyn},
        title={Control Variates as Screening Functions},
        proceedings={3rd International ICST Conference on Performance Evaluation Methodologies and Tools},
        publisher={ICST},
        proceedings_a={VALUETOOLS},
        year={2010},
        month={5},
        keywords={Estimation Monte Carlo simulation large deviations computable bounds measure concentration variance reduction Markov chain Monte Carlo (MCMC)},
        doi={10.4108/ICST.VALUETOOLS2008.4242}
    }
    
  • S. Kyriazopoulou-Panagiotopoulou
    I. Kontoyiannis
    S. P. Meyn
    Year: 2010
    Control Variates as Screening Functions
    VALUETOOLS
    ICST
    DOI: 10.4108/ICST.VALUETOOLS2008.4242
S. Kyriazopoulou-Panagiotopoulou1,*, I. Kontoyiannis1,*, S. P. Meyn2,*
  • 1: Department of Informatics, Athens U of Econ & Business, Athens 10434, Greece
  • 2: Dept. of ECE & CSL, U Illinois, Urbana-Champaign, Urbana, IL 61801, USA
*Contact email: sofiakp@stanford.edu, yiannis@aueb.gr, meyn@uiuc.edu

Abstract

Suppose that the mean μ = E[F(X)] of a given function F: ℝ → ℝ is to be estimated by the empirical average Sn: = 1/nΣi=1n F(Xi) of the values F(Xi), where X1,X2, ..., Xn are independent samples distributed like X. In cases when the mean v = E[U(X)] of a different function U: ℝ → ℝ is known, we introduce a sampling rule, called the "screened estimator," which states that we should only consider estimates that correspond to times n when the empirical average of the {U(Xi)} is sufficiently close to its known mean. Under the assumption that U dominates F in an appropriate sense, it is shown that the screened estimates admit exponential error bounds, even when F(X) is heavy-tailed. A geometric interpretation, in the spirit of Sanov's theorem, is given for this fact, and nonasymptotic, explicit exponential bounds for the screened estimates are derived. The mathematical tools used in the analysis consist, primarily, of large deviations techniques. A detailed Markov Chain Monte Carlo (MCMC) simulation example illustrates that, in certain MCMC scenarios, screening can be very effective in terms of variance reduction, even in cases where the standard technique of control variates fails.