# Debiasing Conditional Stochastic Optimization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 42 references that are in the map.
- First posted on arXiv 20 Apr 2023.

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

- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [Kernel Instrumental Variable Regression](https://mlsanity.com/paper/1906.00232/) (2019)
- [Reinforcement Learning via Fenchel-Rockafellar Duality](https://mlsanity.com/paper/2001.01866/) (2020)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [Accelerating Stochastic Composition Optimization](https://mlsanity.com/paper/1607.07329/) (2016)
- [Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations](https://mlsanity.com/paper/2006.13476/) (2020)
- [Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergence](https://mlsanity.com/paper/2104.08736/) (2021)
- [Multi-Level Composite Stochastic Optimization via Nested Variance Reduction](https://mlsanity.com/paper/1908.11468/) (2019)
- [Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applications](https://mlsanity.com/paper/2202.12396/) (2022)
- [Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimization](https://mlsanity.com/paper/1905.11957/) (2019)
- [Near-optimal method for highly smooth convex optimization](https://mlsanity.com/paper/1812.08026/) (2018)
- [Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization](https://mlsanity.com/paper/2207.08540/) (2022)
- [Momentum Accelerates the Convergence of Stochastic AUPRC Maximization](https://mlsanity.com/paper/2107.01173/) (2021)
- [Learning with Group Invariant Features: A Kernel Perspective](https://mlsanity.com/paper/1506.02544/) (2015)
- [Fast Incremental Method for Nonconvex Optimization](https://mlsanity.com/paper/1603.06159/) (2016)
- [Constructing unbiased gradient estimators with finite variance for conditional stochastic optimization](https://mlsanity.com/paper/2206.01991/) (2022)
- [Bias Correction with Jackknife, Bootstrap, and Taylor Series](https://mlsanity.com/paper/1709.06183/) (2017)

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

- [Contextual Stochastic Bilevel Optimization](https://mlsanity.com/paper/2310.18535/) (2023)
- [Advantage Shaping as Surrogate Reward Maximization: Unifying Pass@K Policy Gradients](https://mlsanity.com/paper/2510.23049/) (2025)
- [A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization](https://mlsanity.com/paper/2405.10815/) (2024)
- [Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling](https://mlsanity.com/paper/2411.05868/) (2024)
- [Quantum speedup of non-linear Monte Carlo problems](https://mlsanity.com/paper/2502.05094/) (2025)
- [Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimization](https://mlsanity.com/paper/2603.13048/) (2026)

## Abstract (arXiv)

In this paper, we study the conditional stochastic optimization (CSO) problem which covers a variety of applications including portfolio selection, reinforcement learning, robust learning, causal inference, etc. The sample-averaged gradient of the CSO objective is biased due to its nested structure, and therefore requires a high sample complexity for convergence. We introduce a general stochastic extrapolation technique that effectively reduces the bias. We show that for nonconvex smooth objectives, combining this extrapolation with variance reduction techniques can achieve a significantly better sample complexity than the existing bounds. Additionally, we develop new algorithms for the finite-sum variant of the CSO problem that also significantly improve upon existing results. Finally, we believe that our debiasing technique has the potential to be a useful tool for addressing similar challenges in other stochastic optimization problems.