Even Sharper Bounds for Transductive Learning and Its Applications
Abstract
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 cO{dVClog(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.
Related
- Sharper Bounds for the Complex Grothendieck Constant
- Sharper Zarankiewicz and Diagonal Bipartite Ramsey Bounds
- The price of multi-group transductive learning
- Sharper Bounds for Graphical Two-Choice Allocation
- Optimal Transport for Network Comparison: A Unified Review with New Spectral Bounds and Machine Learning Applications
BibTeX
@misc{yang2026even,
title = {{Even Sharper Bounds for Transductive Learning and Its Applications}},
author = {Yingzhen Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28459},
eprint = {2609.28459},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28459},
}
RIS
TY - UNPB
TI - Even Sharper Bounds for Transductive Learning and Its Applications
AU - Yingzhen Yang
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.28459
UR - https://arxiv.org/abs/2609.28459
AB - 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 cO{dVClog(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.
ER -