
Combinatorial and Geometric Challenges in PAC Learning with Partial Concepts
Shay Moran, of the Technion, presents a seminar on an extension of the classical PAC learning framework developed by Vapnik, Chervonenkis, and Valiant. He explains how replacing total function classes with partial function classes, where functions can be undefined on parts of the domain, lets the model capture practical assumptions like margin conditions or low-dimensional structure. Moran shows that this shift breaks familiar results, including the failure of empirical risk minimization, the principle that otherwise fully characterizes learnability in classical PAC theory. The talk then turns to how much more expressive partial functions are than total ones, connecting the question to open problems in combinatorics, geometry, and topology. Delivered as part of a Computer Science/Discrete Mathematics seminar, the lecture assumes no prior background in learning theory and runs just under an hour.