# Unbiased Simulation for Optimizing Stochastic Function Compositions

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2017.

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

- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization](https://mlsanity.com/paper/2206.01991/) (2022)
- [Multi-level Monte-Carlo Gradient Methods for Stochastic Optimization with Biased Oracles](https://mlsanity.com/paper/2408.11084/) (2024)
- [Doubly Robust Instance-Reweighted Adversarial Training](https://mlsanity.com/paper/2308.00311/) (2023)
- [Riemannian Stochastic Gradient Method for Nested Composition Optimization](https://mlsanity.com/paper/2207.09350/) (2022)
- [Multistage Conditional Compositional Optimization](https://mlsanity.com/paper/2604.14075/) (2026)
- [Scalable Cox Regression via Grouped Risk Sets and Sharper LogSumExp Rates](https://mlsanity.com/paper/2609.40120/) (2026)

## Abstract (arXiv)

In this paper, we introduce an unbiased gradient simulation algorithms for solving convex optimization problem with stochastic function compositions. We show that the unbiased gradient generated from the algorithm has finite variance and finite expected computation cost. We then combined the unbiased gradient simulation with two variance reduced algorithms (namely SVRG and SCSG) and showed that the proposed optimization algorithms based on unbiased gradient simulations exhibit satisfactory convergence properties. Specifically, in the SVRG case, the algorithm with simulated gradient can be shown to converge linearly to optima in expectation and almost surely under strong convexity. Finally, for the numerical experiment,we applied the algorithms to two important cases of stochastic function compositions optimization: maximizing the Cox's partial likelihood model and training conditional random fields.