Why Approximate Inference Needs Its Own Error Term
A structured prediction problem may have too many feasible outputs to search exhaustively. A decoder can therefore return an output whose conditional task risk is close to, but not necessarily equal to, the minimum. That optimization shortfall is inference error. Separately, the conditional distribution used by the decoder may be estimated from data and differ from the true conditional distribution. That discrepancy is estimation error. A risk guarantee should make both sources visible rather than treating an approximate solution as an exact Bayes decision.
The distinction matters even when the decoder is highly accurate computationally. Exact optimization under an estimated distribution eliminates inference error, but it does not generally eliminate the gap between the resulting decision and the best decision under the true distribution. Conversely, a perfect conditional distribution does not make an approximate search procedure exact.
Conditional Task Risk and Approximate Optimality
Fix an input \(x\). Let \(\mathcal Y\) be a finite outcome space and \(\mathcal A\) a finite set of feasible actions or predictions. The true conditional distribution of the outcome is \(p_x(y)=P(Y=y\mid X=x)\). A task loss \(\Delta(a,y)\) measures the cost of taking action \(a\) when the outcome is \(y\). Its conditional risk is the expected task loss under the conditional distribution.
The value \(R^*_{p_x}\) is the conditional Bayes risk. An action minimizing it is a Bayes action. If the decoder instead uses an estimated conditional distribution \(q_x\), define \(R_{q_x}(a)\) in the same way, replacing \(p_x\) by \(q_x\). We measure distributional discrepancy by total variation distance, using the convention \(\operatorname{TV}(p_x,q_x)=\frac12\sum_y|p_x(y)-q_x(y)|\).
This definition concerns the optimization criterion itself: it does not presume that \(q_x\) is close to \(p_x\). The following result relates the two distributions to the task-risk error. Assume throughout the result that \(0\leq\Delta(a,y)\leq M\) for every feasible \(a\) and outcome \(y\), for a finite constant \(M\).
Proof. Write \(d_y=p(y)-q(y)\), so \(\sum_y d_y=0\). The sum of the positive \(d_y\)'s and the absolute sum of the negative \(d_y\)'s are both \(\operatorname{TV}(p,q)\). Since each loss value lies between 0 and \(M\), the largest possible value of \(\sum_y d_y\Delta(a,y)\) is at most \(M\) times the sum of the positive \(d_y\)'s. Its smallest possible value is at least \(-M\) times the absolute sum of the negative \(d_y\)'s. Thus the absolute value of this sum is at most \(M\operatorname{TV}(p,q)\). This sum is \(R_p(a)-R_q(a)\), proving the claim. \(\square\)
A Regret Bound for an Approximate Decoder
The lemma controls the risk discrepancy for any fixed action. To compare the decoder’s action with the true Bayes action, we also need to account for the fact that the minimizing action itself can differ between \(p_x\) and \(q_x\).
Proof. For brevity, write \(p=p_x\), \(q=q_x\), and \(a=\hat a(x)\). Choose an action \(a_p^*\) attaining \(\min_{a\in\mathcal A}R_p(a)\), which exists because \(\mathcal A\) is finite. Add and subtract \(R_q(a)\) and \(R_q(a_p^*)\):
The first and third bracketed terms are each at most \(M\operatorname{TV}(p,q)\), by the lemma. Approximate optimality implies \(R_q(a)\leq\min_bR_q(b)+\delta(x)\leq R_q(a_p^*)+\delta(x)\), so the middle term is at most \(\delta(x)\). Adding these bounds gives the result. \(\square\)
The two distribution-discrepancy terms are needed because both the returned action’s risk and the benchmark risk are evaluated under \(p_x\), while the approximate optimization guarantee is under \(q_x\). The bound is an upper bound, not usually an exact decomposition: the two sources of error can interact, and the inequality may be conservative.
Worked Example: A Three-Class Decoder
Suppose the possible labels and predictions are \(1,2,3\), and the task loss is zero-one loss: \(\Delta(a,y)=1\) if \(a\ne y\), and 0 otherwise. Let \(p=(0.6,0.3,0.1)\) and \(q=(0.5,0.4,0.1)\). The loss is bounded by \(M=1\).
Under \(q\), the risks of predicting labels \(1,2,3\) are respectively \(1-0.5=0.5\), \(1-0.4=0.6\), and \(1-0.1=0.9\). If the decoder returns label 2, its inference error is \(\delta=0.6-0.5=0.1\). The total variation distance is \(\frac12(|0.6-0.5|+|0.3-0.4|+|0.1-0.1|)=0.1\).
Under the true distribution \(p\), the risks are \(0.4,0.7,0.9\). The true Bayes action is label 1, so the returned label 2 has excess risk \(0.7-0.4=0.3\). The theorem gives the bound \(0.1+2(1)(0.1)=0.3\), exactly matching this excess risk.
From Conditional Regret to Population Risk
A predictor is evaluated over inputs as well as outcomes. The conditional guarantee can be averaged over the input distribution, and—if the estimated distribution or decoder depends on a training sample—over that sample too. The result below requires the conditional inequality to hold for almost every input and training sample, with measurable risks and outputs so that the expectations are defined.
Derivation. The theorem gives the stated upper bound for almost every realization of the input and training sample. Both sides are nonnegative and measurable under the stated conditions, so taking expectations preserves the inequality. Linearity of expectation gives \(E[\delta(X)+2M\operatorname{TV}(p_X,q_X)]=E[\delta(X)]+2M E[\operatorname{TV}(p_X,q_X)]\). No independence between the decoder’s inference error and its distributional estimation error is required. \(\square\)
Worked Example: Exact-Match Decoding of a Short Sequence
Consider four possible two-symbol sequences, \(00,01,10,11\), and use exact-match loss: the loss is zero for a correct sequence and one otherwise. Let the true probabilities in that order be \(p=(0.42,0.28,0.18,0.12)\), and let the decoder’s estimated probabilities be \(q=(0.35,0.35,0.20,0.10)\).
Under exact-match loss, the risk of predicting a sequence is one minus its probability. The minimum \(q\)-risk is \(1-0.35=0.65\), attained by either \(00\) or \(01\). Suppose an approximate search returns \(10\), whose \(q\)-risk is \(1-0.20=0.80\). Its inference error is therefore \(\delta=0.80-0.65=0.15\).
The total variation distance is \(\frac12(0.07+0.07+0.02+0.02)=0.09\). Under \(p\), the minimum risk is \(1-0.42=0.58\), attained by \(00\), while the risk of \(10\) is \(1-0.18=0.82\). The excess risk is \(0.82-0.58=0.24\). The theorem bounds it by \(0.15+2(1)(0.09)=0.33\). The bound is not tight here, but it separately charges \(0.15\) for approximate search and at most \(0.18\) for distributional discrepancy.
Worked Example: Averaging Over Two Input Types
Let \(X\) take values \(x_1,x_2\), each with probability \(1/2\). Use binary zero-one loss. At \(x_1\), suppose \(p_{x_1}=(0.8,0.2)\), \(q_{x_1}=(0.7,0.3)\), and the decoder returns label 2. At \(x_2\), suppose \(p_{x_2}=(0.4,0.6)\), \(q_{x_2}=(0.45,0.55)\), and it returns label 2.
At \(x_1\), the true Bayes risk is \(0.2\), while the returned label has true risk \(0.8\), giving excess risk \(0.6\). Under \(q_{x_1}\), label 1 has risk \(0.3\) and label 2 has risk \(0.7\), so \(\delta(x_1)=0.4\). Also, \(\operatorname{TV}(p_{x_1},q_{x_1})=0.1\), and the pointwise bound is \(0.4+2(0.1)=0.6\).
At \(x_2\), label 2 is optimal under both distributions. Its true excess risk is 0 and \(\delta(x_2)=0\). The total variation distance is \(0.05\), giving a bound of \(0.10\). Averaging, the actual population excess risk is \(\frac12(0.6+0)=0.30\). The corollary bounds it by \(\frac12(0.4+0)+2\frac12(0.1+0.05)=0.20+0.15=0.35\).
Using the Bound and Avoiding a Common Mistake
The result is useful when a task loss is bounded and a decoder can provide an additive optimization guarantee, even if the output space is too large for exact search. It also clarifies what evidence is needed to support a task-risk claim: a guarantee on the decoder’s optimization gap controls inference error, while a guarantee on the estimated conditional distribution controls estimation error. The earlier material on surrogate-to-task excess-risk transfer concerns a different link in the analysis; it does not make these two decoder-level errors interchangeable.
- If inference is exact under \(q_x\): set \(\delta(x)=0\), but the term \(2M\operatorname{TV}(p_x,q_x)\) remains.
- If the conditional distribution is correct: set \(q_x=p_x\), so the bound reduces to the decoder’s additive inference error \(\delta(x)\).
- If both are controlled: the task excess risk is bounded by their combined contributions, with the estimation contribution scaled by the loss range.
Common mistake: counting only one distribution-discrepancy term. One might compare the returned action’s true risk with its estimated risk and conclude that the excess risk is at most \(\delta+M\operatorname{TV}(p,q)\). That comparison controls the returned action alone; it does not account for the fact that the true Bayes benchmark may also have a different risk under \(q\). The proof compares both actions across distributions, producing two terms and the factor \(2M\). The factor can sometimes be improved with additional structure, but it cannot be dropped from this general argument.
Another pitfall is to call every failure of a decoder “estimation error.” A search procedure can fail to find the best action even when its input distribution is known exactly; that is inference error. A decoder can also optimize its estimated risk exactly and still select a suboptimal action under the true distribution; that is estimation error. Keeping the two quantities separate makes both computational and statistical improvements interpretable.
Check Your Understanding
Use the definitions and bounds above to answer these questions.
- For loss values in \([0,M]\), what is the largest possible risk difference for a fixed action when two outcome distributions have total variation distance \(t\)?
- Why does the approximate-decoder theorem contain two distribution-discrepancy terms rather than one?
- If a decoder is exact under an estimated distribution, which term in the regret bound is zero, and which may remain?
- In the sequence example, verify the total variation distance by listing the four absolute probability differences before dividing their sum by two.
- In the two-input example, explain why averaging the pointwise guarantees does not require independence between estimation error and inference error.