# Localized Complexities for Transductive Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Nov 2014.

## Built on by (most cited first, 6 of 6)

- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding](https://mlsanity.com/paper/2406.01977/) (2024)
- [Information-Theoretic Generalization Bounds for Transductive Learning and its Applications](https://mlsanity.com/paper/2311.04561/) (2023)
- [Graph Contrastive Learning with Low-Rank Regularization and Low-Rank Attention for Noisy Node Classification](https://mlsanity.com/paper/2402.09600/) (2024)
- [Transductive Generalization via Optimal Transport and Its Application to Graph Node Classification](https://mlsanity.com/paper/2603.09257/) (2026)
- [Even Sharper Bounds for Transductive Learning and Its Applications](https://mlsanity.com/paper/2609.28459/) (2026)

## Abstract (arXiv)

We show two novel concentration inequalities for suprema of empirical processes when sampling without replacement, which both take the variance of the functions into account. While these inequalities may potentially have broad applications in learning theory in general, we exemplify their significance by studying the transductive setting of learning theory. For which we provide the first excess risk bounds based on the localized complexity of the hypothesis class, which can yield fast rates of convergence also in the transductive learning setting. We give a preliminary analysis of the localized complexities for the prominent case of kernel classes.