mlsanityData to 14 Oct 2026

PAC Learning is just Bipartite Matching (Sort of)

arXiv 2502.00607 ↗First posted 2 Feb 2025cs.LG cs.DS stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

The main goal of this article is to convince you, the reader, that supervised learning in the Probably Approximately Correct (PAC) model is closely related to -- of all things -- bipartite matching! En-route from PAC learning to bipartite matching, I will overview a particular transductive model of learning, and associated one-inclusion graphs, which can be viewed as a generalization of some of the hat puzzles that are popular in recreational mathematics. Whereas this transductive model is far from new, it has recently seen a resurgence of interest as a tool for tackling deep questions in learning theory. A secondary purpose of this article could be as a (biased) tutorial on the connections between the PAC and transductive models of learning.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 18 of its 53 references that are in the map. First posted on arXiv 2 Feb 2025.

Builds on

18 of 53 references.

References · 18

  1. 2022A Characterization of Multiclass Learnabilitycited by 67
  2. 2014Optimal Learners for Multiclass Problemscited by 65
  3. 2021A Theory of PAC Learnability of Partial Concept Classescited by 60
  4. 2023Optimal PAC Bounds Without Uniform Convergencecited by 33
  5. 2021From Local Pseudorandom Generators to Hardness of Learningcited by 24
  6. 2023Optimal Learners for Realizable Regression: PAC Learning and Online Learningcited by 23
  7. 2023On the Provable Advantage of Unsupervised Pretrainingcited by 22
  8. 2022Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterizationcited by 17
  9. 2021Learning local regularization for variational image restorationcited by 16
  10. 2023Regularization and Optimal Multiclass Learningcited by 15
  11. 2021Transductive Robust Learning Guaranteescited by 10
  12. 2020Suboptimality of Constrained Least Squares and Improvements via Non-Linear Predictorscited by 9
6 more
  1. 2024Improved Hardness Results for Learning Intersections of Halfspacescited by 6
  2. 2024Is Transductive Learning Equivalent to PAC Learning?cited by 4
  3. 2024Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?cited by 3
  4. 2015Local Computation Algorithms for Graphs of Non-Constant Degreescited by 2
  5. 2024Transductive Learning Is Compactcited by 2
  6. 2019Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samplescited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026A One-Inclusion Graph Approach to Multi-Group Learningcited by 0