From 427a8fa280f32f0a04a539cbbd85471934e2f97a Mon Sep 17 00:00:00 2001
From: Jaron Kent-Dobias <jaron@kent-dobias.com>
Date: Sat, 3 Aug 2024 15:51:41 +0200
Subject: Lots of writing.

---
 topology.tex | 99 ++++++++++++++++++++++++++++++++++++------------------------
 1 file changed, 59 insertions(+), 40 deletions(-)

(limited to 'topology.tex')

diff --git a/topology.tex b/topology.tex
index decfa6f..5233c54 100644
--- a/topology.tex
+++ b/topology.tex
@@ -25,20 +25,43 @@
 \affiliation{Istituto Nazionale di Fisica Nucleare, Sezione di Roma I, Rome, Italy 00184}
 
 \begin{abstract}
-  We consider the set of solutions to $M$ random polynomial equations on the
-  $(N-1)$-sphere. When solutions exist, they form a manifold. We compute the
-  average Euler characteristic of this manifold, and find different behaviors
-  depending on $\alpha=M/N$. When $\alpha<1$, the average Euler characteristic
-  is subexponential in $N$ but positive, indicating the presence of few
-  simply-connected components. When $1\leq\alpha<\alpha_\text{\textsc{sat}}$, it is
-  exponentially large in $N$, indicating a shattering transition in the space
-  of solutions. Finally, when $\alpha_\text{\textsc{sat}}\leq\alpha$, the number of
-  solutions vanish. We further compute the average logarithm of the Euler
-  characteristic, which is representative of typical manifolds.
+  We consider the set of solutions to $M$ random polynomial equations with
+  independent Gaussian coefficients on the $(N-1)$-sphere. When solutions
+  exist, they form a manifold. We compute the average Euler characteristic of
+  this manifold, and find different behaviors depending on the variances of the
+  coefficients and $\alpha=M/N$. When $\alpha<1$, the average Euler
+  characteristic is subexponential in $N$ but positive, indicating the presence
+  of few connected components. When $1<\alpha<\alpha_\text{\textsc{sat}}$, it
+  is exponentially large in $N$, indicating a shattering transition of the
+  manifold of solutions into many components. Finally, when
+  $\alpha_\text{\textsc{sat}}<\alpha$, the set of solutions vanishes. Some
+  choices of variances produce $\alpha_\text{\textsc{sat}}<1$, and the shattering
+  transition never takes place. We further compute the average logarithm of the
+  Euler characteristic, which is representative of typical manifolds, and find
+  that most of the quantitative predictions agree.
 \end{abstract}
 
 \maketitle
 
+Constraint satisfaction problems seek configurations that simultaneously
+satisfy a set of equations, and form a basis for thinking about problems as
+diverse as neural networks \cite{Mezard_2009_Constraint}, granular materials
+\cite{Franz_2017_Universality}, ecosystems \cite{Altieri_2019_Constraint}, and
+confluent tissues \cite{Urbani_2023_A}. All but the last of these examples deal
+with sets of inequalities, while the last considers a set of equality
+constraints. Inequality constraints are familiar in situations like zero-cost
+solutions in neural networks with ReLu activations and stable equilibrium in the
+forces between physical objects. Equality constraints naturally appear in the
+zero-gradient solutions to overparameterized smooth neural networks and,
+indeed, in vertex models of tissues.
+
+In such problems, there is great interest in characterizing structure in the
+set of solutions, which can be influential in how algorithms behave when trying
+to solve them \cite{Baldassi_2016_Unreasonable, Baldassi_2019_Properties,
+Beneventano_2023_On}. Here, we show how \emph{topological} information about
+the set of solutions can be calculated in a simple model of satisfying random
+nonlinear equalities. This allows us to reason about the connectivity of this
+solution set.
 
 We consider the problem of finding configurations $\mathbf x\in\mathbb R^N$
 lying on the $(N-1)$-sphere $\|\mathbf x\|^2=N$ that simultaneously satisfy $M$
@@ -47,15 +70,18 @@ constraints are taken to be centered Gaussian random functions with covariance
 \begin{equation} \label{eq:covariance}
   \overline{V_i(\mathbf x)V_j(\mathbf x')}=\delta_{ij}f\left(\frac{\mathbf x\cdot\mathbf x'}N\right)
 \end{equation}
-for some choice of $f$.
-When the covariance function $f$ is polynomial, the $V_k$ are also polynomial, with terms of degree $p$ in $f$ corresponding to all possible terms of degree $p$ in $V_k$. In particular, taking
+for some choice of $f$. When the covariance function $f$ is polynomial, the
+$V_k$ are also polynomial, with a term of degree $p$ in $f$ corresponding to
+all possible terms of degree $p$ in $V_k$. In particular, taking
 \begin{equation}
   V_k(\mathbf x)
   =\sum_{p=0}^\infty\frac1{p!}\sqrt{\frac{f^{(p)}(0)}{N^p}}
   \sum_{i_1\cdots i_p}^NJ^{(k,p)}_{i_1\cdots i_p}x_{i_1}\cdots x_{i_p}
 \end{equation}
-and each of the elements of the tensors $J^{(k,p)}$ as independently
-distributed with a unit normal distribution satisfies \eqref{eq:covariance}.
+with the elements of the tensors $J^{(k,p)}$ as independently distributed
+unit normal random variables satisfies \eqref{eq:covariance}. The size of the
+series coefficients of $f$ therefore control the variances in the coefficients
+of random polynomial constraints.
 
 
 This problem or small variations thereof have attracted attention recently for
@@ -65,21 +91,19 @@ tissues \cite{Fyodorov_2019_A, Fyodorov_2020_Counting,
   Kamali_2023_Stochastic, Urbani_2024_Statistical, Montanari_2023_Solving,
 Montanari_2024_On, Kent-Dobias_2024_Conditioning, Kent-Dobias_2024_Algorithm-independent}. In each of these cases, the authors studied properties of
 the cost function
-\begin{equation}
+\begin{equation} \label{eq:cost}
   \mathcal C(\mathbf x)=\frac12\sum_{k=1}^MV_k(\mathbf x)^2
 \end{equation}
-which achieves zero cost only for configurations that satisfy all the
-constraints.
-Here we dispense with defining a cost function, and instead study
-the set of solutions directly.
-
-The set of solutions to our nonlinear random constraint satisfaction problem
+which achieves zero only for configurations that satisfy all the constraints.
+Here we dispense with the cost function and study the set of solutions
+directly.
+This set
 can be written as
 \begin{equation}
-  \Omega=\{\mathbf x\in\mathbb R^N\mid \|\mathbf x\|^2=N,0=V_k(\mathbf x)
-  \;\forall\;k=1,\ldots,M\}
+  \Omega=\{\mathbf x\in\mathbb R^N\mid \|\mathbf x\|^2=N,V_k(\mathbf x)=0
+  \;\forall\;k=1,\ldots,M\}.
 \end{equation}
-$\Omega$ is almost always a manifold without singular points. The conditions for a singular point are that
+Because the constraints are all smooth functions, $\Omega$ is almost always a manifold without singular points. The conditions for a singular point are that
 $0=\frac\partial{\partial\mathbf x}V_k(\mathbf x)$ for all $k$. This is
 equivalent to asking that the constraints $V_k$ all have a stationary point at
 the same place. When the $V_k$ are independent and random, this is vanishingly
@@ -87,9 +111,10 @@ unlikely, requiring $NM$ independent equations to be simultaneously satisfied.
 This means that different connected components of the set of solutions do not
 intersect, nor are there self-intersections, without extraordinary fine-tuning.
 
-One result of this previous work is the value of $\alpha$ for the
-satisfiability transition, which is $\alpha_\text{\textsc{sat}}=f'(1)/f(1)$.
-For $\alpha$ larger than $\alpha_\text{\textsc{sat}}$ solutions do not exist.
+When $M$ is too large, no solutions exist and $\Omega$ becomes the empty set.
+Following previous work, a replica symmetric equilibrium calculation using the
+cost function \eqref{eq:cost} predicts that solutions vanish when the ratio
+$\alpha=M/N$ is larger than $\alpha_\text{\textsc{sat}}=f'(1)/f(1)$. Based on the results of this paper, and the fact that this $\alpha_\text{\textsc{sat}}$ is consistent 
 
 The Euler characteristic $\chi$ of a manifold is a topological invariant \cite{Hatcher_2002_Algebraic}. It is
 perhaps most familiar in the context of connected compact orientable surfaces, where it
@@ -207,12 +232,15 @@ is positive, and $\overline\chi$ is exponentially large in $N$. Finally, when
 $\alpha\geq\alpha_\text{\textsc{sat}}$ the action and $\overline\chi$ are ill-defined.
 
 \begin{figure}
-  \includegraphics{figs/characteristic.pdf}
+  \includegraphics{figs/quenched.pdf}
 
   \caption{
     The logarithm of the average Euler characteristic $\overline\chi$ as a
-    function of $\alpha$. The covariance function is $f(q)=\frac12q^2$ and
-    $\alpha_\text{\textsc{sat}}=2$.
+    function of $\alpha$. The covariance function is $f(q)=\frac12+\frac12q^3$ and
+    $\alpha_\text{\textsc{sat}}=\frac32$. The dashed line shows the average of
+    $\log\chi$, the so-called quenched average, whose value differs in the
+    region $1<\alpha<\alpha_\text{\textsc{sat}}$ but whose transition points
+    are the same.
   } \label{fig:characteristic}
 \end{figure}
 
@@ -293,6 +321,7 @@ these eigenvalues is difficult to understand directly, in situations where
 there is a continuous \textsc{rsb} transition the sign of one of the
 eigenvalues changes \cite{Kent-Dobias_2023_When}. At the $\alpha_\text{\textsc{rsb}}$ predicted in \cite{Urbani_2023_A} we see no instability of this kind, and instead only observe such an instability at $\alpha_\text{\textsc{sat}}$.
 
+\cite{Franz_2016_The, Franz_2017_Universality, Franz_2019_Critical, Annesi_2023_Star-shaped, Baldassi_2023_Typical}
 
 \begin{acknowledgements}
   JK-D is supported by a \textsc{DynSysMath} Specific Initiative of the INFN.
@@ -410,14 +439,4 @@ where $\Delta f=f(1)-f(0)$ and $\tilde r_d$ is given by
 \end{align}
 When $\alpha\to\alpha_\text{\textsc{sat}}=f'(1)/f(1)$ from below, $\tilde r_d\to -1$, which produces $N^{-1}\overline{\log\chi}\to0$.
 
-\begin{figure}
-  \includegraphics{figs/quenched.pdf}
-
-  \caption{
-    Comparison of the annealed and replica symmetric quenched calculations of
-    the logarithmic of the Euler characteristic. The covariance function is
-    $f(q)=\frac12+\frac12q^3$ and $\alpha_\text{\textsc{sat}}=\frac32$.
-  }
-\end{figure}
-
 \end{document}
-- 
cgit v1.2.3-70-g09d2

