Selecting Neural Architectures With Complexity Penalties

Why Architecture Selection Needs a Penalty

A neural architecture determines a collection of predictors, not just one fitted network. A small class may be unable to represent the signal well; a large class may fit the training sample especially closely without predicting well on new observations. Selecting an architecture by training loss alone ignores this difference. A complexity penalty makes the comparison account for how much empirical performance could be due to fitting the sample.

The goal here is a finite-sample comparison: after selecting a class using the data, how does the selected predictor’s population risk compare with what could have been achieved using any one of the candidate classes? The answer requires a deviation guarantee that holds simultaneously over the classes being compared. A bound for one fixed architecture is not, by itself, enough to justify choosing among many architectures.

Setup and Selector

Let $Z_1,\ldots,Z_n$ be independent observations with common distribution $P$. For a predictor $f$, let $\ell_f(z)$ be its loss at observation $z$, and suppose $0\leq \ell_f(z)\leq 1$. Define its population risk and empirical risk by

R(f)=E[\ell_f(Z)],\qquad \widehat R_n(f)=\frac{1}{n}\sum_{i=1}^n \ell_f(Z_i).

Consider $M$ candidate architecture classes $\mathcal F_1,\ldots,\mathcal F_M$. Each class may contain many networks—for example, networks with a specified depth, width, or parameter constraint. For each class, a training procedure returns a fitted predictor $\widehat f_m\in\mathcal F_m$. Its optimization error is at most $\tau_m\geq 0$ when

\widehat R_n(\widehat f_m) \leq \inf_{f\in\mathcal F_m}\widehat R_n(f)+\tau_m.

Exact empirical risk minimization corresponds to $\tau_m=0$. In practice, a nonzero $\tau_m$ allows the fitting procedure to stop before reaching the minimum. The selector considered here chooses among these fitted predictors; it does not require solving a new optimization problem across the union of all architectures.

Definition: Given nonnegative penalties $\operatorname{pen}_1,\ldots,\operatorname{pen}_M$, define the selected index and predictor by $$ \widehat m\in\arg\min_{1\leq m\leq M} \left\{\widehat R_n(\widehat f_m)+\operatorname{pen}_m\right\}, \qquad \widehat f=\widehat f_{\widehat m}. $$ A fixed, measurable tie-breaking rule is understood if the minimum is attained at more than one index.

The penalty is intended to cover the possible gap between empirical and population risk in a class. Make that idea precise by supposing there are deterministic radii $a_m\geq 0$ for which, on an event $\mathcal E$,

\sup_{f\in\mathcal F_m} \left|R(f)-\widehat R_n(f)\right|\leq a_m \qquad\text{for every }m=1,\ldots,M.

The simultaneous nature of this condition matters: the fitted network and the architecture are both chosen using the data. A deviation guarantee for a predictor fixed before seeing the sample would not automatically apply to this data-dependent choice.

Worked Example: Computing a Finite-Class Penalty

Suppose there are three finite candidate classes with cardinalities $N_1=10$, $N_2=100$, and $N_3=1000$. Let $n=1000$, and seek a simultaneous deviation guarantee with probability at least $0.95$. Hoeffding’s inequality and a union bound give the valid radii $$ a_m=\sqrt{\frac{\log(2MN_m/\delta)}{2n}}, \qquad M=3,\quad \delta=0.05. $$

For class 1, the logarithm is $\log(2\cdot3\cdot10/0.05)=\log(1200)\approx7.090$, so $a_1\approx\sqrt{7.090/2000}=0.0595$. For class 2, $\log(12000)\approx9.393$, giving $a_2\approx0.0685$. For class 3, $\log(120000)\approx11.695$, giving $a_3\approx0.0765$.

Use $\operatorname{pen}_m=2a_m$, and suppose the three fitted empirical risks are $0.18$, $0.15$, and $0.14$. Their penalized scores are approximately $0.2991$, $0.2871$, and $0.2929$, respectively. The selector chooses class 2. Although class 3 has the smallest training risk, its larger penalty makes class 2 preferable under this criterion.

An Oracle Comparison

Theorem: Suppose the simultaneous deviation event $\mathcal E$ holds, the fitted predictors satisfy the optimization inequalities above, and $\operatorname{pen}_m\geq a_m$ for every $m$. Then $$ R(\widehat f) \leq \min_{1\leq m\leq M} \left\{ \inf_{f\in\mathcal F_m}R(f)+a_m+\operatorname{pen}_m+\tau_m \right\}. $$ In particular, choosing $\operatorname{pen}_m=2a_m$ yields an added deviation cost of $3a_m$, in addition to $\tau_m$.

The comparison is called an oracle inequality because its right-hand side takes the best value across candidate classes, even though the selector does not know which class will perform best in population. The infimum risk in a class captures how well that architecture could perform; the radius and penalty account for data-driven selection, and $\tau_m$ accounts for imperfect fitting.

Control the selected predictor’s risk.
On $\mathcal E$, $R(\widehat f)\leq\widehat R_n(\widehat f)+a_{\widehat m}\leq\widehat R_n(\widehat f)+\operatorname{pen}_{\widehat m}$.

Use the selection rule.
For any fixed candidate index $m$, the selected penalized score is no larger than the score for $\widehat f_m$: $\widehat R_n(\widehat f)+\operatorname{pen}_{\widehat m}\leq\widehat R_n(\widehat f_m)+\operatorname{pen}_m$.

Compare the candidate fit with its class optimum.
Optimization accuracy and the deviation bound give $\widehat R_n(\widehat f_m)\leq\inf_{f\in\mathcal F_m}\widehat R_n(f)+\tau_m\leq\inf_{f\in\mathcal F_m}R(f)+a_m+\tau_m$.

Combine the inequalities.
Thus $R(\widehat f)\leq\inf_{f\in\mathcal F_m}R(f)+a_m+\tau_m+\operatorname{pen}_m$. This holds for each $m$, so taking the minimum proves the claim. $\square$

The theorem also clarifies why the penalty need not equal the deviation radius exactly. Any penalty at least $a_m$ cancels the selected architecture’s deviation term in the first comparison. A larger penalty remains in the oracle bound, so an unnecessarily large penalty can make the guarantee—and often the selection rule itself—too conservative.

Result: For finite classes of sizes $N_m$, if losses lie in $[0,1]$, then with probability at least $1-\delta$, the simultaneous deviation event holds with $$ a_m=\sqrt{\frac{\log(2MN_m/\delta)}{2n}}. $$

To verify this result, fix a class $m$ and predictor $f$. Hoeffding’s inequality for independent random variables in $[0,1]$ gives $$ P\left(\left|R(f)-\widehat R_n(f)\right|>t\right)\leq2\exp(-2nt^2). $$ There are $N_m$ predictors in class $m$, so the union bound over all predictors and all $M$ classes gives a failure probability at most $$ \sum_{m=1}^{M}2N_m\exp(-2na_m^2). $$ Substituting the displayed value of $a_m$ makes each summand $2N_m\exp\{-\log(2MN_m/\delta)\}=\delta/M$. The total is therefore at most $\delta$, proving the simultaneous claim. $\square$

Neural architecture classes are often infinite. The oracle argument itself does not require finiteness: it only needs radii $a_m$ for which the simultaneous deviation event is valid. A justified uniform-convergence certificate for each class can supply such radii; for example, one may use bounds based on pseudo-dimension or covering numbers. The complexity measure and its assumptions must match the loss class and the desired probability guarantee. The finite-class formula above illustrates how both class complexity and the number $M$ of architectures enter the penalty.

Worked Example: Allowing Imperfect Optimization

Suppose three fitted architectures have empirical risks $0.20, 0.15, 0.12$, valid deviation radii $a_1=0.02, a_2=0.04, a_3=0.07$, and optimization tolerances $\tau_1=0.005, \tau_2=0.010, \tau_3=0.020$. Use penalties $2a_m$, so the selection scores are $0.20+0.04=0.24$, $0.15+0.08=0.23$, and $0.12+0.14=0.26$. The selector chooses class 2.

For class 2, the oracle theorem gives $$ R(\widehat f)\leq\inf_{f\in\mathcal F_2}R(f)+0.04+0.08+0.010 =\inf_{f\in\mathcal F_2}R(f)+0.13. $$ For comparison, the corresponding additive terms for classes 1 and 3 are $0.02+0.04+0.005=0.065$ and $0.07+0.14+0.020=0.23$. These are not risk estimates by themselves: each is added to that class’s best population risk. The example shows why optimization accuracy belongs in an oracle comparison even when it is not included in the selection score.

Why Unpenalized Selection Can Fail

Worked Example: A Rich Class Wins on Training Loss

Let one observation $X$ be uniform on $\{1,2,3,4\}$, and use zero-one loss. A simple predictor $f_0$ has loss $1/4$ at every possible observation, so its empirical and population risks are both $1/4$. A richer class contains six predictors $f_A$, one for each two-element subset $A$ of $\{1,2,3,4\}$, with loss $\ell_{f_A}(X)=\mathbf 1\{X\in A\}$.

For any such subset, $P(X\in A)=2/4=1/2$, so every rich-class predictor has population risk $1/2$. But after observing $X=x$, there is a two-element subset $A$ that does not contain $x$. Its empirical risk on this one-observation sample is zero. An unpenalized empirical-risk selector therefore chooses a rich-class predictor with population risk $1/2$, rather than the simple predictor with risk $1/4$.

The error is not that the training-risk calculation is wrong; the chosen rich predictor really does have zero empirical risk. The mistake is treating that data-dependent minimum as if it had been evaluated on an independent observation. A complexity penalty can discourage such a choice when it reflects the rich class’s greater opportunity to fit the observed sample.

Using the Comparison in Practice

Architecture selection is useful when candidate networks express different approximation-versus-estimation tradeoffs. The oracle inequality does not claim that the selected architecture is best among all possible networks; it compares only with the supplied candidate classes. A poor candidate set, an invalid deviation certificate, or a fitting procedure with a large optimization error can all weaken the conclusion.

A sound workflow is to specify candidate classes and a risk measure, obtain a valid simultaneous complexity certificate, set penalties at least as large as its deviation radii, and fit each candidate accurately enough that its optimization error is controlled. Complexity penalties should reflect the candidate classes’ capacity, not simply their number of parameters unless that quantity is justified for the problem. The important feature is not a particular complexity measure, but a defensible bound that remains valid after the architecture has been selected from the data.

Common Mistake

Wrong reasoning: “Each architecture has a small generalization gap, so selecting the one with the smallest training loss is safe.”
Correction: A guarantee for each fixed architecture need not hold simultaneously after data-driven selection. Use a uniform deviation bound over the candidate classes, or otherwise account for the selection step in the penalty.
Wrong reasoning: “The penalty handles everything, even if network training did not approach the empirical optimum.”
Correction: The oracle comparison has a separate $\tau_m$ term. Generalization control does not erase optimization error.

Key takeaway: Minimize empirical risk plus a complexity penalty across the fitted architectures. If the penalty dominates a valid simultaneous deviation radius, the selected predictor is bounded by the best candidate class’s population risk plus its complexity and optimization costs.

Check Your Understanding

Answer these questions using the definitions and comparison above.

Why must the deviation event hold simultaneously over all candidate architectures?
In the oracle inequality, what does each of the terms $a_m$, $\operatorname{pen}_m$, and $\tau_m$ account for?
For finite classes, how does increasing the number of candidate architectures affect the displayed deviation radius?
What changes in the oracle bound if fitting is exact within every class?
Why can an architecture with the lowest empirical risk still have worse population risk than a simpler candidate?