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

On Monte-Carlo methods in convex stochastic optimization

Author

Listed:
  • Daniel Bartl
  • Shahar Mendelson

Abstract

We develop a novel procedure for estimating the optimizer of general convex stochastic optimization problems of the form $\min_{x\in\mathcal{X}} \mathbb{E}[F(x,\xi)]$, when the given data is a finite independent sample selected according to $\xi$. The procedure is based on a median-of-means tournament, and is the first procedure that exhibits the optimal statistical performance in heavy tailed situations: we recover the asymptotic rates dictated by the central limit theorem in a non-asymptotic manner once the sample size exceeds some explicitly computable threshold. Additionally, our results apply in the high-dimensional setup, as the threshold sample size exhibits the optimal dependence on the dimension (up to a logarithmic factor). The general setting allows us to recover recent results on multivariate mean estimation and linear regression in heavy-tailed situations and to prove the first sharp, non-asymptotic results for the portfolio optimization problem.

Suggested Citation

  • Daniel Bartl & Shahar Mendelson, 2021. "On Monte-Carlo methods in convex stochastic optimization," Papers 2101.07794, arXiv.org, revised Jan 2022.
  • Handle: RePEc:arx:papers:2101.07794
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Georg Pflug, 1999. "Stochastic programs and statistical data," Annals of Operations Research, Springer, vol. 85(0), pages 59-78, January.
    2. Huifu Xu & Dali Zhang, 2012. "Monte Carlo methods for mean-risk optimization and portfolio selection," Computational Management Science, Springer, vol. 9(1), pages 3-29, February.
    3. Sujin Kim & Raghu Pasupathy & Shane G. Henderson, 2015. "A Guide to Sample Average Approximation," International Series in Operations Research & Management Science, in: Michael C Fu (ed.), Handbook of Simulation Optimization, edition 127, chapter 0, pages 207-243, Springer.
    4. Daniel Bartl & Ludovic Tangpi, 2020. "Non-asymptotic convergence rates for the plug-in estimation of risk measures," Papers 2003.10479, arXiv.org, revised Oct 2022.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Härdle, Wolfgang & Klochkov, Yegor & Petukhina, Alla & Zhivotovskiy, Nikita, 2021. "Robustifying Markowitz," IRTG 1792 Discussion Papers 2021-018, Humboldt University of Berlin, International Research Training Group 1792 "High Dimensional Nonstationary Time Series".
    2. Petukhina, Alla & Klochkov, Yegor & Härdle, Wolfgang Karl & Zhivotovskiy, Nikita, 2024. "Robustifying Markowitz," Journal of Econometrics, Elsevier, vol. 239(2).
    3. Wolfgang Karl Hardle & Yegor Klochkov & Alla Petukhina & Nikita Zhivotovskiy, 2022. "Robustifying Markowitz," Papers 2212.13996, arXiv.org.

    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. Sereshti, Narges & Adulyasak, Yossiri & Jans, Raf, 2024. "Managing flexibility in stochastic multi-level lot sizing problem with service level constraints," Omega, Elsevier, vol. 122(C).
    2. Irawan, Chandra Ade & Jones, Dylan & Hofman, Peter S. & Zhang, Lina, 2023. "Integrated strategic energy mix and energy generation planning with multiple sustainability criteria and hierarchical stakeholders," European Journal of Operational Research, Elsevier, vol. 308(2), pages 864-883.
    3. David Bergman & Carlos Cardonha & Jason Imbrogno & Leonardo Lozano, 2023. "Optimizing the Expected Maximum of Two Linear Functions Defined on a Multivariate Gaussian Distribution," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 304-317, March.
    4. Bayliss, Christopher & Currie, Christine S.M. & Bennell, Julia A. & Martinez-Sykora, Antonio, 2021. "Queue-constrained packing: A vehicle ferry case study," European Journal of Operational Research, Elsevier, vol. 289(2), pages 727-741.
    5. Qi Fan & Jiaqiao Hu, 2018. "Surrogate-Based Promising Area Search for Lipschitz Continuous Simulation Optimization," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 677-693, November.
    6. Dmitry B. Rokhlin, 2021. "Relative utility bounds for empirically optimal portfolios," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 93(3), pages 437-462, June.
    7. Bernard G. Zweers & Sandjai Bhulai & Rob D. Mei, 2021. "Planning hinterland container transportation in congested deep-sea terminals," Flexible Services and Manufacturing Journal, Springer, vol. 33(3), pages 583-622, September.
    8. Eric Larsen & Sébastien Lachapelle & Yoshua Bengio & Emma Frejinger & Simon Lacoste-Julien & Andrea Lodi, 2022. "Predicting Tactical Solutions to Operational Planning Problems Under Imperfect Information," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 227-242, January.
    9. Kim, Sojung & Weber, Stefan, 2022. "Simulation methods for robust risk assessment and the distorted mix approach," European Journal of Operational Research, Elsevier, vol. 298(1), pages 380-398.
    10. Jyotirmoy Dalal & Halit Üster, 2018. "Combining Worst Case and Average Case Considerations in an Integrated Emergency Response Network Design Problem," Transportation Science, INFORMS, vol. 52(1), pages 171-188, January.
    11. MacLean, Leonard C. & Sanegre, Rafael & Zhao, Yonggan & Ziemba, William T., 2004. "Capital growth with security," Journal of Economic Dynamics and Control, Elsevier, vol. 28(5), pages 937-954, February.
    12. Karakaya, Sırma & Balcik, Burcu, 2024. "Developing a national pandemic vaccination calendar under supply uncertainty," Omega, Elsevier, vol. 124(C).
    13. Sojung Kim & Stefan Weber, 2020. "Simulation Methods for Robust Risk Assessment and the Distorted Mix Approach," Papers 2009.03653, arXiv.org, revised Jan 2022.
    14. Tadese, Mekonnen & Drapeau, Samuel, 2020. "Relative bound and asymptotic comparison of expectile with respect to expected shortfall," Insurance: Mathematics and Economics, Elsevier, vol. 93(C), pages 387-399.
    15. Xinyu Yao & Karmel S. Shehadeh & Rema Padman, 2024. "Multi-resource allocation and care sequence assignment in patient management: a stochastic programming approach," Health Care Management Science, Springer, vol. 27(3), pages 352-369, September.
    16. Yifei Sun & Usha Nandini Raghavan & Vikrant Vaze & Christopher S Hall & Patricia Doyle & Stacey Sullivan Richard & Christoph Wald, 2021. "Stochastic programming for outpatient scheduling with flexible inpatient exam accommodation," Health Care Management Science, Springer, vol. 24(3), pages 460-481, September.
    17. Daniel Bartl & Ludovic Tangpi, 2020. "Non-asymptotic convergence rates for the plug-in estimation of risk measures," Papers 2003.10479, arXiv.org, revised Oct 2022.
    18. Shehadeh, Karmel S. & Cohn, Amy E.M. & Epelman, Marina A., 2019. "Analysis of models for the Stochastic Outpatient Procedure Scheduling Problem," European Journal of Operational Research, Elsevier, vol. 279(3), pages 721-731.
    19. Dmitry B. Rokhlin, 2020. "Relative utility bounds for empirically optimal portfolios," Papers 2006.05204, arXiv.org.
    20. Backe, Stian & Ahang, Mohammadreza & Tomasgard, Asgeir, 2021. "Stable stochastic capacity expansion with variable renewables: Comparing moment matching and stratified scenario generation sampling," Applied Energy, Elsevier, vol. 302(C).

    More about this item

    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:2101.07794. 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.