Seminar Details

We introduce the problem of learning conditional averages in the PAC framework. The learner receives a sample labeled by an unknown target concept from a known concept class, as in standard PAC learning, but the goal is not to learn the target concept itself. Instead, for each instance, the learner must predict the average label over its neighborhood in a given graph on the domain. When all neighborhoods are singletons, this reduces exactly to classic PAC learning. More generally, it extends PAC learning to a graph-structured setting capturing tasks that arise in explainability, fairness, and recommendation systems. Our main contribution is a complete characterization of when conditional averages are learnable, together with sample complexity bounds that are tight up to logarithmic factors. The characterization hinges on the joint finiteness of two novel combinatorial parameters, which depend on both the concept class and the neighborhood graph, and are closely related to the graph’s independence number.