Independent scholarship · Open accessThe monthly digest

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 845–944 of 1085. Source text is displayed literally.

845\end{theorem}846 847\noindent On $31$ unknowns $\kappa=414.3$ and $\kappa^2=171{,}682$; gradient descent with the optimal step needs848$2862$ and $1{,}185{,}936$ iterations to gain six digits. \chk{K3} On $64$ points the regression rates at $k=1$ and849$16$ are $0.5008$ and $0.0048$, a ratio of $1/104$, and the strong-form rates are $0.5000$ and $206.8$, a ratio of850$414$. \chk{K4} The bias is reversed and the spread of rates is four times as large: the low modes, which carry the solution,851are now the slow ones relative to the step that the high modes allow. This852is a linear model of the training difficulties reported for physics-informed networks \cite{KGZKM21,WTP21}, and853it is the reason the weak formulation is the standard one in numerical analysis854\cite[Ch.~12]{PDEHC}.855 856\section{Noise}\label{sec:noise}857 858Gradient descent with small isotropic noise on a loss $V$ is modelled by the Langevin equation859$dX=-V'(X)\,dt+\sqrt{2/\beta}\,dW$, whose density solves a Fokker--Planck equation with stationary solution860proportional to $e^{-\beta V}$ \cite{MHB17}.861 862\begin{proposition}\label{prop:langevin}863\Scl[\cite{Kra40,BaEm85}] \emph{(a)} For $V=\frac12\lambda x^2$ the spectral gap is $\lambda$ for every $\beta$.864\emph{(b)} For a symmetric double well with minima $\pm a$ and barrier $\Delta V$ at $0$, the gap is865$\frac1\pi\sqrt{V''(a)|V''(0)|}\,e^{-\beta\Delta V}(1+O(\beta^{-1}))$. \emph{(c)} Constant-step stochastic gradient866descent on $\frac12\lambda x^2$ with gradient noise of variance $\sigma^2$ has stationary variance867$\eta\sigma^2/\lambda(2-\eta\lambda)$.868\end{proposition}869 870\noindent A reversible discretization has the Gibbs density as its exact stationary vector, and for $\lambda=1$ its871gap is $0.9997$ at $\beta=1$ and at $\beta=4$. \chk{L1} For $V=(x^2-1)^2$ the gap divided by872$\frac{\sqrt{32}}\pi e^{-\beta}$ is $0.903$, $0.928$, $0.947$, $0.959$ at $\beta=4,6,8,10$, and the gap at873$\beta=10$ is $7.8\times10^{-5}$. \chk{L2} The recursion for the variance converges to $0.0625$ for $\eta=0.1$,874$\lambda=2$, $\sigma=1.5$; the first-order value $\eta\sigma^2/2\lambda$ is $0.05625$, corresponding to the875temperature $\beta^{-1}=\eta\sigma^2/2$. \chk{L3} Within a basin, mixing is as fast as the curvature and does not876depend on the noise; between basins it is exponentially slow in the ratio of barrier height to noise. The877exponent in (b) is where a claim that noise selects wide minima has to be made quantitative.878 879\section{Control}\label{sec:control}880 881\begin{proposition}\label{prop:bellman}882\Scl[\cite{CrLi83,BaSo91}] The Bellman operator $TV=\min_a(c_a+\gamma P_aV)$ is monotone and a contraction of883factor $\gamma$ in the supremum norm. A monotone, stable and consistent scheme for a Hamilton--Jacobi equation884converges to its viscosity solution.885\end{proposition}886 887\noindent For a random problem with $6$ states and $3$ actions, monotonicity and the contraction hold on $300$888random pairs, with largest ratio $0.7072$ at $\gamma=0.9$, and value iteration obeys the geometric bound.889\chk{Q1} For $|u'|=1$ on the unit interval with zero boundary values the scheme890$u_i=\min(u_{i-1},u_{i+1})+h$ converges to the distance to the boundary exactly, and has residual $2h$ on a891sawtooth and on minus the distance, which satisfy the equation almost everywhere. \chk{Q2} Monotonicity is the892discrete maximum principle: the Bellman operator is to control what a Markov kernel is to diffusion, and the893selection of the viscosity solution is the selection of the entropy solution of a conservation law894\cite[Thm.~14.3]{PDEHC}.895 896\section{How many numbers an operator needs}\label{sec:rank}897 898Operator learning approximates a solution map by a finite-rank one, composed with nonlinear maps899\cite{LJPZK21,KLLABSA23}. For linear problems the best rank-$r$ error is the $(r+1)$-st singular value.900 901\begin{theorem}[Rank by type]\label{thm:rank}902\Scl On the unit interval with Dirichlet conditions:903\begin{enumerate}[label=(\alph*),leftmargin=1.6em,itemsep=1pt,topsep=2pt]904\item \emph{Elliptic.} $(-\pd_x^2)^{-1}$ has singular values $(\pi k)^{-2}$: relative accuracy $\epsilon$ needs905$\epsilon^{-1/2}$ modes.906\item \emph{Parabolic.} $e^{t\pd_x^2}$ has singular values $e^{-\pi^2k^2t}$: accuracy $\epsilon$ needs907$\sqrt{1+\log(1/\epsilon)/\pi^2t}$ modes.908\item \emph{Hyperbolic.} The wave propagator is an isometry of the energy: every mode is needed.909\item Translates of a step function have covariance eigenvalues $((k-\frac12)\pi)^{-2}$, so the best910$r$-dimensional linear approximation of the family has relative error $\sim(\pi^2r/2)^{-1/2}$.911\end{enumerate}912\end{theorem}913 914\noindent At $\epsilon=10^{-6}$ this is $1000$ modes for the elliptic inverse and $11$ for the heat flow at915$t=0.01$ ($12$ on a grid of $63$ points, whose stencil underestimates the higher eigenvalues as in916\cref{thm:alias}(b)); the discrete wave propagator preserves the energy form to $10^{-15}$. \chk{O1} For the917steps, the first three eigenvalues are $0.40531$, $0.04505$, $0.01623$ on $60$ points, and the relative error918is $0.142$ with ten modes and $0.045$ with a hundred (\cref{fig:rank}). \chk{O2} A linear-reduction architecture is therefore919well matched to parabolic problems, adequate for elliptic ones, and badly matched to transport, where the920natural coordinates are the characteristics of \cref{sec:flows} and not a fixed basis. This is the Kolmogorov921barrier of reduced-order modelling \cite{OhRa16}, read off the type of the equation.922 923\begin{figure}[t]924\centering925\begin{tikzpicture}926\begin{scope}[shift={(0,0)}]927\draw[ink2] (0,3.6)--(0,0)--(6.3,0);928\draw[ink2] (0,0)--(0,-0.07) node[below,inner sep=1.5pt]{\scriptsize $1$};929\draw[ink2] (1.454,0)--(1.454,-0.07) node[below,inner sep=1.5pt]{\scriptsize $10$};930\draw[ink2] (3.069,0)--(3.069,-0.07) node[below,inner sep=1.5pt]{\scriptsize $20$};931\draw[ink2] (4.685,0)--(4.685,-0.07) node[below,inner sep=1.5pt]{\scriptsize $30$};932\draw[ink2] (6.3,0)--(6.3,-0.07) node[below,inner sep=1.5pt]{\scriptsize $40$};933\draw[ink2] (0,0)--(-0.07,0) node[left,inner sep=1.5pt]{\scriptsize $10^{-6}$};934\draw[ink2] (0,1.112)--(-0.07,1.112) node[left,inner sep=1.5pt]{\scriptsize $10^{-4}$};935\draw[ink2] (0,2.223)--(-0.07,2.223) node[left,inner sep=1.5pt]{\scriptsize $10^{-2}$};936\draw[ink2] (0,3.335)--(-0.07,3.335) node[left,inner sep=1.5pt]{\scriptsize $1$};937\node[below] at (3.15,-0.38) {\scriptsize mode $k$};938\draw[thick,accent] plot coordinates {(0,3.335) (0.162,3.335) (0.323,3.335) (0.485,3.335) (0.646,3.335) (0.808,3.335) (0.969,3.335) (1.131,3.335) (1.292,3.335) (1.454,3.335) (1.615,3.335) (1.777,3.335) (1.938,3.335) (2.1,3.335) (2.262,3.335) (2.423,3.335) (2.585,3.335) (2.746,3.335) (2.908,3.335) (3.069,3.335) (3.231,3.335) (3.392,3.335) (3.554,3.335) (3.715,3.335) (3.877,3.335) (4.038,3.335) (4.2,3.335) (4.362,3.335) (4.523,3.335) (4.685,3.335) (4.846,3.335) (5.008,3.335) (5.169,3.335) (5.331,3.335) (5.492,3.335) (5.654,3.335) (5.815,3.335) (5.977,3.335) (6.138,3.335) (6.3,3.335)};939\draw[thick,ink2,densely dashed] plot coordinates {(0,3.335) (0.162,3.07) (0.323,2.946) (0.485,2.865) (0.646,2.804) (0.808,2.756) (0.969,2.716) (1.131,2.681) (1.292,2.651) (1.454,2.624) (1.615,2.6) (1.777,2.578) (1.938,2.558) (2.1,2.539) (2.262,2.522) (2.423,2.506) (2.585,2.491) (2.746,2.477) (2.908,2.463) (3.069,2.45) (3.231,2.438) (3.392,2.427) (3.554,2.416) (3.715,2.405) (3.877,2.395) (4.038,2.386) (4.2,2.376) (4.362,2.368) (4.523,2.359) (4.685,2.351) (4.846,2.343) (5.008,2.335) (5.169,2.327) (5.331,2.32) (5.492,2.313) (5.654,2.306) (5.815,2.299) (5.977,2.293) (6.138,2.286) (6.3,2.28)};940\draw[thick,fwd] plot coordinates {(0,3.335) (0.162,3) (0.323,2.804) (0.485,2.666) (0.646,2.558) (0.808,2.47) (0.969,2.395) (1.131,2.331) (1.292,2.274) (1.454,2.223) (1.615,2.177) (1.777,2.135) (1.938,2.097) (2.1,2.061) (2.262,2.027) (2.423,1.996) (2.585,1.967) (2.746,1.939) (2.908,1.913) (3.069,1.889) (3.231,1.865) (3.392,1.843) (3.554,1.821) (3.715,1.801) (3.877,1.781) (4.038,1.762) (4.2,1.744) (4.362,1.726) (4.523,1.709) (4.685,1.693) (4.846,1.677) (5.008,1.662) (5.169,1.647) (5.331,1.632) (5.492,1.618) (5.654,1.605) (5.815,1.592) (5.977,1.579) (6.138,1.566) (6.3,1.554)};941\draw[thick,bwd] plot coordinates {(0,3.335) (0.162,3.263) (0.323,3.144) (0.485,2.977) (0.646,2.763) (0.808,2.501) (0.969,2.191) (1.131,1.834) (1.292,1.429) (1.454,0.976) (1.615,0.476)};942\node[accent] at (4.685,3.502) {\scriptsize wave propagator};943\node[ink2] at (4.685,2.656) {\scriptsize translated steps};944\node[fwd] at (4.846,1.342) {\scriptsize elliptic inverse};