The Sub-Root Fixed-Point Lemma

Why a Fixed Point Matters

In localized learning arguments, a complexity bound often depends on the radius at which it is evaluated. The relevant radius is then chosen where the complexity curve meets the identity line. The sub-root fixed-point lemma makes this choice precise: under suitable conditions, there is exactly one positive intersection, and the curve is controlled on both sides of it.

This tutorial concerns that lemma and its consequences, not a general excess-risk bound. The key condition is stronger than ordinary monotonicity: after dividing the function by the square root of its argument, the resulting ratio must be nonincreasing. This restriction is what yields useful comparisons at every radius, not just at the fixed point.

Definition: A function $\psi:[0,\infty)\to[0,\infty)$ is sub-root if it is continuous, nondecreasing, and the function $r\mapsto\psi(r)/\sqrt{r}$ is nonincreasing on $(0,\infty)$. For the fixed-point lemma below, also assume that $\psi(a)>0$ for at least one $a>0$. A positive fixed point is a number $r_*>0$ satisfying $\psi(r_*)=r_*$.

Continuity is included explicitly because it gives existence of an intersection. Positivity somewhere rules out the degenerate function that is identically zero. The ratio condition is imposed only for positive $r$, so no value for $\psi(r)/\sqrt r$ at zero is required.

The Fixed-Point Lemma

Theorem: Let $\psi$ be sub-root and suppose $\psi(a)>0$ for some $a>0$. Then there is a unique positive fixed point $r_*$. For every $r>r_*$, $$ \psi(r)<r $$ and for every $0<r<r_*$, $$ \psi(r)>r. $$ More precisely, $$ \psi(r)\leq \sqrt{r r_*}\quad\text{if }r\geq r_*, \qquad \psi(r)\geq \sqrt{r r_*}\quad\text{if }0<r\leq r_*. $$

The proof uses the ratio $g(r)=\psi(r)/r$, whose value is one exactly at a positive fixed point. Write $q(r)=\psi(r)/\sqrt r$. By assumption, $q$ is nonincreasing, and $g(r)=q(r)/\sqrt r$. The additional factor $1/\sqrt r$ makes $g$ strictly decrease wherever its later value is positive.

Find values on both sides of one.
Choose $a>0$ with $q(a)>0$. For $0<r<a$, $q(r)\geq q(a)$, so $g(r)\geq q(a)/\sqrt r$, which exceeds one for sufficiently small $r$. For $r>a$, $q(r)\leq q(a)$, so $g(r)\leq q(a)/\sqrt r$, which is less than one for sufficiently large $r$.

Use continuity for existence.
The function $g$ is continuous on $(0,\infty)$, since $\psi$ is continuous and $r$ is positive there. Between a point where $g>1$ and a larger point where $g<1$, the intermediate value theorem gives a point $r_*$ with $g(r_*)=1$, hence $\psi(r_*)=r_*$.

Establish uniqueness and the signs.
If $0<r_1<r_2$ and $g(r_2)>0$, then $q(r_1)\geq q(r_2)>0$, and therefore $g(r_1)=q(r_1)/\sqrt{r_1}>q(r_2)/\sqrt{r_2}=g(r_2)$. Thus $g$ cannot equal one at two positive points. The same strict comparison with $r_*$ shows $g(r)>1$ below $r_*$ and $g(r)<1$ above it.

Compare the square-root ratios.
For $r\geq r_*$, $q(r)\leq q(r_*)=\sqrt{r_*}$, so $\psi(r)=\sqrt r\,q(r)\leq\sqrt{rr_*}$. For $0<r\leq r_*$, $q(r)\geq q(r_*)=\sqrt{r_*}$, giving $\psi(r)\geq\sqrt{rr_*}$.

The signs also follow directly from the square-root comparisons: when $r>r_*$, $\sqrt{rr_*}<r$; when $r<r_*$, $\sqrt{rr_*}>r$. To see that the comparison is strict for $g$, use the strict ratio argument in Step 3. At $r=r_*$, both the function and the identity equal $r_*$. $\square$

Working With the Lemma

The inequalities can be read in two equivalent ways. The function value is at most $\sqrt{rr_*}$ above the fixed point and at least $\sqrt{rr_*}$ below it. Dividing these bounds by $r>0$ gives a relative comparison:

\frac{\psi(r)}{r}\leq\sqrt{\frac{r_*}{r}}\quad(r\geq r_*), \qquad \frac{\psi(r)}{r}\geq\sqrt{\frac{r_*}{r}}\quad(0<r\leq r_*).

The bounds are sharp under the definition: a function proportional to $\sqrt r$ can attain equality over a range of radii. The strict inequalities against $r$, however, hold away from the fixed point. These distinctions matter when using the lemma: the square-root comparison may be an equality, but it still places the function strictly below or above the identity on the respective side.

Worked Example: A Constant Sub-Root Function

Let $\psi(r)=4$ for all $r\geq0$. It is continuous, nonnegative, and nondecreasing. For $r>0$, $\psi(r)/\sqrt r=4/\sqrt r$, which is decreasing, so $\psi$ is sub-root.

The fixed-point equation is $4=r$, and hence $r_*=4$. For $r=16$, the upper bound gives $\psi(16)\leq\sqrt{16\cdot4}=8$; indeed, $4\leq8$, and also $4<16$. For $r=1$, the lower bound gives $\psi(1)\geq\sqrt{1\cdot4}=2$; indeed, $4\geq2$, and $4>1$.

This example also illustrates that the square-root bounds need not be equalities. The function itself stays constant, while the comparison value varies with $r$.

Worked Example: Solving a Square-Root Plus Offset

Consider $\psi(r)=1+2\sqrt r$. This function is continuous and nondecreasing. Its ratio is

\frac{\psi(r)}{\sqrt r}=\frac{1}{\sqrt r}+2,

which is nonincreasing, and $\psi(r)>0$ for every $r\geq0$. Thus the lemma applies. To solve the fixed-point equation, put $t=\sqrt{r}$, where $t\geq0$. Then

t^2=1+2t \quad\Longleftrightarrow\quad t^2-2t-1=0 \quad\Longleftrightarrow\quad t=1+\sqrt2,

since the other root $1-\sqrt2$ is negative and cannot equal $\sqrt r$. Therefore $r_*=(1+\sqrt2)^2=3+2\sqrt2$. Substitution verifies the result: $1+2\sqrt{3+2\sqrt2}=1+2(1+\sqrt2)=3+2\sqrt2=r_*$.

At $r=4r_*$, the theorem gives $\psi(r)\leq\sqrt{4r_*^2}=2r_*$, which is strictly less than $4r_*$. At $r=r_*/4$, it gives $\psi(r)\geq\sqrt{r_*^2/4}=r_*/2$, which is strictly greater than $r_*/4$. Both conclusions agree with the sign of $\psi(r)-r$.

Worked Example: A Piecewise Complexity Curve

Define $\psi(r)=\min\{3,\sqrt{3r}\}$ for $r\geq0$. The function is continuous and nondecreasing: it equals $\sqrt{3r}$ up to $r=3$, then stays at 3. Its ratio is

\frac{\psi(r)}{\sqrt r}= \begin{cases} \sqrt3,&0<r\leq3,\\ 3/\sqrt r,&r\geq3. \end{cases}

The ratio is constant up to 3 and decreases thereafter, so the sub-root condition holds. In the first branch, the fixed-point equation $\sqrt{3r}=r$ has the positive solution $r=3$; in the second branch, $3=r$ also gives $r=3$. The branches meet there, so the unique fixed point is $r_*=3$.

For $r=12$, $\psi(12)=3$ and $\sqrt{12\cdot3}=6$, confirming $3\leq6<12$. For $r=3/4$, $\psi(3/4)=\sqrt{9/4}=3/2$, and $\sqrt{(3/4)\cdot3}=3/2$; thus the lower square-root bound holds with equality, while $3/2>3/4$. A sub-root curve can therefore meet its comparison bound exactly without meeting the identity anywhere else.

Common Pitfall and Practical Use

A common mistake is to assume that continuity and monotonicity alone guarantee the lemma. They do not. For example, $\psi(r)=r$ is continuous, nonnegative, and nondecreasing, but it has every positive $r$ as a fixed point. It fails the sub-root condition because $\psi(r)/\sqrt r=\sqrt r$ increases rather than decreases. Monotonicity of $\psi$ controls its absolute values; the ratio condition controls how quickly those values can grow relative to $\sqrt r$.

A second caution is that a positive fixed point is not guaranteed if the function is identically zero. That is why the lemma assumes positivity somewhere. Nor should the conclusion be applied to a discontinuous function without further argument: the ratio behavior can force values above and below one, but without continuity it need not force the function to equal one in between.

In applications, the practical benefit is that an equation that may be difficult to solve exactly can still be used through its unique crossing and its one-sided comparisons. Once a candidate sub-root function has been verified, the fixed point marks the scale at which the function and the radius balance. Larger radii have complexity below the identity, while smaller positive radii have complexity above it. This is the structural fact used when localized arguments select a critical radius.

Key takeaway: For a continuous, nonnegative, nondecreasing function whose ratio to $\sqrt r$ is nonincreasing and positive somewhere, there is exactly one positive solution of $\psi(r)=r$. Around it, $\psi(r)$ is bounded by $\sqrt{rr_*}$, and lies strictly below or above the identity according as $r$ is above or below $r_*$.

Check Your Understanding

Use the definition and the fixed-point lemma to answer the following.

Why does positivity of $\psi$ at one positive argument imply that $\psi(r)/r$ exceeds one for sufficiently small positive $r$?
For $\psi(r)=9$, find the fixed point and state the lemma's comparison at $r=36$.
For $\psi(r)=2+\sqrt r$, verify the ratio condition and solve for the positive fixed point.
Explain why $\psi(r)=r$ does not satisfy the sub-root ratio condition, despite being continuous and nondecreasing.
State the square-root comparison that applies when $0<r<r_*$, and explain why it implies $\psi(r)>r$.

What You'll Learn