Multiplicative Oracle Inequalities for Transductive Learning via Level-Set Aggregation

We revisit transductive learning where predictions are made with the set of all covariates known in advance. In the leave-one-out (LOO) setting, the prediction is made with labels of the remaining sample points and evaluated by the average error. In particular, we study multiplicative oracle inequalities for agnostic transductive LOO prediction for a variety of tasks, including classification with 0-1 loss, squared loss regression, density estimation, and logistic regression. Specifically, we introduce Median of Level-Set Aggregation (MLSA), an aggregation procedure built on near-ERM level sets (i.e., empirical-risk level sets around the ERM). We prove a general multiplicative oracle inequality for the LOO error of the form [ LOOS(MLSA) ;≤; C left( frac1n minh∈ H LS(h) ;+; fraclog |H|nright), qquad C>1, ] where H is the hypothesis/function class. This inequality holds for hypothesis classes under a local level-set growth condition together with losses satisfying a mild monotonicity assumption. For classification with VC classes under the 0--1 loss, the log |H| factor can be improved to be dlog n, where d is the VC dimension, recovering Long (1998) up to a log n factor. For logistic regression with bounded covariates and parameters, the log |H| factor can be improved to be dlog n up to problem-dependent factors, where d is the ambient dimension.