Sample average approximation with heavier tails II: localization in stochastic convex optimization and persistence results for the Lasso

Abstract

``Localization'' has proven to be a valuable tool in the Statistical Learning literature as it allows sharp risk bounds in terms of the problem geometry. Localized bounds seem to be much less exploited in the Stochastic Optimization literature. In addition, there is an obvious interest in both communities in obtaining risk bounds that require weak moment assumptions or ``heavier-tails''. In this work we use a localization toolbox to derive risk bounds in two specific applications. The first is in portfolio risk minimization with conditional value-at-risk constraints. We consider a setting where, among all assets with high returns, there is a portion of dimension $g$, unknown to the investor, that has significant less risk than the other remaining portion. Our rates for the SAA problem show that ``risk inflation'', caused by a multiplicative factor, affects the statistical rate only via a term proportional to $g$. As the ``normalized risk'' increases, the contribution in the rate from the extrinsic dimension diminishes while the dependence on $g$ is kept fixed. Localization is a key tool to show this property. As a second application of our localization toolbox, we obtain sharp oracle inequalities for least-squares estimators with a Lasso-type constraint under weak moment assumptions. One main consequence of these inequalities is to obtain \emph{persistence}, as posed by Greenshtein and Ritov, with covariates having heavier tails. This gives improvements in prior work of Bartlett, Mendelson and Neeman.

arXiv commentAccepted in Mathematical Programming

References in corpus (14)

• Simultaneous analysis of Lasso and Dantzig selector
• Lasso-type recovery of sparse representations for high-dimensional data
• High-dimensional generalized linear models and the lasso
• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Local Rademacher complexities
• Sparsity oracle inequalities for the Lasso
• Aggregation for Gaussian regression
• The Dantzig selector and sparsity oracle inequalities
• Sup-norm convergence rate and sign concentration property of Lasso and Dantzig estimators
• Best subset selection, persistence in high-dimensional statistical learning and optimization under $l_1$ constraint
• The lower tail of random quadratic forms, with applications to ordinary least squares and restricted eigenvalue properties
• Sparse recovery in convex hulls via entropy penalization
• Aggregation for Regression Learning
• General nonexact oracle inequalities for classes with a subexponential envelope