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

801\noindent Statement (b) is the Poisson summation formula of \cite[Thm.~4.6]{PDEHC}: sampling in space is802summation over the dual lattice. On $64$ points $\mu^N_k/\mu_k$ is $1.0016$, $1.0852$ and $1.2346$ at803$k=1,10,16$. \chk{K1} With $\eta=1$ and target $\cos x+\cos8x$, after $200$ steps mode $1$ is fitted to rounding804and $0.0380$ of mode $8$ remains; the steps needed to reach one per cent are $6.6$, $282$ and $956$ for805$k=1,8,16$ (\cref{fig:bias}). \chk{K2} For (c), with five data points the interpolant satisfies the homogeneous equation away from806the data to $10^{-9}$ and its derivative jumps by $-c_i$ at $x_i$: the representer theorem is the statement807that the minimizer is a combination of fundamental solutions. \chk{K5}808 809\begin{figure}[t]810\centering811\begin{tikzpicture}812\begin{scope}[shift={(0,0)}]813\draw[ink2] (0,3.4)--(0,0)--(6.3,0);814\draw[ink2] (0,0)--(0,-0.07) node[below,inner sep=1.5pt]{\scriptsize $0$};815\draw[ink2] (1.575,0)--(1.575,-0.07) node[below,inner sep=1.5pt]{\scriptsize $100$};816\draw[ink2] (3.15,0)--(3.15,-0.07) node[below,inner sep=1.5pt]{\scriptsize $200$};817\draw[ink2] (4.725,0)--(4.725,-0.07) node[below,inner sep=1.5pt]{\scriptsize $300$};818\draw[ink2] (6.3,0)--(6.3,-0.07) node[below,inner sep=1.5pt]{\scriptsize $400$};819\draw[ink2] (0,0)--(-0.07,0) node[left,inner sep=1.5pt]{\scriptsize $10^{-3}$};820\draw[ink2] (0,1.092)--(-0.07,1.092) node[left,inner sep=1.5pt]{\scriptsize $10^{-2}$};821\draw[ink2] (0,2.184)--(-0.07,2.184) node[left,inner sep=1.5pt]{\scriptsize $10^{-1}$};822\draw[ink2] (0,3.276)--(-0.07,3.276) node[left,inner sep=1.5pt]{\scriptsize $1$};823\node[below] at (3.15,-0.38) {\scriptsize gradient steps};824\draw[thick,ink2] plot coordinates {(0,3.276) (0.032,2.617) (0.063,1.958) (0.094,1.299) (0.126,0.64)};825\draw[thick,accent] plot coordinates {(0,3.276) (0.032,3.217) (0.063,3.159) (0.094,3.101) (0.126,3.042) (0.158,2.984) (0.189,2.926) (0.221,2.867) (0.252,2.809) (0.283,2.751) (0.315,2.692) (0.346,2.634) (0.378,2.576) (0.409,2.518) (0.441,2.459) (0.472,2.401) (0.504,2.343) (0.535,2.284) (0.567,2.226) (0.599,2.168) (0.63,2.109) (0.661,2.051) (0.693,1.993) (0.725,1.934) (0.756,1.876) (0.787,1.818) (0.819,1.76) (0.85,1.701) (0.882,1.643) (0.913,1.585) (0.945,1.526) (0.976,1.468) (1.008,1.41) (1.04,1.351) (1.071,1.293) (1.103,1.235) (1.134,1.176) (1.165,1.118) (1.197,1.06) (1.228,1.001) (1.26,0.943) (1.292,0.885) (1.323,0.827) (1.354,0.768) (1.386,0.71) (1.417,0.652) (1.449,0.593) (1.48,0.535) (1.512,0.477) (1.543,0.418) (1.575,0.36) (1.607,0.302) (1.638,0.243) (1.669,0.185) (1.701,0.127) (1.732,0.068) (1.764,0.01)};826\draw[thick,fwd] plot coordinates {(0,3.276) (0.032,3.26) (0.063,3.245) (0.094,3.229) (0.126,3.214) (0.158,3.198) (0.189,3.183) (0.221,3.167) (0.252,3.152) (0.283,3.136) (0.315,3.121) (0.346,3.105) (0.378,3.09) (0.409,3.074) (0.441,3.059) (0.472,3.043) (0.504,3.028) (0.535,3.012) (0.567,2.997) (0.599,2.981) (0.63,2.966) (0.661,2.95) (0.693,2.935) (0.725,2.919) (0.756,2.904) (0.787,2.888) (0.819,2.873) (0.85,2.857) (0.882,2.842) (0.913,2.826) (0.945,2.811) (0.976,2.795) (1.008,2.78) (1.04,2.764) (1.071,2.749) (1.103,2.733) (1.134,2.718) (1.165,2.702) (1.197,2.687) (1.228,2.671) (1.26,2.656) (1.292,2.64) (1.323,2.624) (1.354,2.609) (1.386,2.593) (1.417,2.578) (1.449,2.562) (1.48,2.547) (1.512,2.531) (1.543,2.516) (1.575,2.5) (1.607,2.485) (1.638,2.469) (1.669,2.454) (1.701,2.438) (1.732,2.423) (1.764,2.407) (1.795,2.392) (1.827,2.376) (1.859,2.361) (1.89,2.345) (1.921,2.33) (1.953,2.314) (1.984,2.299) (2.016,2.283) (2.047,2.268) (2.079,2.252) (2.111,2.237) (2.142,2.221) (2.173,2.206) (2.205,2.19) (2.236,2.175) (2.268,2.159) (2.3,2.144) (2.331,2.128) (2.362,2.113) (2.394,2.097) (2.425,2.082) (2.457,2.066) (2.489,2.051) (2.52,2.035) (2.551,2.02) (2.583,2.004) (2.615,1.989) (2.646,1.973) (2.678,1.958) (2.709,1.942) (2.74,1.927) (2.772,1.911) (2.803,1.896) (2.835,1.88) (2.866,1.865) (2.898,1.849) (2.929,1.834) (2.961,1.818) (2.993,1.803) (3.024,1.787) (3.056,1.772) (3.087,1.756) (3.118,1.741) (3.15,1.725) (3.181,1.71) (3.213,1.694) (3.244,1.679) (3.276,1.663) (3.308,1.648) (3.339,1.632) (3.371,1.617) (3.402,1.601) (3.433,1.586) (3.465,1.57) (3.496,1.555) (3.528,1.539) (3.559,1.524) (3.591,1.508) (3.623,1.493) (3.654,1.477) (3.686,1.462) (3.717,1.446) (3.748,1.431) (3.78,1.415) (3.811,1.4) (3.843,1.384) (3.874,1.369) (3.906,1.353) (3.938,1.338) (3.969,1.322) (4,1.307) (4.032,1.291) (4.063,1.276) (4.095,1.26) (4.127,1.245) (4.158,1.229) (4.189,1.214) (4.221,1.198) (4.253,1.183) (4.284,1.167) (4.316,1.152) (4.347,1.136) (4.378,1.121) (4.41,1.105) (4.441,1.09) (4.473,1.074) (4.505,1.059) (4.536,1.043) (4.567,1.028) (4.599,1.012) (4.631,0.997) (4.662,0.981) (4.693,0.966) (4.725,0.95) (4.756,0.935) (4.788,0.919) (4.819,0.904) (4.851,0.888) (4.883,0.873) (4.914,0.857) (4.946,0.842) (4.977,0.826) (5.008,0.811) (5.04,0.795) (5.071,0.78) (5.103,0.764) (5.134,0.749) (5.166,0.733) (5.197,0.718) (5.229,0.702) (5.26,0.687) (5.292,0.671) (5.324,0.656) (5.355,0.64) (5.386,0.625) (5.418,0.609) (5.449,0.594) (5.481,0.578) (5.513,0.563) (5.544,0.547) (5.575,0.532) (5.607,0.516) (5.639,0.501) (5.67,0.485) (5.701,0.47) (5.733,0.454) (5.764,0.439) (5.796,0.423) (5.827,0.408) (5.859,0.392) (5.89,0.377) (5.922,0.361) (5.954,0.346) (5.985,0.33) (6.016,0.315) (6.048,0.299) (6.079,0.284) (6.111,0.268) (6.143,0.253) (6.174,0.237) (6.205,0.222) (6.237,0.206) (6.269,0.191) (6.3,0.175)};827\draw[thick,bwd] plot coordinates {(0,3.276) (0.032,3.271) (0.063,3.266) (0.094,3.262) (0.126,3.257) (0.158,3.253) (0.189,3.248) (0.221,3.244) (0.252,3.239) (0.283,3.234) (0.315,3.23) (0.346,3.225) (0.378,3.221) (0.409,3.216) (0.441,3.212) (0.472,3.207) (0.504,3.203) (0.535,3.198) (0.567,3.193) (0.599,3.189) (0.63,3.184) (0.661,3.18) (0.693,3.175) (0.725,3.171) (0.756,3.166) (0.787,3.161) (0.819,3.157) (0.85,3.152) (0.882,3.148) (0.913,3.143) (0.945,3.139) (0.976,3.134) (1.008,3.129) (1.04,3.125) (1.071,3.12) (1.103,3.116) (1.134,3.111) (1.165,3.107) (1.197,3.102) (1.228,3.097) (1.26,3.093) (1.292,3.088) (1.323,3.084) (1.354,3.079) (1.386,3.075) (1.417,3.07) (1.449,3.066) (1.48,3.061) (1.512,3.056) (1.543,3.052) (1.575,3.047) (1.607,3.043) (1.638,3.038) (1.669,3.034) (1.701,3.029) (1.732,3.024) (1.764,3.02) (1.795,3.015) (1.827,3.011) (1.859,3.006) (1.89,3.002) (1.921,2.997) (1.953,2.992) (1.984,2.988) (2.016,2.983) (2.047,2.979) (2.079,2.974) (2.111,2.97) (2.142,2.965) (2.173,2.96) (2.205,2.956) (2.236,2.951) (2.268,2.947) (2.3,2.942) (2.331,2.938) (2.362,2.933) (2.394,2.929) (2.425,2.924) (2.457,2.919) (2.489,2.915) (2.52,2.91) (2.551,2.906) (2.583,2.901) (2.615,2.897) (2.646,2.892) (2.678,2.887) (2.709,2.883) (2.74,2.878) (2.772,2.874) (2.803,2.869) (2.835,2.865) (2.866,2.86) (2.898,2.855) (2.929,2.851) (2.961,2.846) (2.993,2.842) (3.024,2.837) (3.056,2.833) (3.087,2.828) (3.118,2.823) (3.15,2.819) (3.181,2.814) (3.213,2.81) (3.244,2.805) (3.276,2.801) (3.308,2.796) (3.339,2.792) (3.371,2.787) (3.402,2.782) (3.433,2.778) (3.465,2.773) (3.496,2.769) (3.528,2.764) (3.559,2.76) (3.591,2.755) (3.623,2.75) (3.654,2.746) (3.686,2.741) (3.717,2.737) (3.748,2.732) (3.78,2.728) (3.811,2.723) (3.843,2.718) (3.874,2.714) (3.906,2.709) (3.938,2.705) (3.969,2.7) (4,2.696) (4.032,2.691) (4.063,2.686) (4.095,2.682) (4.127,2.677) (4.158,2.673) (4.189,2.668) (4.221,2.664) (4.253,2.659) (4.284,2.655) (4.316,2.65) (4.347,2.645) (4.378,2.641) (4.41,2.636) (4.441,2.632) (4.473,2.627) (4.505,2.623) (4.536,2.618) (4.567,2.613) (4.599,2.609) (4.631,2.604) (4.662,2.6) (4.693,2.595) (4.725,2.591) (4.756,2.586) (4.788,2.581) (4.819,2.577) (4.851,2.572) (4.883,2.568) (4.914,2.563) (4.946,2.559) (4.977,2.554) (5.008,2.549) (5.04,2.545) (5.071,2.54) (5.103,2.536) (5.134,2.531) (5.166,2.527) (5.197,2.522) (5.229,2.518) (5.26,2.513) (5.292,2.508) (5.324,2.504) (5.355,2.499) (5.386,2.495) (5.418,2.49) (5.449,2.486) (5.481,2.481) (5.513,2.476) (5.544,2.472) (5.575,2.467) (5.607,2.463) (5.639,2.458) (5.67,2.454) (5.701,2.449) (5.733,2.444) (5.764,2.44) (5.796,2.435) (5.827,2.431) (5.859,2.426) (5.89,2.422) (5.922,2.417) (5.954,2.412) (5.985,2.408) (6.016,2.403) (6.048,2.399) (6.079,2.394) (6.111,2.39) (6.143,2.385) (6.174,2.381) (6.205,2.376) (6.237,2.371) (6.269,2.367) (6.3,2.362)};828\node[ink2,right] at (0.346,0.521) {\scriptsize $k=1$};829\node[accent,right] at (1.496,1.178) {\scriptsize $4$};830\node[fwd] at (4.567,1.466) {\scriptsize $8$};831\node[bwd] at (5.197,2.75) {\scriptsize $16$};832\end{scope}833\end{tikzpicture}834\caption{Spectral bias in the kernel regime: the remaining fraction of mode $k$ of the target against the number of gradient steps, for the sampled $H^1$ kernel on $64$ points (\cref{thm:bias}).}\label{fig:bias}835\end{figure}836 837A physics-informed loss \cite{RPK19} for $-u''=f$ is the squared residual $\lVert Au-f\rVert^2$ with838$A=-\pd_x^2$; the energy, or Ritz, loss \cite{EYu18} is $\frac12\langle u,Au\rangle-\langle f,u\rangle$.839 840\begin{theorem}[Squaring the operator]\label{thm:pinn}841\Scl[cf.\ \cite{KGZKM21,WTP21}] \emph{(a)} The Hessian of the strong-form loss is $A^{\T}A$ and that of the842energy loss is $A$: the condition numbers are $\kappa^2$ and $\kappa$, with $\kappa\sim4N^2/\pi^2$ for $N$843unknowns. \emph{(b)} Composed with the kernel of \cref{thm:bias}, the strong-form loss has mode rates844$\mu_kk^4=k^4/(1+k^2)$, increasing in $k$.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