Inverting Calibration Bounds for Classification Rates

From Surrogate Error to Classification Regret

A surrogate loss is useful for classification only if its excess risk controls the excess zero-one risk of the classifier it produces. The calibration function gives this control on the surrogate-risk scale: it tells us how much surrogate excess risk must accompany a specified amount of classification regret. To turn a surrogate guarantee into a classification guarantee, we reverse that relationship.

Write \(R(h)\) for the zero-one risk of a classifier \(h\), and \(R^*=\inf_h R(h)\) for the optimal zero-one risk. For a score function \(s\), let \(h_s\) be its associated classifier, and write \(R_\phi(s)\) for its risk under a surrogate loss \(\phi\). Let \(R_\phi^*=\inf_s R_\phi(s)\), where the infimum is over the score functions under consideration. Their excess risks are

The calibration inequality is the starting point. In what follows, assume it holds for every score function under consideration. The bound we derive is deterministic; if a surrogate-risk bound holds only on an event, the classification bound holds on that same event.

The inequality says that classification regret is first passed through \(\psi\), and the result is no larger than surrogate excess risk. If \(\psi\) is strictly increasing, this suggests applying its inverse. A generalized inverse makes the same operation precise even if \(\psi\) has flat portions.

The Inverse Calibration Bound

For \(\delta\geq 0\), define the generalized inverse

The set in this definition is nonempty because \(\psi(0)=0\). Its supremum lies in \([0,1]\), so the definition automatically respects the largest possible classification regret. If \(\psi\) is continuous and strictly increasing, this is its ordinary inverse for \(\delta<\psi(1)\), and it equals 1 for \(\delta\geq\psi(1)\).

Proof. The calibration inequality and the assumed surrogate bound give \(\psi(\Delta(h_s))\leq\Delta_\phi(s)\leq\delta\). Thus \(\Delta(h_s)\) belongs to the set whose supremum defines \(\psi^{\leftarrow}(\delta)\). Every element of that set is at most its supremum. Therefore \(\Delta(h_s)\leq\psi^{\leftarrow}(\delta)\). \(\square\)

For a strictly increasing calibration function, the theorem is ordinary inversion: apply \(\psi^{-1}\) to both sides of \(\psi(\Delta(h_s))\leq\delta\). The generalized-inverse proof does not require strict increase or continuity. It also shows why the bound is clipped at 1: no classifier can have excess zero-one risk greater than 1.

Power-Law Calibration

A common form, especially near zero, is a power law. For an exact power-law calibration function \(\psi(u)=c u^q\) on \([0,1]\), where \(c>0\) and \(q>0\), inversion gives a simple expression.

Derivation. The condition \(\psi(u)\leq\delta\) is \(c u^q\leq\delta\). Since \(c>0\) and \(q>0\), this is equivalent to \(u\leq(\delta/c)^{1/q}\). Restricting \(u\) to \([0,1]\), the largest admissible value is \((\delta/c)^{1/q}\) if that value is less than 1, and 1 otherwise. This gives the stated formula.

For small \(\delta\), the inverse is proportional to \(\delta^{1/q}\). Thus an excess surrogate risk of order \(n^{-\beta}\) yields a classification-regret bound of order \(n^{-\beta/q}\), when the same power law applies in the relevant range. Larger \(q\) means a flatter calibration function near zero and, consequently, a weaker rate after inversion.

Local Power Laws and Rates

Some calibration functions are not exact power laws on the entire interval \([0,1]\). A local lower bound is often enough. If \(\psi(u)\geq c u^q\) for \(0\leq u\leq u_0\), and a surrogate excess-risk bound \(\delta\) is smaller than \(\psi(u_0)\), then any regret \(r\) satisfying \(\psi(r)\leq\delta\) must be below \(u_0\). The power-law lower bound can then be inverted within its valid range.

Proof. Set \(r=\Delta(h_s)\). Calibration gives \(\psi(r)\leq\delta\). If \(r\geq u_0\), monotonicity would imply \(\psi(r)\geq\psi(u_0)>\delta\), a contradiction. Hence \(r<u_0\), where the local lower bound applies. Therefore \(c r^q\leq\psi(r)\leq\delta\), and taking the positive \(q\)th root yields \(r\leq(\delta/c)^{1/q}\). \(\square\)

Using the Bound Correctly

The inverse calculation is short, but it is easy to reverse the relationship or use a calibration function outside the range where it is valid. Keep the direction of the calibration inequality explicit: \(\psi(\text{classification regret})\leq\text{surrogate excess risk}\). The task is to bound the regret by applying an inverse, not to apply \(\psi\) to the surrogate bound.

• Wrong: If \(\psi(u)=u^2/2\) and surrogate excess risk is at most \(\delta\), conclude regret is at most \(\psi(\delta)=\delta^2/2\). Correction: Invert the inequality to obtain the bound \(\sqrt{2\delta}\), clipped at 1.
• Wrong: Treat a local approximation near zero as an exact formula for every regret value. Correction: Check that the resulting bound lies in the range where the power-law lower bound holds; the local result above states a sufficient condition.
• Wrong: Apply a high-probability surrogate bound and report the classification conclusion as certain. Correction: The inverse argument preserves the event and its probability; it does not remove the uncertainty in the original bound.
• Wrong: Ignore the range of possible classification regret when the inverse expression exceeds 1. Correction: Use the clipped bound, since excess zero-one risk cannot exceed 1.

The shape of \(\psi\) is therefore more than a technical detail. It determines how efficiently a surrogate-risk guarantee transfers to classification. When \(\psi(u)\) behaves like \(c u^q\) near zero, the exponent \(1/q\) controls the conversion of small surrogate errors into small classification regret.