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 641–740 of 1085. Source text is displayed literally.
641\draw[fwd] plot coordinates {(0,2.548) (0.076,2.54) (0.151,2.532) (0.227,2.525) (0.302,2.517) (0.378,2.51) (0.454,2.503) (0.529,2.496) (0.605,2.489) (0.68,2.482) (0.756,2.475) (0.832,2.469) (0.907,2.462) (0.983,2.456) (1.058,2.45) (1.134,2.444) (1.21,2.438) (1.285,2.433) (1.361,2.427) (1.436,2.422) (1.512,2.417) (1.588,2.412) (1.663,2.408) (1.739,2.404) (1.814,2.4) (1.89,2.396) (1.966,2.393) (2.041,2.39) (2.117,2.387) (2.192,2.385) (2.268,2.383) (2.344,2.381) (2.419,2.38) (2.495,2.38) (2.57,2.38) (2.646,2.38) (2.722,2.382) (2.797,2.383) (2.873,2.386) (2.948,2.388) (3.024,2.392) (3.1,2.396) (3.175,2.401) (3.251,2.407) (3.326,2.413) (3.402,2.42) (3.478,2.427) (3.553,2.434) (3.629,2.443) (3.704,2.451) (3.78,2.46) (3.856,2.468) (3.931,2.477) (4.007,2.486) (4.082,2.495) (4.158,2.505) (4.234,2.514) (4.309,2.523) (4.385,2.532) (4.46,2.541) (4.536,2.55) (4.612,2.559) (4.687,2.569) (4.763,2.578) (4.838,2.587) (4.914,2.596) (4.99,2.605) (5.065,2.614) (5.141,2.623) (5.216,2.633) (5.292,2.642) (5.368,2.651) (5.443,2.66) (5.519,2.669) (5.594,2.678) (5.67,2.687) (5.746,2.697) (5.821,2.706) (5.897,2.715) (5.972,2.724) (6.048,2.733) (6.124,2.742)};642\draw[fwd] plot coordinates {(0,2.764) (0.076,2.753) (0.151,2.743) (0.227,2.733) (0.302,2.723) (0.378,2.713) (0.454,2.704) (0.529,2.694) (0.605,2.685) (0.68,2.676) (0.756,2.667) (0.832,2.658) (0.907,2.65) (0.983,2.641) (1.058,2.633) (1.134,2.625) (1.21,2.618) (1.285,2.61) (1.361,2.603) (1.436,2.596) (1.512,2.589) (1.588,2.583) (1.663,2.577) (1.739,2.571) (1.814,2.566) (1.89,2.561) (1.966,2.556) (2.041,2.552) (2.117,2.548) (2.192,2.544) (2.268,2.542) (2.344,2.539) (2.419,2.537) (2.495,2.535) (2.57,2.535) (2.646,2.534) (2.722,2.534) (2.797,2.535) (2.873,2.536) (2.948,2.538) (3.024,2.54) (3.1,2.543) (3.175,2.546) (3.251,2.549) (3.326,2.553) (3.402,2.558) (3.478,2.562) (3.553,2.567) (3.629,2.572) (3.704,2.577) (3.78,2.583) (3.856,2.588) (3.931,2.593) (4.007,2.599) (4.082,2.604) (4.158,2.61) (4.234,2.615) (4.309,2.62) (4.385,2.626) (4.46,2.631) (4.536,2.637) (4.612,2.642) (4.687,2.648) (4.763,2.653) (4.838,2.658) (4.914,2.664) (4.99,2.669) (5.065,2.675) (5.141,2.68) (5.216,2.686) (5.292,2.691) (5.368,2.697) (5.443,2.702) (5.519,2.707) (5.594,2.713) (5.67,2.718) (5.746,2.724) (5.821,2.729) (5.897,2.735) (5.972,2.74) (6.048,2.746) (6.124,2.751)};643\draw[fwd] plot coordinates {(0,2.98) (0.076,2.967) (0.151,2.954) (0.227,2.941) (0.302,2.929) (0.378,2.917) (0.454,2.905) (0.529,2.893) (0.605,2.881) (0.68,2.87) (0.756,2.859) (0.832,2.848) (0.907,2.837) (0.983,2.827) (1.058,2.816) (1.134,2.807) (1.21,2.797) (1.285,2.788) (1.361,2.778) (1.436,2.77) (1.512,2.761) (1.588,2.753) (1.663,2.745) (1.739,2.738) (1.814,2.731) (1.89,2.725) (1.966,2.718) (2.041,2.713) (2.117,2.708) (2.192,2.703) (2.268,2.698) (2.344,2.694) (2.419,2.691) (2.495,2.688) (2.57,2.686) (2.646,2.684) (2.722,2.682) (2.797,2.681) (2.873,2.681) (2.948,2.681) (3.024,2.681) (3.1,2.681) (3.175,2.682) (3.251,2.683) (3.326,2.685) (3.402,2.686) (3.478,2.688) (3.553,2.69) (3.629,2.691) (3.704,2.693) (3.78,2.695) (3.856,2.697) (3.931,2.699) (4.007,2.701) (4.082,2.703) (4.158,2.705) (4.234,2.708) (4.309,2.71) (4.385,2.712) (4.46,2.714) (4.536,2.716) (4.612,2.718) (4.687,2.72) (4.763,2.722) (4.838,2.724) (4.914,2.726) (4.99,2.728) (5.065,2.73) (5.141,2.732) (5.216,2.734) (5.292,2.736) (5.368,2.738) (5.443,2.74) (5.519,2.742) (5.594,2.744) (5.67,2.747) (5.746,2.749) (5.821,2.751) (5.897,2.753) (5.972,2.755) (6.048,2.757) (6.124,2.759)};644\draw[fwd] plot coordinates {(0,3.195) (0.076,3.18) (0.151,3.165) (0.227,3.15) (0.302,3.135) (0.378,3.12) (0.454,3.106) (0.529,3.092) (0.605,3.078) (0.68,3.064) (0.756,3.051) (0.832,3.037) (0.907,3.025) (0.983,3.012) (1.058,3) (1.134,2.988) (1.21,2.976) (1.285,2.965) (1.361,2.954) (1.436,2.943) (1.512,2.933) (1.588,2.923) (1.663,2.914) (1.739,2.905) (1.814,2.896) (1.89,2.888) (1.966,2.88) (2.041,2.873) (2.117,2.866) (2.192,2.859) (2.268,2.853) (2.344,2.848) (2.419,2.843) (2.495,2.838) (2.57,2.834) (2.646,2.83) (2.722,2.827) (2.797,2.823) (2.873,2.821) (2.948,2.818) (3.024,2.816) (3.1,2.814) (3.175,2.812) (3.251,2.811) (3.326,2.809) (3.402,2.808) (3.478,2.806) (3.553,2.805) (3.629,2.804) (3.704,2.803) (3.78,2.801) (3.856,2.8) (3.931,2.799) (4.007,2.798) (4.082,2.797) (4.158,2.796) (4.234,2.795) (4.309,2.794) (4.385,2.792) (4.46,2.791) (4.536,2.79) (4.612,2.789) (4.687,2.788) (4.763,2.787) (4.838,2.786) (4.914,2.784) (4.99,2.783) (5.065,2.782) (5.141,2.781) (5.216,2.78) (5.292,2.779) (5.368,2.778) (5.443,2.776) (5.519,2.775) (5.594,2.774) (5.67,2.773) (5.746,2.772) (5.821,2.771) (5.897,2.77) (5.972,2.769) (6.048,2.767) (6.124,2.766)};645\draw[fwd] plot coordinates {(0,3.411) (0.076,3.393) (0.151,3.376) (0.227,3.358) (0.302,3.341) (0.378,3.324) (0.454,3.307) (0.529,3.29) (0.605,3.274) (0.68,3.258) (0.756,3.242) (0.832,3.227) (0.907,3.212) (0.983,3.197) (1.058,3.183) (1.134,3.169) (1.21,3.155) (1.285,3.142) (1.361,3.129) (1.436,3.116) (1.512,3.104) (1.588,3.093) (1.663,3.081) (1.739,3.071) (1.814,3.06) (1.89,3.05) (1.966,3.041) (2.041,3.032) (2.117,3.023) (2.192,3.015) (2.268,3.007) (2.344,2.999) (2.419,2.992) (2.495,2.986) (2.57,2.979) (2.646,2.973) (2.722,2.967) (2.797,2.962) (2.873,2.957) (2.948,2.952) (3.024,2.947) (3.1,2.942) (3.175,2.938) (3.251,2.933) (3.326,2.929) (3.402,2.924) (3.478,2.92) (3.553,2.916) (3.629,2.912) (3.704,2.908) (3.78,2.903) (3.856,2.899) (3.931,2.895) (4.007,2.891) (4.082,2.887) (4.158,2.882) (4.234,2.878) (4.309,2.874) (4.385,2.87) (4.46,2.866) (4.536,2.861) (4.612,2.857) (4.687,2.853) (4.763,2.849) (4.838,2.845) (4.914,2.84) (4.99,2.836) (5.065,2.832) (5.141,2.828) (5.216,2.824) (5.292,2.819) (5.368,2.815) (5.443,2.811) (5.519,2.807) (5.594,2.803) (5.67,2.799) (5.746,2.794) (5.821,2.79) (5.897,2.786) (5.972,2.782) (6.048,2.778) (6.124,2.773)};646\draw[fwd] plot coordinates {(0,3.627) (0.076,3.607) (0.151,3.586) (0.227,3.566) (0.302,3.546) (0.378,3.527) (0.454,3.508) (0.529,3.489) (0.605,3.47) (0.68,3.452) (0.756,3.434) (0.832,3.416) (0.907,3.399) (0.983,3.382) (1.058,3.366) (1.134,3.35) (1.21,3.334) (1.285,3.319) (1.361,3.304) (1.436,3.289) (1.512,3.275) (1.588,3.262) (1.663,3.249) (1.739,3.236) (1.814,3.224) (1.89,3.212) (1.966,3.2) (2.041,3.189) (2.117,3.179) (2.192,3.168) (2.268,3.158) (2.344,3.149) (2.419,3.14) (2.495,3.131) (2.57,3.122) (2.646,3.114) (2.722,3.106) (2.797,3.098) (2.873,3.09) (2.948,3.082) (3.024,3.075) (3.1,3.067) (3.175,3.06) (3.251,3.052) (3.326,3.045) (3.402,3.038) (3.478,3.031) (3.553,3.024) (3.629,3.016) (3.704,3.009) (3.78,3.002) (3.856,2.995) (3.931,2.988) (4.007,2.981) (4.082,2.973) (4.158,2.966) (4.234,2.959) (4.309,2.952) (4.385,2.945) (4.46,2.938) (4.536,2.931) (4.612,2.923) (4.687,2.916) (4.763,2.909) (4.838,2.902) (4.914,2.895) (4.99,2.888) (5.065,2.88) (5.141,2.873) (5.216,2.866) (5.292,2.859) (5.368,2.852) (5.443,2.845) (5.519,2.838) (5.594,2.83) (5.67,2.823) (5.746,2.816) (5.821,2.809) (5.897,2.802) (5.972,2.795) (6.048,2.787) (6.124,2.78)};647\fill[black] (6.3,2.764) circle (1.8pt);648\fill[black] (6.3,1.036) circle (1.8pt);649\node[accent] at (2.406,4.016) {\scriptsize $t^*$};650\end{scope}651\end{tikzpicture}652\caption{Characteristics of the flow-matching field from $N(0,1)$ to the two points $\pm1$ (\cref{prop:pitchfork}). The midpoint is attracting until $t^*=0.382$ and repelling afterwards; the dotted line is the unstable trajectory. No two characteristics cross.}\label{fig:pitchfork}653\end{figure}654 655\noindent The field satisfies the continuity equation with $p_t$ to $10^{-13}$; the slope at the midpoint changes656sign at $0.381966$ and is $890$ at $t=0.9$ (\cref{fig:pitchfork}). \chk{F3} This is the transport-side picture of657\cref{thm:illposed}(c): mass begins to be committed to one of the two points at a definite time $t^*$, by the bifurcation658that \cite[Thm.~14.7]{PDEHC} describes for a buckling rod, and the field then steepens without bound as the659characteristics focus. Such transition times have been studied for diffusion models in high dimension660\cite{BBDM24}.661 662\section{Graph networks}\label{sec:graphs}663 664Let $L$ be the Laplacian of a connected graph with eigenvalues $0=\lambda_1<\lambda_2\le\dots\le\lambda_n$. The665linear part of a message-passing layer is $X\mapsto(I-\tau L)X$, one explicit Euler step of the heat equation on666the graph \cite{CRGBB21}.667 668\begin{theorem}[Oversmoothing is the spectral gap]\label{thm:oversmooth}669\Scl[\cite{LHW18,OoSu20}] For $0<\tau\le1/\lambda_n$ the non-constant part of $X$ is multiplied by at most670$1-\tau\lambda_2$ per layer, with equality in the limit, and the Dirichlet energy $X^{\T}LX$ by at most671$(1-\tau\lambda_2)^2$. The depth at which features become indistinguishable is of order $1/\tau\lambda_2$.672\end{theorem}673 674\noindent On a random connected graph with $12$ nodes, $\lambda_2=0.6251$, $\lambda_n=8.2655$ and the measured675factor is $0.92437$, as predicted; $99\%$ of the Dirichlet energy of a random input is gone after $15$ layers,676the bound from $\lambda_2$ alone being $29$. \chk{G1} The depth scale varies by orders of magnitude with the677graph: on $32$ nodes, with $\tau$ at its largest stable value, it is $415$ layers for a path678($\lambda_2=0.00963$), $5$ for the hypercube ($\lambda_2=2$, $\lambda_n=10$) and $1$ for the complete graph,679where a single layer returns the mean exactly (\cref{fig:smooth}). \chk{G2} Graphs that are good for propagating information are680the ones that oversmooth fastest; the two are the same eigenvalue.681 682\begin{figure}[t]683\centering684\begin{tikzpicture}685\begin{scope}[shift={(0,0)}]686\draw[ink2] (0,3.6)--(0,0)--(6.3,0);687\draw[ink2] (0,0)--(0,-0.07) node[below,inner sep=1.5pt]{\scriptsize $0$};688\draw[ink2] (2.1,0)--(2.1,-0.07) node[below,inner sep=1.5pt]{\scriptsize $20$};689\draw[ink2] (4.2,0)--(4.2,-0.07) node[below,inner sep=1.5pt]{\scriptsize $40$};690\draw[ink2] (6.3,0)--(6.3,-0.07) node[below,inner sep=1.5pt]{\scriptsize $60$};691\draw[ink2] (0,0)--(-0.07,0) node[left,inner sep=1.5pt]{\scriptsize $10^{-8}$};692\draw[ink2] (0,0.774)--(-0.07,0.774) node[left,inner sep=1.5pt]{\scriptsize $10^{-6}$};693\draw[ink2] (0,1.548)--(-0.07,1.548) node[left,inner sep=1.5pt]{\scriptsize $10^{-4}$};694\draw[ink2] (0,2.322)--(-0.07,2.322) node[left,inner sep=1.5pt]{\scriptsize $10^{-2}$};695\draw[ink2] (0,3.096)--(-0.07,3.096) node[left,inner sep=1.5pt]{\scriptsize $1$};696\node[below] at (3.15,-0.38) {\scriptsize layers};697\draw[thick,accent] plot coordinates {(0,3.096) (0.105,3.318) (0.21,3.323) (0.315,3.125) (0.42,3.116) (0.525,3.297) (0.63,3.315) (0.735,3.189) (0.84,3.118) (0.945,3.285) (1.05,3.305) (1.155,3.206) (1.26,3.149) (1.365,3.277) (1.47,3.293) (1.575,3.222) (1.68,3.161) (1.785,3.264) (1.89,3.302) (1.995,3.215) (2.1,3.168) (2.205,3.264) (2.31,3.293) (2.415,3.222) (2.52,3.201) (2.625,3.253) (2.73,3.265) (2.835,3.248) (2.94,3.234) (3.045,3.237) (3.15,3.237) (3.255,3.249) (3.36,3.263) (3.465,3.249) (3.57,3.206) (3.675,3.219) (3.78,3.298) (3.885,3.255) (3.99,3.183) (4.095,3.206) (4.2,3.291) (4.305,3.289) (4.41,3.172) (4.515,3.166) (4.62,3.298) (4.725,3.307) (4.83,3.122) (4.935,3.166) (5.04,3.311) (5.145,3.303) (5.25,3.103) (5.355,3.16) (5.46,3.322) (5.565,3.302) (5.67,3.089) (5.775,3.138) (5.88,3.326) (5.985,3.311) (6.09,3.088) (6.195,3.134) (6.3,3.311)};698\draw[thick,fwd] plot coordinates {(0,3.096) (0.105,2.805) (0.21,2.707) (0.315,2.632) (0.42,2.569) (0.525,2.514) (0.63,2.466) (0.735,2.424) (0.84,2.388) (0.945,2.356) (1.05,2.329) (1.155,2.305) (1.26,2.284) (1.365,2.266) (1.47,2.249) (1.575,2.234) (1.68,2.22) (1.785,2.206) (1.89,2.194) (1.995,2.182) (2.1,2.17) (2.205,2.159) (2.31,2.148) (2.415,2.137) (2.52,2.127) (2.625,2.116) (2.73,2.106) (2.835,2.096) (2.94,2.087) (3.045,2.077) (3.15,2.067) (3.255,2.058) (3.36,2.049) (3.465,2.04) (3.57,2.031) (3.675,2.022) (3.78,2.014) (3.885,2.005) (3.99,1.997) (4.095,1.988) (4.2,1.98) (4.305,1.972) (4.41,1.964) (4.515,1.956) (4.62,1.949) (4.725,1.941) (4.83,1.934) (4.935,1.926) (5.04,1.919) (5.145,1.912) (5.25,1.905) (5.355,1.898) (5.46,1.891) (5.565,1.884) (5.67,1.878) (5.775,1.871) (5.88,1.865) (5.985,1.858) (6.09,1.852) (6.195,1.846) (6.3,1.84)};699\draw[thick,bwd] plot coordinates {(0,3.096) (0.105,2.849) (0.21,2.662) (0.315,2.52) (0.42,2.407) (0.525,2.31) (0.63,2.223) (0.735,2.141) (0.84,2.062) (0.945,1.984) (1.05,1.908) (1.155,1.832) (1.26,1.757) (1.365,1.682) (1.47,1.606) (1.575,1.531) (1.68,1.456) (1.785,1.381) (1.89,1.306) (1.995,1.231) (2.1,1.156) (2.205,1.081) (2.31,1.006) (2.415,0.931) (2.52,0.856) (2.625,0.781) (2.73,0.706) (2.835,0.631) (2.94,0.556) (3.045,0.481) (3.15,0.406) (3.255,0.331) (3.36,0.256) (3.465,0.181) (3.57,0.106) (3.675,0.031)};700\node[accent] at (4.62,2.74) {\scriptsize wave layer, path};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 whose