Fully connected and residual networks with the Du Gram kernel

Assume AC, DC and countable choice for the Gaussian probability-law constructions below. The displayed finite real network recurrences and empirical loss are deterministic definitions for fixed parameters. Fix positive integers $d,n,H,m$, training inputs $x_1,\dots ,x_n\in {\mathbb{R}}^d$ with $\mathrm{\parallel }{x}_i{\mathrm{\parallel }}_2=1$, labels $y_1,\dots ,y_n\in \mathbb{R}$, an analytic nonpolynomial activation $\sigma$ satisfying $\mathrm{\mid }\sigma (0)\mathrm{\mid }<\mathrm{\infty }$ and finite Lipschitz constants for $\sigma$ and ${\sigma }^{\mathrm{\prime }}$, and the positive finite normalization $c_{\sigma }=({\mathbb{E}}_{Z\sim N(0,1)}[\sigma (Z{)}^2]{)}^{-1}$. A fully connected network of width $m$ and depth $H$ is the finite feedforward recurrence

$x^{(0)}=x,x^{(h)}=\sqrt{c_{\sigma }\mathrm{/}m}\sigma (W^{(h)}{x}^{(h-1)})(1\le h\le H),f_{\mathrm{f}\mathrm{c}}(x,\theta )=a^T{x}^{(H)},$

where $W^{(1)}\in {\mathbb{R}}^{m\times d}$, $W^{(h)}\in {\mathbb{R}}^{m\times m}$ for $h\ge 2$, $a\in {\mathbb{R}}^m$, and $\sigma$ acts coordinatewise. The residual network uses the same first layer and then

$x^{(1)}=\sqrt{c_{\sigma }\mathrm{/}m}\sigma (W^{(1)}x),x^{(h)}=x^{(h-1)}+\frac{c_{\mathrm{r}\mathrm{e}\mathrm{s}}}{H\sqrt{m}}\sigma (W^{(h)}{x}^{(h-1)})(2\le h\le H),f_{\mathrm{r}\mathrm{e}\mathrm{s}}(x,\theta )=a^T{x}^{(H)},$

with $0<c_{\mathrm{r}\mathrm{e}\mathrm{s}}<1$. In either architecture, random initialization means all entries of all matrices $W^{(h)}$ and of $a$ are independent $N(0,1)$ random variables; all these entries are trained by full-batch gradient descent. The empirical quadratic loss is $L(\theta )=\frac{1}{2}{\sum }_{i=1}^n(f(x_i,\theta )-y_i{)}^2$.

For the fully connected architecture and the same fixed data, define the population matrices by

$K_{ij}^{(0)}=⟨x_i,x_j⟩\mathrm{.}$

For $1\le h<H$, let $(U_{ij}^{(h)},V_{ij}^{(h)})$ be a centered bivariate normal vector with covariance

$A_{ij}^{(h)}=\left(\begin{array}{cc}{K}_{ii}^{(h-1)}& K_{ij}^{(h-1)}\\ K_{ji}^{(h-1)}& K_{jj}^{(h-1)}\end{array}\right),$

and put $K_{ij}^{(h)}=c_{\sigma }\mathbb{E}[\sigma (U_{ij}^{(h)})\sigma (V_{ij}^{(h)})]$. For $h=H$, use the same bivariate-normal definition with $A_{ij}^{(H)}$ formed from $K^{(H-1)}$, and set

$K_{ij}^{(H)}=c_{\sigma }{K}_{ij}^{(H-1)}\mathbb{E}[{\sigma }^{\mathrm{\prime }}(U_{ij}^{(H)}){\sigma }^{\mathrm{\prime }}(V_{ij}^{(H)})]\mathrm{.}$

When $H=1$, this last formula uses $K^{(0)}$ directly and there are no intermediate activation-covariance matrices. For the fully connected theorem, this terminal matrix is denoted $K_{\mathrm{f}\mathrm{c}}^{(H)}$.

For the residual architecture with $H\ge 2$, use a separate sequence $S^{(h)}$ and mean vector $b^{(h)}$. Set $S^{(0)}=K^{(0)}$. For $G^{(0)}\sim N_n(0,S^{(0)})$, put

$S_{ij}^{(1)}=c_{\sigma }\mathbb{E}[\sigma (G_i^{(0)})\sigma (G_j^{(0)})],b_i^{(1)}=\sqrt{c_{\sigma }}\mathbb{E}[\sigma (G_i^{(0)})]\mathrm{.}$

Write $\alpha =c_{\mathrm{r}\mathrm{e}\mathrm{s}}\mathrm{/}H$. For $2\le h<H$, take a fresh centered Gaussian vector $G^{(h-1)}$ with covariance $S^{(h-1)}$, put ${\mu }_i^{(h-1)}=\mathbb{E}[\sigma (G_i^{(h-1)})]$, and define

$S_{ij}^{(h)}=S_{ij}^{(h-1)}+\alpha (b_i^{(h-1)}{\mu }_j^{(h-1)}+b_j^{(h-1)}{\mu }_i^{(h-1)})+{\alpha }^2\mathbb{E}[\sigma (G_i^{(h-1)})\sigma (G_j^{(h-1)})],b_i^{(h)}=b_i^{(h-1)}+\alpha {\mu }_i^{(h-1)}\mathrm{.}$

For $G\sim N_n(0,S^{(H-1)})$, define the residual terminal matrix by

$K_{\mathrm{r}\mathrm{e}\mathrm{s},ij}^{(H)}=\frac{c_{\mathrm{r}\mathrm{e}\mathrm{s}}^2}{H^2}{S}_{ij}^{(H-1)}\mathbb{E}[{\sigma }^{\mathrm{\prime }}(G_i){\sigma }^{\mathrm{\prime }}(G_j)]\mathrm{.}$

The fully connected and residual convergence statements use $K_{\mathrm{f}\mathrm{c}}^{(H)}$ and $K_{\mathrm{r}\mathrm{e}\mathrm{s}}^{(H)}$, respectively. At $H=1$, the two architectures coincide; define $K_{\mathrm{r}\mathrm{e}\mathrm{s}}^{(1)}=K_{\mathrm{f}\mathrm{c}}^{(1)}$. The residual recursion above is the scalar specialization of the source's general mean/second-moment recursion, equation (16); in particular it includes the mean cross terms. Its terminal Gaussian covariance is $S^{(H-1)}$, as determined by the finite-width last-layer Gram formula (14).

The residual recurrence has one identity contribution from $x^{(h-1)}$ and one nonlinear contribution at every layer $2\le h\le H$; the arrows below depict that convention for one generic layer and do not enter any proof.

diagram failed to render:
\begin{tikzpicture}[>=stealth,node distance=1.3cm]
  \node (in) {$x^{(h-1)}$};
  \node[draw,rectangle,right=1.7cm of in] (act) {$\frac{c_{\rm res}}{H\sqrt m}\sigma(W^{(h)}x^{(h-1)})$};
  \node[draw,circle,right=2.0cm of act] (sum) {$+$};
  \node[right=1.2cm of sum] (out) {$x^{(h)}$};
  \draw[->] (in) -- (act);
  \draw[->] (act) -- (sum);
  \draw[->] (in) to[bend right=28] (sum);
  \draw[->] (sum) -- (out);
\end{tikzpicture}

Du et al., fully connected and residual architectures, equations (2)–(3)

Du et al., population Gram recursions, Definitions 5.1 and 6.1, equations (7) and (8)

Du et al., Appendix C, last-layer Gram formula (14)

Du et al., Appendix E.1, general population mean and second-moment recursion (16)–(17)

Finite feedforward computation graphs and layered perceptrons

Princeton Theory of Deep Learning, Chapter 8, §§8.1–8.5, infinite-width context