Finite-Dictionary Selection Under Log Loss

Why Log Loss Has a Divergence Interpretation

A predictive probability distribution is judged not only by whether it assigns high probability to the outcome that occurs, but also by how its probabilities compare with the distribution that generates the data. Log loss makes this comparison precise. When the predictor assigns very little probability to an outcome that occurs, its loss is large; assigning probability zero to such an outcome gives infinite loss.

This tutorial studies predictors that return conditional probability distributions. It first identifies the population risk difference between a candidate and the true conditional distribution. It then uses a finite-dictionary argument to compare the predictor selected by empirical log loss with the best candidate in the dictionary. The risk bound requires bounded losses; this condition matters because log loss is not automatically bounded.

Definition: Let $(X,Y)$ have joint distribution $P$, and suppose the conditional distribution of $Y$ given $X=x$ has density or mass function $p(\,\cdot\mid x)$ with respect to a common measure. A predictive distribution $q$ assigns a density or mass function $q(\,\cdot\mid x)$. Its log loss at $(x,y)$ is $-\log q(y\mid x)$, and its population risk is $$ R(q)=E[-\log q(Y\mid X)]. $$ The Kullback–Leibler divergence from $p(\,\cdot\mid x)$ to $q(\,\cdot\mid x)$ is $$ \operatorname{KL}(p(\,\cdot\mid x)\,\|\,q(\,\cdot\mid x)) =\int p(y\mid x)\log\frac{p(y\mid x)}{q(y\mid x)}\,dy, $$ with a sum replacing the integral for discrete outcomes. The divergence is $+\infty$ if $q(y\mid x)=0$ on a set to which $p(\,\cdot\mid x)$ assigns positive probability.

The expectation defining risk is taken over both the covariate $X$ and the outcome $Y$. For the identity below, assume the logarithms in the risk difference are integrable and that the conditional divergences are well-defined. In particular, the identity applies directly when $Y$ has finitely many possible values and the candidate probabilities are positive. More generally, it applies whenever the relevant expectations are finite; if a candidate rules out a possible outcome, its risk and the corresponding divergence can instead be infinite.

Theorem: Under these integrability conditions, $$ R(q)-R(p)=E_X\!\left[\operatorname{KL}\{p(\,\cdot\mid X)\,\|\,q(\,\cdot\mid X)\}\right]. $$ Consequently, $R(q)\geq R(p)$, with equality exactly when $q(\,\cdot\mid X)=p(\,\cdot\mid X)$ almost surely (up to sets of outcome measure zero).

To see the identity, condition on $X=x$. Under the true conditional distribution, the expected loss difference is the expectation of $\log\{p(Y\mid x)/q(Y\mid x)\}$. Averaging that conditional expectation over $X$ gives the stated formula. Nonnegativity follows from the nonnegativity of Kullback–Leibler divergence. Thus the true conditional distribution is the population minimizer of log-loss risk, while a restricted dictionary can only approximate it.

Worked Example: Comparing Two Binary Predictors

Suppose $Y$ is binary, $P(Y=A)=0.8$, and $P(Y=B)=0.2$. The true distribution is $p=(0.8,0.2)$. Consider candidates $q_1=(0.7,0.3)$ and $q_2=(0.9,0.1)$. Since there is no covariate in this example, each risk difference from the true risk is the corresponding KL divergence.

For $q_1$, the divergence is $$ \operatorname{KL}(p\|q_1) =0.8\log(0.8/0.7)+0.2\log(0.2/0.3). $$ The two weighted terms are $0.8\log(8/7)\approx 0.106825$ and $0.2\log(2/3)\approx -0.081093$. Therefore, $\operatorname{KL}(p\|q_1)\approx 0.025732$.

For $q_2$, $$ \operatorname{KL}(p\|q_2) =0.8\log(0.8/0.9)+0.2\log(0.2/0.1). $$ Here $0.8\log(8/9)\approx -0.09423$, and $0.2\log 2\approx 0.138629$. Thus $\operatorname{KL}(p\|q_2)\approx 0.044403$. Candidate $q_1$ has the smaller excess risk by about $0.044403-0.025732=0.018671$. A negative contribution from one outcome is possible; the complete weighted sum, not each term separately, is the divergence.

Worked Example: Averaging Risk Across Covariate Values

Let $X$ take values $a$ and $b$, each with probability $1/2$. At both values, suppose the true conditional probability of $Y=A$ is $0.8$, so the true conditional distribution is $(0.8,0.2)$. A predictor uses $(0.7,0.3)$ at $a$ and $(0.9,0.1)$ at $b$.

At $a$, its conditional excess risk is the first divergence calculated above, approximately $0.025732$. At $b$, its conditional excess risk is approximately $0.044403$. The population excess risk averages over the distribution of $X$: $$ R(q)-R(p)=\tfrac12(0.025732)+\tfrac12(0.044403)\approx 0.035068. $$ The predictor is closer to the true conditional probabilities at $a$ than at $b$, but the overall risk difference reflects both covariate values and their probabilities. If the two covariate values had different probabilities, the average would use those probabilities as weights instead.

A Finite-Dictionary Oracle Comparison

Now suppose a finite dictionary contains $M$ fixed predictive distributions $q_1,\ldots,q_M$. “Fixed” means they are specified before the evaluation sample is observed, or are independent of that sample. Let $(X_i,Y_i)$, $i=1,\ldots,n$, be independent and identically distributed observations from the distribution of $(X,Y)$. Define the empirical log-loss risk by $$ \widehat R_n(q_j)=\frac{1}{n}\sum_{i=1}^n-\log q_j(Y_i\mid X_i). $$ The empirical risk selector $\widehat j$ minimizes this quantity over $j=1,\ldots,M$, with any fixed tie-breaking rule. Its selected predictor is $q_{\widehat j}$. The oracle comparator is the candidate with the smallest population risk, $\min_{1\leq j\leq M}R(q_j)$; it is a comparator, not a claim that this candidate is known in advance.

To obtain a simple finite-sample guarantee, assume $Y$ has $K$ possible outcomes and that every candidate satisfies $q_j(y\mid x)\geq\eta$ for every outcome $y$, covariate $x$, and candidate $j$, where $0<\eta\leq 1/K$. Each log loss then lies between $0$ and $B=\log(1/\eta)$. The lower probability bound is substantive: without it, a candidate can assign probabilities arbitrarily close to zero, so log loss can be arbitrarily large.

Theorem: Under the independent and identically distributed sampling and bounded-loss conditions just stated, for every $0<\delta<1$, with probability at least $1-\delta$, $$ R(q_{\widehat j})\leq \min_{1\leq j\leq M}R(q_j) +B\sqrt{\frac{2\log(2M/\delta)}{n}}. $$

The result follows from uniform concentration of the empirical risks over the finite dictionary. The proof gives the constants and shows why selection after looking at the data requires control over all $M$ candidates at once.

Concentrate each candidate's empirical risk.
For a fixed $j$, the $n$ losses are independent, identically distributed, and lie in $[0,B]$. Hoeffding's inequality gives $P(|\widehat R_n(q_j)-R(q_j)|>\varepsilon)\leq 2\exp(-2n\varepsilon^2/B^2)$.

Control the whole dictionary.
The union bound makes the probability that any candidate violates this deviation bound at most $2M\exp(-2n\varepsilon^2/B^2)$. Choose $\varepsilon=B\sqrt{\log(2M/\delta)/(2n)}$; the probability is then at most $\delta$.

Compare the selected candidate with the oracle.
On the event of simultaneous deviation control, empirical minimization and two applications of the deviation bound give $R(q_{\widehat j})\leq\widehat R_n(q_{\widehat j})+\varepsilon\leq\min_j\widehat R_n(q_j)+\varepsilon\leq\min_jR(q_j)+2\varepsilon$.

For completeness, the concentration step uses Hoeffding's inequality for independent bounded random variables. Taking a union bound does not require the empirical risks of different candidates to be independent: it only adds the $M$ individual failure probabilities. Substituting the chosen $\varepsilon$ into $2\varepsilon$ gives the theorem's remainder $B\sqrt{2\log(2M/\delta)/n}$. This proves the oracle comparison. $\square$

Worked Example: Reading the Finite-Dictionary Bound

Suppose there are $K=3$ possible outcomes, $M=4$ candidates, $n=1000$ independent observations, and every candidate assigns probability at least $\eta=0.05$ to every outcome. Then $B=\log(20)\approx2.9957$. At confidence level $1-\delta=0.95$, the remainder is $$ 2.9957\sqrt{\frac{2\log(2\cdot4/0.05)}{1000}} =2.9957\sqrt{\frac{2\log(160)}{1000}} \approx 2.9957(0.10075)\approx 0.302. $$ Thus, with probability at least $0.95$, the selected candidate's risk is at most the best candidate's risk plus approximately $0.302$ in log-loss units. This is a bound, not a prediction that the realized excess risk will equal $0.302$; it can be conservative.

Interpretation and a Common Pitfall

The bound separates three influences. The factor $B$ records how large the losses can be; the $\log(2M/\delta)$ term accounts for searching among candidates and the desired confidence; and the $1/\sqrt n$ factor reflects the concentration available from the sample. For log loss, imposing a minimum candidate probability makes the loss bounded, but a very small $\eta$ makes $B=\log(1/\eta)$ large. The probability floor therefore enables this particular simple guarantee while affecting its numerical strength.

The comparator is the best candidate in the dictionary, not necessarily the true conditional distribution. The KL identity says that the true conditional distribution minimizes population log-loss risk, but a finite dictionary may not contain it. The oracle comparison controls the cost of selecting from the dictionary relative to its best member; it does not remove the approximation gap between that member and the truth.

Common mistake: It is tempting to say that log loss is bounded because probabilities lie between zero and one. This reverses the relevant implication: as $q(y\mid x)$ approaches zero, $-\log q(y\mid x)$ grows without bound. The correction is to check a positive lower bound on every candidate probability, or to use a different concentration argument with assumptions suited to unbounded losses. The finite-dictionary theorem above is asserted only under its stated bounded-loss conditions.

Key takeaway: Under suitable integrability conditions, excess log-loss risk is expected conditional KL divergence from the true distribution. For a finite dictionary with bounded log losses, empirical risk selection has a high-probability risk no larger than the dictionary oracle risk plus an explicit sampling-and-search remainder.

Check Your Understanding

Answer these questions using the definitions and conditions in this tutorial.

Why can a candidate that assigns zero probability to an outcome with positive true probability have infinite log-loss risk?
For a fixed covariate value, express the expected loss difference between a candidate $q$ and the true conditional distribution $p$ as a divergence.
In the finite-dictionary theorem, which assumption ensures that each log loss is at most $B=\log(1/\eta)$?
Why does the proof use a union bound over the dictionary rather than concentration only for the eventual selected candidate?
Does the finite-dictionary oracle comparison assert that the selected predictor has the same risk as the true conditional distribution? Explain.

Finite-Dictionary Selection Under Log Loss

What You'll Learn