Choosing A Theoretical Regularization Scale

Why the Regularization Scale Is a Statistical Quantity

A complexity penalty must be large enough to offset the random advantage that a complicated predictor can gain by fitting the observed sample. That advantage depends on the noise level and sample size, but also on how many predictors are being compared. A penalty calibrated without these quantities may either leave the comparison too optimistic or make simpler predictors look preferable for statistical rather than substantive reasons.

We derive a theoretical scale under a stated concentration assumption. The result is not a universal prescription for every loss or regularizer: different deviation assumptions can produce different rates. Here the key case has deviations of order the noise scale times the square root of a logarithmic complexity divided by sample size.

Setup and a Simultaneous Deviation Bound

Let $Z_1,\ldots,Z_n$ be independent observations from a common distribution. There is a countable collection of models indexed by $m$. Model $m$ contains a finite set $\mathcal F_m$ of predictors, with $N_m\geq 1$ members. For a predictor $f$, let $R(f)$ be its population risk and let $\widehat R(f)$ be its empirical risk, the average loss over the $n$ observations.

Assume that a known constant $\sigma>0$ gives the following two-sided deviation bound for every fixed predictor $f$ and every $t>0$:

P\left(\left|\widehat R(f)-R(f)\right|>\sigma\sqrt{\frac{2t}{n}}\right)\leq 2e^{-t}.

This assumption specifies the noise and concentration regime for the tutorial. Set $a_n=\sigma\sqrt{2/n}$. Give each model a nonnegative weight $w_m$, with $\sum_m e^{-w_m}\leq 1$, and define its dimensionless complexity

\kappa_m=\sqrt{\log(2N_m)+w_m}.

The term $\log N_m$ accounts for searching among predictors within a model; $w_m$ accounts for searching across models. The factor $2$ inside the logarithm is chosen to pair with the two-sided tail bound.

Theorem: Under the stated deviation assumption and weight condition, for every $x>0$, with probability at least $1-e^{-x}$, all predictors in all models simultaneously satisfy $$ \left|\widehat R(f)-R(f)\right|\leq a_n\left(\kappa_m+\sqrt{x}\right),\qquad f\in\mathcal F_m. $$

Proof. Fix $x>0$, a model $m$, and $f\in\mathcal F_m$. Apply the assumed tail bound with $t=\log(2N_m)+w_m+x$. The probability of exceeding the resulting threshold is at most

2e^{-\log(2N_m)-w_m-x} =e^{-\log N_m-w_m-x}.

Summing this probability over the $N_m$ predictors in model $m$ gives at most $e^{-w_m-x}$. Summing over all models gives at most

e^{-x}\sum_m e^{-w_m}\leq e^{-x}.

Thus, outside an event of probability at most $e^{-x}$, every predictor obeys the deviation bound with threshold $a_n\sqrt{\log(2N_m)+w_m+x}$. Since $\sqrt{u+v}\leq\sqrt{u}+\sqrt{v}$ for nonnegative $u,v$, this threshold is at most $a_n(\kappa_m+\sqrt{x})$, as claimed. $\square$

From Deviations to a Penalty Scale

Consider minimizing empirical risk plus a model penalty. For now, suppose a minimizer $\widehat f$ exists over the union of the models, with $\widehat f\in\mathcal F_{\widehat m}$, and that it satisfies

\widehat R(\widehat f)+\lambda\kappa_{\widehat m} \leq \widehat R(f)+\lambda\kappa_m \qquad\text{for every }m\text{ and }f\in\mathcal F_m.

The coefficient $\lambda$ has the units of risk; $\kappa_m$ is dimensionless. The simultaneous bound suggests choosing $\lambda$ at least as large as $a_n=\sigma\sqrt{2/n}$. This is the theoretical scale for this particular concentration inequality. Complexity appears in the penalty through $\kappa_m$, rather than in the coefficient $\lambda$ itself.

Theorem: On the simultaneous-deviation event, if $\lambda\geq a_n$, then for every $x>0$ defining that event, $$ R(\widehat f)\leq \inf_{m}\inf_{f\in\mathcal F_m} \left\{R(f)+(\lambda+a_n)\kappa_m\right\}+2a_n\sqrt{x}. $$

Proof. Work on the event where the deviation bound holds for all predictors. For any $f\in\mathcal F_m$, first apply the deviation bound to $\widehat f$, then the minimizing property, and then the deviation bound to $f$:

\begin{aligned} R(\widehat f) &\leq \widehat R(\widehat f)+a_n\kappa_{\widehat m}+a_n\sqrt{x}\\ &\leq \widehat R(f)+\lambda\kappa_m-\lambda\kappa_{\widehat m} +a_n\kappa_{\widehat m}+a_n\sqrt{x}\\ &\leq R(f)+a_n\kappa_m+a_n\sqrt{x} +\lambda\kappa_m+(a_n-\lambda)\kappa_{\widehat m} +a_n\sqrt{x}\\ &\leq R(f)+(\lambda+a_n)\kappa_m+2a_n\sqrt{x}. \end{aligned}

The last inequality uses $(a_n-\lambda)\kappa_{\widehat m}\leq 0$. Since the inequality holds for every $m$ and every $f\in\mathcal F_m$, taking the infimum proves the result. $\square$

This proof separates the two roles of the penalty. It charges the comparator model through $\lambda\kappa_m$, and it prevents the selected model’s complexity fluctuation from appearing as an uncontrolled positive term. At the threshold choice $\lambda=a_n$, the complexity term in the oracle bound is $2a_n\kappa_m$. Choosing a larger $\lambda$ remains valid, but increases the comparator’s penalty in that bound.

Worked Examples: Computing the Scale

Worked Example: A Sixteen-Predictor Model

Suppose $\sigma=2$, $n=800$, $N_m=16$, $w_m=2$, and $x=\log 20$. Compute the model’s deviation bound and the confidence level.

The coefficient is $a_n=2\sqrt{2/800}=2\sqrt{0.0025}=0.10$. The model complexity is $\kappa_m=\sqrt{\log(2\cdot16)+2}=\sqrt{\log32+2}$. Since $\log32\approx3.4657$, this gives $\kappa_m\approx\sqrt{5.4657}\approx2.338$. The common remainder is $a_n\sqrt{x}=2\sqrt{2\log(20)/800}\approx0.1731$. Therefore the deviation bound for every predictor in this model is approximately $0.10(2.338)+0.1731=0.4069$.

The event has probability at least $1-e^{-x}=1-1/20=0.95$, provided the model weights across the full collection satisfy the stated weight condition. The penalty coefficient threshold is $a_n=0.10$; the model-specific penalty at that threshold is $0.10(2.338)\approx0.234$.

Worked Example: Comparing Two Model Complexities

Take $\sigma=1$, $n=500$, and two models with $w_1=w_2=\log2$. Let $N_1=4$ and $N_2=64$. Find the complexity values and the corresponding penalty thresholds.

Here $a_n=\sqrt{2/500}=\sqrt{0.004}\approx0.06325$. For the first model, $\kappa_1=\sqrt{\log8+\log2}=\sqrt{\log16}\approx1.6651$. For the second, $\kappa_2=\sqrt{\log128+\log2}=\sqrt{\log256}\approx2.3548$.

The threshold penalty contributions $a_n\kappa_m$ are therefore approximately $0.06325(1.6651)=0.1053$ and $0.06325(2.3548)=0.1489$. The larger class receives the larger penalty because its empirical risk has more opportunities to fluctuate downward. The coefficient threshold is the same in both models; the complexity multiplier is not.

Under-Regularization and Over-Regularization

The derivation also quantifies what happens below the threshold. Suppose more generally that the model penalty is $p_m$, not necessarily $\lambda\kappa_m$. The same proof gives, on the simultaneous-deviation event,

R(\widehat f)\leq \inf_m\inf_{f\in\mathcal F_m} \left\{R(f)+p_m+a_n\kappa_m\right\} +2a_n\sqrt{x}+\Delta, \qquad \Delta=\sup_m\left(a_n\kappa_m-p_m\right)_+,

when $\Delta$ is finite. Here $u_+=\max(u,0)$. To see the extra term, the proof’s selected-model contribution is $a_n\kappa_{\widehat m}-p_{\widehat m}$, which is at most $\Delta$. If $p_m=\lambda\kappa_m$ and $\lambda<a_n$, then $\Delta=(a_n-\lambda)\sup_m\kappa_m$, provided that supremum is finite. If it is infinite, this argument supplies no finite uniform remainder. A penalty below the theoretical scale is not automatically invalid, but this oracle argument can no longer control the selected model’s complexity by the penalty alone.

Over-regularization has a different cost. When $\lambda>a_n$, the selected-model term is safely nonpositive, but the comparator term $(\lambda+a_n)\kappa_m$ is larger. Thus the bound may become less informative for complex models even though the proof remains valid. The oracle inequality describes this tradeoff; it does not establish that the largest penalty satisfying the proof is optimal for every prediction problem.

Worked Example: How an Excessive Penalty Changes the Oracle Choice

Suppose two candidate models have risks and complexity values $(R_A,\kappa_A)=(0.02,1)$ and $(R_B,\kappa_B)=(0,4)$. Compare their oracle criterion $R+\lambda\kappa$ at two values of $\lambda$.

At $\lambda=0.005$, model A has criterion $0.02+0.005(1)=0.025$, while model B has $0+0.005(4)=0.020$. The more complex model has the smaller criterion. At $\lambda=0.01$, the criteria are $0.02+0.01(1)=0.030$ for A and $0+0.01(4)=0.040$ for B, so the simpler model has the smaller criterion.

The crossover solves $0.02+\lambda=4\lambda$, giving $\lambda=0.02/3\approx0.00667$. This calculation does not say which model is truly preferable in a particular application; it shows explicitly how increasing a penalty can change the comparator favored by the oracle expression.

What the Scale Does—and Does Not—Claim

In this setting, the coefficient scale is

\lambda\ \text{of order}\ \frac{\sigma}{\sqrt n}, \qquad \text{with model penalty of order }\frac{\sigma}{\sqrt n}\, \sqrt{\log(2N_m)+w_m}.

This order follows from the assumed square-root deviation inequality. It is not a context-free rule for all regularization problems. A different tail condition, a variance-sensitive bound, a curvature condition, or a different normalization of the objective can change the penalty form or its rate. In particular, if the objective uses a sum of losses rather than an average, a penalty expressed on that scale must be multiplied by $n$. Always check how empirical risk and the penalty are normalized before comparing coefficients.

The result also concerns a theoretical penalty calibrated using a known noise bound and specified complexity weights. It does not itself explain how to estimate an unknown noise level or select among penalties using held-out data. Its purpose is narrower: under explicit assumptions, it shows which order is sufficient to absorb simultaneous empirical-risk fluctuations and what remains in the oracle inequality.

Common Mistake

Ignoring the two-sided tail factor. Substituting $t=\log(2N_m)+w_m+x$ into $2e^{-t}$ gives $e^{-\log N_m-w_m-x}$, not $e^{-\log(2N_m)-w_m-x}$. Multiplying by $N_m$ then gives $e^{-w_m-x}$, which is what makes the model-weight sum at most $e^{-x}$.
Using the same penalty for every model. A coefficient of order $\sigma/\sqrt n$ must be multiplied by an appropriate complexity term when models differ in size or weight.
Calling the threshold universally optimal. It is sufficient for the displayed proof under the stated concentration assumption. It is not a universal tuning rule for other losses, assumptions, or objective normalizations.

Key takeaway: Under the stated sub-Gaussian deviation bound, simultaneous control leads to a model penalty of order $\sigma\sqrt{\{\log(2N_m)+w_m\}/n}$. A coefficient at least $\sigma\sqrt{2/n}$ absorbs the selected-model fluctuation; a smaller coefficient leaves a complexity deficit, while a larger one increases the oracle comparator cost.

Check Your Understanding

Use the assumptions and definitions in this tutorial to answer the following.

If the sample size is multiplied by four while $\sigma$ and model complexity remain fixed, how does the coefficient threshold $a_n$ change?
Why does the within-model complexity involve $N_m$, and what role do the weights $w_m$ play?
For a penalty $p_m$, identify the term in the oracle proof that is controlled by $\Delta$.
Why does choosing $\lambda>a_n$ preserve the proof but increase the comparator penalty in the displayed oracle inequality?
If an objective uses summed losses instead of average losses, what adjustment is needed when translating the penalty scale?