ON MONTE-CARLO METHODS IN CONVEX STOCHASTIC OPTIMIZATION

• 成果类型: Article
• 署名作者: Bartl, Daniel; Mendelson, Shahar
• 署名单位: University of Vienna; Australian National University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/22-AAP1781
• 发表日期: 2022
• 页码: 3146-3198
• 关键词: mean estimation; bounds; distributions; PROGRAMS; matrices

摘要

We develop a novel procedure for estimating the optimizer of general convex stochastic optimization problems of the form min(x is an element of chi) 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 nonasymptotic 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, nonasymptotic results for the portfolio optimization problem.