mlsanityData to 7 Oct 2026

Transductive Rademacher Complexity and its Applications

arXiv 1401.3441 ↗First posted 15 Jan 2014cs.LG cs.AI stat.MLcited by 25

Not on the map. Why?

Abstract (arXiv)

We develop a technique for deriving data-dependent error bounds for transductive learning algorithms based on transductive Rademacher complexity. Our technique is based on a novel general error bound for transduction in terms of transductive Rademacher complexity, together with a novel bounding technique for Rademacher averages for particular algorithms, in terms of their "unlabeled-labeled" representation. This technique is relevant to many advanced graph-based transductive algorithms and we demonstrate its effectiveness by deriving error bounds to three well known algorithms. Finally, we present a new PAC-Bayesian bound for mixtures of transductive algorithms based on our Rademacher bounds.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Jan 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 2; 2023: 5; 2024: 3; 2025: 5; 2026: 5.

25 papers.

Sort:

  1. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  2. 2023Generative Social Choicecited by 43
  3. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  4. 2023WL meet VCcited by 30
  5. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  6. 2021Rethinking Neural vs. Matrix-Factorization Collaborative Filtering: the Theoretical Perspectivescited by 8
  7. 2021Multi-class Probabilistic Bounds for Self-learningcited by 3
  8. 2022TransBoost: Improving the Best ImageNet Performance using Deep Transductioncited by 3
  9. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  10. 2025Implicit Hypergraph Neural Networks: A Stable Framework for Higher-Order Relational Learning with Provable Guaranteescited by 3
  11. 2025Learning from one graph: transductive learning guarantees via the geometry of small random worldscited by 3
  12. 2021Layer-wise Adaptive Graph Convolution Networks Using Generalized Pagerankcited by 2
13 more
  1. 2023Robust Graph Structure Learning with the Alignment of Features and Adjacency Matrixcited by 2
  2. 2023Information-Theoretic Generalization Bounds for Transductive Learning and its Applicationscited by 2
  3. 2025Understanding Generalization in Node and Link Predictioncited by 2
  4. 2025Minimax-Optimal Two-Sample Test with Sliced Wassersteincited by 1
  5. 2021Multi-fidelity Stability for Graph Representation Learningcited by 0
  6. 2022Graph Polynomial Convolution Models for Node Classification of Non-Homophilous Graphscited by 0
  7. 2024Unlock the Power of Algorithm Features: A Generalization Analysis for Algorithm Selectioncited by 0
  8. 2025UPL: Uncertainty-aware Pseudo-labeling for Imbalance Transductive Node Classificationcited by 0
  9. 2026Transductive Generalization via Optimal Transport and Its Application to Graph Node Classificationcited by 0
  10. 2026Generalization Bounds for Spectral GNNs via Fourier Domain Analysiscited by 0
  11. 2026Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networkscited by 0
  12. 2026Bounded Difference Concentration for Infinitely Exchangeable Sequences with Applications to AI Benchmark Uncertaintycited by 0
  13. 2026Even Sharper Bounds for Transductive Learning and Its Applicationscited by 0