On Monte-Carlo methods in convex stochastic optimization

Daniel Bartl and Shahar Mendelson

Papers from arXiv.org

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.

Date: 2021-01, Revised 2022-01
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Published in Annals of Applied Probability, 2022+

Downloads: (external link)
http://arxiv.org/pdf/2101.07794 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2101.07794

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().