Indexed text attachment
parametrized-neural-networks-and-their-representations-in-differential-topology.tex
Source for Parametrized Neural Networks and Their Representations in Differential Topology
View paper · Download original file
Lines 1321–1420 of 2141. Source text is displayed literally.
1321 1322\begin{proof}1323$\loss'(w)=(\tanh w-1)\operatorname{sech}^2w<0$ for all $w$.1324\end{proof}1325 1326So the topology of sublevel sets can change with no critical point to account for it, the change being1327carried off to infinity, and the regular interval theorem \DT{Thm.~8.4}, which needs compactness, does not1328apply. Any use of Morse theory for losses must either restore compactness (weight decay, a bounded1329parameter domain) or account for these ends explicitly, as one does for the Palais--Smale condition in1330infinite dimensions.1331 1332\section*{Notes}1333 1334The manifold of global minima was described by Cooper \cite{Coo21}; the Polyak--\L{}ojasiewicz condition in1335this setting is due to Liu, Zhu and Belkin. Mode connectivity was observed by Garipov et al.\ and Draxler et1336al., and analysed for wide networks by Freeman and Bruna and by Nguyen; permutation alignment is studied in1337\cite{EKSN22}. For the singular structure of the landscape at reducible parameters see \cite{FA00,SGJ21} and1338Watanabe's theory \cite{Wat09}.1339 1340\section*{Exercises}1341 1342\begin{exercise}\label{exer:linreg}1343For the linear family of \cref{exer:linear} with $P>n$ and features in general position, describe $M_y$ and1344the Hessian of the loss.1345\end{exercise}1346 1347\begin{exercise}\label{exer:hyperbola}1348Verify \cref{ex:hyperbola}: find all critical points of $\tfrac12(ab-1)^2$, their Hessians, and the1349components of the sublevel sets.1350\end{exercise}1351 1352\begin{exercise}\label{exer:PL}1353In the setting of \cref{prop:PL}, show that the limit point of the flow line lies within1354$\sqrt{2\loss(\theta_0)/\mu}$ of $\theta_0$.1355\end{exercise}1356 1357\begin{exercise}\label{exer:deeplin}1358For $F(a_1,\dots,a_k;x)=a_1\cdots a_kx$ with data $(1,1)$, show that $M_y$ has $2^{k-1}$ components and1359dimension $k-1$, and that the origin is a degenerate critical point for $k\ge3$.1360\end{exercise}1361%% ---- end ch/06-loss.tex ----1362\part{Maps}1363%% ---- begin ch/07-isotopy.tex ----1364\chapter{Embeddings, Isotopy, and Depth}\label{ch:isotopy}1365 1366The previous three chapters studied level sets. This one studies the maps themselves, and in particular1367what a network does to a data set regarded as a subset of input space. The standing assumption, usually1368called the manifold hypothesis \cite{FMN16}, is that the data lie on or near a compact submanifold1369$K\subset\R^D$ of dimension $m$ much smaller than $D$, with the classes occupying disjoint closed subsets1370$K_+,K_-$. A hidden layer of width $k$ is a map $h_\theta\colon\R^D\to\R^k$, and the question is what1371$h_\theta(K)$ can be.1372 1373\section{The first layer generically embeds}1374 1375\begin{proposition}\label{prop:firstlayer}\Srf[Whitney; \DT{Thm.~4.5, Cor.~4.8, Prop.~3.12}]1376Let $K\subset\R^D$ be a compact submanifold of dimension $m$, let $k\ge2m+1$, and let $\sigma$ be a1377diffeomorphism of $\R$ onto an open interval. Then for almost every $W\in\R^{k\times D}$ and every $b$, the1378map $x\mapsto\sigma(Wx+b)$ restricted to $K$ is an embedding. The set of such $(W,b)$ is open.1379\end{proposition}1380 1381\begin{proof}1382Applying $\sigma$ coordinatewise after a translation is a diffeomorphism onto its image, so the question is1383whether $W|_K$ is an embedding. The map $(W,(x,y))\mapsto W(x-y)$ on1384$\R^{k\times D}\times(K\times K\setminus\Delta)$ is a submersion to $\R^k$, so by \DT{Thm.~4.5} for almost1385every $W$ its restriction to $K\times K\setminus\Delta$, a manifold of dimension $2m<k$, is transverse to1386$0$ and hence misses it: $W|_K$ is injective. Likewise $(W,(x,v))\mapsto Wv$ on the unit tangent bundle of1387$K$, of dimension $2m-1$, is a submersion, so for almost every $W$ no unit tangent vector is killed: $W|_K$ is1388an immersion. An injective immersion of a compact manifold is an embedding. Openness is \DT{Prop.~3.12}.1389\end{proof}1390 1391So a hidden layer wider than twice the intrinsic dimension of the data loses no topological information for1392almost every choice of weights, however small it is compared with the ambient dimension $D$. This is1393Whitney's embedding theorem read as a statement about random projections. Narrower layers may fail to be1394injective on $K$, and that is where the topology of a representation can change.1395 1396\section{What injective networks cannot do}1397 1398A classifier ends with a linear map, so the last hidden representation must make the classes linearly1399separable. If the network up to that point is injective, its restriction to $K$ is a homeomorphism onto1400the image, and separability becomes a constraint on how $K_+$ and $K_-$ sit in the ambient space.1401 1402\begin{theorem}[Nested classes]\label{thm:obstruction}\Scl[invariance of domain; cf.\ \cite{Joh19}]1403Let $h\colon\R^d\to\R^d$ be continuous and injective, let $\beta\subset\R^d$ be a closed topological ball with1404boundary sphere $S$, and let $p$ be an interior point of $\beta$. Then $h(p)$ lies in the convex hull of1405$h(S)$. In particular no hyperplane separates $h(p)$ from $h(S)$.1406\end{theorem}1407 1408\begin{proof}1409Suppose a linear functional $\lambda$ satisfies $\lambda>0$ on $h(S)$ and $\lambda(h(p))\le0$. Let $q$ be a1410point of the compact set $h(\beta)$ at which $\lambda$ is smallest. Then $\lambda(q)\le0$, so $q\notin h(S)$1411and $q\in h(\operatorname{int}\beta)$, which is open in $\R^d$ by invariance of domain. But a linear1412functional has no local minimum on an open set.1413\end{proof}1414 1415\begin{corollary}\label{cor:width}\Scl[\cite{Joh19,HS17}]1416A feedforward network on $\R^d$ in which every hidden layer has width $d$, every weight matrix is1417invertible, and the activation is injective, cannot separate a point from a sphere surrounding it. To do so1418a network must either have a layer of width at least $d+1$ or use a layer that is not injective.1419\end{corollary}1420