# Learning Conditional Averages

arXiv: https://arxiv.org/abs/2602.11920 · HTML: https://mlsanity.com/paper/2602.11920/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 29 references that are in the map.
- First posted on arXiv 12 Feb 2026.

## Builds on (most cited first, 16 of 16)

- ["Why Should I Trust You?": Explaining the Predictions of Any Classifier](https://mlsanity.com/paper/1602.04938/) (2016)
- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Characterization of Multiclass Learnability](https://mlsanity.com/paper/2203.01550/) (2022)
- [Optimal Learners for Multiclass Problems](https://mlsanity.com/paper/1405.2420/) (2014)
- [A Theory of PAC Learnability of Partial Concept Classes](https://mlsanity.com/paper/2107.08444/) (2021)
- [Framework for Evaluating Faithfulness of Local Explanations](https://mlsanity.com/paper/2202.00734/) (2022)
- [Multi-group Agnostic PAC Learnability](https://mlsanity.com/paper/2105.09989/) (2021)
- [Easy Learning from Label Proportions](https://mlsanity.com/paper/2302.03115/) (2023)
- [An adaptive nearest neighbor rule for classification](https://mlsanity.com/paper/1905.12717/) (2019)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [PAC Learning Linear Thresholds from Label Proportions](https://mlsanity.com/paper/2310.10098/) (2023)
- [Auditing Local Explanations is Hard](https://mlsanity.com/paper/2407.13281/) (2024)
- [Optimistic Rates for Learning from Label Proportions](https://mlsanity.com/paper/2406.00487/) (2024)
- [On the Complexity of Learning from Label Proportions](https://mlsanity.com/paper/2004.03515/) (2020)
- [Distribution-Specific Auditing For Subgroup Fairness](https://mlsanity.com/paper/2401.16439/) (2024)
- [Nearly Optimal Sample Complexity for Learning with Label Proportions](https://mlsanity.com/paper/2505.05355/) (2025)

## Abstract (arXiv)

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. However, instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its 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.