Uniform Convergence for Conditional Distribution Estimators

Why Uniform Convergence Matters

A conditional distribution estimator is often judged at covariate values $x$ that vary across a population or a prediction region. A score-risk estimate that is accurate at each fixed $x$ need not be accurate across all such values at once. Uniform control is stronger: it rules out covariate values, possibly changing with sample size, where the estimator performs unusually poorly.

The same issue arises over candidate conditional laws. A model-selection procedure may choose whichever candidate looks best in the data. A bound that holds separately for each fixed candidate does not automatically protect the chosen candidate. Uniform convergence supplies a common error bound over the entire set being considered.

Conditional Score Risk and Its Estimate

Let $F_x$ denote the conditional distribution of the response $Y$ given covariates $X=x$, and let $\mathcal Q$ be a set of candidate response distributions. For a score $S(q,y)$, the conditional score risk of candidate $q$ at $x$ is its expected score under $F_x$. Lower scores are taken to be preferable. The result below concerns convergence of these risks; it does not require the score to be proper.

Definition: The conditional score risk is $$ R(x,q)=E[S(q,Y)\mid X=x] =\int S(q,y)\,dF_x(y), $$ whenever the conditional expectation exists. An estimator $\hat R_n(x,q)$ estimates this risk. Uniform convergence over an index set $\mathcal T\subseteq\mathcal X\times\mathcal Q$ means $$ \sup_{(x,q)\in\mathcal T}|\hat R_n(x,q)-R(x,q)| \xrightarrow{p}0. $$

To state a general deviation result, represent the estimate as an average of independent contributions. For each index $t=(x,q)$, let $G_t(W_i)$ be the contribution from observation $i$, where $W_1,\ldots,W_n$ are independent and identically distributed. Assume $G_t(W_i)$ is measurable and $$ E[G_t(W_i)]=R(t),\qquad \hat R_n(t)=\frac{1}{n}\sum_{i=1}^{n}G_t(W_i). $$ For direct conditional sampling at a fixed $x$, $G_{(x,q)}(W_i)$ can be $S(q,Y_i)$ with $Y_i\sim F_x$. In other estimation schemes, contributions may include weights or other terms. What matters for the result is the stated mean and boundedness conditions, not a particular estimator construction. When the index set is infinite, we also assume the relevant suprema are measurable, or that the process has a separable version for which they are measurable.

This formulation makes an important distinction. An estimator can have a nonzero bias, meaning $E[\hat R_n(t)]\ne R(t)$. The deviation result first controls fluctuation around the estimator’s mean. To obtain convergence to the target risk, any bias must also vanish uniformly; this is made explicit below.

A Finite-Class Uniform Bound

Suppose the index set $\mathcal T$ is finite and has $M$ elements. Assume that, for a common pair of constants $a\le b$, $$ a\le G_t(W_i)\le b $$ almost surely for every $t\in\mathcal T$ and every $i$. Write $B=b-a$ for the range of the contributions. Hoeffding’s inequality states that for independent random variables $U_1,\ldots,U_n$ with $a\le U_i\le b$, $$ P\left(\left|\frac{1}{n}\sum_{i=1}^n U_i- \frac{1}{n}\sum_{i=1}^n E[U_i]\right|>\epsilon\right) \le 2\exp\left(-\frac{2n\epsilon^2}{(b-a)^2}\right), $$ for $\epsilon>0$ and $b>a$.

Theorem: Under the finite-class conditions above, if $B>0$, then for every $\epsilon>0$, $$ P\left(\max_{t\in\mathcal T}|\hat R_n(t)-R(t)|>\epsilon\right) \le 2M\exp\left(-\frac{2n\epsilon^2}{B^2}\right). $$ If $B=0$, the maximum error is zero almost surely.

Proof. Fix one $t\in\mathcal T$. Its contributions $G_t(W_1),\ldots,G_t(W_n)$ are independent, bounded between $a$ and $b$, and each has expectation $R(t)$. Hoeffding’s inequality therefore gives $$ P(|\hat R_n(t)-R(t)|>\epsilon) \le 2\exp\left(-\frac{2n\epsilon^2}{B^2}\right). $$ The event that at least one index has error greater than $\epsilon$ is the union, over the $M$ indices, of the corresponding individual events. The union bound gives $$ P\left(\max_{t\in\mathcal T}|\hat R_n(t)-R(t)|>\epsilon\right) \le \sum_{t\in\mathcal T}P(|\hat R_n(t)-R(t)|>\epsilon) \le 2M\exp\left(-\frac{2n\epsilon^2}{B^2}\right). $$ No independence between the errors at different indices is needed. If $B=0$, every contribution equals $a$ almost surely; since the index set is finite, all contributions equal $a$ simultaneously almost surely. Thus $\hat R_n(t)=R(t)=a$ for every $t$, proving the separate claim. $\square$

Worked Example: A Finite Set of Covariates and Candidate Laws

Suppose conditional outcomes are binary, and candidates are Bernoulli distributions with four possible probabilities $q\in\{0.2,0.4,0.6,0.8\}$. Consider six covariate values and the Brier score $S(q,y)=(y-q)^2$, which lies in $[0,1]$ for $y\in\{0,1\}$ and $q\in[0,1]$. There are $M=6\cdot4=24$ covariate-candidate pairs. Assume $n=1000$ independent, bounded contributions at each pair, with the contribution mean equal to the corresponding conditional risk.

Here $B=1$. To make the finite-class upper bound at most $\alpha=0.05$, solve $$ 2M\exp(-2n\epsilon^2)\le\alpha. $$ Taking logarithms and rearranging gives $$ \epsilon\ge\sqrt{\frac{\log(2M/\alpha)}{2n}} =\sqrt{\frac{\log(2\cdot24/0.05)}{2\cdot1000}} =\sqrt{\frac{\log(960)}{2000}} \approx\sqrt{0.00343347} \approx 0.05860. $$ Thus the probability that any of these 24 estimated risks differs from its target by more than $0.05860$ is at most $0.05$, up to rounding the displayed threshold. The guarantee is simultaneous: it remains valid for a candidate chosen after comparing all 24 estimated risks.

The bound also shows how class size affects the guarantee. For a sequence of finite classes $\mathcal T_n$, the bound tends to zero at each fixed $\epsilon>0$ if $$ \frac{\log |\mathcal T_n|}{n}\longrightarrow 0. $$ The relevant complexity is the logarithm of the number of indices, rather than the number alone. A class that grows too quickly may defeat this particular bound, even when each fixed index has a well-behaved estimate.

Extending the Bound to an Infinite Class

For a continuum of covariate values or candidate laws, counting indices is not possible. A common alternative is to approximate the index set by a finite net. Let $d$ be a metric on $\mathcal T$. A finite subset $\mathcal N_\delta$ is a $\delta$-net if every $t\in\mathcal T$ is within distance $\delta$ of some $s\in\mathcal N_\delta$. The covering number $N(\delta,\mathcal T,d)$ is the smallest size of such a net, when a finite net exists.

Theorem: Suppose $B>0$, the contributions satisfy $a\le G_t(W_i)\le b$ simultaneously for $t\in\mathcal T$ almost surely, and for some $L<\infty$, $$ |G_t(W_i)-G_s(W_i)|\le Ld(t,s) $$ for all $s,t\in\mathcal T$ and $i$, almost surely. Suppose also that $R(t)=E[G_t(W_i)]$. If $\mathcal N_\delta$ is a finite $\delta$-net, then for every $\epsilon>0$, $$ P\left(\sup_{t\in\mathcal T}|\hat R_n(t)-R(t)|> 2L\delta+\epsilon\right) \le 2N(\delta,\mathcal T,d) \exp\left(-\frac{2n\epsilon^2}{B^2}\right). $$

Proof. For any $s,t\in\mathcal T$, averaging the assumed bound on the contributions gives $$ |\hat R_n(t)-\hat R_n(s)| \le\frac{1}{n}\sum_{i=1}^n|G_t(W_i)-G_s(W_i)| \le Ld(t,s). $$ Taking expectations of the same pointwise bound gives $$ |R(t)-R(s)|\le E[|G_t(W_i)-G_s(W_i)|]\le Ld(t,s). $$ For each $t$, choose a net point $s\in\mathcal N_\delta$ with $d(t,s)\le\delta$. The triangle inequality yields $$ |\hat R_n(t)-R(t)| \le |\hat R_n(s)-R(s)| +|\hat R_n(t)-\hat R_n(s)| +|R(t)-R(s)| \le |\hat R_n(s)-R(s)|+2L\delta. $$ Consequently, if the supremum over $\mathcal T$ exceeds $2L\delta+\epsilon$, some net point has error greater than $\epsilon$. Apply the finite-class bound to the net, whose size is $N(\delta,\mathcal T,d)$. This gives the stated inequality. $\square$

In particular, consider a sequence of nets with radii $\delta_n\to0$. If $$ \frac{\log N(\delta_n,\mathcal T,d)}{n}\longrightarrow 0, $$ then the theorem implies uniform convergence in probability. To see this, fix $\eta>0$. For sufficiently large $n$, $2L\delta_n<\eta/2$. Apply the bound with $\epsilon=\eta/2$; its right-hand side tends to zero because its logarithm is at most $$ \log 2+\log N(\delta_n,\mathcal T,d)-\frac{n\eta^2}{2B^2}, $$ which tends to negative infinity under the displayed complexity condition.

Worked Example: A Net Bound Over a Continuum

Let the index set be $\mathcal T=[0,1]$ with the usual distance. Suppose $B=1$ and the contribution functions satisfy $|G_t(W_i)-G_s(W_i)|\le2|t-s|$, so $L=2$. Use the grid $\{0,0.01,0.02,\ldots,1\}$, which has 101 points and is a $0.01$-net: every point of $[0,1]$ lies within $0.01$ of a grid point. Let $n=10{,}000$.

The net theorem shows that a uniform error greater than $2(2)(0.01)+0.06=0.10$ has probability at most $$ 2(101)\exp\left(-\frac{2(10{,}000)(0.06)^2}{1^2}\right) =202\exp(-72) \approx 1.09\times10^{-29}. $$ The $0.04$ part of the tolerance accounts for moving from an arbitrary index to its grid point; the remaining $0.06$ is the allowed error on the finite grid. The net argument is useful only when the assumed regularity bound is justified for the estimator’s contributions. It is not enough that the target risk alone looks smooth.

Why Pointwise Convergence Is Not Enough

Pointwise convergence asks whether the error tends to zero at each fixed index. Uniform convergence asks whether the largest error over all indices tends to zero. The maximizing index in that supremum can change with $n$, so separate pointwise guarantees cannot rule out a sequence of increasingly narrow errors that moves through the index set.

Worked Example: A Moving Spike

On the domain $\mathcal T=(0,1]$, define $$ f_n(x)=\max\left\{1-n\left|x-\frac{1}{2n}\right|,\,0\right\}. $$ For any fixed $x>0$, choose $n>3/(2x)$. Then $nx>3/2$, so $$ n\left|x-\frac{1}{2n}\right|=nx-\frac12>1, $$ and therefore $f_n(x)=0$. Thus $f_n(x)\to0$ at every fixed $x\in(0,1]$. However, $x=1/(2n)$ belongs to the domain and $$ f_n\left(\frac{1}{2n}\right)=1. $$ It follows that $\sup_{x\in(0,1]}|f_n(x)|=1$ for every $n$. Pointwise convergence to zero therefore does not imply uniform convergence to zero. The moving-spike construction is a logical example about convergence; it is not itself an estimator.

In conditional distribution learning, pointwise accuracy at a fixed covariate value can therefore coexist with poor performance at a value that depends on the sample size. This matters if a later procedure searches across covariate values or candidate laws, or if a scientific claim is intended to apply across a whole covariate region. Uniform convergence is the relevant guarantee in those settings.

Separate Stochastic Error from Bias

The preceding bounds assume $E[\hat R_n(t)]=R(t)$. More generally, write $\mu_n(t)=E[\hat R_n(t)]$. Then, whenever the quantities are defined, $$ \sup_{t\in\mathcal T}|\hat R_n(t)-R(t)| \le \sup_{t\in\mathcal T}|\hat R_n(t)-\mu_n(t)| +\sup_{t\in\mathcal T}|\mu_n(t)-R(t)|. $$ The first term is stochastic fluctuation; the second is bias. A concentration inequality controls the first term under its independence and boundedness hypotheses. To conclude uniform convergence to $R$, the second term must also tend to zero. For instance, if the fluctuation tends to zero in probability and the supremum bias is bounded by a deterministic sequence tending to zero, then the total error tends to zero in probability by the displayed inequality.

This distinction is especially important for conditional estimators. A construction may use localized observations or other adjustments, so its finite-sample expectation need not equal the target conditional risk. A small stochastic error alone does not correct a persistent or nonuniform bias. The theorem describes the uniform-convergence step once the estimator’s mean and complexity conditions have been established; it does not assert those conditions for every conditional estimation method.

Common Mistake

Wrong reasoning: “For every fixed $x$ and $q$, the estimate converges to its conditional risk, so the largest error over $x$ and $q$ must also vanish.” The moving-spike example disproves this implication.
Correction: Control the whole indexed class. For a finite class, use a simultaneous bound whose cost depends on $\log M$. For an infinite class, establish a finite approximation and regularity conditions, then account for both the net error and the approximation error.
Another pitfall: Applying a bounded-variable inequality when the range is not finite, or using its formula with $B=0$. Verify the common bound first. If $B=0$, treat the constant-contribution case separately: the error is exactly zero under the common almost-sure bound.

Key takeaway: Uniform conditional score-risk convergence requires control over all covariate-candidate pairs at once. Bounded contributions control concentration, while the size or covering complexity of the index set controls the cost of taking a supremum. Any bias must be handled separately.

Check Your Understanding

Use the definitions and bounds above to answer these questions.

What is the difference between pointwise convergence in $(x,q)$ and uniform convergence over $\mathcal T$?
In the finite-class bound, what roles do $B$, $M$, and $n$ play in the probability of a large maximum error?
Why does the finite-class proof not require the errors at different indices to be independent?
For the net theorem, identify the two terms that produce the factor $2L\delta$.
If an estimator’s mean differs from the target risk, what additional quantity must be controlled to conclude uniform convergence to that target?