Even Sharper Bounds for Transductive Learning and Its Applications

arXiv:2609.28459v1 Announce Type: new 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 VC, with training size m, test size u, and uge mgeVC, STLC yields O{VClog(me/VC)/m}. This matches the standard inductive rate and, when mge9, is within a logarithmic factor of the transductive minimax lower bound of order VC/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.

Source: arXiv cs.LG | 2026-09-24