Learning Conditional Averages
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Recommendation SystemsSimilar Papers 제목 키워드 기반
Estimating Aleatoric Uncertainty in the Causal Treatment Effect
Previous work on causal inference has primarily focused on averages and conditional averages of treatment effects, with significantly less attention on variability and uncertainty in individual treatment responses. In th…
Causal InferencePosterior Average Effects
Economists are often interested in estimating averages with respect to distributions of unobservables, such as moments of individual fixed-effects, or average partial effects in discrete choice models. For such quantitie…
Discrete Choice ModelsInformativenessGANs and Closures: Micro-Macro Consistency in Multiscale Modeling
Sampling the phase space of molecular systems -- and, more generally, of complex systems effectively modeled by stochastic differential equations -- is a crucial modeling step in many fields, from protein folding to mate…
Dimensionality ReductionProtein FoldingDiffESM: Conditional Emulation of Earth System Models with Diffusion Models
Earth System Models (ESMs) are essential tools for understanding the impact of human actions on Earth's climate. One key application of these models is studying extreme weather events, such as heat waves or dry spells, w…
Feature-guided score diffusion for sampling conditional densities
Score diffusion methods can learn probability densities from samples. The score of the noise-corrupted density is estimated using a deep neural network, which is then used to iteratively transport a Gaussian white noise …
DenoisingOut-of-Distribution Generalization