The price of multi-group transductive learning

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 $$LOO_S(MLSA) \;\le\; C \left( \frac{1}{n} \min_{h\in H} L_S(h) \;+\; \frac{\log |H|}{n}\right), \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 $d\log 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 $d\log n$ 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 $\mathcal{H}$ is learnable if there is a learning algorithm $\mathcal{A}$, such that for every realizable sequence, the number of mistakes made by $\mathcal{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 study a \emph{max-risk} objective for active learning in a multi-group mean estimation $d$-armed bandits: a learner adaptively allocates a budget of $T$ samples across $d$ groups to minimize the worst-case uncertainty index $\max_{k\in[d]}σ_k^2/n_k$, where $σ_k$ is the standard deviation of the distribution of arm $d$, and $n_k$ is the number of times arm $d$ is sampled. We develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class. The bound separates difficulty into three orthogonal factors: a \emph{budget} term, a \emph{heteroscedasticity} index measuring how unevenly the uncertainty is spread across arms, and a model-dependent complexity measure, the \emph{Variance Local Curvature} ($\mathrm{VLC}$), which captures how much information a local change of variance creates inside the hypothesis class. For smooth classes, the $\mathrm{VLC}$ is a reparametrization of a variance--Fisher information, with closed-form values for common families. Benchmarking against the strongest available upper bound shows near-optimality up to logarithmic factors in broad regimes, and pinpoints a systematic gap in highly heterogeneous instances. Our proof introduces two key ingredients: a loss-induced $\ell_1$ geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.