Research map / Learning theory and algorithms / Kernels and regression theory
A New Concentration Inequality for Sampling Without Replacement and Its Application for Transductive Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Transductive Local Complexity (TLC), a localized Rademacher-style framework with a new concentration inequality for sampling without replacement, yielding sharper transductive excess-risk bounds (including for transductive kernel learning) than Tolstikhin et al. (2014).
Problem
Obtaining sharp, local-complexity-based generalization/excess-risk bounds for transductive learning, whose existing bounds diverge with factors n/m and n/u when training or test sizes grow slowly relative to n.
Approach
Defines a test-train supremum process under uniform sampling without replacement, proves a new concentration inequality for it via exponential Efron-Stein applied twice, and combines it with a peeling strategy and a surrogate variance operator to get TLC bounds that match inductive LRC rates.
Key results
- Proves excess-risk bound (16) for generic transductive learning with rate (ru + rm + r*) + O(1/min{u,m}), matching inductive LRC form and removing the n/m and n/u factors of Tolstikhin et al. (2014).
- For transductive kernel learning, bound (17) converges to 0 as u, m grow (r(u,n,Q) <= Theta(1/sqrt(u)+1/sqrt(m))), whereas Tolstikhin et al.'s bound diverges when u or m = o(n^{1/(2alpha+1)}).
- New concentration inequality for sup of empirical process under sampling without replacement (Theorem 5.1) is claimed sharper than both concentration inequalities of Tolstikhin et al. (2014).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TLC with the test-train process and surrogate variance operator instead of the prior local-complexity bound | Transductive learning · Generic transductive learning | excess risk upper bound: Θ(n/m · r∗u + n/u · r∗m + 1/m + 1/u) -> c0 (ru + rm) + 4Bc2r∗/K + c3x/min {m, u} | Helped |
| Use the TLC-based bound instead of the Tolstikhin et al. (2014) bound | Transductive Kernel Learning · Transductive Kernel Learning | excess risk upper bound: Θ(n/u · r∗m + n/m · r∗u + 1/m + 1/u) -> c5 (min0≤Q≤n r(u, m, Q) + x/min {m, u}) | Helped |
| Use the new sampling-without-replacement concentration inequality for the test-train process | Transductive learning · Test-train process | concentration bound: g(d) ≤ Ed[g(d)] + 8√(5rx/min {u, m}) + 2√2 infα>0 (R+min{u,m}(H2)/α + 2αx/min {u, m}) + 8H0²x/min {u, m} | Helped |
| Use the new concentration inequality for a general supremum of empirical processes instead of the Tolstikhin et al. (2014) bounds | Transductive learning · Sampling uniformly without replacement | concentration bound: gu(d) − Ed[gu(d)] ≲ m/n (√(rx/min {u, m}) + infα>0 (R+min{u,m}(H2)/α + αx/min {u, m}) + x/min {u, m}) | Helped |
Surprising findings
- The existing transductive local complexity bound of Tolstikhin et al. (2014) can diverge under standard kernel learning models, even though it is derived under the same assumptions.
Limitations
- Theory requires the regime m >> u^2 or u >> m^2 for the concentration result.
- Analysis assumes bounded loss and Lipschitz/uniform-convexity conditions (Assumptions 1-2).
Experimental setup
Metrics: excess risk bound concentration inequality tail bound
Baselines: Tolstikhin et al. 2014 transductive local complexity bound
Builds on: Local Rademacher Complexity Tolstikhin et al. 2014 transductive bounds El-Yaniv & Pechyony transductive Rademacher complexity Efron-Stein inequality
Closest papers by meaning
- Transductive Learning is Compact (NeurIPS 2024 · similarity 0.87)
- Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.85)
- Certification-Enhanced Generalization Bounds (NeurIPS 2026 · similarity 0.85)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.85)
- The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination (NeurIPS 2025 · similarity 0.85)
- Tolerant Algorithms for Learning with Arbitrary Covariate Shift (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.