IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2307.04676.html
   My bibliography  Save this paper

Importance Sampling for Minimization of Tail Risks: A Tutorial

Author

Listed:
  • Anand Deo
  • Karthyek Murthy

Abstract

This paper provides an introductory overview of how one may employ importance sampling effectively as a tool for solving stochastic optimization formulations incorporating tail risk measures such as Conditional Value-at-Risk. Approximating the tail risk measure by its sample average approximation, while appealing due to its simplicity and universality in use, requires a large number of samples to be able to arrive at risk-minimizing decisions with high confidence. This is primarily due to the rarity with which the relevant tail events get observed in the samples. In simulation, Importance Sampling is among the most prominent methods for substantially reducing the sample requirement while estimating probabilities of rare events. Can importance sampling be used for optimization as well? If so, what are the ingredients required for making importance sampling an effective tool for optimization formulations involving rare events? This tutorial aims to provide an introductory overview of the two key ingredients in this regard, namely, (i) how one may arrive at an importance sampling change of measure prescription at every decision, and (ii) the prominent techniques available for integrating such a prescription within a solution paradigm for stochastic optimization formulations.

Suggested Citation

  • Anand Deo & Karthyek Murthy, 2023. "Importance Sampling for Minimization of Tail Risks: A Tutorial," Papers 2307.04676, arXiv.org.
    • Handle: RePEc:arx:papers:2307.04676
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2307.04676
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Raghu Pasupathy, 2010. "On Choosing Parameters in Retrospective-Approximation Algorithms for Stochastic Root Finding and Simulation Optimization," Operations Research, INFORMS, vol. 58(4-part-1), pages 889-901, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    2. Stefania Bellavia & Nataša Krejić & Benedetta Morini, 2020. "Inexact restoration with subsampled trust-region methods for finite-sum minimization," Computational Optimization and Applications, Springer, vol. 76(3), pages 701-736, July.
    3. Hu, Shaolong & Dong, Zhijie Sasha & Dai, Rui, 2024. "A machine learning based sample average approximation for supplier selection with option contract in humanitarian relief," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 186(C).
    4. Wang, Honggang, 2012. "Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation," European Journal of Operational Research, Elsevier, vol. 217(1), pages 141-148.
    5. Nataša Krejić & Nataša Krklec Jerinkić, 2019. "Spectral projected gradient method for stochastic optimization," Journal of Global Optimization, Springer, vol. 73(1), pages 59-81, January.
    6. J. O. Royset & E. Y. Pee, 2012. "Rate of Convergence Analysis of Discretization and Smoothing Algorithms for Semiinfinite Minimax Problems," Journal of Optimization Theory and Applications, Springer, vol. 155(3), pages 855-882, December.
    7. Johannes Royset, 2013. "On sample size control in sample average approximations for solving smooth stochastic programs," Computational Optimization and Applications, Springer, vol. 55(2), pages 265-309, June.
    8. Johannes O. Royset & Roger J-B Wets, 2016. "Optimality Functions and Lopsided Convergence," Journal of Optimization Theory and Applications, Springer, vol. 169(3), pages 965-983, June.
    9. Suvrajeet Sen & Yifan Liu, 2016. "Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction," Operations Research, INFORMS, vol. 64(6), pages 1422-1437, December.
    10. Honggang Wang, 2017. "Subspace dynamic‐simplex linear interpolation search for mixed‐integer black‐box optimization problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(4), pages 305-322, June.
    11. Kyle Cooper & Susan R. Hunter & Kalyani Nagaraj, 2020. "Biobjective Simulation Optimization on Integer Lattices Using the Epsilon-Constraint Method in a Retrospective Approximation Framework," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1080-1100, October.
    12. Tsai, Shing Chih & Zheng, Ya-Xin, 2013. "A simulation optimization approach for a two-echelon inventory system with service level constraints," European Journal of Operational Research, Elsevier, vol. 229(2), pages 364-374.
    13. Hu, Shaolong & Hu, Qingmi & Tao, Sha & Dong, Zhijie Sasha, 2023. "A multi-stage stochastic programming approach for pre-positioning of relief supplies considering returns," Socio-Economic Planning Sciences, Elsevier, vol. 88(C).
    14. Bismark Singh & David P. Morton & Surya Santoso, 2018. "An adaptive model with joint chance constraints for a hybrid wind-conventional generator system," Computational Management Science, Springer, vol. 15(3), pages 563-582, October.
    15. Xiang He & Xiqun (Michael) Chen & Chenfeng Xiong & Zheng Zhu & Lei Zhang, 2017. "Optimal Time-Varying Pricing for Toll Roads Under Multiple Objectives: A Simulation-Based Optimization Approach," Transportation Science, INFORMS, vol. 51(2), pages 412-426, May.
    16. Devang Sinha & Siddhartha P. Chakrabarty, 2024. "Multilevel Monte Carlo in Sample Average Approximation: Convergence, Complexity and Application," Papers 2407.18504, arXiv.org.
    17. Johannes O. Royset & Roberto Szechtman, 2013. "Optimal Budget Allocation for Sample Average Approximation," Operations Research, INFORMS, vol. 61(3), pages 762-776, June.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2307.04676. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.