| Many inference and optimization tasks in machine learning can be solved bysampling approaches such as Markov Chain Monte Carlo (MCMC) and simulatedannealing. These methods can be slow if a single target density query requiresmany runs of a simulation (or a complete sweep of a training data set). Weintroduce a hierarchy of MCMC samplers that allow most steps to be taken inthe solution space using only a small sample of simulation runs (or trainingexamples). This is shown to accelerate learning in a policy searchoptimization task. |