Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 7 min ago
PreprintCC BY 4.0arXiv

Combinatorial Characterizations of the Learnability of Conditional Distributions

  • Mihir Dhanakshirur
  • Ambuj Tewari
Open at sourcePDFDOICite

Abstract

We study the PAC-learnability of function classes that map inputs to probability distributions over a finite space. The learner observes i.i.d. input-label pairs, with each label sampled from the conditional distribution of an unknown target hypothesis in the class. We measure learning through excess risk under a bounded proper loss that satisfies two mild assumptions. We introduce the \textbf{fatγNatarajan dimension}, which generalizes both fatγ and Natarajan dimension, and prove that its finiteness at every positive scale is necessary and sufficient for learnability. We also introduce a \textbf{fatγGraph} dimension extending the classical \gra dimension and establish inequalities comparing the two dimensions at different scales, leading to an equivalent characterization of learnability. Finally, we show that a distribution-valued function class is learnable if and only if each of its coordinate classes is learnable in the probabilistic concept model.

Related

  1. Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction
    Zonghuan Xu
    arXivPreprintCC BY-NC-ND 4.0Full textStatisticsarXiv
  2. Continuous Distributional Characterizations via a Single Characterizing Function and Lambert W Conditional Expectation Identities
    Ali A. Al-Shomrani
    AxiomsPeer-reviewedCC BY 4.0General mathematicsCrossref
  3. Measuring Differences between Conditional Distributions using Kernel Embeddings
    Peter Moskvichev, Siu Lun Chau, Dino Sejdinovic
    arXivPreprintarXiv licenceFull textStatisticsarXiv
  4. On the continuity of conditional distributions and stratification for derivative pricing
    Aleksandar Arandjelovic, Patrick Cheridito
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  5. On the Complexity of the Compatibility Problem for Succinctly Encoded Conditional Distributions
    Guy Emerson
    arXivPreprintCC BY 4.0Full textProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{dhanakshirur2026combinatorial,
  title = {{Combinatorial Characterizations of the Learnability of Conditional Distributions}},
  author = {Mihir Dhanakshirur and Ambuj Tewari},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.31890},
  eprint = {2610.31890},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.31890},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Combinatorial Characterizations of the Learnability of Conditional Distributions
AU  - Mihir Dhanakshirur
AU  - Ambuj Tewari
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2610.31890
UR  - https://arxiv.org/abs/2610.31890
AB  - We study the PAC-learnability of function classes that map inputs to probability distributions over a finite space. The learner observes i.i.d. input-label pairs, with each label sampled from the conditional distribution of an unknown target hypothesis in the class. We measure learning through excess risk under a bounded proper loss that satisfies two mild assumptions. We introduce the \textbf{fat_γNatarajan dimension}, which generalizes both fat_γ and Natarajan dimension, and prove that its finiteness at every positive scale is necessary and sufficient for learnability. We also introduce a \textbf{fat_γGraph} dimension extending the classical \gra dimension and establish inequalities comparing the two dimensions at different scales, leading to an equivalent characterization of learnability. Finally, we show that a distribution-valued function class is learnable if and only if each of its coordinate classes is learnable in the probabilistic concept model.
ER  -