Even Sharper Bounds for Transductive Learning and Its Applications
STLC matches inductive excess-risk rates for transductive learning without an extra logarithmic confidence factor.
The paper introduces Sharper Transductive Local Complexity (STLC) for transductive learning under uniform sampling without replacement. It starts from a Bernstein-type bound on the test-train empirical process, proved via the swap walk's modified log-Sobolev inequality and a two-parameter entropy closure. For realizable binary VC classes with test size at least training size, the excess-risk rate matches classical inductive local Rademacher bounds and is within a log factor of the transductive minimax lower bound when m is at least 9. A spectrum-adaptive kernel bound avoids multiplicative imbalance factors from earlier local-complexity results.
- STLC uses a Bernstein inequality for the test-train empirical process.
- Proof relies on a modified log-Sobolev inequality and two-parameter entropy closure.
- For VC classes it matches the inductive rate O(dVC log(me/dVC)/m).
- Kernel bound is spectrum-adaptive and drops earlier imbalance factors.
Full article155 words · extracted from arxiv.org · click to collapse
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\ge m\ge\dVC$, STLC yields $\cO\{\dVC\log(me/\dVC)/m\}$. This matches the standard inductive rate and, when $m\ge9$, 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.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.28459