Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization

Abstract

We study stochastic gradient descent for solving conditional stochastic optimization problems, in which an objective to be minimized is given by a parametric nested expectation with an outer expectation taken with respect to one random variable and an inner conditional expectation with respect to the other random variable. The gradient of such a parametric nested expectation is again expressed as a nested expectation, which makes it hard for the standard nested Monte Carlo estimator to be unbiased. In this paper, we show under some conditions that a multilevel Monte Carlo gradient estimator is unbiased and has finite variance and finite expected computational cost, so that the standard theory from stochastic optimization for a parametric (non-nested) expectation directly applies. We also discuss a special case for which yet another unbiased gradient estimator with finite variance and cost can be constructed.

arXiv commentminor revision, 24 pages, 4 figures

References in corpus (12)

• Adam: A Method for Stochastic Optimization
• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• On the Convergence of Adam and Beyond
• Antithetic multilevel Monte Carlo estimation for multi-dimensional SDEs without Lévy area simulation
• Decision-making under uncertainty: using MLMC for efficient estimation of EVPPI
• Computing the variance of a conditional expectation via non-nested Monte Carlo
• Multilevel Monte Carlo estimation of expected information gains
• Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization
• Unbiased MLMC stochastic gradient-based optimization of Bayesian experimental designs
• Unbiased Simulation for Optimizing Stochastic Function Compositions
• Multilevel Monte Carlo estimation of the expected value of sample information
• Unbiased Multilevel Monte Carlo methods for intractable distributions: MLMC meets MCMC