Learning Conditional Averages

Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:837-858, 2026.

Abstract

We introduce the problem of learning \emph{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. However, instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its \emph{neighborhood}—an arbitrary subset of points that contains the instance. In the degenerate case where all neighborhoods are singletons, the problem reduces exactly to classic PAC learning. More generally, it extends PAC learning to a setting that captures learning tasks arising in several domains, including 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 system, and are closely related to the independence number of the associated neighborhood graph.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-bressan26a, title = {Learning Conditional Averages}, author = {Bressan, Marco and Brukhim, Nataly and Cesa-Bianchi, Nicol{\`o} and Esposito, Emmanuel and Mansour, Yishay and Moran, Shay and Thiessen, Maximilian}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {837--858}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/bressan26a/bressan26a.pdf}, url = {https://proceedings.mlr.press/v336/bressan26a.html}, abstract = {We introduce the problem of learning \emph{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. However, instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its \emph{neighborhood}—an arbitrary subset of points that contains the instance. In the degenerate case where all neighborhoods are singletons, the problem reduces exactly to classic PAC learning. More generally, it extends PAC learning to a setting that captures learning tasks arising in several domains, including 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 system, and are closely related to the independence number of the associated neighborhood graph.} }
Endnote
%0 Conference Paper %T Learning Conditional Averages %A Marco Bressan %A Nataly Brukhim %A Nicolò Cesa-Bianchi %A Emmanuel Esposito %A Yishay Mansour %A Shay Moran %A Maximilian Thiessen %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-bressan26a %I PMLR %P 837--858 %U https://proceedings.mlr.press/v336/bressan26a.html %V 336 %X We introduce the problem of learning \emph{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. However, instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its \emph{neighborhood}—an arbitrary subset of points that contains the instance. In the degenerate case where all neighborhoods are singletons, the problem reduces exactly to classic PAC learning. More generally, it extends PAC learning to a setting that captures learning tasks arising in several domains, including 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 system, and are closely related to the independence number of the associated neighborhood graph.
APA
Bressan, M., Brukhim, N., Cesa-Bianchi, N., Esposito, E., Mansour, Y., Moran, S. & Thiessen, M.. (2026). Learning Conditional Averages. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:837-858 Available from https://proceedings.mlr.press/v336/bressan26a.html.

Related Material