Review for NeurIPS paper: Regression with reject option and application to kNN

Summary and Contributions: This paper consider a regression with reject option problem, where one may abstain from predicting at some "hard" instances, with an emphasis on the case where the rejection (abstention) rate is prescribed. The first contribution is a characterization of the optimal prediction rule (knowing the true distribution of the data) given the rejection rate epsilon, which is obtained by predicting using the regression function, and abstaining when the conditional variance at the input point exceeds its (1-epsilon)-quantile. (This is done by first considering a variant where rejection is associated to a fixed penalty, then using the standard correspondence between penalized and constrained problems.) Motivated by this characterization, the authors propose a plug-in approach, which relies on (1) an estimator of the regression function, (2) an estimator of the conditional variance and (3) an estimator of the quantiles of the conditional variance (taken to be the empirical quantile of the estimated conditional variance on a separate set of data inputs). This plug-in approach is shown to be "consistent" (in that its prediction accuracy and rejection rate converge to that of the best predictor with prescribed rejection rate), provided that the previous estimators are consistent in appropriate senses (L 2 for regression function and L 1 for the conditional variance). Finally, the plug-in approach is applied to the k-Nearest Neighbors (k-NN) algorithm, for which nonparametric rates of convergence for Lipschitz regression function and conditional variance (and some "margin condition" describing the mass of the conditional variance around the optimal threshold) are provided using convergence rates of k-NN.