Penalized Likelihood And Kullback-Leibler Oracle Bounds

Likelihood Selection and Kullback-Leibler Risk

A likelihood criterion rewards models that assign high density to the observed data. But the model with the largest observed likelihood need not have the smallest risk under the data-generating distribution: a favorable sample fluctuation can change their empirical ranking. Penalizing the likelihood trades some fit to the sample for protection against such fluctuations. The relevant comparison is not simply “fit versus complexity.” It has three distinct terms: the risk difference to a comparator, the fluctuation between empirical and population likelihood, and the difference in penalties.

For independent observations $X_1,\ldots,X_n$ from a distribution $P$, let $P_n g=n^{-1}\sum_{i=1}^n g(X_i)$ and $Pg=E[g(X)]$. Consider a deterministic class $\mathcal Q$ of candidate densities $q$ with respect to a common measure $\mu$. Write $\ell_q(x)=-\log q(x)$ for negative log-likelihood loss. Assume the candidate densities are positive $P$-almost surely and that the expectations and empirical losses used below are finite.

Definition: The population negative log-likelihood risk of $q$ is $R(q)=P\ell_q=E[-\log q(X)]$. If $P$ has density $p$ with respect to $\mu$, its Kullback-Leibler divergence from $q$ is $D(P\|q)=\int p(x)\log\{p(x)/q(x)\}\,d\mu(x)$. Whenever these quantities are finite, $R(q)=D(P\|q)+E[-\log p(X)]$. Thus differences in population negative log-likelihood risk are exactly differences in Kullback-Leibler risk.

The additive term $E[-\log p(X)]$ does not depend on the candidate. Consequently, minimizing $R(q)$ over $\mathcal Q$ is equivalent to minimizing $D(P\|q)$. If $P$ is not itself in $\mathcal Q$, the best available density is the member of $\mathcal Q$ with smallest Kullback-Leibler divergence; it need not equal the true density.

For conditional density models $q(y\mid x)$, the same statements apply to the loss $-\log q(Y\mid X)$. The corresponding risk difference is the difference between the expected conditional Kullback-Leibler divergences, averaging over the distribution of $X$. The observations in that case are the pairs $(X_i,Y_i)$.

The Basic Penalized-Likelihood Comparison

Let $\operatorname{pen}(q)$ be a deterministic penalty, and let $\hat q$ be a measurable choice whose penalized empirical negative log-likelihood is within $\delta\geq 0$ of the infimum: $P_n\ell_{\hat q}+\operatorname{pen}(\hat q)\leq P_n\ell_q+\operatorname{pen}(q)+\delta$ for every $q\in\mathcal Q$. The case $\delta=0$ is exact minimization. The tolerance $\delta$ allows for approximate optimization.

Theorem: Under the stated finiteness conditions, for every comparator $q\in\mathcal Q$, $$ R(\hat q)-R(q) \leq (P-P_n)(\ell_{\hat q}-\ell_q) +\operatorname{pen}(q)-\operatorname{pen}(\hat q)+\delta. $$ When the relevant Kullback-Leibler divergences are finite, the left side is also $D(P\|\hat q)-D(P\|q)$.

Proof. Add and subtract the empirical risk to the population risk difference:

\begin{aligned} R(\hat q)-R(q) &=(P-P_n)(\ell_{\hat q}-\ell_q) +P_n\ell_{\hat q}-P_n\ell_q\\ &\leq (P-P_n)(\ell_{\hat q}-\ell_q) +\operatorname{pen}(q)-\operatorname{pen}(\hat q)+\delta. \end{aligned}

The inequality follows by rearranging the defining approximate-minimization inequality. For the Kullback-Leibler statement, subtract the same constant $E[-\log p(X)]$ from both risks. $\square$

The fluctuation term is indexed by the selected model as well as the comparator. It is not generally a fixed error term independent of the data: $\hat q$ is chosen using the same sample that appears in $P_n$. To turn the comparison into an oracle statement, one needs a deviation control that holds simultaneously over the candidate class, or another valid way to control the selected fluctuation.

From Simultaneous Deviations to an Oracle Bound

Suppose $a(q)\geq0$ is a deviation allowance and that, on an event $\mathcal E$, every candidate satisfies $\lvert(P_n-P)\ell_q\rvert\leq a(q)$. The event must hold simultaneously over $\mathcal Q$, so it applies to the data-dependent $\hat q$ as well as to any comparator. For an uncountable class, the event and selected quantities must be measurable; alternatively, one can work with a countable class or a suitable measurable version of the uniform bound.

Theorem: On $\mathcal E$, suppose the penalty satisfies $\operatorname{pen}(q)\geq a(q)$ for every $q\in\mathcal Q$. Then, for every $q\in\mathcal Q$, $$ D(P\|\hat q) \leq D(P\|q)+a(q)+\operatorname{pen}(q)+\delta \leq D(P\|q)+2\operatorname{pen}(q)+\delta. $$ The same result holds with $R$ in place of $D(P\|\cdot)$.

Proof. Apply the basic comparison and use the simultaneous event to bound the fluctuation from above:

\begin{aligned} R(\hat q)-R(q) &\leq (P-P_n)(\ell_{\hat q}-\ell_q) +\operatorname{pen}(q)-\operatorname{pen}(\hat q)+\delta\\ &\leq a(\hat q)+a(q) +\operatorname{pen}(q)-\operatorname{pen}(\hat q)+\delta\\ &\leq a(q)+\operatorname{pen}(q)+\delta. \end{aligned}

The last inequality uses $a(\hat q)\leq\operatorname{pen}(\hat q)$. The further bound $a(q)\leq\operatorname{pen}(q)$ gives the displayed factor $2$. Since the inequality holds for every $q$, it can be expressed as $D(P\|\hat q)\leq\inf_{q\in\mathcal Q}\{D(P\|q)+2\operatorname{pen}(q)\}+\delta$. This is an oracle comparison: it relates the selected model to the best tradeoff available within the candidate class, not necessarily to the true density itself. $\square$

This theorem separates the roles of the terms. The comparator’s risk measures how well the available class can represent the data-generating distribution. The deviation allowance measures uncertainty in empirical likelihood. The penalty compensates for that uncertainty, including at the selected model; its value at the comparator remains in the oracle bound. The theorem does not itself provide a particular deviation allowance. That requires assumptions suited to the losses and candidate class at hand.

Worked Likelihood Comparisons

Worked Example: Bernoulli Likelihood and a Small Penalty

Let $P$ be Bernoulli with success probability $1/4$, and compare candidates $q_{1/4}$ and $q_{1/2}$, also Bernoulli densities. In a sample of size $n=10$, suppose four observations are successes. Use natural logarithms.

For a Bernoulli candidate $q_\theta$, the negative log-likelihood per observation is $-\log\theta$ for a success and $-\log(1-\theta)$ for a failure. Therefore,

\begin{aligned} P_n\ell_{q_{1/4}} &=-0.4\log(1/4)-0.6\log(3/4) \approx 0.72712699,\\ P_n\ell_{q_{1/2}}&=-\log(1/2)=\log 2 \approx 0.69314718. \end{aligned}

The empirical loss difference, candidate $q_{1/2}$ minus candidate $q_{1/4}$, is approximately $0.69314718-0.72712699=-0.03397981$. Set $\operatorname{pen}(q_{1/4})=0$ and $\operatorname{pen}(q_{1/2})=0.02$. The penalized empirical difference is $-0.03397981+0.02=-0.01397981$, so $q_{1/2}$ is selected between these two candidates.

Under the true success probability $1/4$, the population loss difference is

\begin{aligned} R(q_{1/2})-R(q_{1/4}) &=\tfrac14\log\!\left(\frac{1/4}{1/2}\right) +\tfrac34\log\!\left(\frac{3/4}{1/2}\right)\\ &=\tfrac14\log(1/2)+\tfrac34\log(3/2) \approx 0.13081204. \end{aligned}

Thus the likelihood fluctuation for this difference is population minus empirical: $0.13081204-(-0.03397981)=0.16479185$. The basic comparison against $q_{1/4}$ has penalty difference $0-0.02=-0.02$, so its right side is approximately $0.16479185-0.02=0.14479185$, which exceeds the risk difference $0.13081204$. The sample favors $q_{1/2}$, even though it has higher population risk; the fluctuation term accounts for that reversal.

Worked Example: Checking the Penalty Sign

Suppose two candidates are called $q_0$ and $q_2$, and for the observed sample their empirical loss difference is $P_n(\ell_{q_2}-\ell_{q_0})=-0.4$. Let the penalty difference be $\operatorname{pen}(q_2)-\operatorname{pen}(q_0)=0.3$. The penalized empirical criterion difference is $-0.4+0.3=-0.1$, so $q_2$ has the smaller criterion and is selected.

Assume the population risk difference is $R(q_2)-R(q_0)=2$. The fluctuation difference is therefore $ (P-P_n)(\ell_{q_2}-\ell_{q_0})=2-(-0.4)=2.4$. In the basic inequality with selected candidate $q_2$ and comparator $q_0$, the penalty term is $\operatorname{pen}(q_0)-\operatorname{pen}(q_2)=-0.3$. Consequently,

2\leq 2.4-0.3=2.1.

The comparison holds. This calculation illustrates why the penalty is comparator minus selected model in the risk inequality, even though the criterion itself adds a penalty to each empirical loss.

Worked Example: Gaussian Location Candidates

Let the data-generating distribution be $P=N(0,1)$, and compare $q_0=N(0,1)$ and $q_2=N(2,1)$. For a unit-variance normal candidate with mean $\mu$, the loss is $\ell_{q_\mu}(x)=\tfrac12\log(2\pi)+\tfrac12(x-\mu)^2$. The population loss difference is

R(q_2)-R(q_0) =\tfrac12 E[(X-2)^2-X^2] =\tfrac12(4-4E[X])=2,

since $E[X]=0$. Equivalently, $D(N(0,1)\|N(2,1))=2$ and $D(N(0,1)\|N(0,1))=0$.

Now suppose the sample consists of two observations, both equal to $2$. For each observation, the loss difference is $\ell_{q_2}(2)-\ell_{q_0}(2)=\tfrac12(0^2-2^2)=-2$, so the empirical difference is $-2$. Assign penalties $0$ to $q_0$ and $0.5$ to $q_2$. The penalized empirical difference is $-2+0.5=-1.5$, and $q_2$ is selected. Its fluctuation difference is $2-(-2)=4$; the basic inequality against $q_0$ reads $2\leq4-0.5=3.5$. A sample can strongly favor a candidate with worse population Kullback-Leibler risk, and the fluctuation term records the size of the discrepancy.

Interpretation and a Common Pitfall

The oracle bound has practical meaning even when the true distribution is outside the candidate class. A small comparator divergence represents good approximation by an available model; the penalty term then describes what must be paid to control selection by empirical likelihood. If every candidate has appreciable deviation, or the penalty is too small to cover it, the stated oracle conclusion need not follow. Nor does a small empirical loss alone establish a small Kullback-Leibler risk.

Common mistake: treating the penalty as if it always appears with a positive sign in the comparison. The criterion adds $\operatorname{pen}(q)$, but after rearrangement the comparison of selected model $\hat q$ to comparator $q$ contains $\operatorname{pen}(q)-\operatorname{pen}(\hat q)$. For example, if the selected candidate’s penalty is $0.3$ larger, its penalty contribution to the upper bound is $-0.3$, not $+0.3$. Separately, the fluctuation is $(P-P_n)(\ell_{\hat q}-\ell_q)$, population minus empirical loss difference. Keeping these two sign checks distinct prevents reversing the conclusion.

Key takeaway: Penalized-likelihood oracle comparisons bound Kullback-Leibler risk through an exact basic inequality. To obtain a useful oracle bound, control the likelihood fluctuation uniformly and choose a penalty large enough to absorb the selected-model deviation.

Check Your Understanding

Use the definitions and comparisons above to answer these questions.

Why does a difference in population negative log-likelihood risk equal a difference in Kullback-Leibler divergence?
Write the basic inequality’s penalty term when $\hat q$ is compared with $q$, and explain why its order is comparator minus selected model.
If the empirical loss difference is $-0.1$ and the population loss difference is $0.3$, what is the fluctuation difference $(P-P_n)(\ell_{\hat q}-\ell_q)$?
Why must a simultaneous deviation event apply to the selected candidate, not only to each fixed candidate considered separately?
If $\operatorname{pen}(q)\geq a(q)$ holds for every candidate, how does this condition control the selected-model term in the oracle proof?