# Multiplicative Oracle Inequalities for Transductive Learning via Level-Set Aggregation

arXiv: https://arxiv.org/abs/2603.02043 · HTML: https://mlsanity.com/paper/2603.02043/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 22 references that are in the map.
- First posted on arXiv 2 Mar 2026.

## Builds on (most cited first, 10 of 10)

- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [Optimal PAC Bounds Without Uniform Convergence](https://mlsanity.com/paper/2304.09167/) (2023)
- [An improper estimator with optimal excess risk in misspecified density estimation and logistic regression](https://mlsanity.com/paper/1912.10784/) (2019)
- [Optimal Learners for Realizable Regression: PAC Learning and Online Learning](https://mlsanity.com/paper/2307.03848/) (2023)
- [Distribution-Free Robust Linear Regression](https://mlsanity.com/paper/2102.12919/) (2021)
- [Regularization and Optimal Multiclass Learning](https://mlsanity.com/paper/2309.13692/) (2023)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [Prediction, Learning, Uniform Convergence, and Scale-sensitive Dimensions](https://mlsanity.com/paper/2304.11059/) (2023)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)

## Abstract (arXiv)

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.