A Fixed-Point Bound for Excess Risk

From Local Complexity to an Excess-Risk Guarantee

A localized complexity fixed point describes the scale at which the empirical fluctuations of low-risk candidates become comparable to their population excess risk. To turn that scale into a guarantee for an empirical risk minimizer, one also needs a deviation inequality: on a high-probability event, it must relate population excess risk to empirical excess risk and localized complexity. The fixed-point calculation then controls the complexity term at the unknown risk of the selected estimator.

The confidence level matters as well. Under a boundedness-based deviation inequality, the confidence contribution generally has square-root dependence on the logarithm of the inverse failure probability. A term of order $\log(1/\delta)/n$ requires stronger control than boundedness alone; it is not a free consequence of the fixed-point argument.

Excess-Loss Classes and Localized Complexity

Let $Z_1,\ldots,Z_n$ be independent observations from a distribution $P$. For a predictor $f$, write its loss on observation $z$ as $\ell_f(z)$, and let $f_*$ be a risk minimizer in the comparison class. Define the excess-loss function $g_f(z)=\ell_f(z)-\ell_{f_*}(z)$. Its population excess risk is $Pg_f=E[g_f(Z)]$, and its empirical excess risk is $P_ng_f=n^{-1}\sum_{i=1}^n g_f(Z_i)$.

Write $\mathcal G$ for the resulting class of excess-loss functions. The risk minimizer ensures $Pg\geq 0$ for every $g\in\mathcal G$. For $r\geq0$, the localized class contains functions whose population excess risk is at most $r$. Its expected Rademacher complexity measures the size of signed empirical fluctuations within that class.

Definition: Let $\mathcal G(r)=\{g\in\mathcal G:Pg\leq r\}$. Its expected localized Rademacher complexity is $$ \mathcal R_n(r)=E_{Z,\varepsilon}\left[\sup_{g\in\mathcal G(r)} \frac{1}{n}\sum_{i=1}^n\varepsilon_i g(Z_i)\right], $$ where $\varepsilon_1,\ldots,\varepsilon_n$ are independent random signs, each equal to $1$ or $-1$ with probability $1/2$, independent of the data. Assume the suprema are measurable (or that a standard measurable-separability condition makes them well-defined).

A common upper bound on $\mathcal R_n(r)$ is a sub-root function. For the fixed-point argument here, it is important to include nondecreasingness among its conditions.

Definition: A function $\psi:[0,\infty)\to[0,\infty)$ is sub-root here if it is continuous, $\psi(0)=0$, nondecreasing, and $r\mapsto\psi(r)/\sqrt r$ is nonincreasing on $r>0$. We assume it has a unique positive fixed point $r_*$, so $\psi(r_*)=r_*$. In applications, $\psi(r)$ is an upper bound for $\mathcal R_n(r)$.

The fixed point identifies the scale at which the complexity envelope meets the risk radius. Its main use is the following envelope bound.

Lemma: If $\psi$ satisfies the sub-root conditions above and $\psi(r_*)=r_*$ for $r_*>0$, then $$ \psi(r)\leq r_* \quad (0\leq r\leq r_*), \qquad \psi(r)\leq\sqrt{r r_*}\quad (r\geq r_*). $$

Proof. If $r\leq r_*$, nondecreasingness gives $\psi(r)\leq\psi(r_*)=r_*$. If $r\geq r_*$, the ratio condition gives $\psi(r)/\sqrt r\leq\psi(r_*)/\sqrt{r_*}=\sqrt{r_*}$. Multiplying by $\sqrt r$ proves the second inequality. $\square$

Worked Example: Finding a Sub-Root Fixed Point

Suppose an upper bound on localized complexity is $\psi(r)=a\sqrt{r/n}$, where $a>0$. This function is continuous, nonnegative and nondecreasing, and $\psi(r)/\sqrt r=a/\sqrt n$ is constant for $r>0$. Thus it satisfies the stated sub-root conditions.

To find its positive fixed point, solve $r=a\sqrt{r/n}$. Squaring both sides gives $r^2=a^2r/n$. Since the positive solution has $r>0$, division by $r$ gives $$ r_*=\frac{a^2}{n}. $$ Substitution checks the answer: $\psi(a^2/n)=a\sqrt{a^2/n^2}=a^2/n=r_*$. The envelope for $r\geq r_*$ is $\psi(r)\leq\sqrt{r a^2/n}$.

The Deviation Input and Fixed-Point Bound

The fixed-point lemma by itself is deterministic; it does not say that empirical and population risks are close. The theorem below makes the required concentration input explicit. This separation matters: boundedness supplies an envelope for concentration arguments, but boundedness alone does not automatically establish every localized deviation inequality.

Localized deviation hypothesis: For some envelope bound $b>0$, complexity envelope $\psi$, and constant $K>0$, suppose that for every $0<\delta<1$, with probability at least $1-\delta$, the following inequality holds simultaneously for all $g\in\mathcal G$: $$ Pg\leq P_ng+2\psi(Pg)+K b\sqrt{\frac{\log(2/\delta)}{n}}. $$ Here $\psi(r)$ upper-bounds the expected localized Rademacher complexity at radius $r$, and satisfies the sub-root conditions with positive fixed point $r_*$.

A typical bounded-loss setting has $0\leq\ell_f(z)\leq b$ for every predictor under consideration and every $z$, so $|g_f(z)|\leq b$. The deviation hypothesis must still be justified for the class and localization scheme at hand; the theorem does not infer it from boundedness alone. We also require an empirical risk minimizer $\hat f$ over the comparison class, or at least a candidate whose empirical excess risk satisfies $P_ng_{\hat f}\leq0$.

Theorem: Under the localized deviation hypothesis, suppose $0\in\mathcal G$, $Pg\geq0$ for all $g\in\mathcal G$, and an empirical risk minimizer $\hat f$ satisfies $g_{\hat f}\in\mathcal G$ and $P_ng_{\hat f}\leq0$. Then, with probability at least $1-\delta$, $$ Pg_{\hat f}\leq 4r_*+2K b\sqrt{\frac{\log(2/\delta)}{n}}. $$

Proof. Work on the event in the deviation hypothesis, and set $R=Pg_{\hat f}\geq0$ and $q=K b\sqrt{\log(2/\delta)/n}$. Applying the inequality to $g_{\hat f}$, and using $P_ng_{\hat f}\leq0$, gives $R\leq2\psi(R)+q$.

If $R\leq r_*$, then $R\leq4r_*+2q$ immediately. If $R>r_*$, the fixed-point envelope gives $\psi(R)\leq\sqrt{Rr_*}$, and hence $R\leq2\sqrt{Rr_*}+q$. The elementary inequality $2\sqrt{Rr_*}\leq R/2+2r_*$ follows by expanding $(\sqrt{R/2}-\sqrt{2r_*})^2\geq0$. Therefore $R\leq R/2+2r_*+q$, so $R\leq4r_*+2q$. Substituting the definition of $q$ proves the claim. $\square$

Worked Example: Substituting a Confidence Level

Suppose $n=400$, $\psi(r)=2\sqrt{r/n}$, $b=1$, $K=2$, and $\delta=0.05$. The fixed point from the preceding calculation is $r_*=2^2/400=0.01$. Also, $\log(2/\delta)=\log(40)\approx3.689$, so the confidence term inside the theorem is $$ K b\sqrt{\frac{\log(2/\delta)}{n}} =2\sqrt{\frac{3.689}{400}} \approx2(0.0960)=0.1920. $$ The theorem therefore gives $Pg_{\hat f}\leq4(0.01)+2(0.1920)=0.424$, with probability at least $0.95$. This is a valid, potentially conservative guarantee under the deviation hypothesis; it is not a claim that the actual excess risk equals $0.424$.

Why the Assumptions and Confidence Term Matter

The proof uses the fixed point only after the deviation inequality has been applied at the estimator’s own population risk. The envelope controls $\psi(R)$ at that unknown radius. In particular, nondecreasingness controls $\psi(r)$ below the fixed point, while the ratio condition controls it above the fixed point. Neither role can be silently dropped.

The stated confidence contribution is proportional to $\sqrt{\log(2/\delta)/n}$. Replacing it with a term proportional to $\log(2/\delta)/n$ requires a stronger deviation input, typically one that exploits additional variance structure. Bounded losses alone do not justify that replacement. This distinction is useful when interpreting a bound: the fixed-point complexity scale and the confidence scale come from different parts of the argument.

Worked Example: Why Monotonicity Cannot Be Omitted

Consider $\psi(r)=\sqrt r\,e^{-10r}$ for $r\geq0$, with $\psi(0)=0$. For $r>0$, $\psi(r)/\sqrt r=e^{-10r}$ is nonincreasing, but $\psi$ itself is not nondecreasing. A positive fixed point solves $\sqrt r e^{-10r}=r$, or equivalently $e^{-10r}/\sqrt r=1$. The left side decreases strictly from infinity to zero, so there is a unique positive solution.

At $r=0.05$, $e^{-0.5}\approx0.6065>\sqrt{0.05}\approx0.2236$, so $\psi(r)>r$. At $r=0.12$, $e^{-1.2}\approx0.3010<\sqrt{0.12}\approx0.3464$, so $\psi(r)<r$. Thus $0.05<r_*<0.12$. But $\psi(0.05)=\sqrt{0.05}e^{-0.5}\approx0.1357>0.12>r_*$. Consequently, the claim $\psi(r)\leq r_*$ for $r\leq r_*$ would fail for this function. The correction is to require nondecreasingness, as in the definition used in the lemma.

Common Mistake

Using the fixed-point envelope without checking its conditions. The reasoning “$r\leq r_*$, so $\psi(r)\leq\psi(r_*)$” is valid only if $\psi$ is nondecreasing. The condition that $\psi(r)/\sqrt r$ is nonincreasing does not imply that $\psi$ is nondecreasing. State and verify both properties before using the two-part envelope.
Attributing the whole guarantee to complexity. The fixed point does not itself compare empirical and population risks. The deviation inequality and the empirical minimizer’s property are also essential.
Changing the confidence rate without a new assumption. A bound with a $\log(1/\delta)/n$ term cannot be obtained merely by algebraically simplifying the square-root confidence term. It requires a stronger concentration input.

Key takeaway: A sub-root fixed point controls localized complexity through $\psi(r)\leq r_*$ below the fixed point and $\psi(r)\leq\sqrt{rr_*}$ above it, provided $\psi$ is also nondecreasing. Combined with an explicit localized deviation inequality and empirical optimality, this yields a high-probability excess-risk bound.

Check Your Understanding

Check the assumptions and the algebra in each question.

For $\psi(r)=a\sqrt{r/n}$, find the positive fixed point and verify it by substitution.
Which sub-root condition justifies $\psi(r)\leq r_*$ when $r\leq r_*$?
In the theorem’s proof, where is the empirical risk minimizer’s property $P_ng_{\hat f}\leq0$ used?
What is the confidence contribution when $K=1$, $b=2$, $n=100$, and $\delta=0.05$?
Why does boundedness alone not justify replacing the square-root confidence contribution by a term of order $\log(1/\delta)/n$?