Finite-Candidate Selection Under Absolute Error

Why Absolute Error Changes the Prediction Target

When a response is numerical, a finite dictionary can be selected by comparing its candidates on observed data. Under absolute error, the comparison is particularly transparent when responses and predictions are bounded: every loss is bounded, so concentration gives a finite-sample oracle guarantee. But the target of absolute-error prediction is not generally the target of squared-error prediction. At a fixed covariate value, a conditional median minimizes expected absolute error; a conditional mean minimizes expected squared error.

The distinction matters even if the same finite-selection procedure is used for both losses. The selection guarantee compares the chosen candidate with the best candidate in the dictionary under the chosen risk. It does not say that this best candidate is the conditional median or mean at every covariate value.

Absolute-Error Risk and Empirical Selection

Let \((X_i,Y_i)\), \(i=1,\ldots,n\), be independent and identically distributed observations of a covariate \(X\) and a real-valued response \(Y\). Suppose the finite dictionary consists of fixed measurable predictors \(f_1,\ldots,f_M\), where \(M\geq 1\). For a new pair \((X,Y)\) from the same distribution, define the risk of candidate \(j\) by

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

The empirical risk minimizer is any index \(\hat j\in\operatorname*{arg\,min}_{1\leq j\leq M}\widehat R_j\). A fixed rule can break ties. The oracle index \(j^*\) minimizes population risk over this same dictionary: \(j^*\in\operatorname*{arg\,min}_{1\leq j\leq M}R_j\). This oracle is a benchmark, not a procedure available to the analyst: its definition uses the unknown distribution.

Definition: The finite-dictionary oracle risk is \(\min_{1\leq j\leq M}R_j\). The selection excess risk is \(R_{\hat j}-\min_{1\leq j\leq M}R_j\), the difference between the selected candidate’s population risk and the best risk available in the dictionary.

Assume that \(Y\in[a,b]\) almost surely and that every candidate prediction lies in \([a,b]\) for every covariate value, where \(a<b\). Then each absolute loss lies in \([0,B]\), with \(B=b-a\). More generally, the argument below applies whenever all candidate losses are almost surely in a common interval of length \(B\).

Worked Example: Selecting Among Three Constant Predictors

Suppose the observed responses are \(0,0,1,3\), and the dictionary consists of the constant predictions \(f_1(x)=0.5\), \(f_2(x)=1.5\), and \(f_3(x)=2.5\). Calculate the empirical risks and select a candidate.

For \(f_1\), the four absolute errors are \(0.5,0.5,0.5,2.5\). Their sum is \(4\), so \(\widehat R_1=4/4=1\).

For \(f_2\), the errors are \(1.5,1.5,0.5,1.5\), which sum to \(5\). Thus \(\widehat R_2=5/4=1.25\).

For \(f_3\), the errors are \(2.5,2.5,1.5,0.5\), which sum to \(7\). Thus \(\widehat R_3=7/4=1.75\). The empirical risk minimizer is \(f_1\), with empirical risk \(1\). This calculation identifies the sample winner; by itself, it does not establish that \(f_1\) has the smallest population risk.

A High-Probability Oracle Comparison

For each fixed candidate, the observed losses are independent, identically distributed random variables in \([0,B]\). Hoeffding’s inequality for independent variables in an interval of length \(B\) states that, for \(t>0\), \(P(|\widehat R_j-R_j|>t)\leq 2\exp(-2nt^2/B^2)\). Applying this bound to all \(M\) candidates gives a simultaneous guarantee.

Theorem: Suppose the observations are independent and identically distributed, the dictionary is fixed before observing them, and every candidate loss lies in a common interval of length \(B>0\) almost surely. For any \(0<\delta<1\), every empirical risk minimizer satisfies, with probability at least \(1-\delta\),

R_{\hat j}\leq \min_{1\leq j\leq M}R_j +B\sqrt{\frac{2\log(2M/\delta)}{n}}.

The excess risk is also at most \(B\), so the displayed penalty can be replaced by its minimum with \(B\).

Proof. Define \(Z=\max_{1\leq j\leq M}|\widehat R_j-R_j|\). The union bound and Hoeffding’s inequality give

P(Z>t) \leq \sum_{j=1}^M P(|\widehat R_j-R_j|>t) \leq 2M\exp\left(-\frac{2nt^2}{B^2}\right).

Set \(t=B\sqrt{\log(2M/\delta)/(2n)}\). Substitution makes the final expression equal to \(\delta\), so \(Z\leq t\) with probability at least \(1-\delta\). Let \(j^*\) be a population risk minimizer in the finite dictionary. Since \(\hat j\) minimizes empirical risk, \(\widehat R_{\hat j}\leq\widehat R_{j^*}\). Therefore,

\begin{aligned} R_{\hat j}-R_{j^*} &=(R_{\hat j}-\widehat R_{\hat j}) +(\widehat R_{\hat j}-\widehat R_{j^*}) +(\widehat R_{j^*}-R_{j^*})\\ &\leq |R_{\hat j}-\widehat R_{\hat j}| +|\widehat R_{j^*}-R_{j^*}|\\ &\leq 2Z\leq 2t =B\sqrt{\frac{2\log(2M/\delta)}{n}}. \end{aligned}

This is the claimed inequality. Also \(0\leq R_{\hat j}\leq B\) and \(R_{j^*}\geq0\), so their difference cannot exceed \(B\). \(\square\)

The bound has a \(\log M\) dependence on dictionary size and a \(1/\sqrt n\) dependence on sample size. It is a slow-rate comparison with the best candidate, not a guarantee of small risk in absolute terms: if every dictionary member performs poorly, the theorem only says the selected one is close to the best of those poor options.

Worked Example: Evaluating a Finite-Sample Penalty

Suppose \(n=200\), there are \(M=2\) fixed candidates, responses and predictions lie in \([0,2]\), and the desired failure probability is \(\delta=0.05\). Here the loss bound is \(B=2\), and \(2M/\delta=80\). The theorem gives the penalty

2\sqrt{\frac{2\log(80)}{200}} =2\sqrt{\frac{8.764053\ldots}{200}} =2\sqrt{0.0438203\ldots} \approx 0.418666.

Thus, with probability at least \(0.95\), the selected candidate’s risk exceeds the better candidate’s risk by at most approximately \(0.419\). This is a valid upper bound, not a claim that the realized excess risk equals the penalty. The bound is distribution-free under the stated assumptions and may be conservative.

Why the Conditional Median Minimizes Absolute Error

To identify the pointwise target, fix a covariate value \(x\) and let \(K_x\) be the conditional distribution of \(Y\) given \(X=x\). Suppose \(Y\) is bounded, so the conditional absolute risks below are finite. Write \(F_x(s)=K_x((-\infty,s])\) and \(q_x(t)=\int |y-t|\,K_x(dy)\). A median \(m\) of \(K_x\) is a value satisfying \(F_x(m-)\leq 1/2\leq F_x(m)\), where \(F_x(m-)=K_x((-\infty,m))\).

Proposition: For a bounded response distribution, every median minimizes \(q_x(t)\) over real \(t\). Thus, whenever a conditional median can be selected measurably as a function of \(X\), it minimizes conditional expected absolute error at each covariate value.

Proof. For any finite \(u<v\) and any fixed \(y\),

|y-v|-|y-u|=\int_u^v \operatorname{sign}(s-y)\,ds,

where the value assigned to the sign function at zero does not affect the integral. Since the integrand is bounded, Fubini’s theorem permits integration in either order against \(K_x\) and Lebesgue measure. A probability distribution has at most countably many atoms, so for almost every \(s\), \(\int\operatorname{sign}(s-y)\,K_x(dy)=2F_x(s)-1\). Consequently,

q_x(v)-q_x(u)=\int_u^v (2F_x(s)-1)\,ds.

If \(s<m\), then \(F_x(s)\leq F_x(m-)\leq 1/2\), so the integrand is nonpositive. If \(s>m\), then \(F_x(s)\geq F_x(m)\geq 1/2\), so the integrand is nonnegative. Taking \(u=t,v=m\) when \(t<m\) shows \(q_x(m)-q_x(t)\leq0\); taking \(u=m,v=t\) when \(t>m\) shows \(q_x(t)-q_x(m)\geq0\). Hence \(q_x(m)\leq q_x(t)\) for every \(t\), proving the result. \(\square\)

Boundedness here ensures the conditional risks are finite and the difference identity is meaningful. Without a finite first moment, absolute risks can all be infinite, and subtracting two such risks to obtain a finite difference would not be justified.

Worked Example: A Conditional Median and a Different Conditional Mean

At a particular covariate value, suppose the response is \(0\) with probability \(0.2\), \(4\) with probability \(0.5\), and \(10\) with probability \(0.3\). The cumulative probability reaches \(0.7\) at \(4\), while the probability strictly below \(4\) is \(0.2\). Thus \(4\) is a median. The conditional mean is

E[Y\mid X=x]=0(0.2)+4(0.5)+10(0.3)=5.

The absolute risk at the median is \(q_x(4)=0.2|0-4|+0.5|4-4|+0.3|10-4|=0.8+0+1.8=2.6\). At \(t=3.8\), \(q_x(3.8)=0.2(3.8)+0.5(0.2)+0.3(6.2)=0.76+0.10+1.86=2.72\). At the actual conditional mean \(5\), it is \(q_x(5)=0.2(5)+0.5(1)+0.3(5)=1+0.5+1.5=3\). So the mean is not an absolute-error minimizer in this example.

For squared error, the conditional mean performs better than the median here. The squared risks are \(E[(Y-5)^2\mid X=x]=0.2(25)+0.5(1)+0.3(25)=13\) and \(E[(Y-4)^2\mid X=x]=0.2(16)+0.5(0)+0.3(36)=14\).

The example verifies that the two losses can favor different prediction targets.

Mean Versus Median Under Squared Error

The comparison follows directly from a conditional squared-error decomposition. If \(E[Y^2\mid X=x]<\infty\), let \(\mu_x=E[Y\mid X=x]\). For any fixed prediction \(t\), expand \(Y-t=(Y-\mu_x)+(\mu_x-t)\) and take the conditional expectation. The cross term is zero because \(E[Y-\mu_x\mid X=x]=0\), giving

E[(Y-t)^2\mid X=x] =E[(Y-\mu_x)^2\mid X=x]+(t-\mu_x)^2.

The right-hand side is minimized at \(t=\mu_x\). By contrast, the absolute-error proposition identifies any conditional median as a minimizer. The distinction is therefore about the loss being optimized, not a difference in the data or covariates.

In the finite-dictionary setting, even these pointwise targets need not belong to the dictionary. The oracle risk is the smallest integrated risk among \(f_1,\ldots,f_M\); it may be larger than the risk of an unrestricted conditional-median predictor. The selection theorem compares against the finite oracle only.

Common Pitfall

A common mistake is to say that absolute-error selection estimates the conditional mean because the response is numeric, or to interpret the oracle bound as a guarantee that the selected prediction is a conditional median. Neither follows. The conditional median minimizes pointwise absolute risk among all real-valued predictions, while the empirical selection theorem compares a data-selected candidate only against the best fixed member of the specified finite dictionary. A dictionary may omit the conditional median, and predictors are assessed by their integrated population risks.

Key takeaway: With bounded absolute losses, empirical risk minimization over a fixed finite dictionary has a high-probability excess-risk penalty of order \(B\sqrt{\log(M/\delta)/n}\). Its loss-specific population target is the conditional median, not generally the conditional mean.

Check Your Understanding

Answer these questions using the definitions and results above.

What assumptions allow the finite-dictionary oracle bound, and which part of the guarantee depends on the number of candidates?
Why does the proof compare the selected candidate with the oracle using two uniform-deviation terms?
For a conditional distribution with probability \(0.4\) at \(0\) and probability \(0.6\) at \(5\), identify a median and the mean.
Can the finite-dictionary oracle be worse than a predictor that uses a conditional median at every covariate value? Explain.
Why is a finite first moment relevant when deriving a difference identity for conditional absolute risks?