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.
From the original article
1 min read at arxiv.orgWe 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.
By Yingzhen Yang · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.