Optimal randomized multilevel Monte Carlo for repeatedly nested expectations

TY - JOUR

T1 - Optimal randomized multilevel Monte Carlo for repeatedly nested expectations

AU - Syed, Yasa

AU - Wang, Guanyang

N1 - Publisher Copyright: © 2023 Proceedings of Machine Learning Research. All rights reserved.

PY - 2023

Y1 - 2023

N2 - The estimation of repeatedly nested expectations is a challenging task that arises in many real-world systems. However, existing methods generally suffer from high computational costs when the number of nestings becomes large. Fix any non-negative integer D for the total number of nestings. Standard Monte Carlo methods typically cost at least O(ε−(2+D)) and sometimes O(ε−2(1+D)) to obtain an estimator up to εerror. More advanced methods, such as multilevel Monte Carlo, currently only exist for D = 1. In this paper, we propose a novel Monte Carlo estimator called READ, which stands for “Recursive Estimator for Arbitrary Depth.” Our estimator has an optimal computational cost of O(ε−2) for every fixed D under suitable assumptions, and a nearly optimal computational cost of O(ε−2(1+δ)) for any 0 < δ < 12 under much more general assumptions. Our estimator is also unbiased, which makes it easy to parallelize. The key ingredients in our construction are an observation of the problem's recursive structure and the recursive use of the randomized multilevel Monte Carlo method.

AB - The estimation of repeatedly nested expectations is a challenging task that arises in many real-world systems. However, existing methods generally suffer from high computational costs when the number of nestings becomes large. Fix any non-negative integer D for the total number of nestings. Standard Monte Carlo methods typically cost at least O(ε−(2+D)) and sometimes O(ε−2(1+D)) to obtain an estimator up to εerror. More advanced methods, such as multilevel Monte Carlo, currently only exist for D = 1. In this paper, we propose a novel Monte Carlo estimator called READ, which stands for “Recursive Estimator for Arbitrary Depth.” Our estimator has an optimal computational cost of O(ε−2) for every fixed D under suitable assumptions, and a nearly optimal computational cost of O(ε−2(1+δ)) for any 0 < δ < 12 under much more general assumptions. Our estimator is also unbiased, which makes it easy to parallelize. The key ingredients in our construction are an observation of the problem's recursive structure and the recursive use of the randomized multilevel Monte Carlo method.

UR - http://www.scopus.com/inward/record.url?scp=85174389500&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85174389500&partnerID=8YFLogxK

M3 - Conference article

SN - 2640-3498

VL - 202

SP - 33343

EP - 33364

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

T2 - 40th International Conference on Machine Learning, ICML 2023

Y2 - 23 July 2023 through 29 July 2023

ER -