Skip to content

Combinatorial Characterizations of the Learnability of Conditional Distributions

Oct 2026 · 0 citations · 18 references
Mathematics Computer Science

TL;DR

The PAC-learnability of function classes that map inputs to probability distributions over a finite space is studied, and it is shown that a distribution-valued function class is learnable if and only if each of its coordinate classes is learnable in the probabilistic concept model.

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$_\gamma$Natarajan dimension}, which generalizes both fat$_\gamma$ and Natarajan dimension, and prove that its finiteness at every positive scale is necessary and sufficient for learnability. We also introduce a \textbf{fat$_\gamma$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.

View source

Similar papers

Preprint Oct 2026

PAC Learning with Query Feedback

We study realizable multiclass PAC learning with query feedback, where each training example provides a single binary response indicating whether its true label belongs to a chosen subset from a fixed query family. Our main contribution is the query dimension, a combinatorial parameter that captures both the structure...

Chase Hutton, Adam Melrod, Han Shao · 0 citations
Sep 2026

A Separation Between Distribution-Free SQ Learning and Dimension Complexity

We show that there exists a class of boolean functions C such that $(i)$ there is a distribution-independent statistical query algorithm for learning C that makes a polynomial number of queries of inverse polynomial tolerance and $(ii)$ for any set of functions $\Phi_1, \dots, \Phi_r$ such that for all $f \in$ C we can...

Shyamal Patel · 0 citations
Preprint Oct 2026

Actually, All Learnable Distribution Classes Are Privately Learnable

We show that every class of distributions that is learnable up to arbitrarily small target error in total variation distance with finitely many samples is also learnable under ($\varepsilon, \delta$)-differential privacy up to arbitrarily small target error with finitely many samples. This proves a conjecture of Ashtia...

Mohammad Afzali, H. Ashtiani, Alex Bie et al. · 0 citations
Preprint Oct 2026

Tight Stochastic Sequential Covers for General VC Classes with Unknown i.i.d. Features

We study hybrid online learning with stochastic features and adversarial labels when the feature distribution is unknown. Prior work gave stochastic sequential covers of log-size $O(d\log^2 T)$ for a general VC class and logarithmic bounds only under stronger star-type structure. We show that finite VC dimension alone...

Chang-Long Wu, Wojciech Szpankowski · 0 citations
Preprint Nov 2026

Near-Optimal Sample Complexity of Deterministic Agnostic PAC Learning

We study the problem of agnostic PAC learning under deterministic labels, where the examples are labeled by an arbitrary deterministic function, which need not belong to the concept class $C$. This model captures misspecification without stochastic label noise and lies between the realizable and fully agnostic settings...

S. Ben-David, Steve Hanneke, Farnam Mansouri et al. · 0 citations

Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

It is shown that a simple Follow-the-Perturbed-Leader algorithm with Gaussian perturbation for each observed context achieves the optimal $\widetilde O(\sqrt{T\log N})$ expected regret for a class of $N$ experts, while requiring one optimization-oracle call per round and no explicit enumeration of the class.

G. Buzaglo, Elad Hazan · 4 citations · ⚡1

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.