Generalization Bounds From Convolutional Parameter Sharing

Why Parameter Sharing Changes a Complexity Bound

A convolutional layer applies the same filter at many spatial locations. This is a structural restriction: instead of fitting a separate set of weights at every location, the model reuses one set. A complexity bound can reflect this restriction through the number of free parameters, but that comparison is meaningful only after the model, pooling rule, and norm budgets have been specified.

We derive a covering-based bound for a single convolutional layer followed by average pooling and a fixed linear readout. The calculation makes the filter norm and number of channels explicit. We then compare it with a layer that has independent filters at each location. The result isolates one benefit of sharing—the parameter-dimension term is smaller—without claiming that sharing always improves prediction or yields a factor of the number of locations in the final bound.

Model and Norm Assumptions

Definition: An input has $m$ spatial patches $z_1,\ldots,z_m\in\mathbb R^q$, each satisfying $\|z_p\|_2\le R$. A convolutional layer has $C$ filters, collected as the rows of $W\in\mathbb R^{C\times q}$. With coordinatewise activation $\sigma$, fixed readout $a\in\mathbb R^C$, and average pooling, its scalar prediction is $$ f_W(x)=a^\top\left(\frac{1}{m}\sum_{p=1}^m \sigma(Wz_p)\right). $$ We assume $\|W\|_F\le B$, $\|a\|_2\le A$, and that $\sigma(0)=0$ and $|\sigma(u)-\sigma(v)|\le |u-v|$. There are no trainable biases in this model.

The assumptions are deliberately explicit. The patch bound controls how much a change in filter weights can change a prediction. The Frobenius norm $B$ controls the filter matrix, while $A$ controls the readout. The activation condition includes ReLU and ensures $\|\sigma(v)\|_2\le\|v\|_2$ for vectors, by applying the scalar inequality coordinatewise.

For comparison, define an unshared layer by replacing $W$ with separate matrices $W_1,\ldots,W_m$, so that location $p$ uses $W_p$. We impose $\|W_p\|_F\le B$ at every location. This matches the per-filter norm budget in the shared model; it does not impose the same total number of free parameters.

Worked Example: Counting the Free Filter Parameters

Suppose patches have $q=9$ entries and the layer has $C=16$ channels. Each shared filter has 9 entries, so the shared layer has $Cq=16(9)=144$ trainable filter entries.

If there are $m=25$ locations and the filters are unshared, there are $mCq=25(16)(9)=3{,}600$ entries. The ratio is $3{,}600/144=25$: the unshared parameterization has one independent copy of the filter bank per location. This is a parameter-count comparison, not yet a claim that the shared model has exactly one twenty-fifth the generalization error.

How Filter Perturbations Change Predictions

The first step is to bound the effect of changing the parameters. In the shared model, the same perturbation affects every patch, but average pooling averages the resulting changes. The triangle inequality gives a direct bound without assuming that different patches are independent.

Lemma: Under the model assumptions, for any $W,U\in\mathbb R^{C\times q}$, $$ |f_W(x)-f_U(x)|\le AR\|W-U\|_F. $$ For the unshared model, if $\|W_p\|_F,\|U_p\|_F\le B$ for every $p$, then $$ |f_{W_1,\ldots,W_m}(x)-f_{U_1,\ldots,U_m}(x)| \le \frac{AR}{\sqrt m} \left(\sum_{p=1}^m\|W_p-U_p\|_F^2\right)^{1/2}. $$

Proof. For the shared model, Cauchy–Schwarz and the 1-Lipschitz property give

\begin{aligned} |f_W(x)-f_U(x)| &\le \|a\|_2\frac{1}{m}\sum_{p=1}^m \|\sigma(Wz_p)-\sigma(Uz_p)\|_2\\ &\le A\frac{1}{m}\sum_{p=1}^m \|(W-U)z_p\|_2\\ &\le A\frac{1}{m}\sum_{p=1}^m \|W-U\|_F\|z_p\|_2 \le AR\|W-U\|_F. \end{aligned}

For unshared filters, apply the same inequalities at each location, then use Cauchy–Schwarz on the sum:

\begin{aligned} |f_{\mathbf W}(x)-f_{\mathbf U}(x)| &\le \frac{AR}{m}\sum_{p=1}^m\|W_p-U_p\|_F\\ &\le \frac{AR}{m}\sqrt m \left(\sum_{p=1}^m\|W_p-U_p\|_F^2\right)^{1/2}. \end{aligned}

Since $\sqrt m/m=1/\sqrt m$, this is the stated bound. Neither derivation assumes independence among patches. $\square$

Worked Example: Reading the Sensitivity Constants

Take $A=2$, $R=3$, and $m=49$. For shared filters, changing $W$ by Frobenius distance $0.01$ changes any prediction by at most $AR(0.01)=2(3)(0.01)=0.06$.

For unshared filters, a joint perturbation of Euclidean Frobenius distance $0.01$, meaning $(\sum_p\|W_p-U_p\|_F^2)^{1/2}=0.01$, changes the prediction by at most $AR(0.01)/\sqrt{49}=6(0.01)/7\approx0.008571$. This smaller sensitivity is a consequence of average pooling and the joint parameter norm. It does not erase the fact that the unshared model has more parameters.

A Covering Bound for Shared and Unshared Filters

A finite covering of the parameter set induces a finite covering of the prediction functions: if two parameter values are close enough, the lemma ensures their predictions are uniformly close on every allowed input. We use this observation to state the complexity comparison precisely.

Theorem: Let $\mathcal F_{\mathrm{sh}}$ be the shared-filter class above, with $\|W\|_F\le B$, and let $\mathcal F_{\mathrm{un}}$ be the unshared class with $\|W_p\|_F\le B$ at every location. For any fixed sample $S=(x_1,\ldots,x_n)$ satisfying the patch bound and any $\varepsilon>0$, their empirical Rademacher complexities satisfy $$ \begin{aligned} \mathfrak R_S(\mathcal F_{\mathrm{sh}}) &\le \varepsilon+ABR \sqrt{\frac{2\left[\log 2+Cq\log(1+2ABR/\varepsilon)\right]}{n}},\\ \mathfrak R_S(\mathcal F_{\mathrm{un}}) &\le \varepsilon+ABR \sqrt{\frac{2\left[\log 2+mCq\log(1+2ABR/\varepsilon)\right]}{n}}. \end{aligned} $$ Here $\mathfrak R_S(\mathcal F)=E_\xi[\sup_{f\in\mathcal F}n^{-1}\sum_{i=1}^n\xi_i f(x_i)]$, where the $\xi_i$ are independent random signs.

Proof. First, every shared prediction is bounded in absolute value by $ABR$:

|f_W(x)| \le A\frac{1}{m}\sum_{p=1}^m\|\sigma(Wz_p)\|_2 \le A\frac{1}{m}\sum_{p=1}^m\|W\|_F\|z_p\|_2 \le ABR.

The same bound holds for the unshared model, since each $\|W_p\|_F\le B$. Thus both classes have prediction functions bounded by $M=ABR$.

For the shared class, the Frobenius ball of radius $B$ in $Cq$ dimensions has a parameter net of radius $r$ with at most $(1+2B/r)^{Cq}$ points. This is the standard Euclidean ball covering bound. By the lemma, choosing $r=\varepsilon/(AR)$ gives a function net with uniform prediction error at most $\varepsilon$, and its size $N_{\mathrm{sh}}$ obeys

\log N_{\mathrm{sh}}\le Cq\log(1+2ABR/\varepsilon).

For the unshared class, stack all $m$ matrices into one vector in dimension $mCq$. The constraint $\|W_p\|_F\le B$ implies that the stacked vector has norm at most $\sqrt m B$. A parameter net of radius $r=\varepsilon\sqrt m/(AR)$, together with the unshared sensitivity bound, gives uniform prediction error at most $\varepsilon$. The ball covering bound therefore yields

\log N_{\mathrm{un}}\le mCq\log\left(1+\frac{2\sqrt m B}{\varepsilon\sqrt m/(AR)}\right) =mCq\log(1+2ABR/\varepsilon).

Finally, suppose a function class has a uniform $\varepsilon$-net of size $N$ and all its functions are bounded by $M$. Replacing any function in the Rademacher supremum by a net function changes the signed sample average by at most $\varepsilon$. For the finite net, each signed average has moment-generating function bounded by $\exp(\lambda^2M^2/(2n))$, because it is a sum of independent signs with coefficients bounded by $M/n$. Applying the log-sum-exp bound to the $N$ net functions gives an expected maximum at most $M\sqrt{2\log N/n}$. Including a zero function in the net if necessary, or using the harmless upper bound $\log(2N)$, gives

\mathfrak R_S(\mathcal F)\le \varepsilon+M\sqrt{\frac{2\log(2N)}{n}}.

Substituting $M=ABR$ and the two covering-number bounds proves both inequalities. $\square$

Worked Example: Evaluating the Bound at a Chosen Resolution

Let $A=B=R=1$, $n=100{,}000$, and choose prediction resolution $\varepsilon=0.1$. Take $Cq=2$ and $m=4$. Then $\log(1+2ABR/\varepsilon)=\log(21)\approx3.044522$.

For shared filters, the quantity inside the square root is

\frac{2[\log 2+2\log(21)]}{100{,}000} =\frac{2[0.693147+6.089044]}{100{,}000} \approx0.000135644.

Its square root is approximately $0.011647$. The bound is therefore $0.1+0.011647=0.111647$.

For unshared filters, the parameter dimension is $mCq=8$, giving

\frac{2[\log 2+8\log(21)]}{100{,}000} =\frac{2[0.693147+24.356176]}{100{,}000} \approx0.000500986.

The square root is approximately $0.022383$, so the bound is $0.122383$. At this chosen resolution, the covering bound is smaller for sharing. Both values are upper bounds, not estimates of the actual complexity, and their shared $0.1$ approximation term remains.

What the Comparison Says—and Does Not Say

The theorem isolates a clear architectural effect: the dimension in the covering term is $Cq$ for shared filters and $mCq$ for position-specific filters. For fixed $A,B,R,\varepsilon$, the difference enters through the logarithm of the covering size. It is not generally a multiplicative $1/m$ reduction in the full bound. The filter and readout norms control the scale $ABR$, while the channel count enters through $Cq$.

The use of average pooling matters. It produces the $1/\sqrt m$ sensitivity for a joint perturbation of unshared parameters, while the per-location norm constraint keeps predictions bounded by $ABR$. With a different pooling rule, norm budget, or readout, the calculation can change. Consequently, complexity comparisons should state these choices rather than relying only on the phrase “weight sharing.”

Worked Example: A Larger Shared Layer and Its Unshared Counterpart

Suppose $q=25$, $C=32$, and $m=49$. The shared filter matrix has $Cq=32(25)=800$ entries. The unshared version has $mCq=49(800)=39{,}200$, exactly 49 times as many.

Now take $A=2$, $B=0.5$, and $R=3$. The common prediction scale in the theorem is $ABR=2(0.5)(3)=3$. The shared parameter-to-prediction sensitivity is $AR=6$; for the unshared joint parameter norm it is $AR/\sqrt{49}=6/7\approx0.857143$. Since the unshared per-location constraint implies a stacked radius of at most $\sqrt{49}B=3.5$, its radius times sensitivity is $3.5(6/7)=3$, matching $ABR$. Thus the comparison has the same logarithmic scale $1+2(3)/\varepsilon$, but dimension 800 versus 39,200.

Generalization Interpretation and a Common Pitfall

To turn a predictor-class complexity bound into a risk statement, let observations be independent and identically distributed, and suppose the loss $\ell(y,t)$ takes values in $[0,1]$ and is 1-Lipschitz in $t$. The standard Rademacher generalization bound controls the difference between population and empirical risks, with high probability, by twice the empirical Rademacher complexity of the loss class plus a term of order $\sqrt{\log(1/\eta)/n}$, where $1-\eta$ is the confidence level. Contraction transfers the predictor-class bound to this loss class, up to the usual harmless treatment of additive constants. Thus the covering comparison informs a generalization bound when these loss and sampling conditions hold.

Common mistake: “There are $m$ times fewer parameters, so the generalization bound must be $m$ times smaller.” The theorem does not say this. The dimension appears inside a square root and a logarithm, and the bound also contains the norm scale, the chosen covering resolution, and the sampling term from the risk inequality. Moreover, sharing restricts the functions the model can represent. If location-specific patterns genuinely differ, independent filters may fit them better, even though their complexity bound is larger. The appropriate comparison considers both estimation complexity and the modeling restriction.

Key takeaway: Under the stated pooling and norm assumptions, sharing changes the covering dimension from $mCq$ to $Cq$. The resulting bound depends on filter and readout norms as well as channel count; it quantifies a complexity advantage, not a guarantee that sharing is always more accurate.

Check Your Understanding

Use the assumptions and notation defined above.

How many trainable filter entries are there in each parameterization when $q=5$, $C=8$, and $m=12$?
Which step in the unshared sensitivity calculation introduces the factor $1/\sqrt m$?
Why does the theorem’s comparison not imply an $m$-fold reduction in the full complexity bound?
What changes in the argument if the patch norm bound $R$ is doubled while $A$ and $B$ stay fixed?
Give one reason that a lower complexity bound for a shared class need not mean it has lower prediction error on a particular problem.