Validating Data-Dependent Neural Norm Bounds

Why a Data-Selected Norm Changes the Claim

Many neural generalization bounds depend on a measure of network size, such as a product of spectral norms or a path norm. Such a bound is usually established for a fixed class: for example, all networks in a given architecture whose chosen norm is at most $r$. If training produces a network with norm $\hat r$, it is tempting to substitute $\hat r$ into the fixed-class formula and report the resulting number. The substitution is not automatically valid. The radius $\hat r$ was selected using data, and the event on which the fixed-radius guarantee holds may fail at that selected radius.

This is a post-selection issue, not an objection to norm-based complexity measures. A bound for a class fixed independently of the sample can remain valid after optimizing over all networks in that class. What requires additional justification is choosing among classes or radii using the same sample and then treating the chosen class as though it had been fixed in advance.

Definition: Let $Z_1,\ldots,Z_n$ be independent observations from a distribution $P$, and let $f$ be a predictor with loss $\ell_f(z)\in[0,1]$. Its population and empirical risks are $$ R(f)=E[\ell_f(Z)],\qquad \widehat R_n(f)=\frac{1}{n}\sum_{i=1}^n\ell_f(Z_i). $$ For a specified neural norm measure $N(f)$, define the radius-constrained class $\mathcal F_r=\{f:N(f)\le r\}$. A fixed-radius guarantee is a probability statement for a radius $r$ chosen independently of the sample. A simultaneous guarantee holds for every radius in a stated collection on one common event.

For clarity, assume throughout that the architecture and loss are specified and that the observations are i.i.d. The bounded-loss assumption is used in the elementary concentration examples below. More refined neural complexity results may replace the concentration term or add a complexity term, but the selection issue is the same. We will express such a result abstractly: for each fixed radius $r_j$, suppose a valid theorem supplies a deterministic number $A_j$ such that $$ P\left(\sup_{f\in\mathcal F_{r_j}}|R(f)-\widehat R_n(f)|\le A_j+\sqrt{\frac{\log(2/\delta_j)}{2n}}\right)\ge 1-\delta_j. $$ The term $A_j$ represents the fixed-class complexity contribution supplied by the chosen neural bound. Our task is to preserve its guarantee when the radius is selected from data.

What Goes Wrong After Selection

A probability statement for each fixed $r$ does not assert that all those statements hold together. For example, if two candidate radii each have a failure probability at most $0.05$, the probability that at least one of their bounds fails can be as large as $0.10$. If a data-dependent procedure tends to choose the radius whose bound failed, the fixed-radius guarantee cannot simply be applied at the selected value. A continuum of possible radii makes the gap more consequential: there is no finite union bound over every real number unless further structure is supplied.

This does not mean every data-dependent norm estimate is invalid. It means the proof must cover the selection step. A norm chosen from an independent validation sample can be handled conditionally on the data used to construct the candidate predictors, provided that the validation procedure itself has a valid uniform or finite-candidate guarantee. Alternatively, one can constrain the radius before observing the data, or establish simultaneous control over a collection that includes the selected radius.

Worked Example: Selecting the Best of Eight Candidates

Suppose eight predictors are fixed before an independent validation sample of size $n=200$ is examined. Their losses lie in $[0,1]$. The validation sample is used to choose the predictor with the smallest empirical risk. If the selected predictor has empirical risk $0.12$, find a one-sided population-risk bound with confidence at least $0.95$.

For each fixed predictor $f_k$, Hoeffding's inequality gives $$ P\{R(f_k)-\widehat R_n(f_k)>t\}\le e^{-2nt^2}. $$ There are eight candidates. By the union bound, the probability that any one of their inequalities fails is at most $8e^{-2nt^2}$. Choose $t$ to make this at most $0.05$: $$ 8e^{-2(200)t^2}=0.05,\qquad t=\sqrt{\frac{\log(8/0.05)}{2\cdot200}} =\sqrt{\frac{\log(160)}{400}}\approx 0.11264. $$ Thus, with probability at least $0.95$, all eight candidates simultaneously satisfy $R(f_k)\le\widehat R_n(f_k)+0.11264$. This includes whichever candidate the validation procedure selects. Its population risk is therefore at most $0.12+0.11264=0.23264$, or approximately $0.2326$.

The key is that the inequality holds for every candidate on one event, not merely for a candidate named before the validation data were seen. If the eight candidates were themselves constructed using the validation observations, this argument would not apply as stated; the independence or an appropriate uniform guarantee would need to be addressed.

Simultaneous Control Over Norm Radii

A standard remedy is to allocate failure probability across a predetermined collection of radii. The following result needs no independence among the events for different radii. It uses only the fixed-radius guarantees and the union bound.

Theorem: Let $r_1,r_2,\ldots$ be a finite or countable collection of radii fixed independently of the data. Suppose that for each $j$, an event $E_j$ has probability at least $1-\delta_j$, where $\delta_j>0$ and $\sum_j\delta_j\le\delta$. Then, with probability at least $1-\delta$, every event $E_j$ holds. In particular, if $E_j$ is the fixed-radius risk bound displayed above, then that bound holds simultaneously for every $j$. Any data-dependent choice $\hat j$ from this collection is covered on the same event.

Proof. The event that at least one of the $E_j$ fails is $\bigcup_j E_j^c$. Countable subadditivity gives $$ P\left(\bigcup_j E_j^c\right)\le\sum_jP(E_j^c)\le\sum_j\delta_j\le\delta. $$ Therefore the probability that all the $E_j$ hold is at least $1-\delta$. On that event, the bound for $j=\hat j$ holds because it holds for every index in the collection. $\square$

For a countable, unbounded radius grid, a convenient allocation is $\delta_j=\delta/[j(j+1)]$, since $1/[j(j+1)]=1/j-1/(j+1)$ and the sum over positive integers is $1$. The price of allowing more radii appears in the confidence term for each individual class. Other grids and allocations are possible; the important requirement is that the radii and allocation rule are set without using the data.

Worked Example: A Countable Grid of Network Norms

Consider radii $r_1,r_2,\ldots$ and suppose the fixed-class theorem provides the stated two-sided bound with complexity contributions $A_1=0.04$ and $A_2=0.02$ for the first two radii. Let $n=1000$, total failure probability $\delta=0.05$, and allocate $\delta_j=0.05/[j(j+1)]$.

For $j=1$, $\delta_1=0.025$, so the confidence term is $$ \sqrt{\frac{\log(2/0.025)}{2(1000)}} =\sqrt{\frac{\log(80)}{2000}} \approx\sqrt{0.002191}\approx0.0468. $$ The total deviation bound at radius $r_1$ is $A_1+0.0468=0.0868$.

For $j=2$, $\delta_2=0.05/6\approx0.008333$, so $$ \sqrt{\frac{\log(2/\delta_2)}{2000}} =\sqrt{\frac{\log(240)}{2000}} \approx\sqrt{0.002740}\approx0.0524. $$ The total deviation bound at $r_2$ is $A_2+0.0524=0.0724$. If a procedure selects $r_2$ and returns a network with empirical risk $0.18$, its population risk is at most $0.18+0.0724=0.2524$ on the simultaneous event. The result is valid even though the radius was selected from the data, because the event covers the entire predetermined grid. The total failure probability across the grid is at most $0.05$.

A grid is not the only route. One may choose a radius before training and restrict the optimizer to $\mathcal F_r$; a fixed-radius theorem then applies directly to every fitted network in that class. For a continuously valued norm, a grid-based result may be used with a radius rounded upward, provided the class is nested and the complexity bound is evaluated at that larger radius. A direct theorem uniform in $r$ is another option, but it must genuinely establish a common event rather than repeat separate fixed-radius statements.

Complexity Penalties That Account for Selection

The same simultaneous bounds can justify choosing a radius by penalized empirical risk. Define $$ c_j=A_j+\sqrt{\frac{\log(2/\delta_j)}{2n}}. $$ On the simultaneous event, every $f\in\mathcal F_{r_j}$ satisfies both $R(f)\le\widehat R_n(f)+c_j$ and $\widehat R_n(f)\le R(f)+c_j$. Thus the quantity $c_j$ is not merely a preference for smaller networks: it is calibrated to a bound that holds across the selection candidates.

For the cleanest statement, consider a finite set of candidate networks $f_j$, where $f_j\in\mathcal F_{r_j}$, and select an index minimizing $\widehat R_n(f_j)+c_j$. The same argument applies to minimization over each class when the minima exist, or to approximate minimizers with the corresponding optimization error added. A penalty that is chosen after inspecting the data, without a simultaneous guarantee or an equivalent argument, does not by itself establish validity.

Theorem: Suppose the simultaneous two-sided bounds $|R(f)-\widehat R_n(f)|\le c_j$ hold for every candidate $f_j$ on one event. If $\hat j$ minimizes $\widehat R_n(f_j)+c_j$, then on that event, for every candidate index $k$, $$ R(f_{\hat j})\le R(f_k)+2c_k. $$

Proof. Apply the upper deviation bound to the selected candidate, then use its minimizing property, and finally apply the lower deviation bound to the comparator: $$ R(f_{\hat j}) \le\widehat R_n(f_{\hat j})+c_{\hat j} \le\widehat R_n(f_k)+c_k \le R(f_k)+2c_k. $$ Each inequality holds on the same simultaneous event, so the statement holds for every $k$ there. $\square$

Worked Example: A Penalty-Calibrated Radius Choice

Suppose two candidate networks have valid simultaneous deviation allowances $c_1=0.08$ and $c_2=0.12$, and empirical risks $0.20$ and $0.14$, respectively. Their penalized values are $$ \widehat R_n(f_1)+c_1=0.20+0.08=0.28,\qquad \widehat R_n(f_2)+c_2=0.14+0.12=0.26. $$ The penalized rule therefore selects $f_2$, despite its larger complexity allowance. On the simultaneous event its direct risk bound is $R(f_2)\le0.14+0.12=0.26$.

The oracle comparison also holds. If the first candidate has population risk $R(f_1)=0.25$, the theorem with $k=1$ gives $R(f_2)\le0.25+2(0.08)=0.41$. This comparison is looser than the direct bound in these numbers, but it illustrates the general guarantee: the selected model is controlled relative to every fixed candidate, with the comparator's penalty determining the remainder. Without the simultaneous event behind $c_1$ and $c_2$, the penalized comparison would be algebraically true for empirical risks but would not imply this population-risk statement.

Common Pitfall and Practical Checks

Common mistake: “The trained network has norm $\hat r$, and the theorem gives a bound $B(r)$ for each fixed radius $r$, so the risk is bounded by substituting $B(\hat r)$.” The reasoning silently treats a data-chosen radius as fixed. The correction is to identify the theorem's probability event: if it only covers one prespecified radius, it does not necessarily cover $\hat r$. Fix the radius in advance, establish a simultaneous bound over the allowed radii, or use a penalty derived from such a bound.

Before reporting a data-dependent neural norm bound, check that the norm measure, architecture, loss, and candidate radii match those covered by the theorem. Check also whether the candidate set was fixed independently of the evaluation sample, whether the failure probabilities sum to the claimed level, and whether the reported complexity term is evaluated at a covered radius. If a network's norm is merely observed after training, that observation alone is not a validation argument.

Key takeaway: A fixed-class norm bound is not automatically a bound at a data-selected norm. Valid selection requires either a class fixed independently of the data or a common high-probability guarantee covering the full selection procedure; complexity penalties are justified when they encode that guarantee.

Check Your Understanding

Use the distinction between fixed-class and simultaneous control to answer these questions.

Why does a high-probability bound for each fixed radius not, by itself, establish the same confidence level at a radius selected from the data?
State the condition on failure-probability allocations that lets a union bound cover a countable grid of radii.
What independence condition makes the eight-candidate validation example valid, and what changes if the candidates use the validation observations during training?
In the penalized comparison theorem, identify where the upper and lower deviation inequalities are used.
Give one way to handle a continuously valued selected norm without claiming that separate fixed-radius bounds hold simultaneously over all real radii.