A Worked Architecture-Selection Rate Calculation

From an Oracle Bound to an Architecture Choice

Architecture selection is a balance: a more expressive neural class can approximate the target more closely, but its estimation cost is often larger. An oracle inequality turns that tradeoff into a quantitative calculation. Given approximation errors and complexity penalties, we can identify the architecture favored by the bound and determine the resulting excess-risk rate.

The calculation has an important scope. It identifies the architecture minimizing a stated bound or criterion; it does not, by itself, reveal which architecture a particular data set will select. That data-dependent choice also depends on the observed empirical risks. Here we focus on the oracle calculation and on what it guarantees about risk.

Definition: Let $\mathcal F$ be a predictor class with risk $R(f)$, and let $R^*=\inf_{f\in\mathcal F}R(f)$. For each architecture index $m$, suppose $\mathcal F_m\subseteq\mathcal F$. Its approximation error relative to $\mathcal F$ is $$ a_m=\inf_{f\in\mathcal F_m}R(f)-R^*. $$ Thus $a_m\geq 0$. A penalized architecture criterion has the form $a_m+\operatorname{pen}_n(m)$, where $\operatorname{pen}_n(m)\geq0$ represents the complexity cost at sample size $n$.

The containment condition matters: it makes $R^*$ a valid common comparator for all candidate classes. If a candidate class were not contained in $\mathcal F$, its best risk could be below $R^*$, so the displayed difference would not necessarily be a nonnegative approximation error.

Power-Law Approximation and Complexity

A common calculation assumes that larger architectures reduce approximation error at a power-law rate, while their complexity penalty grows as a power of size. For positive constants $A,\alpha,\lambda_n,\beta$, consider the criterion $$ Q_n(m)=A m^{-\alpha}+\lambda_n m^\beta,\qquad m\geq 1. $$ Here $m$ is an integer architecture index. The first term decreases with size; the second increases. The power-law form is a model for the tradeoff, not a universal description of every neural class or complexity measure.

Theorem: For the continuous relaxation $m>0$, the unique minimizer of $Q_n(m)$ is $$ m_n^*=\left(\frac{\alpha A}{\beta\lambda_n}\right)^{1/(\alpha+\beta)}. $$ If $m_n^*\geq1$, then $$ \inf_{m>0}Q_n(m) =\frac{\alpha+\beta}{\beta}A^{\beta/(\alpha+\beta)} \left(\frac{\beta\lambda_n}{\alpha}\right)^{\alpha/(\alpha+\beta)}. $$

Proof. Differentiate the criterion for $m>0$:

Q_n'(m)=-\alpha A m^{-\alpha-1}+\beta\lambda_n m^{\beta-1}.

Setting this derivative to zero and multiplying by $m^{\alpha+1}>0$ gives $$ \beta\lambda_n m^{\alpha+\beta}=\alpha A, $$ so the only stationary point is $m_n^*=(\alpha A/(\beta\lambda_n))^{1/(\alpha+\beta)}$. The derivative is negative when $m<m_n^*$ and positive when $m>m_n^*$, so this point is the unique global minimum. At the stationary point, $\lambda_n(m_n^*)^\beta=(\alpha/\beta)A(m_n^*)^{-\alpha}$. Therefore $$ Q_n(m_n^*)=\frac{\alpha+\beta}{\beta}A(m_n^*)^{-\alpha} =\frac{\alpha+\beta}{\beta}A^{\beta/(\alpha+\beta)} \left(\frac{\beta\lambda_n}{\alpha}\right)^{\alpha/(\alpha+\beta)}. $$ This proves the claim. $\square$

The continuous minimizer is a balance point, not generally an allowable architecture. Since $Q_n$ decreases up to $m_n^*$ and increases afterward, when $m_n^*\geq1$ the integer minimizer is among $\lfloor m_n^*\rfloor$ and $\lceil m_n^*\rceil$. Evaluate both when choosing the best integer; rounding to the nearest integer is not guaranteed to minimize $Q_n$.

Rate consequence: Suppose $a_m\leq A m^{-\alpha}$, $\operatorname{pen}_n(m)=\lambda_n m^\beta$, and the selected estimator satisfies, with probability at least $1-\delta$, $$ R(\hat f_{\hat m})-R^* \leq C\inf_{m\geq1}\{a_m+\operatorname{pen}_n(m)\}+\varepsilon_n, $$ for constants $C>0$ and $\varepsilon_n\geq0$. When $\lambda_n$ tends to zero so that $m_n^*\geq1$, the power-law calculation gives an upper bound of order $\lambda_n^{\alpha/(\alpha+\beta)}+\varepsilon_n$. This is a guaranteed upper rate; a matching lower rate does not follow from the approximation upper bound alone.

To see the integer issue does not change this order for small $\lambda_n$, choose $m=\lceil m_n^*\rceil$. When $m_n^*\geq1$, we have $m_n^*\leq m\leq2m_n^*$. Hence $$ A m^{-\alpha}\leq A(m_n^*)^{-\alpha}, \qquad \lambda_n m^\beta\leq 2^\beta\lambda_n(m_n^*)^\beta. $$ Both terms at $m_n^*$ are proportional to $\lambda_n^{\alpha/(\alpha+\beta)}$, so the integer criterion is bounded above by a constant times that same order. The continuous minimum is also a lower bound for the integer minimum. Thus the integer restriction changes constants, not this rate.

Worked Architecture Calculations

Worked Example: Choosing Between Integer Architectures

Suppose the approximation error is exactly $a_m=2/m$ and the penalty is $0.01m^2$. Find the continuous balance point and the minimizing integer architecture.

Here $A=2$, $\alpha=1$, $\lambda_n=0.01$, and $\beta=2$. The balance point is $$ m_n^*=\left(\frac{1\cdot2}{2\cdot0.01}\right)^{1/3} =100^{1/3}\approx4.642. $$ The integer candidates are 4 and 5. Their criterion values are $$ Q_n(4)=\frac{2}{4}+0.01(4^2)=0.5+0.16=0.66, $$ and $$ Q_n(5)=\frac{2}{5}+0.01(5^2)=0.4+0.25=0.65. $$ Since the criterion decreases before the balance point and increases afterward, these are the only candidates to compare. The minimizing integer architecture is $m=5$, with criterion value $0.65$.

Worked Example: Sample-Size Penalty and the Correct Balance Point

Let $a_m=2/m$, and suppose the penalty is $\lambda_n m^2$, where $\lambda_n=3L_n/n$. Take $n=10{,}000$ and $L_n=12.2061$. Calculate the balance point, the integer choice, and the rate as $n$ grows.

The constants are $A=2$, $\alpha=1$, and $\beta=2$. Consequently, $$ m_n^*= \left(\frac{1\cdot2}{2\cdot(3L_n/n)}\right)^{1/3} =\left(\frac{n}{3L_n}\right)^{1/3}. $$ At the stated values, $$ m_n^*=\left(\frac{10{,}000}{36.6183}\right)^{1/3} \approx(273.09)^{1/3}\approx6.49. $$ The integer candidates are 6 and 7. The penalty coefficient is $\lambda_n=36.6183/10{,}000=0.00366183$, so $$ Q_n(6)=\frac{2}{6}+0.00366183(36) \approx0.333333+0.131826=0.465159, $$ whereas $$ Q_n(7)=\frac{2}{7}+0.00366183(49) \approx0.285714+0.179430=0.465144. $$ Thus $m=7$ has the slightly smaller criterion. For comparison, $Q_n(8)=0.25+0.00366183(64)\approx0.484357$, which is larger.

For the rate, the continuous minimum is $$ \frac{3}{2}\,2^{2/3}\left(\frac{6L_n}{n}\right)^{1/3}, $$ so the oracle term is of order $(L_n/n)^{1/3}$. Under the stated oracle inequality, the resulting excess-risk upper bound is of order $(L_n/n)^{1/3}+\varepsilon_n$, with the inequality's constant and probability qualification retained.

Worked Example: A Finite Architecture-Size Cap

Suppose the exact approximation error is $a_m=1/m^2$ and the penalty is $0.04m$, but only architectures $m\in\{1,2,3\}$ are available. Determine the unconstrained balance point and the selected available architecture.

The parameters are $A=1$, $\alpha=2$, $\lambda_n=0.04$, and $\beta=1$. Without the cap, $$ m_n^*=\left(\frac{2\cdot1}{1\cdot0.04}\right)^{1/3} =50^{1/3}\approx3.684. $$ This lies above the largest available architecture. Evaluate the criterion at each allowed index: $$ Q_n(1)=1+0.04=1.04,\qquad Q_n(2)=\frac14+0.08=0.33,\qquad Q_n(3)=\frac19+0.12\approx0.231111. $$ The selected available architecture is $m=3$. The cap forces a boundary choice; the unconstrained balance point does not itself identify a feasible architecture. If a sample-size-dependent penalty shrinks enough that its balance point exceeds a fixed cap, the best available choice can remain at that cap rather than following the unconstrained rate calculation.

Turning the Criterion into an Excess-Risk Statement

The calculation is useful because it converts assumptions about approximation and complexity into a concrete risk guarantee. If $\lambda_n=L_n/n$, the power-law bound yields the order $$ (L_n/n)^{\alpha/(\alpha+\beta)}+\varepsilon_n. $$ For instance, $\alpha=1$ and $\beta=2$ give exponent $1/3$, as in the preceding example. The log factor $L_n$ is part of the rate and should not be silently treated as a constant when reporting a finite-sample bound.

The approximation assumption $a_m\leq A m^{-\alpha}$ supplies an upper bound on the best risk available at each size. It does not establish that the approximation error is at least a constant times $m^{-\alpha}$. Therefore the derived result is an upper guarantee, not automatically a sharp characterization of the actual selected estimator's risk. A matching lower-rate claim needs additional lower-bound assumptions.

Likewise, the oracle inequality is an input to the calculation, not a consequence of differentiating $Q_n$. Its validity depends on the stated statistical setup and the relevant complexity control. If optimization error or another remainder is present, it must be included, for example as $\varepsilon_n$; it can dominate the displayed rate if it fails to be smaller. When candidate architectures have a finite size range, minimize over that range rather than applying the unconstrained formula without checking feasibility.

Common Pitfalls

Using an invalid comparator. Calling $\inf_{f\in\mathcal F_m}R(f)-R^*$ a nonnegative approximation error requires $\mathcal F_m\subseteq\mathcal F$. Without that condition, nonnegativity does not follow.
Dropping a factor in the balance equation. The derivative equation is $\beta\lambda_n m^{\alpha+\beta}=\alpha A$. Keep both $\alpha A$ and $\beta\lambda_n$ when solving for $m_n^*$.
Treating the continuous solution as an integer selection. It is a guide to the neighboring candidates, not necessarily an allowed architecture. Evaluate the integer criterion, and account for any size cap.
Claiming more than the assumptions imply. An approximation upper bound and an oracle inequality yield a risk upper rate. They do not alone prove a matching lower rate or specify the empirical architecture selected on every data set.

Key takeaway: First verify that approximation errors use a common comparator. Then balance $A m^{-\alpha}$ against $\lambda_n m^\beta$, check the neighboring feasible integer sizes, and carry the minimized criterion through the oracle inequality. The resulting excess-risk order is $\lambda_n^{\alpha/(\alpha+\beta)}$, up to constants and any additional remainder.

Check Your Understanding

Use the definitions and balance calculation above to answer these questions.

Why does $\mathcal F_m\subseteq\mathcal F$ ensure that the approximation error $a_m$ is nonnegative?
For $A=1$, $\alpha=2$, $\beta=1$, and $\lambda_n=0.01$, calculate the continuous balance point.
If $\lambda_n=L_n/n$, what is the excess-risk upper-rate exponent when $\alpha=2$ and $\beta=3$, ignoring any additional remainder?
Why should both neighboring integers around the continuous minimizer be evaluated rather than simply rounding to the nearest integer?
What extra kind of assumption would be needed to claim that the derived upper rate is also a matching lower rate?