Approximation Error in Misspecified Candidate Dictionaries

Approximation and Estimation Are Different Sources of Error

An exponential aggregate assigns data-dependent weights to a finite set of candidate predictors. Its risk can be close to that of the best candidate even when none of the candidates is close to the prediction rule one would ideally use. These are different questions: estimation error concerns the cost of learning weights from a finite sample, while approximation error concerns what the dictionary can achieve in the first place.

The distinction matters because an oracle inequality is a comparison, not a promise that the candidate set is adequate. A small estimation term says that the aggregate is competitive with a specified comparator. To conclude that its absolute risk is small, one must also control the comparator’s gap from the ideal risk.

Setup and Definitions

Let $Z_1,\ldots,Z_n$ be independent observations with a common distribution $P$. A finite, fixed dictionary contains predictors $f_1,\ldots,f_M$, where each $f_j$ maps an input $x$ to a prediction. The dictionary is fixed independently of the sample. Let $\ell(f(x),y)$ be the loss, assumed measurable and convex as a function of the prediction. Suppose throughout this tutorial that $0\leq \ell(f_j(X),Y)\leq 1$ almost surely for every dictionary member $j$. For squared loss, this boundedness requires suitable restrictions such as clipping, as discussed in the earlier material on clipping and tail conditions.

Write the population risk of candidate $j$ and its empirical risk as

R_j=E[\ell(f_j(X),Y)], \qquad \widehat R_j=\frac{1}{n}\sum_{i=1}^n \ell(f_j(X_i),Y_i).

Let $\pi=(\pi_1,\ldots,\pi_M)$ be a prior distribution on the dictionary, with $\pi_j>0$ and $\sum_{j=1}^M\pi_j=1$. Given a temperature $\eta>0$, define the exponential weights

\widehat\rho_j = \frac{\pi_j\exp(-\eta n\widehat R_j)} {\sum_{k=1}^M\pi_k\exp(-\eta n\widehat R_k)}.

These weights define a deterministic convex aggregate $\widehat f(x)=\sum_{j=1}^M\widehat\rho_j f_j(x)$. They also define a randomized predictor that selects $f_j$ with probability $\widehat\rho_j$. The deterministic aggregate’s loss is no greater than the weighted average loss of its components, by convexity. The two predictors need not have the same risk; here the target is the deterministic aggregate.

Definition: Let $\mathcal F$ be a reference class of predictors containing the dictionary, and define $R_*=\inf_{f\in\mathcal F}R(f)$, where $R(f)=E[\ell(f(X),Y)]$. The dictionary approximation error is $$ a_{\mathcal D}=\min_{1\leq j\leq M}R_j-R_*. $$ It is nonnegative. The dictionary is misspecified relative to $\mathcal F$ when $a_{\mathcal D}>0$; in particular, no dictionary member then attains the reference-class optimal risk.

The infimum defining $R_*$ need not be attained. What matters for the decomposition is that it is finite and no greater than the risk of any dictionary member.

Worked Example: A Dictionary with a Positive Approximation Gap

Suppose $Y$ is Bernoulli with success probability $1/2$, the input $X$ is constant, and the loss is squared error. The reference class contains every constant prediction in $[0,1]$, but the dictionary contains only $f_1(x)=1/4$ and $f_2(x)=3/4$. For a constant prediction $c$,

R(c)=E[(Y-c)^2] =\frac12(1-c)^2+\frac12c^2 =c^2-c+\frac12 =(c-\tfrac12)^2+\frac14.

This is minimized over $[0,1]$ at $c=1/2$, giving $R_*=1/4$. For either dictionary member,

R(1/4)=R(3/4) =(1/4)^2-(1/4)+1/2 =\frac{1}{16}-\frac{4}{16}+\frac{8}{16} =\frac{5}{16}.

Thus $\min_j R_j=5/16$ and $a_{\mathcal D}=5/16-1/4=1/16$. Neither candidate is optimal in the reference class, however large the sample becomes. In this example a convex aggregate can predict $1/2$, but the basic oracle comparison below is against dictionary members; its approximation gap is therefore the gap to the best member.

A Finite-Sample Oracle Comparison

The following bound separates comparator risk from two finite-sample costs: the prior-mass penalty for a comparator and a uniform deviation term. It holds for every fixed comparator distribution $q=(q_1,\ldots,q_M)$ on the dictionary. Define $\operatorname{KL}(q\|\pi)=\sum_{j:q_j>0}q_j\log(q_j/\pi_j)$.

Theorem: Under the setup above, for any $0<\delta<1$, with probability at least $1-\delta$, the exponential aggregate satisfies, simultaneously for every distribution $q$ on the dictionary and every $\eta>0$, $$ R(\widehat f) \leq \sum_{j=1}^M q_jR_j +\frac{\operatorname{KL}(q\|\pi)}{\eta n} +2\sqrt{\frac{\log(2M/\delta)}{2n}}. $$ In particular, choosing $q$ concentrated on any candidate $j$ gives $$ R(\widehat f) \leq R_j+\frac{\log(1/\pi_j)}{\eta n} +2\sqrt{\frac{\log(2M/\delta)}{2n}}. $$

The simultaneous statement concerns all comparator distributions $q$ and all positive temperatures for the same sample-dependent weights formed at the chosen temperature. The probability event needed in the proof does not depend on either choice.

Proof. For each fixed $j$, Hoeffding’s inequality for independent losses in $[0,1]$ gives

P\left( |\widehat R_j-R_j|> \sqrt{\frac{\log(2M/\delta)}{2n}} \right) \leq \frac{\delta}{M}.

A union bound over the $M$ candidates shows that, with probability at least $1-\delta$, all $M$ deviations are at most $\varepsilon=\sqrt{\log(2M/\delta)/(2n)}$. Work on this event. For any distribution $s$ on the dictionary, the deviation of its weighted average risks is also at most $\varepsilon$, since

\left|\sum_j s_j\widehat R_j-\sum_j s_jR_j\right| \leq \sum_j s_j|\widehat R_j-R_j| \leq \varepsilon.

Let $Z_\eta=\sum_j\pi_j\exp(-\eta n\widehat R_j)$; then $\widehat\rho_j=\pi_j\exp(-\eta n\widehat R_j)/Z_\eta$. For any distribution $q$, nonnegativity of $\operatorname{KL}(q\|\widehat\rho)$ and the definition of $\widehat\rho$ imply

0\leq \operatorname{KL}(q\|\widehat\rho) =\operatorname{KL}(q\|\pi)+\eta n\sum_jq_j\widehat R_j+\log Z_\eta.

Consequently, $-\log Z_\eta/(\eta n)\leq \sum_jq_j\widehat R_j+\operatorname{KL}(q\|\pi)/(\eta n)$. Taking $q=\widehat\rho$ in the same identity gives $-\log Z_\eta/(\eta n)=\sum_j\widehat\rho_j\widehat R_j+ \operatorname{KL}(\widehat\rho\|\pi)/(\eta n)$, which is at least $\sum_j\widehat\rho_j\widehat R_j$. Combining these inequalities yields

\sum_j\widehat\rho_j\widehat R_j \leq \sum_jq_j\widehat R_j+\frac{\operatorname{KL}(q\|\pi)}{\eta n}.

By convexity of the loss, pointwise in each observation, $\ell(\widehat f(X_i),Y_i)\leq\sum_j\widehat\rho_j\ell(f_j(X_i),Y_i)$. Therefore $\widehat R(\widehat f)\leq\sum_j\widehat\rho_j\widehat R_j$. The uniform deviation event applies to the data-dependent distribution $\widehat\rho$, because it controls every weighted average of the candidate deviations. Hence

R(\widehat f) \leq \widehat R(\widehat f)+\varepsilon \leq \sum_j\widehat\rho_j\widehat R_j+\varepsilon \leq \sum_jq_j\widehat R_j+\frac{\operatorname{KL}(q\|\pi)}{\eta n}+\varepsilon \leq \sum_jq_jR_j+\frac{\operatorname{KL}(q\|\pi)}{\eta n}+2\varepsilon.

The event used only the simultaneous candidate-risk deviations, so the inequality holds on that event for every $q$ and every $\eta>0$. For $q$ concentrated on $j$, $\operatorname{KL}(q\|\pi)=\log(1/\pi_j)$, proving both claims. $\square$

From the Oracle Bound to an Approximation–Estimation Decomposition

Since the theorem holds for each dictionary member, it holds for the best one as well. For a finite dictionary, a risk-minimizing index exists. Subtracting and adding $R_*$ gives the desired decomposition:

R(\widehat f)-R_* \leq \underbrace{\left(\min_jR_j-R_*\right)}_{\text{approximation error}} + \underbrace{\frac{\log(1/\pi_{j_*})}{\eta n} +2\sqrt{\frac{\log(2M/\delta)}{2n}}}_{\text{estimation and complexity}}, \qquad j_*\in\arg\min_j R_j.

The prior-mass term reflects how costly it is, under the chosen prior, to compete with the best candidate. With a uniform prior, it is $\log M/(\eta n)$. The deviation term controls empirical-to-population discrepancies across the entire dictionary. The bound is an oracle comparison: it says the aggregate is not much worse than a comparator, up to the displayed costs. It does not assert that the right-hand side is small when the dictionary is inadequate.

Worked Example: Reading the Gap When the Best Candidate Is Not Ideal

Use the Bernoulli regression setup above, with a uniform prior on the two candidates, $n=1000$, $\eta=1$, and confidence level $1-\delta=0.9$. The best candidate has risk $5/16$, while the reference risk is $1/4$. The prior penalty for either candidate is

\frac{\log(1/\pi_j)}{\eta n} =\frac{\log 2}{1000} \approx 0.0006931.

The deviation contribution is

2\sqrt{\frac{\log(2M/\delta)}{2n}} =2\sqrt{\frac{\log(40/0.9)}{2000}} =2\sqrt{\frac{\log(44.444\ldots)}{2000}} \approx 0.08711.

Thus, with probability at least $0.9$, the theorem gives $R(\widehat f)\leq 5/16+0.0006931+0.08711\approx0.40031$. Relative to the ideal risk, the corresponding upper bound is approximately $1/16+0.0006931+0.08711=0.15031$. The $1/16$ term is not an estimation failure: it remains because neither candidate is ideal. This numerical bound is conservative, but the decomposition correctly identifies the two sources of error.

Worked Example: Effect of Dictionary Size and Confidence

Suppose there are $M=3$ candidates with a uniform prior, $n=1000$, $\delta=0.1$, and $\eta=1$. For any selected comparator, the common deviation contribution is

2\sqrt{\frac{\log(2M/\delta)}{2n}} =2\sqrt{\frac{\log(60)}{2000}} \approx 0.09049.

The prior cost is $\log 3/1000\approx0.001099$. Therefore the oracle inequality gives, with probability at least $0.9$, $R(\widehat f)\leq R_{j_*}+0.001099+0.09049 =R_{j_*}+0.09159$, to the shown precision. If $R_*=0.12$ and the best dictionary risk is $R_{j_*}=0.20$, then the approximation gap is $0.20-0.12=0.08$, and the risk relative to $R_*$ is bounded by approximately $0.08+0.09159=0.17159$. Increasing $n$ reduces these displayed estimation terms; it does not by itself remove the $0.08$ approximation gap.

Why the Distinction Matters—and a Common Mistake

Approximation error is useful in model assessment because it indicates whether improving the learning procedure can plausibly reach the desired risk. If the dictionary’s best risk is already close to $R_*$, controlling estimation error may be enough for a strong overall guarantee. If the gap is large, more data or a different temperature cannot make the current best candidate ideal; the candidate set or reference target must change.

Common mistake: “The oracle inequality says the aggregate is close to the best candidate, so it must be close to the ideal predictor.” The conclusion does not follow. The inequality compares the aggregate with a dictionary candidate, and that candidate may itself have substantial excess risk. The correction is to add and inspect the approximation gap: $R(\widehat f)-R_*=[R(\widehat f)-\min_jR_j]+[\min_jR_j-R_*]$. The first bracket is the aggregate’s excess over the best dictionary risk; the second is the dictionary’s approximation error. A bound on the first does not control the second.

A related caution is that the theorem’s uniform deviation term is a sufficient finite-sample bound, not a claim that every data set incurs exactly that much error. Also, convexity is used to transfer control of weighted candidate losses to the deterministic aggregate. Without the stated convexity and boundedness conditions, this proof does not establish the same result.

Worked Example: A Well-Fitting Dictionary Versus a Misspecified One

Consider two settings with the same sample size, prior, and confidence level, so that the theorem contributes the same estimation allowance $e$. In the first setting, suppose $R_*=0.10$ and the best dictionary risk is $0.11$. Then $a_{\mathcal D}=0.01$, and the bound relative to the reference risk is $R(\widehat f)-R_*\leq0.01+e$. In a second setting, suppose $R_*=0.10$ but the best dictionary risk is $0.35$. Now $a_{\mathcal D}=0.25$, so the corresponding guarantee is $R(\widehat f)-R_*\leq0.25+e$.

The estimation allowance is identical in both calculations; the difference is entirely the candidate dictionary’s approximation quality. This comparison explains why a report of the estimation term alone is incomplete when the scientific target may lie outside the candidate set.

Key takeaway: The oracle bound separates the price of competing with a dictionary comparator from the dictionary’s own distance to the ideal risk. Estimation control establishes competitiveness; approximation control establishes adequacy.

Check Your Understanding

Answer each question using the definitions and conditions above.

What quantity is the approximation error when the reference risk is $R_*$ and the best dictionary candidate has risk $R_{j_*}$?
For a comparator concentrated on candidate $j$, what does the prior-complexity term become?
Why does the proof require convexity of the loss in the prediction for the deterministic aggregate?
If the estimation terms tend to zero as the sample size grows but the approximation error is positive, what can the oracle comparison conclude relative to $R_*$?
With $M=4$, a uniform prior, and comparator $j$, express its prior penalty as a function of $\eta$ and $n$.