Debiasing Conditional Stochastic Optimization

Abstract

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.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

He and Kasiviswanathan. "Debiasing Conditional Stochastic Optimization." Neural Information Processing Systems, 2023.

Markdown

[He and Kasiviswanathan. "Debiasing Conditional Stochastic Optimization." Neural Information Processing Systems, 2023.](https://mlanthology.org/neurips/2023/he2023neurips-debiasing/)

BibTeX

@inproceedings{he2023neurips-debiasing,
  title     = {{Debiasing Conditional Stochastic Optimization}},
  author    = {He, Lie and Kasiviswanathan, Shiva P.},
  booktitle = {Neural Information Processing Systems},
  year      = {2023},
  url       = {https://mlanthology.org/neurips/2023/he2023neurips-debiasing/}
}