Multiplicative Oracle Inequalities for Transductive Learning via Level-Set Aggregation
Authors: Jian Qian, Jiachen Xu
Organizations: The University of Hong Kong · Hong Kong University of Science and Technology
Abstract
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 \emph{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(n1h∈HminLS(h)+nlog∣H∣),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 dlogn, where d is the VC dimension, recovering Long (1998) up to a logn factor. For logistic regression with bounded covariates and parameters, the log∣H∣ factor can be improved to be dlogn up to problem-dependent factors, where d is the ambient dimension.
We consider the problem of universal transductive online classification with a possibly unbounded label space. This setting considers online learning, with the sequence of instances (without labels) known to the learner in advance. We say a concept class H is learnable if there is a learning algorithm A, such that for every realizable sequence, the number of mistakes made by A grows at most sublinearly with the number of predictions. We characterize the learnability of this setting and show that there are only two possible optimal rates for the learnable classes: either bounded or increasing logarithmically. We introduce a new combinatorial structure, called ``Level-Constrained-Littlestone-Littlestone (LCLL) tree'', which, along with the indifference property, characterizes the learnability. We also extend the learnability result to the agnostic case and the case where only the stochastic process that generates the instance sequence is known.
We show every multi-group learner in the transductive setting may incur a multiplicative penalty in its error rate on some group relative to the error rate achievable in the single-group setting, and the penalty can increasing linearly with the number of groups, up to roughly the square-root of the sample size. This stands in stark contrast to optimal multi-group learners in an analogous (group-realizable) statistical setting, where the penalty is always at most logarithmic in the sample size and independent of the number of groups.
We revisit the problem of learning predictors robust to adversarial examples at test-time. We prove that VC classes are adversarially robustly learnable with sample complexity linear in the VC dimension d, providing an exponential improvement over the previous upper bound of Montasser, Hanneke, and Srebro (2019). Remarkably, this result is achieved with a simple improper algorithm that combines the classic heuristic bagging (bootstrap aggregation) of Breiman (1996) with robust empirical risk minimization (RERM). Our algorithm computes RERMs on O(d⋆) independent bootstrap samples and outputs their majority vote, where d⋆ denotes the dual VC dimension. We complement this result with a lower bound showing that this is unavoidable: in general, any learner in this oracle model requires Ω(d⋆) calls to an RERM oracle, even when given arbitrarily many training examples.