# Even Sharper Bounds for Transductive Learning and Its Applications

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 13 references that are in the map.
- First posted on arXiv 23 Sep 2026.

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

- [Transductive Rademacher Complexity and its Applications](https://mlsanity.com/paper/1401.3441/) (2014)
- [Minimax Lower Bounds for Realizable Transductive Classification](https://mlsanity.com/paper/1602.03027/) (2016)
- [Localized Complexities for Transductive Learning](https://mlsanity.com/paper/1411.7200/) (2014)
- [Modified log-Sobolev inequalities for strongly log-concave distributions](https://mlsanity.com/paper/1903.06081/) (2019)

## Abstract (arXiv)

We introduce Sharper Transductive Local Complexity (STLC), a localized complexity method for transductive learning under uniform sampling without replacement. The construction starts from a Bernstein-type concentration inequality for the supremum of the test--train empirical process. Its proof uses the modified log-Sobolev inequality for the swap walk and a two-parameter entropy closure. A peeling argument with a surrogate localization functional then gives excess-risk bounds with the same fixed-point and confidence terms as the classical inductive local Rademacher-complexity bounds, without the additional logarithmic confidence factor in earlier transductive results. For realizable learning over a binary class of VC dimension dVC, with training size m, test size u, and u≥ m≥dVC, STLC yields cOdVClog(me/dVC)/m. This matches the standard inductive rate and, when m≥9, is within a logarithmic factor of the transductive minimax lower bound of order dVC/m. For transductive kernel learning, STLC gives a spectrum-adaptive excess-risk bound without the multiplicative imbalance factors appearing in the earlier local-complexity bound.