Even Sharper Bounds for Transductive Learning and Its Applications

We introduce Sharper Transductive Local Complexity (STLC) as a new tool for analyzing the generalization performance of transductive learning methods, improving upon the current transductive bounds. Our work extends the classical local complexity-based analysis to the transductive setting, incorporating substantial and novel components beyond standard inductive and transductive analysis. Although Local Rademacher Complexity (LRC) has been used to obtain sharp inductive generalization bounds and local complexity-based transductive bounds, it has remained an open problem whether a localized Rademacher complexity framework can achieve exactly the same sharp bounds matching their inductive counterparts. STLC provides a confirmative answer to this question. STLC is constructed by first deriving a new and sharp concentration inequality for the supremum of empirical processes capturing the gap between test and training losses, or the test-train process, under uniform sampling without replacement. The proof establishes a Bernstein-type concentration inequality via a novel entropy-based approach built on the modified log-Sobolev inequality for the swap walk. A subsequent peeling strategy with a surrogate variance operator then yields excess risk bounds in the transductive setting that exactly match the classical LRC-based inductive bounds without the additional logarithmic gap in existing works. We further advance the current state-of-the-art in transductive learning through two applications: (1) for realizable transductive learning over binary-valued function classes with finite VC dimension $\dVC$ and $u \ge m \ge \dVC$, where $u$ and $m$ are the number of test features and training features, STLC gives a nearly optimal bound $\Theta(\dVC \log(me/\dVC)/m)$ nearly matching the minimax rate $\Theta(\dVC/m)$ up to $\log m$ and exactly matching the inductive bound, resolving a decade-old open question; and (2) STLC presents a sharper excess risk bound for transductive kernel learning compared to the prior local complexity–based results.