Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization

2022-06-04 · Takashi Goda, Wataru Kitade

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.

📄 PDF Abstract BibTeX arXiv:2206.01991

Code (0)

등록된 구현이 없습니다.

Tasks

Stochastic Optimization

Unbiased Gradient Estimation for Variational Auto-Encoders using Coupled Markov Chains

2020-10-05 · Francisco J. R. Ruiz, Michalis K. Titsias, Taylan Cemgil, Arnaud Doucet

The variational auto-encoder (VAE) is a deep latent variable model that has two neural networks in an autoencoder-like architecture; one of them parameterizes the model's likelihood. Fitting its parameters via maximum li…

Rao-Blackwellized Stochastic Gradients for Discrete Distributions

2018-10-10 · Runjing Liu, Jeffrey Regier, Nilesh Tripuraneni, Michael. I. Jordan 외

We wish to compute the gradient of an expectation over a finite or countably infinite sample space having $K \leq \infty$ categories. When $K$ is indeed infinite, or finite but very large, the relevant summation is intra…

General Classification

Unbiased and Biased Variance-Reduced Forward-Reflected-Backward Splitting Methods for Stochastic Composite Inclusions

2026-03-16 · Quoc Tran-Dinh, Nghia Nguyen-Trung arxiv

This paper develops new variance-reduction techniques for the forward-reflected-backward splitting (FRBS) method to solve a class of possibly nonmonotone stochastic composite inclusions. Unlike unbiased estimators such a…

Reinforcement Learning

A Better Baseline for Second Order Gradient Estimation in Stochastic Computation Graphs

2018-09-27 · Jingkai Mao, Jakob Foerster, Tim Rocktäschel, Gregory Farquhar 외

Motivated by the need for higher order gradients in multi-agent reinforcement learning and meta-learning, this paper studies the construction of baselines for second order Monte Carlo gradient estimators in order to redu…

Meta-Learning Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning+1

On Advantage Estimates for Max@K Policy Gradients

2026-06-04 · Shota Takashiro, Soichiro Nishimori, Paavo Parmas, Yongmin Kim 외 arxiv

Reinforcement learning with verifiable rewards is widely used for post-training reasoning models, but sparse outcome rewards make exploration difficult. A complementary approach is to optimize inference-time objectives s…