Indexed text attachment
partial-differential-equations-in-machine-learning-and-ai.tex
Source for Partial Differential Equations in Machine Learning and AI: Naturality, Well-Posedness, and Spectral Rates
View paper · Download original file
Lines 701–800 of 1085. Source text is displayed literally.
701\node[fwd] at (4.41,2.089) {\scriptsize heat layer, path};702\node[bwd,right] at (2.835,0.959) {\scriptsize heat layer, hypercube};703\end{scope}704\end{tikzpicture}705\caption{Dirichlet energy of a random signal on $32$ nodes against depth, relative to its initial value. Heat-type layers lose it at a rate set by the spectral gap, slowly on a path and quickly on a hypercube; a wave-type layer on the path (\cref{thm:wavegnn}) keeps it.}\label{fig:smooth}706\end{figure}707 708A layer of second order in depth behaves as a wave equation \cite{RCRMB22}.709 710\begin{theorem}[Wave layers]\label{thm:wavegnn}711\Srf[\cite{PDEHC}, Thm.~12.3] The recursion $X_{m+1}=2X_m-X_{m-1}-\tau^2LX_m$ conserves712\[ \tau^{-2}\lVert X_{m+1}-X_m\rVert^2+X_{m+1}^{\T}LX_m, \]713which is positive definite on non-constant signals for $\tau^2\lambda_n<4$. For $\tau^2\lambda_n>4$ the top mode714grows per layer by the modulus of the larger root of $\xi^2+(\tau^2\lambda_n-2)\xi+1=0$.715\end{theorem}716 717\noindent Over $500$ layers at $\tau^2\lambda_n=3.6$ the invariant drifts by $2\times10^{-15}$ and the mean718Dirichlet energy of the last hundred layers is $1.001$ times that of the first hundred: nothing is smoothed. At719$\tau^2\lambda_n=4.4$ the growth factor is $1.8633$. \chk{G3} The bound is the Courant--Friedrichs--Lewy720condition, and the dichotomy between the two theorems is that of \cite[Ch.~4]{PDEHC}: a Markov semigroup721forgets, a symplectic group does not.722 723Both layers assume that neighbouring nodes should agree. A \term{cellular sheaf} \cite{HaGh19} replaces724agreement by agreement after transport: each edge carries linear maps from the data at its ends, and the sheaf725Laplacian $L_{\mathcal F}$ penalizes the mismatch. Its kernel is the space $H^0$ of global sections. The simplest726case is a sign $\sigma_e=\pm1$ on each edge, with $x^{\T}L_{\mathcal F}x=\sum_{e=uv}(x_u-\sigma_ex_v)^2$.727 728\begin{theorem}[Sheaf diffusion]\label{thm:sheaf}729\Sli[\cite{HaGh19,BDCLB22}] Diffusion by $L_{\mathcal F}$ converges to the orthogonal projection of the input730onto $H^0$. For a sign sheaf on a connected graph, $H^0$ has dimension one if the signs are a coboundary,731$\sigma_{uv}=\ell_u\ell_v$, in which case it is spanned by $\ell$; otherwise $H^0=0$. The obstruction is the class732of $\sigma$ in $H^1(G;\Z/2)$, a group of order $2^{E-V+1}$.733\end{theorem}734 735\noindent On a random graph with ten nodes, two classes, and signs $+$ within and $-$ between classes, sheaf736diffusion converges to the class labelling times $\langle\ell,X_0\rangle/n$, to rounding, while ordinary diffusion737converges to a constant and loses the classes. Reversing one edge that lies on a cycle makes the smallest738eigenvalue $0.1606$ and the limit zero; for a cycle of length $7$ with one negative edge it is739$4\sin^2\frac\pi{14}=0.19806$, the antiperiodic Laplacian. \chk{G4} On a graph with $5$ nodes and $7$ edges,740exactly $16=2^{V-1}$ of the $128$ sign assignments have a non-zero section, and they are exactly those whose741Laplacian is singular over the rationals; the $128$ assignments fall into $8=2^{E-V+1}$ classes. \chk{G5} This742is the same first cohomology that classifies flat gauge fields in \cite[Prop.~13.1]{PDEHC}: choosing the743transport maps of a sheaf network is choosing a connection, and heterophily is non-trivial holonomy. A sign744sheaf whose class is non-zero cannot be made consistent by relabelling nodes, and its diffusion has no745non-trivial limit.746 747\section{Depth as time}\label{sec:depth}748 749A residual layer $x\mapsto x+hf(x)$ is one step of forward Euler for $\dot x=f(x)$750\cite{E17,HaRu17}. The type of the linearization of $f$ decides which schemes are admissible, as for partial751differential equations \cite[Ch.~12]{PDEHC}.752 753\begin{theorem}[Layers by type]\label{thm:layers}754\Srf[\cite{HaRu17,CMHRBH18}; \cite{PDEHC}, Thm.~12.2, 12.3]755\begin{enumerate}[label=(\alph*),leftmargin=1.6em,itemsep=1pt,topsep=2pt]756\item \emph{Parabolic}, $f=-Ax$ with $A$ positive definite: forward Euler is stable if and only if757$h\le2/\lambda_{\max}(A)$.758\item \emph{Hyperbolic}, $f=Jx$ with $J$ antisymmetric with eigenvalues $\pm i\omega$: forward Euler multiplies759the norm by $\sqrt{1+h^2\omega^2}$ per layer, for every $h$.760\item For $h,\omega>0$, the leapfrog layer $q\mapsto q+hp$ followed by $p\mapsto p-h\omega^2q$, with the new $q$,761has determinant one, conserves $p^2+\omega^2q^2+h\omega^2pq$, and has bounded powers exactly when $h\omega<2$.762\item In this stable range, the Jacobian of $N$ leapfrog layers in coordinates $(\omega q,p)$ has condition number at most763$(1+\frac{h\omega}2)/(1-\frac{h\omega}2)$, for every $N$. The Jacobian of $N$ parabolic layers with764$h\lambda_{\max}<1$ has condition number $\bigl((1-h\lambda_{\min})/(1-h\lambda_{\max})\bigr)^N$.765\end{enumerate}766\end{theorem}767\begin{proof}768(a) and (b) follow from the eigenvalues of $I+hDf$. For (c), direct computation gives the invariant,769which is positive definite when $h\omega<2$. The update matrix has trace $2-(h\omega)^2$ and determinant one.770At $h\omega=2$ it has a nontrivial Jordan block at $-1$, giving linear growth for some data.771For $h\omega>2$ an eigenvalue has modulus greater than one.772(d): a map that preserves a positive definite quadratic form $Q$ is conjugate to an orthogonal one by $Q^{1/2}$,773so its powers have condition number at most that of $Q$.774\end{proof}775 776\noindent For a random positive definite $A$ of size $6$ the per-layer factor is $0.9814$ at777$h=1.9/\lambda_{\max}$ and $1.1000$ at $2.1/\lambda_{\max}$. \chk{R1} Forward Euler on a rotation grows by778$1.6446$ over time $10$ with $h=0.1$ and by $1.0513$ with $h=0.01$, that is by $e^{h\omega^2T/2}$: the instability779vanishes only in the limit of infinitely many layers. \chk{R2} Leapfrog conserves its invariant to $10^{-14}$ at780$h\omega=1.9$ and grows by $1.8773$ per layer at $2.1$. \chk{R3} With $h\omega=\frac12$ the condition number of the781product of $50$, $200$ and $800$ leapfrog Jacobians is $1.07$, $1.30$ and $1.53$, below the bound $1.667$; for782fifty Euler layers on eigenvalues $1$ and $10$ with $h=0.05$ it is $8.7\times10^{13}$. \chk{R4} Since783back-propagation multiplies by the transposed Jacobians, (d) is a statement about vanishing and exploding784gradients: a symplectic architecture has neither, by the conservation law that a wave equation has and a heat785equation lacks. The price is \cref{thm:wavegnn}: it does not forget either.786 787\section{Kernels and losses}\label{sec:kernels}788 789In the kernel regime, gradient descent on the squared loss moves the function by790$f\mapsto f-\eta K(f-y)$ for a positive kernel operator $K$ \cite{JGH18}. For a translation-invariant kernel791whose Fourier coefficients decay like $k^{-2}$, as for the simplest rectifier networks on the circle792\cite{RBADLHBC19}, the model case is $K=(1-\pd_x^2)^{-1}$, the Green's operator of an elliptic equation.793 794\begin{theorem}[Spectral bias, with aliases]\label{thm:bias}795\Srf[\cite{RBADLHBC19,JGH18}] \emph{(a)} The residual in mode $k$ after $m$ steps is $(1-\eta\mu_k)^m$ times796its initial value, with $\mu_k=(1+k^2)^{-1}$. \emph{(b)} On $N$ equally spaced samples the eigenvalue is797\[ \mu^N_k=\sum_{m\in\Z}\frac1{1+(k+mN)^2}=\frac{\frac\pi N\sinh\frac{2\pi}N}{\cosh\frac{2\pi}N-\cos\frac{2\pi k}N}. \]798\emph{(c)} The interpolant $u=\sum_ic_iK(\cdot-x_i)$ solves $u-u''=\sum_ic_i\delta_{x_i}$.799\end{theorem}800