mlsanityData to 7 Oct 2026

Debiasing Conditional Stochastic Optimization

arXiv 2304.10613 ↗First posted 20 Apr 2023cs.LG stat.MLcited by 6

Not on the map. Why?

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.

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

Builds on

26 of 42 references.

References · 26

  1. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,861
  2. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  3. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 401
  4. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  5. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  6. 2017SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradientcited by 218
  7. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  8. 2016Stochastic Variance Reduction for Nonconvex Optimizationcited by 143
  9. 2017Non-convex Optimization for Machine Learningcited by 132
  10. 2019Kernel Instrumental Variable Regressioncited by 118
  11. 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
  12. 2014Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functionscited by 93
14 more
  1. 2016Accelerating Stochastic Composition Optimizationcited by 46
  2. 2020Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learningcited by 46
  3. 2020Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitationscited by 39
  4. 2021Stochastic Optimization of Areas Under Precision-Recall Curves with Provable Convergencecited by 34
  5. 2019Multi-Level Composite Stochastic Optimization via Nested Variance Reductioncited by 28
  6. 2022Finite-Sum Coupled Compositional Stochastic Optimization: Theory and Applicationscited by 27
  7. 2019Sample Complexity of Sample Average Approximation for Conditional Stochastic Optimizationcited by 19
  8. 2018Near-optimal method for highly smooth convex optimizationcited by 16
  9. 2022Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimizationcited by 16
  10. 2021Momentum Accelerates the Convergence of Stochastic AUPRC Maximizationcited by 14
  11. 2015Learning with Group Invariant Features: A Kernel Perspectivecited by 13
  12. 2016Fast Incremental Method for Nonconvex Optimizationcited by 9
  13. 2022Constructing unbiased gradient estimators with finite variance for conditional stochastic optimizationcited by 6
  14. 2017Bias Correction with Jackknife, Bootstrap, and Taylor Seriescited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 2; 2026: 1.

6 papers.

  1. 2023Contextual Stochastic Bilevel Optimizationcited by 14
  2. 2025Advantage Shaping as Surrogate Reward Maximization: Unifying Pass@K Policy Gradientscited by 10
  3. 2024A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimizationcited by 3
  4. 2024Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Samplingcited by 1
  5. 2025Quantum speedup of non-linear Monte Carlo problemscited by 0
  6. 2026Convergence Rate of a Functional Learning Method for Contextual Stochastic Optimizationcited by 0