# Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization

arXiv: https://arxiv.org/abs/2206.01991 · HTML: https://mlsanity.com/paper/2206.01991/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 50 references that are in the map.
- First posted on arXiv 4 Jun 2022.

## Builds on (most cited first, 17 of 17)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Kernel Instrumental Variable Regression](https://mlsanity.com/paper/1906.00232/) (2019)
- [Deep Generalized Method of Moments for Instrumental Variable Analysis](https://mlsanity.com/paper/1905.12495/) (2019)
- [On Nesting Monte Carlo Estimators](https://mlsanity.com/paper/1709.06181/) (2017)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization](https://mlsanity.com/paper/1905.11957/) (2019)
- [Unbiased MLMC stochastic gradient-based optimization of Bayesian experimental designs](https://mlsanity.com/paper/2005.08414/) (2020)
- [Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applications](https://mlsanity.com/paper/1904.09929/) (2019)
- [Multilevel Monte Carlo estimation of expected information gains](https://mlsanity.com/paper/1811.07546/) (2018)
- [Unbiased Simulation for Optimizing Stochastic Function Compositions](https://mlsanity.com/paper/1711.07564/) (2017)
- [Unbiased Multilevel Monte Carlo methods for intractable distributions: MLMC meets MCMC](https://mlsanity.com/paper/2204.04808/) (2022)
- [Unbiased Estimation of the Gradient of the Log-Likelihood in Inverse Problems](https://mlsanity.com/paper/2003.04896/) (2020)
- [Computing the variance of a conditional expectation via non-nested Monte Carlo](https://mlsanity.com/paper/1605.05454/) (2016)
- [Unbiased Estimation of the Gradient of the Log-Likelihood for a Class of Continuous-Time State-Space Models](https://mlsanity.com/paper/2105.11522/) (2021)

## Built on by (most cited first, 6 of 6)

- [Contextual Stochastic Bilevel Optimization](https://mlsanity.com/paper/2310.18535/) (2023)
- [Debiasing Conditional Stochastic Optimization](https://mlsanity.com/paper/2304.10613/) (2023)
- [A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization](https://mlsanity.com/paper/2405.10815/) (2024)
- [Deep Learning for Markov Chains: Lyapunov Functions, Poisson's Equation, and Stationary Distributions](https://mlsanity.com/paper/2508.16737/) (2025)
- [T-SKM-Net: Trainable Neural Network Framework for Linear Constraint Satisfaction via Sampling Kaczmarz-Motzkin Method](https://mlsanity.com/paper/2512.10461/) (2025)
- [Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization](https://mlsanity.com/paper/2603.13048/) (2026)

## Abstract (arXiv)

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.