Tie-Breaking and Nonunique Empirical Minimizers

Why Ties Change the Consistency Question

Empirical risk minimization can return more than one hypothesis. When several hypotheses attain the same smallest training risk, a learning rule must either choose one of them or leave the answer set-valued. These are different statistical questions: does the chosen hypothesis have vanishing excess risk, or do all empirical minimizers have vanishing excess risk?

The distinction matters because a favorable choice can hide a poor alternative. A particular tie-breaking rule might always select a good minimizer, even when another minimizer has high population risk. To guarantee that the minimization problem itself is reliable, the guarantee must hold simultaneously for every empirical minimizer.

Definition: Let $Z_1,\ldots,Z_n$ be independent and identically distributed observations from a distribution $P$, and let $\ell(h;z)$ be the loss of hypothesis $h$ on observation $z$. Define the population risk and empirical risk by $$ R(h)=E[\ell(h;Z)], \qquad R_n(h)=\frac{1}{n}\sum_{i=1}^n \ell(h;Z_i). $$ Let $R^*=\inf_{h\in\mathcal H}R(h)$. The excess risk of $h$ is $R(h)-R^*$. An exact empirical minimizer belongs to $M_n=\operatorname{argmin}_{h\in\mathcal H}R_n(h)$.

We consider finite population risks and assume the empirical minimizer set is nonempty with probability one whenever exact minimizers are discussed. A selected empirical minimizer is a measurable choice $\hat h_n\in M_n$. It is risk consistent if $R(\hat h_n)-R^*\xrightarrow{p}0$. By contrast, consistency of every empirical minimizer means that the largest excess risk among the minimizers vanishes:

\sup_{h\in M_n}\{R(h)-R^*\}\xrightarrow{p}0.

The second statement implies consistency of any measurable selected minimizer. The converse does not follow: controlling one chosen member of $M_n$ says nothing by itself about the other members.

A Bound That Covers Every Minimizer

The key quantity is the uniform deviation between empirical and population risk,

D_n=\sup_{h\in\mathcal H}|R_n(h)-R(h)|.

Assume the supremum is measurable (or use the corresponding outer-probability formulation). When $D_n$ is small, empirical risk is close to population risk for every hypothesis at once. This simultaneous control is what lets the following result apply to all ties rather than just to one selected minimizer.

Theorem: Suppose $M_n$ is nonempty and $D_n$ is finite almost surely. Then, almost surely, $$ \sup_{h\in M_n}\{R(h)-R^*\}\leq 2D_n. $$ Consequently, if $D_n\xrightarrow{p}0$, every empirical minimizer has vanishing excess risk in the simultaneous sense.

Proof. Fix a sample and any $h\in M_n$. For every $g\in\mathcal H$, the definition of $D_n$ gives $R(h)\leq R_n(h)+D_n$ and $R_n(g)\leq R(g)+D_n$. Since $h$ minimizes empirical risk, $R_n(h)\leq R_n(g)$. Therefore $$ R(h)\leq R_n(h)+D_n\leq R_n(g)+D_n\leq R(g)+2D_n. $$ This holds for every $g$, so taking the infimum over $g\in\mathcal H$ yields $R(h)\leq R^*+2D_n$. The bound holds for every $h\in M_n$; taking the supremum over that set proves the inequality. If $D_n\xrightarrow{p}0$, then for any $\varepsilon>0$, $$ P\!\left(\sup_{h\in M_n}\{R(h)-R^*\}>\varepsilon\right) \leq P(D_n>\varepsilon/2)\longrightarrow 0. $$ Thus every empirical minimizer has vanishing excess risk. $\square$

Worked Example: Turning a Deviation Bound Into an All-Minimizers Guarantee

Suppose that on a given sample $D_n\leq 0.03$, and the empirical minimizer set contains several hypotheses. The theorem gives, for each $h\in M_n$, $$ R(h)-R^*\leq 2D_n\leq 2(0.03)=0.06. $$ So even the worst population risk among the tied minimizers is at most $0.06$ above the best risk in the class. The conclusion is not merely that a particular tie-breaking choice is good; it bounds every member of the set.

If instead $P(D_n>0.03)\leq 0.05$, then $$ P\!\left(\sup_{h\in M_n}\{R(h)-R^*\}>0.06\right) \leq P(D_n>0.03)\leq 0.05. $$ Thus the simultaneous excess-risk bound holds with probability at least $0.95$.

Approximate Minimizers and Optimization Tolerance

In computation, an optimizer may return a hypothesis whose empirical risk is close to the minimum rather than exactly equal to it. The same argument handles this situation, provided the tolerance is included in the guarantee.

Definition: For $\eta_n\geq 0$, an $\eta_n$-approximate empirical minimizer is any $h\in\mathcal H$ satisfying $$ R_n(h)\leq \inf_{g\in\mathcal H}R_n(g)+\eta_n. $$

Derived bound. For every such $h$, and every $g\in\mathcal H$, uniform deviation and the approximate-minimization condition give $$ R(h)\leq R_n(h)+D_n \leq \inf_{u\in\mathcal H}R_n(u)+\eta_n+D_n \leq R_n(g)+\eta_n+D_n \leq R(g)+\eta_n+2D_n. $$ Taking the infimum over $g$ proves $$ R(h)-R^*\leq \eta_n+2D_n. $$ This bound holds simultaneously for all hypotheses satisfying the approximation condition. In particular, if $\eta_n\xrightarrow{p}0$ and $D_n\xrightarrow{p}0$, then the largest excess risk among the approximate minimizers also converges to zero in probability.

Worked Example: Accounting for a Nonzero Optimization Tolerance

Suppose the uniform deviation is at most $0.02$ and a numerical optimizer returns a hypothesis within $0.01$ of the smallest empirical risk. Here $D_n=0.02$ and $\eta_n=0.01$, so every hypothesis meeting that empirical tolerance satisfies $$ R(h)-R^*\leq 0.01+2(0.02)=0.05. $$ The factor of two comes from comparing population and empirical risk once for the candidate $h$, and once for the comparison hypotheses. Ignoring the optimization tolerance would incorrectly report the bound $0.04$.

When One Tie-Breaking Rule Is Not Enough

Worked Example: A Good Minimizer Tied With Persistently Bad Ones

Let $Z_1,\ldots,Z_n$ be independent Uniform$[0,1]$ observations. The loss is $\ell(h;z)=h(z)$. Include the hypothesis $h_0(z)=0$, and for each set $A$ in the following class include $h_A(z)=\mathbf 1\{z\in A\}$: take all sets that are unions of $m/2$ cells from the partition of $[0,1)$ into $m$ equal half-open intervals, for every positive even integer $m$. Every such set has probability $1/2$. Hence $$ R(h_0)=0,\qquad R(h_A)=\frac12,\qquad R^*=0. $$

For any fixed finite sample, choose an even $m\geq 4n$. At most $2n$ partition cells have a sample point in their closure, since each point lies in the closure of at most two cells. There are therefore at least $m-2n\geq m/2$ cells whose closures contain no sample point. Choose any $m/2$ of those cells and let $A$ be their union. Then every sample point lies outside $A$, so $R_n(h_A)=0$. Also $R_n(h_0)=0$. Since all empirical risks are nonnegative, both $h_0$ and $h_A$ are empirical minimizers.

The rule that always selects $h_0$ is a consistent empirical-minimizer selection: its excess risk is zero for every $n$. But for each sample there is also an empirical minimizer $h_A$ with excess risk $1/2$. Thus the largest excess risk among empirical minimizers does not converge to zero. The class of sets is countable, and a measurable bad selection can be made by enumerating its sets and choosing the first one that avoids the observed sample. This example isolates the role of ties: consistency of a favorable selection is not a guarantee about the whole minimizer set.

Reading the Guarantee Correctly

Uniform deviation is sufficient for the all-minimizers conclusion because its bound holds for every hypothesis simultaneously. The theorem does not say that every consistent empirical-minimizer selection must come from a uniformly convergent class, nor that uniform deviation is necessary for all possible ways of controlling minimizers. Its claim is the direct implication proved above.

The distinction is especially important when interpreting an algorithm. If a theorem analyzes a specific measurable tie-breaking rule, its conclusion concerns that rule's output. A claim about every empirical minimizer is stronger and requires an argument that controls the full set, such as the simultaneous deviation bound. If the optimization is approximate, the tolerance must also vanish, or else the bound may leave a nonvanishing excess-risk term.

Common Mistake

Wrong reasoning: “I have shown that the ERM output is consistent, so every empirical minimizer is consistent.” This silently replaces a statement about one selected hypothesis by a statement about all hypotheses attaining the minimum. In the worked tie example, the always-zero rule is consistent even though a bad empirical minimizer exists for every sample.

Correction: State which guarantee is being claimed. For a selected rule, analyze its chosen output. For an all-minimizers guarantee, bound the supremum of excess risk over the empirical minimizer set, or otherwise establish control that holds for every member of that set.

Key takeaway: Ties are harmless for consistency only when the guarantee controls all tied minimizers, or when the claim is explicitly limited to a particular selection rule. Under uniform risk convergence, every exact minimizer has excess risk at most twice the uniform deviation; approximate minimizers incur the additional optimization tolerance.

Check Your Understanding

Answer each question by distinguishing clearly between a selected minimizer and the full minimizer set.

Write the definition of consistency for one selected empirical minimizer and the simultaneous definition for every empirical minimizer.
Why does a bound on $R(\hat h_n)-R^*$ for one selected $\hat h_n$ not automatically bound the excess risk of other empirical minimizers?
If $D_n\leq 0.04$, what upper bound does the theorem give on the excess risk of every exact empirical minimizer?
If the empirical optimization tolerance is $\eta_n$, what is the resulting upper bound on the excess risk of an approximate minimizer?
In the Uniform$[0,1]$ example, why can both a zero-risk hypothesis and a hypothesis of risk $1/2$ attain empirical risk zero?