arXiv preprint ·
Combinatorial Characterizations of the Learnability of Conditional Distributions
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning (Statistics)
Lifetime-valid decisions by continually evolving AI analysts
Rethinking Representation Geometry in Supervised Contrastive Learning under Long-Tailed Data
Residual Calibration via Local Feature-Space Refinement
DBCM: Dual-Branch Calibration Module for Test-Time Adaptation in Time Series Forecasting
Width and Depth Limits Commute During Training in Linear Residual Networks
Get the few papers worth your time in Machine Learning (Statistics) every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.