Title: Cross-validation for extreme value analysis
Authors: Anne Sabourin - MAP5, UMR 8145, Universite Paris-Cite / formerly at Télécom Paris (France) [presenting]
Patrice Bertail - university of Paris-Ouest-Nanterre-La Defense (France)
Anass Aghbalou - LTCI - Telecom Paris- Institut polytechnique de Paris (France)
Francois Portier - Telecom ParisTech (France)
Abstract: A non-asymptotic study is conducted for the Cross Validation (CV) estimate of the generalization risk for learning algorithms dedicated to extreme regions of the covariates space. In this Extreme Value Analysis context, the risk function measures the algorithm's error given that the norm of the input exceeds a high quantile. The main challenge within this framework is the negligible size of the extreme training sample with respect to the full sample size and the necessity to re-scale the risk function by a probability tending to zero. We open the road to a finite sample understanding of CV for extreme values by establishing two new results: an exponential probability bound on the K-fold CV error and a polynomial probability bound on the leave-p-out CV. Our bounds are sharp in the sense that they match state-of-the-art guarantees for standard CV estimates while extending them to encompass a conditioning event of small probability. We illustrate the significance of our results regarding high dimensional classification in extreme regions via a Lasso-type logistic regression algorithm. The tightness of our bounds is investigated in numerical experiments.