{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T04:16:00Z","timestamp":1749701760188,"version":"3.41.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2025,6,6]]},"abstract":"<jats:p>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. In hindsight, a secondary purpose of this article could be as a (biased) tutorial on the connections between the PAC and transductive models of learning.<\/jats:p>","DOI":"10.1145\/3744715.3744721","type":"journal-article","created":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T23:38:13Z","timestamp":1749685093000},"page":"40-62","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Guest Column: PAC Learning is just Bipartite Matching (Sort of)"],"prefix":"10.1145","volume":"56","author":[{"given":"Shaddin","family":"Dughmi","sequence":"first","affiliation":[{"name":"University of Southern California, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00071"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/41958.41994"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263927"},{"key":"e_1_2_1_4_1","first-page":"658","volume-title":"Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)","author":"Alon N.","year":"2021","unstructured":"N. Alon, S. Hanneke, R. Holzman, and S. Moran. A Theory of PAC Learnability of Partial Concept Classes. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 658--671. IEEE, 2021."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511624216"},{"key":"e_1_2_1_6_1","first-page":"5301","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory","author":"Asilis J.","year":"2024","unstructured":"J. Asilis, S. Devic, S. Dughmi, V. Sharan, and S.-H. Teng. Open Problem: Can Local Regularization Learn All Multiclass Problems? In Proceedings of Thirty Seventh Conference on Learning Theory, pages 5301--5305. PMLR, June 2024. URL https:\/\/proceedings.mlr. press\/v247\/asilis24b.html. ISSN: 2640--3498."},{"key":"e_1_2_1_7_1","first-page":"260","volume-title":"Teng. Regularization and Optimal Multiclass Learning. In Proceedings of Thirty Seventh Conference on Learning Theory","author":"Asilis J.","year":"2024","unstructured":"J. Asilis, S. Devic, S. Dughmi, V. Sharan, and S.-H. Teng. Regularization and Optimal Multiclass Learning. In Proceedings of Thirty Seventh Conference on Learning Theory, pages 260--310. PMLR, June 2024. URL https:\/\/proceedings.mlr.press\/v247\/asilis24a.html. ISSN: 2640--3498."},{"key":"e_1_2_1_8_1","volume-title":"The Thirty-eighth Annual Conference on Neural Information Processing Systems","author":"Asilis J.","year":"2024","unstructured":"J. Asilis, S. Devic, S. Dughmi, V. Sharan, and S.-H. Teng. Transductive Learning is Compact. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https:\/\/openreview.net\/forum?id=YWTpmLktMj."},{"key":"e_1_2_1_9_1","volume-title":"Oct.","author":"Attias I.","year":"2023","unstructured":"I. Attias, S. Hanneke, A. Kalavasis, A. Karbasi, and G. Velegkas. Optimal Learners for Realizable Regression: PAC Learning and Online Learning, Oct. 2023. URL http:\/\/arxiv. org\/abs\/2307.03848. arXiv:2307.03848 [cs, stat]."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1038\/s42256-018-0002--3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095--8956(72)90025--1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S1385-7258(51)50053-7","article-title":"A colour problem for infinite graphs and a problem in the theory of relations","volume":"13","author":"Bruijn N. d.","year":"1951","unstructured":"N. d. Bruijn and P. Erdos. A colour problem for infinite graphs and a problem in the theory of relations. Indigationes Mathematicae, 13:371--373, 1951.","journal-title":"Indigationes Mathematicae"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00093"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/080743470"},{"key":"e_1_2_1_15_1","first-page":"287","volume-title":"Proceedings of the 27th Conference on Learning Theory (COLT)","author":"Daniely A.","year":"2014","unstructured":"A. Daniely and S. Shalev-Shwartz. Optimal learners for multiclass problems. In Proceedings of the 27th Conference on Learning Theory (COLT), pages 287--316. PMLR, 2014."},{"key":"e_1_2_1_16_1","first-page":"1358","volume-title":"Proceedings of 34th Conference on Learning Theory (COLT)","author":"Daniely A.","year":"2021","unstructured":"A. Daniely and G. Vardi. From Local Pseudorandom Generators to Hardness of Learning. In Proceedings of 34th Conference on Learning Theory (COLT), pages 1358--1394. PMLR, July 2021. URL https:\/\/proceedings.mlr.press\/v134\/daniely21a.html. ISSN: 2640--3498."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 24th Conference on Learning Theory (COLT), pages 207--232. JMLR Workshop and Conference Proceedings, 2011","author":"Daniely A.","year":"1938","unstructured":"A. Daniely, S. Sabato, S. Ben-David, and S. Shalev-Shwartz. Multiclass Learnability and the ERM principle. In Proceedings of the 24th Conference on Learning Theory (COLT), pages 207--232. JMLR Workshop and Conference Proceedings, 2011. URL https:\/\/proceedings. mlr.press\/v19\/daniely11a.html. ISSN: 1938--7228."},{"key":"e_1_2_1_18_1","volume-title":"June","author":"Daskalakis C.","year":"2024","unstructured":"C. Daskalakis and N. Golowich. Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?, June 2024. URL http:\/\/arxiv.org\/abs\/2406.11667. arXiv:2406.11667 [cs, stat]."},{"key":"e_1_2_1_19_1","volume-title":"May","author":"Dughmi S.","year":"2024","unstructured":"S. Dughmi, Y. Kalayci, and G. York. Is Transductive Learning Equivalent to PAC Learning?, May 2024. URL http:\/\/arxiv.org\/abs\/2405.05190. arXiv:2405.05190 [cs, math, stat]."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Twelfth International Conference on Learning Representations (ICLR)","author":"Ge J.","year":"2024","unstructured":"J. Ge, S. Tang, J. Fan, and C. Jin. On the Provable Advantage of Unsupervised Pretraining. In Proceedings of the Twelfth International Conference on Learning Representations (ICLR), 2024. URL https:\/\/openreview.net\/forum?id=rmXXKxQpOR."},{"key":"e_1_2_1_21_1","first-page":"58","volume-title":"Classic Papers in Combinatorics","author":"Hall P.","year":"1987","unstructured":"P. Hall. On representatives of subsets. Classic Papers in Combinatorics, pages 58--62, 1987."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1948-09098-X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/2372148"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1097"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381196"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"e_1_2_1_27_1","first-page":"3","article-title":"Hat problem on a graph","volume":"21","author":"Krzywkowski M.","year":"2010","unstructured":"M. Krzywkowski. Hat problem on a graph. Mathematica Pannonica, 21:3-- 21, 2010. URL https:\/\/www.researchgate.net\/profile\/Marcin-Krzywkowski\/ publication\/242731015_Hat_problem_on_a_graph\/links\/54ecf5900cf28f3e65351045\/ Hat-problem-on-a-graph.pdf.","journal-title":"Mathematica Pannonica"},{"key":"e_1_2_1_28_1","first-page":"3353","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory","author":"Lechner T.","year":"2024","unstructured":"T. Lechner and S. Ben-David. Inherent limitations of dimensions for characterizing learnability of distribution classes. In Proceedings of Thirty Seventh Conference on Learning Theory, pages 3353--3374. PMLR, June 2024. URL https:\/\/proceedings.mlr.press\/v247\/lechner24a. html. ISSN: 2640--3498."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755615"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.915700"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007666507971"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3360093"},{"key":"e_1_2_1_33_1","volume-title":"Sept.","author":"Montasser O.","year":"2022","unstructured":"O. Montasser, S. Hanneke, and N. Srebro. Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization, Sept. 2022. URL http:\/\/arxiv.org\/abs\/2209. 07369. arXiv:2209.07369 [cs, stat]."},{"key":"e_1_2_1_34_1","first-page":"11461","volume-title":"Proceedings of The 25th International Conference on Artificial Intelligence and Statistics","author":"Montasser O.","year":"2022","unstructured":"O. Montasser, S. Hanneke, and N. Srebro. Transductive Robust Learning Guarantees. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 11461--11471. PMLR, May 2022. URL https:\/\/proceedings.mlr.press\/v151\/ montasser22a.html. ISSN: 2640--3498."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-030--75549--2"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms"},{"key":"e_1_2_1_37_1","volume-title":"Apr.","author":"Rubinfeld R.","year":"2011","unstructured":"R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie. Fast Local Computation Algorithms, Apr. 2011. URL http:\/\/arxiv.org\/abs\/1104.1377. arXiv:1104.1377 [cs]."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2008.07.005"},{"key":"e_1_2_1_39_1","first-page":"259","volume-title":"Machine Learning Proceedings","author":"Schaffer C.","year":"1994","unstructured":"C. Schaffer. A Conservation Law for Generalization Performance. In W. W. Cohen and H. Hirsh, editors, Machine Learning Proceedings 1994, pages 259--265. Morgan Kaufmann, San Francisco (CA), Jan. 1994. ISBN 978--1--55860--335--6. doi: 10.1016\/ B978--1--55860--335--6.50039--8. URL https:\/\/www.sciencedirect.com\/science\/article\/ pii\/B9781558603356500398."},{"key":"e_1_2_1_40_1","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer, 2003. URL https:\/\/link.springer.com\/book\/9783540443896."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107298019"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1953019"},{"key":"e_1_2_1_43_1","first-page":"4764","volume-title":"Proceedings of Thirty Seventh Conference on Learning Theory","author":"Tiegel S.","year":"2024","unstructured":"S. Tiegel. Improved Hardness Results for Learning Intersections of Halfspaces. In Proceedings of Thirty Seventh Conference on Learning Theory, pages 4764--4786. PMLR, June 2024. URL https:\/\/proceedings.mlr.press\/v247\/tiegel24a.html. ISSN: 2640--3498."},{"key":"e_1_2_1_44_1","volume-title":"Springer Series in Statistics","author":"Vapnik V.","year":"1982","unstructured":"V. Vapnik. Estimation of Dependences Based on Empirical Data. Springer Series in Statistics. Springer, New York, NY, 1982."},{"key":"e_1_2_1_45_1","volume-title":"Theory of pattern recognition","author":"Vapnik V.","year":"1974","unstructured":"V. Vapnik and A. Chervonenkis. Theory of pattern recognition. 1974. Publisher: Nauka, Moscow."},{"key":"e_1_2_1_46_1","volume-title":"The Nature of Statistical Learning Theory","author":"Vapnik V. N.","year":"1998","unstructured":"V. N. Vapnik. The Nature of Statistical Learning Theory. Springer, New York, NY, UNITED STATES, 1998. ISBN 978--1--4757--2440-0. URL http:\/\/ebookcentral.proquest.com\/lib\/ socal\/detail.action?docID=3084784."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.3150\/22-BEJ1465"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--88693--8"},{"issue":"1","key":"e_1_2_1_49_1","first-page":"47","article-title":"On the Connection between In-sample Testing and Generalization Error","volume":"6","author":"Wolpert D. H.","year":"1992","unstructured":"D. H. Wolpert. On the Connection between In-sample Testing and Generalization Error. Complex Systems, 6(1):47--94, 1992.","journal-title":"Complex Systems"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3744715.3744721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T23:38:21Z","timestamp":1749685101000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3744715.3744721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,6]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,6]]}},"alternative-id":["10.1145\/3744715.3744721"],"URL":"https:\/\/doi.org\/10.1145\/3744715.3744721","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2025,6,6]]},"assertion":[{"value":"2025-06-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}