Residual Connections in Neural Complexity Bounds

Why Residual Connections Change Complexity Bounds

A norm-based bound for a deep network depends on how changes at one layer are amplified by later layers. In a plain composition, those amplification factors multiply across layers. A residual block adds its transformed input back to the current representation, so its Lipschitz factor is typically bounded by one plus the factor for the residual branch. This is not automatically a smaller bound, but it changes the depth dependence in a meaningful and explicit way.

We derive that dependence for a residual network, then use it to control how much predictions can change when parameters are perturbed. A finite cover of the parameter space yields a prediction cover, which in turn gives a uniform generalization bound. The result is deliberately stated with bounded inputs and bounded losses: those assumptions ensure that the covering argument controls predictions on the data distribution.

Network and Norm Assumptions

Consider a network with \(L\) residual blocks and hidden dimension \(m\). The input is \(x\in\mathbb{R}^d\). Let \(J:\mathbb{R}^d\to\mathbb{R}^m\) be a fixed map with operator norm at most one, and define \(h_0(x)=Jx\). For \(l=1,\ldots,L\), set

Here \(A_l,B_l\) are \(m\times m\) matrices, \(w\in\mathbb{R}^m\), and \(\sigma\) is coordinatewise ReLU. ReLU is 1-Lipschitz in Euclidean norm and satisfies \(\|\sigma(u)\|_2\leq\|u\|_2\). Assume the parameter class obeys

The subscript 2 on a matrix denotes its spectral norm; \(F\) denotes its Frobenius norm. Define \(q_l=1+a_lb_l\). The spectral bounds control propagation through the network, while the Frobenius bounds will control the number of parameter values needed in a cover.

Hidden-State Growth and Parameter Perturbations

The skip connection contributes the identity map to each block. By the triangle inequality and the Lipschitz property of ReLU,

Thus a block can expand differences by at most \(q_l\). Applying this repeatedly also bounds the size of hidden states.

Proof. Since \(\|h_0(x)\|_2=\|Jx\|_2\leq R\), the block bound gives \(\|h_l(x)\|_2\leq q_l\|h_{l-1}(x)\|_2\). Induction proves the hidden-state bound.

For the perturbation claim, write \(e_l=\|h_l(x)-h_l'(x)\|_2\). At block \(l\), add and subtract \(B_l'\sigma(A_lh_{l-1}(x))\) and \(B_l'\sigma(A_l'h_{l-1}(x))\). The residual maps applied to the two hidden states contribute at most \(q_le_{l-1}\). The changes in \(B_l\) and \(A_l\) contribute at most \(a_l\tau\|h_{l-1}(x)\|_2\) and \(b_l\tau\|h_{l-1}(x)\|_2\), respectively. Therefore

Iterating this inequality gives

Finally, compare the two output layers:

Substituting the bound for \(e_L\) proves the claimed inequality. \(\square\)

From Parameter Covers to Generalization

A cover is a finite collection of parameter settings such that every allowed setting is close to one of them. In a \(p\)-dimensional Euclidean ball of radius \(F\), a subset has a \(\tau\)-cover with at most \((1+2F/\tau)^p\) centers chosen from that subset. This follows by taking a maximal \(\tau\)-separated set: its radius-\(\tau/2\) balls are disjoint and lie in a radius-\(F+\tau/2\) ball, so comparison of volumes gives the stated count. Maximality ensures that the set covers the subset within \(\tau\).

Apply this fact to each matrix and to the output vector, with centers restricted to the allowed parameter class. The matrices have \(m^2\) entries and the output vector has \(m\) entries. Taking products of the individual covers and using the perturbation result gives a prediction cover, uniform over the entire input ball.

Proof. The parameter covers just constructed have at most \(N_\tau\) representatives. The perturbation result makes each network's predictions differ from its representative by at most \(K\tau\) for every \(\|x\|_2\leq R\). The Lipschitz condition on the loss therefore makes the corresponding losses differ by at most \(L_\ell K\tau\), on the support of the data distribution and on every sample drawn from it.

For completeness, let \(\mathcal{G}\) be the class of loss functions \(g_\theta(z)=\ell(y,f_\theta(x))\), and let \(\mathcal{G}_\tau\) be the finite class of losses at the cover representatives. On any sample, define the empirical Rademacher average with an absolute supremum by \(\widehat{\mathfrak R}_n(\mathcal{G})=E_\varepsilon[\sup_{g\in\mathcal{G}}|n^{-1}\sum_i\varepsilon_i g(Z_i)|]\), where the \(\varepsilon_i\) are independent signs taking values \(1\) and \(-1\) with equal probability. Approximation by the cover gives

For the second inequality, each representative loss lies in \([0,1]\). For each fixed representative, the Rademacher sum has the usual bounded-variable exponential bound; applying the exponential maximum bound to the \(2N_\tau\) signed sums (including both signs for the absolute value), then optimizing the exponential parameter, gives the displayed square-root bound.

The standard symmetrization inequality bounds the expected supremum of \(P g-P_ng\) by twice the expected empirical Rademacher average. It follows by introducing an independent sample with the same law, applying Jensen's inequality to replace \(Pg\) by the average over that sample, and then independently swapping each paired observation; the swap signs produce the Rademacher sum. Finally, changing one observation changes \(\sup_g(Pg-P_ng)\) by at most \(1/n\), because \(0\leq g\leq1\). McDiarmid's inequality therefore adds at most \(\sqrt{\log(1/\delta)/(2n)}\) with probability at least \(1-\delta\). Combining these facts with the deterministic cover bound proves the theorem. \(\square\)

Interpreting the Depth Dependence

For a plain composition with layer factors \(a_lb_l\), the corresponding propagation factor is a product of those factors. For the residual architecture here, it is bounded by

If \(a_lb_l=c\) at every layer, this becomes \((1+c)^L\), rather than \(c^L\). When the residual branches are small, the inequality \(1+c\leq e^c\) gives \((1+c)^L\leq e^{Lc}\). This can be substantially more controlled than a product of large branch factors, but it still grows with depth unless the branch norms or other constraints control that growth. The cover size also depends on the number of parameters and on the chosen cover radius; skip connections alone do not remove those terms.

The input-support assumption in the theorem is essential. The prediction cover was proved uniformly only for inputs satisfying \(\|x\|_2\leq R\). If the distribution assigns positive probability outside that ball, the cover need not approximate predictions on those observations, so the displayed population-risk conclusion does not follow from this argument. A different proof would need a cover valid on the distribution's support or an explicit treatment of the probability outside the ball.

Common Mistakes

• Multiplying only the residual-branch norms. The block includes the identity path, so its Lipschitz factor is bounded by \(1+a_lb_l\), not just \(a_lb_l\).
• Reading an upper bound as an exact growth rate. Products of \(q_l\) bound hidden-state growth and perturbation propagation; particular networks can grow less.
• Using a cover outside its domain. A cover uniform on an input ball controls population losses only when the input distribution is supported on that ball, or when a separate argument controls inputs outside it.
• Assuming a skip connection guarantees a useful bound. The factors, cover size, and sample size all matter. A mathematically valid bound can still be numerically uninformative.