Overparameterized networks and training to interpolation — Examples

For $t<0$, $\sigma (t)=0$, so its left derivative at $0$ is $0$; for $t>0$, $\sigma (t)=t$, so its right derivative at $0$ is $1$. The two one-sided derivatives differ, and the derivative at $0$ does not exist.

Every analytic real function is differentiable at every point of its domain. Since ReLU is not differentiable at $0$, it is not analytic; it also fails the Lipschitz-derivative condition in [F1].

Substituting $h=2$ gives an identity contribution $x^{(1)}$ and nonlinear contribution $\frac{c_{\mathrm{r}\mathrm{e}\mathrm{s}}}{3\sqrt{m}}\sigma (W^{(2)}{x}^{(1)})$ in $x^{(2)}$.

Substituting $h=3$ gives an identity contribution $x^{(2)}$ and nonlinear contribution $\frac{c_{\mathrm{r}\mathrm{e}\mathrm{s}}}{3\sqrt{m}}\sigma (W^{(3)}{x}^{(2)})$ in $x^{(3)}$. Thus the recurrence contains the skip at both post-initial layers.

At the training point, $g_0(0)=g_1(0)=0=y$, so both one-point empirical losses $\frac{1}{2}(g_j(0)-y{)}^2$ are zero.

At the test point, $g_0(1)=0$ and $g_1(1)=1$, so the two predictors agree on the entire training sample but have different test predictions. This verifies the stated logical limitation of empirical interpolation.

The rows $i,j$ of $K^{(0)}$ coincide because $K_{i\mathrm{\ell }}^{(0)}=⟨x_i,x_{\mathrm{\ell }}⟩=⟨x_j,x_{\mathrm{\ell }}⟩=K_{j\mathrm{\ell }}^{(0)}$ for every $\mathrm{\ell }$. This is the base case.

Assume rows $i,j$ of $K^{(h-1)}$ coincide. By [F2], the matrix is symmetric, so the corresponding columns coincide as well. For each $\mathrm{\ell }$, the covariance matrices $A_{i\mathrm{\ell }}^{(h)}$ and $A_{j\mathrm{\ell }}^{(h)}$ are equal. Thus the Gaussian activation expectations agree for $h<H$, and for $h=H$ both the derivative expectations and prefactors $K_{i\mathrm{\ell }}^{(H-1)}$, $K_{j\mathrm{\ell }}^{(H-1)}$ agree. Hence rows $i,j$ of the fully connected $K^{(h)}$ coincide.

For the fixed $H$, let $P(h)$ assert that rows $i,j$ of $K^{(h)}$ coincide for $0\le h\le H$. Step 1.1 gives the base, and step 1.2 proves $P(h)$ from $P(h-1)$ for every $1\le h\le H$. By [F4], the fully connected terminal rows coincide. For $H=1$, the residual terminal matrix equals this fully connected terminal matrix by definition, so its rows also coincide.

Now assume $H\ge 2$. For $1\le h<H$, let $Q(h)$ assert both that rows $i,j$ of $S^{(h)}$ coincide and that $b_i^{(h)}=b_j^{(h)}$. The base $S^{(0)}=K^{(0)}$ has equal rows by step 1.1. At layer $1$, this equality and symmetry from [F2] make the pair covariance matrices for indices $(i,\mathrm{\ell })$ and $(j,\mathrm{\ell })$ identical for every $\mathrm{\ell }$, and give $S_{ii}^{(0)}=S_{jj}^{(0)}$. Hence the Gaussian marginal means agree, so the defining formulas give $S_{i\mathrm{\ell }}^{(1)}=S_{j\mathrm{\ell }}^{(1)}$ for every $\mathrm{\ell }$ and $b_i^{(1)}=b_j^{(1)}$; this proves $Q(1)$. For $2\le h<H$, assume $Q(h-1)$. Symmetry from [F2] and equal rows of $S^{(h-1)}$ give equal columns, so the covariance matrices for $(i,\mathrm{\ell })$ and $(j,\mathrm{\ell })$ coincide and ${\mu }_i^{(h-1)}={\mu }_j^{(h-1)}$. In the mean recursion this gives $b_i^{(h)}=b_j^{(h)}$. In the second-moment recursion, the old-row terms agree, the terms $b_i^{(h-1)}{\mu }_{\mathrm{\ell }}^{(h-1)}+b_{\mathrm{\ell }}^{(h-1)}{\mu }_i^{(h-1)}$ agree with their $j$-row counterparts, and the Gaussian activation expectations agree; thus $S_{i\mathrm{\ell }}^{(h)}=S_{j\mathrm{\ell }}^{(h)}$ for every $\mathrm{\ell }$. This proves $Q(h)$. Finite induction gives $Q(H-1)$. The terminal residual formula then has equal prefactors $S_{i\mathrm{\ell }}^{(H-1)}=S_{j\mathrm{\ell }}^{(H-1)}$ and equal derivative expectations because the corresponding pair covariance matrices coincide. Therefore the terminal residual rows coincide.

For either terminal matrix, let $v=e_i-e_j\mathrm{\ne }0$. Symmetry and equal rows imply $K^{(H)}v=0$. By [F2]–[F3], this matrix is positive semidefinite and has a nonzero null vector, so zero is an eigenvalue and the smallest eigenvalue is zero. This proves the residual branch and completes the example.

Softplus is positive and nonconstant. It is analytic, has derivative in $(0,1)$, and its second derivative is at most $1\mathrm{/}4$, so it satisfies the activation regularity assumptions. By [F2] and [F4], $\mu$ is finite; because $\sigma (Z)\ge \log 2$ when $Z\ge 0$ and the standard normal density is positive on $(0,1)$, $\mu >0$. Since softplus is nonconstant, choose $z_0$ with $\sigma (z_0)\mathrm{\ne }\mu$; continuity and the positive Gaussian density give $\mathbb{E}[(s-\mu {)}^2]>0$. Expanding this finite square and using $\mathbb{E}s=\mu$ yields $\mathbb{E}[s^2]>{\mu }^2$. Therefore $0<\rho <1$.

Let $U=\mathrm{span}\{x_1,\dots ,x_n\}$. By [F5], ${\mathbb{R}}^d=U\oplus U^{\perp }$, and [F6] supplies an orthonormal basis of $U^{\perp }$. Joining it to $x_1,\dots ,x_n$ gives the columns of an orthogonal matrix $Q$. By [F7], $W^{(1)}Q$ has the same iid Gaussian law as $W^{(1)}$, so all coordinates $W_{r\cdot }^{(1)}{x}_i$ are independent standard normals. Thus $\mathbb{E}[(\mathrm{\Phi }{\mathrm{\Phi }}^T{)}_{ii}]=c_{\sigma }\mathbb{E}[s^2]=1$, while for $i\mathrm{\ne }j$, $\mathbb{E}[(\mathrm{\Phi }{\mathrm{\Phi }}^T{)}_{ij}]=c_{\sigma }{\mu }^2=\rho$. Therefore $\mathbb{E}[\mathrm{\Phi }{\mathrm{\Phi }}^T]=(1-\rho )I_n+\rho {\mathbf{11}}^T$, and its quadratic form in the unit vector $e$ is $1+(n-1)\rho$.

Conditional on the hidden weights, $e^{T}u=e^T\mathrm{\Phi }a$ is a centered normal random variable with variance $S=e^T\mathrm{\Phi }{\mathrm{\Phi }}^{T}e\ge 0$, by [F1] and [F3]. The nonnegative random variable $S$ has expectation $1+(n-1)\rho >\rho n\mathrm{/}2$, so the event $S>\rho n\mathrm{/}2$ has positive probability; otherwise its expectation would be at most $\rho n\mathrm{/}2$. On this event, for any fixed $C>0$, the conditional probability of $\mathrm{\mid }{e}^{T}u\mathrm{\mid }>C\sqrt{n}$ is at least $P\{\mathrm{\mid }Z\mathrm{\mid }>C\sqrt{2\mathrm{/}\rho }\}>0$. Averaging over the hidden weights proves positive unconditional probability. Since $e$ is a unit vector, write $u=(e^{T}u)e+(u-(e^{T}u)e)$; the summands are orthogonal, so $\mathrm{\parallel }u{\mathrm{\parallel }}_2^2=\mathrm{\mid }{e}^{T}u{\mathrm{\mid }}^2+\mathrm{\parallel }u-(e^{T}u)e{\mathrm{\parallel }}_2^2\ge \mathrm{\mid }{e}^{T}u{\mathrm{\mid }}^2$. This proves the asserted absence of one confidence-uniform constant by a local projection calculation.