diff options
Diffstat (limited to 'topology.tex')
| -rw-r--r-- | topology.tex | 99 |
1 files changed, 59 insertions, 40 deletions
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} |