6 Depth bias–variance trade-offs (Appendix I)
6.1 Bias laws, variance profiles, balancing depths (definitions)
Exponentially decaying approximation error: \(\mathsf{bias}(k) = e^{-\alpha k}\), \(\alpha {\gt} 0\).
Polynomially decaying approximation error: \(\mathsf{bias}(k) = k^{-\beta }\), \(\beta {\gt} 0\).
Root-logarithmic estimation profile: \(\mathsf{var}(k,n) = \sqrt{\log k / n}\) (??(i)–(ii)).
Root-polynomial estimation profile: \(\mathsf{var}(k,n) = \sqrt{k^{\gamma } / n}\), \(\gamma {\gt} 0\) (??(iii)–(iv)).
The depth-dependent part of the excess-risk bound of theorem 98: \(\mathsf{gen}(k,n) = \mathsf{bias}(k) + \mathsf{var}(k,n)\).
PP balancing depth \({k^{\ast }}= n^{1/(2\beta +\gamma )}\).
EP balancing depth (leading terms): \({k^{\ast }}= \frac{1}{2\alpha }(\log n - \gamma \log \log n)\).
EP balanced rate \(n^{-1/2}(\log n)^{\gamma /2}\).
EL balancing depth (leading terms): \({k^{\ast }}= \frac{1}{2\alpha }(\log n - \log \log \log n)\).
EL balanced rate \(\sqrt{\log \log n / n}\).
PL balancing depth \({k^{\ast }}= \bigl(2\beta n/\log (2\beta n)\bigr)^{1/(2\beta )}\), the leading term of \(\exp \bigl(W(2\beta n)/(2\beta )\bigr)\) (Lambert \(W\), \(W(x) \sim \log x\)).
PL balanced rate \(\sqrt{\log n/n}\).
6.2 Balancing depths and balanced rates (Appendix I, the four regimes EL, EP, PL, PP; lem:balancing, eq:tradeoff-table)
For \(\alpha {\gt} 0\), \(k \mapsto e^{-\alpha k}\) is nonincreasing.
\(\exp \) is monotone and \(k \mapsto -\alpha k\) is nonincreasing.
For \(\beta {\gt} 0\), \(k \mapsto k^{-\beta }\) is nonincreasing on \((0,\infty )\).
Power with a nonpositive exponent is antitone on the positive reals.
For \(n \ge 0\), \(k \mapsto \sqrt{\log k / n}\) is nondecreasing on \((0,\infty )\).
\(\log \) is monotone on \((0,\infty )\); divide by \(n \ge 0\) and take square roots.
For \(\gamma \ge 0\) and \(n \ge 0\), \(k \mapsto \sqrt{k^{\gamma }/n}\) is nondecreasing on \((0,\infty )\).
\(k \mapsto k^\gamma \) is monotone for \(\gamma \ge 0\); divide by \(n\) and take roots.
If \(\mathsf{bias}\ge 0\) and \(\mathsf{var}(\cdot ,n) \ge 0\) on a set \(S\) of depths, then \(\mathsf{gen}(k,n) \ge \max \{ \mathsf{bias}(k), \mathsf{var}(k,n)\} \) for every \(k \in S\).
Each summand is bounded by the sum because the other one is nonnegative.
Balancing principle. Let \(S \subseteq \mathbb R\) be a set of depths on which \(\mathsf{bias}\ge 0\) is nonincreasing and \(\mathsf{var}(\cdot ,n) \ge 0\) is nondecreasing. If \(k_0 \in S\) balances the two terms, \(\mathsf{bias}(k_0) = \mathsf{var}(k_0,n)\), then \(\mathsf{gen}(k,n) \ge \mathsf{bias}(k_0)\) for every \(k \in S\), while \(\mathsf{gen}(k_0,n) = 2\mathsf{bias}(k_0)\); hence \(k_0\) minimizes the bound over \(S\) up to the factor \(2\).
Case split on \(k \le k_0\) or \(k \ge k_0\): in the first case \(\mathsf{bias}(k) \ge \mathsf{bias}(k_0)\) and \(\mathsf{var}(k,n) \ge 0\); in the second \(\mathsf{var}(k,n) \ge \mathsf{var}(k_0,n) = \mathsf{bias}(k_0)\) and \(\mathsf{bias}(k) \ge 0\). The identity at \(k_0\) is the balance equation.
For \(\beta ,\gamma {\gt} 0\) and \(n {\gt} 0\), \(\mathsf{bias}({k^{\ast }}) = {k^{\ast }}^{-\beta } = n^{-\beta /(2\beta +\gamma )}\).
\((n^{1/(2\beta +\gamma )})^{-\beta } = n^{-\beta /(2\beta +\gamma )}\) by the power rule.
For \(\beta ,\gamma {\gt} 0\) and \(n {\gt} 0\), \(\mathsf{var}({k^{\ast }},n) = \sqrt{{k^{\ast }}^{\gamma }/n} = n^{-\beta /(2\beta +\gamma )}\).
\({k^{\ast }}^\gamma / n = n^{\gamma /(2\beta +\gamma ) - 1} = n^{-2\beta /(2\beta +\gamma )}\), and the square root halves the exponent.
PP regime (??). Let \(\beta ,\gamma {\gt} 0\) and \(n {\gt} 0\). At the balancing depth \({k^{\ast }}= n^{1/(2\beta +\gamma )}\), \(\mathsf{gen}({k^{\ast }},n) = {k^{\ast }}^{-\beta } + \sqrt{{k^{\ast }}^{\gamma }/n} = 2\, n^{-\beta /(2\beta +\gamma )}\), and for every depth \(k {\gt} 0\), \(\mathsf{gen}(k,n) = k^{-\beta } + \sqrt{k^{\gamma }/n} \ge n^{-\beta /(2\beta +\gamma )}\). Thus \({k^{\ast }}\) is optimal up to the factor \(2\) and \(\mathsf{gen}({k^{\ast }},n) \asymp n^{-\beta /(2\beta +\gamma )}\).
Both terms equal \(n^{-\beta /(2\beta +\gamma )}\) at \({k^{\ast }}\) (theorem 384, theorem 385), so the balancing principle theorem 383 on \(S = (0,\infty )\) gives both claims.
For every \(c {\gt} 0\), \(\log x \le c\, x\) for all sufficiently large \(x\).
\(\log x = o(x)\) (Mathlib: ‘Real.isLittleO_log_id_atTop‘).
For every \(c {\gt} 0\), \(\log \log n \le c \log n\) for all sufficiently large \(n\).
Compose theorem 387 with \(\log n \to \infty \).
\(\log x {\lt} x\) for \(x {\gt} 0\).
\(\log x \le x - 1 {\lt} x\).
For \(n {\gt} 0\) and \(L \ge 0\), \(n^{-1/2} L^{\gamma /2} = \sqrt{L^{\gamma }/n}\).
\(\sqrt{L^\gamma /n} = \sqrt{L^\gamma }/\sqrt n = L^{\gamma /2} n^{-1/2}\).
For \(c \ge 0\), \(\sqrt{c\, x/n} = \sqrt c\, \sqrt{x/n}\).
Multiplicativity of the square root.
\(n^{-1/2}(\log n)^{\gamma /2} \ge 0\) for \(n \ge 1\).
Product of two nonnegative powers.
For \(\alpha {\gt} 0\) and \(n {\gt} 1\), \(e^{-\alpha {k^{\ast }}} = n^{-1/2}(\log n)^{\gamma /2}\) exactly.
\(-\alpha {k^{\ast }}= -\tfrac 12 \log n + \tfrac \gamma 2 \log \log n\); exponentiate.
For \(\alpha , \gamma {\gt} 0\) and \(\log n \ge 1\), \({k^{\ast }}\le \log n/(2\alpha )\).
\(\gamma \log \log n \ge 0\) when \(\log n \ge 1\).
For \(\alpha ,\gamma {\gt} 0\), \(n {\gt} 1\), \(\log n \ge 1\) and \(\gamma \log \log n \le \log n\): \(\sqrt{{k^{\ast }}^{\gamma }/n} \le \sqrt{(2\alpha )^{-\gamma }}\; n^{-1/2}(\log n)^{\gamma /2}\).
\(0 \le {k^{\ast }}\le \log n/(2\alpha )\), so \({k^{\ast }}^\gamma \le (2\alpha )^{-\gamma } (\log n)^\gamma \); divide by \(n\) and take roots.
For \(\alpha ,\gamma {\gt} 0\), eventually in \(n\): \(n^{-1/2}(\log n)^{\gamma /2} \le \mathsf{gen}({k^{\ast }},n) \le \bigl(1 + \sqrt{(2\alpha )^{-\gamma }}\bigr)\, n^{-1/2}(\log n)^{\gamma /2}\).
The bias term equals the rate exactly (theorem 393) and the variance term is at most \(\sqrt{(2\alpha )^{-\gamma }}\) times the rate (theorem 395); the side conditions hold for large \(n\) by theorem 388.
If \(0 \le g\) eventually, \(c {\gt} 0\), and \(g \le f \le c\, g\) eventually, then \(f = \Theta (g)\).
Both \(O\)-directions, with constants \(c\) and \(1\).
EP regime (??). Let \(\alpha ,\gamma {\gt} 0\) and \({k^{\ast }}(n) = \frac{1}{2\alpha }(\log n - \gamma \log \log n)\). Then \(\mathsf{gen}({k^{\ast }},n) = e^{-\alpha {k^{\ast }}} + \sqrt{{k^{\ast }}^{\gamma }/n} \asymp n^{-1/2}(\log n)^{\gamma /2}\) as \(n \to \infty \) (more precisely, between \(1\) and \(1 + (2\alpha )^{-\gamma /2}\) times the rate).
Apply theorem 397 to the two-sided bound theorem 396.
EP regime, upper bound: \(\mathsf{gen}({k^{\ast }},n) = O(n^{-1/2}(\log n)^{\gamma /2})\).
The \(O\)-half of theorem 398.
For \(\alpha {\gt} 0\) and \(n {\gt} e\), \(e^{-\alpha {k^{\ast }}} = \sqrt{\log \log n/n}\) exactly.
\(-\alpha {k^{\ast }}= -\tfrac 12\log n + \tfrac 12\log \log \log n\); exponentiate and rewrite \(n^{-1/2}(\log \log n)^{1/2} = \sqrt{\log \log n/n}\).
For \(\alpha {\gt} 0\) and \(\log n \ge e\): \(0 {\lt} {k^{\ast }}\le \log n/(2\alpha )\) and \(\log {k^{\ast }}\le \log \log n + |\log (2\alpha )|\).
\(\log \log \log n \ge 0\) gives the upper bound; \(\log \log \log n {\lt} \log \log n {\lt} \log n\) gives positivity; then \(\log {k^{\ast }}\le \log (\log n/(2\alpha )) = \log \log n - \log (2\alpha )\).
For \(\alpha {\gt} 0\) and \(\log n \ge e\): \(\sqrt{\log {k^{\ast }}/n} \le \sqrt{1 + |\log (2\alpha )|}\, \sqrt{\log \log n/n}\).
\(\log {k^{\ast }}\le \log \log n + |\log 2\alpha | \le (1 + |\log 2\alpha |)\log \log n\) because \(\log \log n \ge 1\) (theorem 401).
For \(\alpha {\gt} 0\), eventually in \(n\): \(\sqrt{\log \log n/n} \le \mathsf{gen}({k^{\ast }},n) \le \bigl(1 + \sqrt{1 + |\log (2\alpha )|}\bigr)\sqrt{\log \log n/n}\).
Bias equals the rate (theorem 400); variance is at most \(\sqrt{1 + |\log 2\alpha |}\) times the rate (theorem 402).
EL regime (??). Let \(\alpha {\gt} 0\) and \({k^{\ast }}(n) = \frac{1}{2\alpha }(\log n - \log \log \log n)\). Then \(\mathsf{gen}({k^{\ast }},n) = e^{-\alpha {k^{\ast }}} + \sqrt{\log {k^{\ast }}/n} \asymp \sqrt{\log \log n/n}\) as \(n \to \infty \).
Apply theorem 397 to theorem 403.
EL regime, upper bound: \(\mathsf{gen}({k^{\ast }},n) = O(\sqrt{\log \log n/n})\).
The \(O\)-half of theorem 404.
For \(\beta {\gt} 0\), \(n {\gt} 0\) and \(L = \log (2\beta n) {\gt} 0\): \({k^{\ast }}^{-\beta } = \sqrt{L/(2\beta n)}\).
\({k^{\ast }}^{-\beta } = (2\beta n/L)^{-1/2} = (L/(2\beta n))^{1/2}\).
For \(\beta {\gt} 0\), \(n {\gt} 0\) and \(L = \log (2\beta n) {\gt} 0\): \(\log {k^{\ast }}= (L - \log L)/(2\beta )\).
\(\log \) of a power and of a quotient.
The PL balancing equation \(k^{2\beta }\log k \asymp n\) holds exactly up to the factor \(1 - \log L/L\): for \(\beta {\gt} 0\), \(n {\gt} 0\) and \(L = \log (2\beta n) {\gt} 0\), \({k^{\ast }}^{2\beta }\log {k^{\ast }}= n\, (1 - \log L/L)\).
\({k^{\ast }}^{2\beta } = 2\beta n/L\) and \(\log {k^{\ast }}= (L - \log L)/(2\beta )\) (theorem 407); multiply out.
\({k^{\ast }}^{2\beta }\log {k^{\ast }}/ n \to 1\) as \(n \to \infty \), i.e. \({k^{\ast }}^{2\beta }\log {k^{\ast }}\sim n\).
By theorem 408 the ratio is \(1 - \log L/L\) with \(L = \log (2\beta n) \to \infty \), and \(\log L / L \to 0\).
For \(\beta {\gt} 0\), \(n {\gt} 0\) and \(L = \log (2\beta n) \ge 1\): \(\sqrt{\log {k^{\ast }}/n} \le \sqrt{L/(2\beta n)}\).
\(\log {k^{\ast }}= (L - \log L)/(2\beta ) \le L/(2\beta )\) since \(\log L \ge 0\).
For \(\beta {\gt} 0\) and \(\log n \ge \max \{ 1, 2|\log 2\beta |\} \): \(\tfrac 12\log n \le \log (2\beta n) \le (1 + |\log 2\beta |)\log n\).
\(\log (2\beta n) = \log 2\beta + \log n\) and \(-|c| \le c \le |c| \le |c|\log n\).
For \(\beta {\gt} 0\), eventually in \(n\): \(\sqrt{1/(4\beta )}\sqrt{\log n/n} \le \mathsf{gen}({k^{\ast }},n) \le 2\sqrt{(1 + |\log 2\beta |)/(2\beta )}\, \sqrt{\log n/n}\).
Both terms are at most \(\sqrt{L/(2\beta n)}\) with \(L = \log (2\beta n)\) (theorem 406, theorem 410), the bias term equals it, and \(\tfrac 12\log n \le L \le (1 + |\log 2\beta |)\log n\) (theorem 411).
PL regime (??). Let \(\beta {\gt} 0\) and \({k^{\ast }}(n) = \bigl(2\beta n/\log (2\beta n)\bigr)^{1/(2\beta )}\). Then \(\mathsf{gen}({k^{\ast }},n) = {k^{\ast }}^{-\beta } + \sqrt{\log {k^{\ast }}/n} \asymp \sqrt{\log n/n}\) as \(n \to \infty \).
Rescale the lower bound of theorem 412 by \(\sqrt{1/(4\beta )}^{-1}\) and apply theorem 397 to the function \(\sqrt{1/(4\beta )}\, \sqrt{\log n/n}\), which is \(\Theta (\sqrt{\log n/n})\).
PL regime, upper bound: \(\mathsf{gen}({k^{\ast }},n) = O(\sqrt{\log n/n})\).
The \(O\)-half of theorem 413.
For \(n {\gt} 1\), \(\sqrt{\log n/n} = n^{-1/2}(\log n)^{1/2}\).
theorem 390 with \(\gamma = 1\).
Ordering note, first half. If \(\gamma \le 1\) then the EP rate is no worse than the PL rate: \(n^{-1/2}(\log n)^{\gamma /2} = O(\sqrt{\log n/n})\).
For \(\log n \ge 1\), \((\log n)^{\gamma /2} \le (\log n)^{1/2}\).
Ordering note, second half. If \(\gamma \ge 1\) then the PL rate is no worse than the EP rate: \(\sqrt{\log n/n} = O(n^{-1/2}(\log n)^{\gamma /2})\).
For \(\log n \ge 1\), \((\log n)^{1/2} \le (\log n)^{\gamma /2}\).
Ordering note (??). The EP and PL balanced rates are not uniformly ordered: EP \(\lesssim \) PL when \(\gamma \le 1\), and PL \(\lesssim \) EP when \(\gamma \ge 1\); for \(\gamma = 1\) they coincide up to constants.
theorem 416 and theorem 417.