diff options
| -rw-r--r-- | topology.bib | 147 | ||||
| -rw-r--r-- | topology.tex | 118 |
2 files changed, 231 insertions, 34 deletions
diff --git a/topology.bib b/topology.bib index dfff5d2..8165e79 100644 --- a/topology.bib +++ b/topology.bib @@ -23,3 +23,150 @@ doi = {10.1103/physrevlett.92.240601} } +@article{Fyodorov_2019_A, + author = {Fyodorov, Yan V.}, + title = {A Spin Glass Model for Reconstructing Nonlinearly Encrypted Signals Corrupted by Noise}, + journal = {Journal of Statistical Physics}, + publisher = {Springer Science and Business Media LLC}, + year = {2019}, + month = {1}, + number = {5}, + volume = {175}, + pages = {789--818}, + url = {https://doi.org/10.1007%2Fs10955-018-02217-9}, + doi = {10.1007/s10955-018-02217-9} +} + +@article{Fyodorov_2020_Counting, + author = {Fyodorov, Y. V. and Tublin, R.}, + title = {Counting Stationary Points of the Loss Function in the Simplest Constrained Least-square Optimization}, + journal = {Acta Physica Polonica B}, + publisher = {Jagiellonian University}, + year = {2020}, + number = {7}, + volume = {51}, + pages = {1663}, + url = {http://dx.doi.org/10.5506/APhysPolB.51.1663}, + doi = {10.5506/aphyspolb.51.1663}, + issn = {1509-5770} +} + +@article{Fyodorov_2022_Optimization, + author = {Fyodorov, Yan V and Tublin, Rashel}, + title = {Optimization landscape in the simplest constrained random least-square problem}, + journal = {Journal of Physics A: Mathematical and Theoretical}, + publisher = {IOP Publishing}, + year = {2022}, + month = {May}, + number = {24}, + volume = {55}, + pages = {244008}, + url = {http://dx.doi.org/10.1088/1751-8121/ac6d8e}, + doi = {10.1088/1751-8121/ac6d8e}, + issn = {1751-8121} +} + +@book{Hatcher_2002_Algebraic, + author = {Hatcher, Allen}, + title = {Algebraic topology}, + publisher = {Cambridge University Press}, + year = {2002}, + address = {Cambridge ; New York}, + isbn = {9780521791601 9780521795401}, + keyword = {Algebraic topology} +} + +@article{Kamali_2023_Dynamical, + author = {Kamali, Persia Jana and Urbani, Pierfrancesco}, + title = {Dynamical mean field theory for models of confluent tissues and beyond}, + journal = {SciPost Physics}, + publisher = {Stichting SciPost}, + year = {2023}, + month = {November}, + number = {5}, + volume = {15}, + pages = {219}, + url = {http://dx.doi.org/10.21468/SciPostPhys.15.5.219}, + doi = {10.21468/scipostphys.15.5.219}, + issn = {2542-4653} +} + +@unpublished{Kamali_2023_Stochastic, + author = {Kamali, Persia Jana and Urbani, Pierfrancesco}, + title = {Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape}, + year = {2023}, + month = {sep}, + url = {http://arxiv.org/abs/2309.04788v2}, + note = {}, + archiveprefix = {arXiv}, + eprint = {2309.04788v2}, + eprintclass = {cs.LG}, + eprinttype = {arxiv} +} + +@unpublished{Montanari_2023_Solving, + author = {Montanari, Andrea and Subag, Eliran}, + title = {Solving overparametrized systems of random equations: I. Model and algorithms for approximate solutions}, + year = {2023}, + month = {jun}, + url = {http://arxiv.org/abs/2306.13326v1}, + note = {}, + archiveprefix = {arXiv}, + eprint = {2306.13326v1}, + eprintclass = {math.PR}, + eprinttype = {arxiv} +} + +@unpublished{Montanari_2024_On, + author = {Montanari, Andrea and Subag, Eliran}, + title = {On {Smale}'s 17th problem over the reals}, + year = {2024}, + month = {may}, + url = {http://arxiv.org/abs/2405.01735v1}, + note = {}, + archiveprefix = {arXiv}, + eprint = {2405.01735v1}, + eprintclass = {cs.DS}, + eprinttype = {arxiv} +} + +@article{Urbani_2023_A, + author = {Urbani, Pierfrancesco}, + title = {A continuous constraint satisfaction problem for the rigidity transition in confluent tissues}, + journal = {Journal of Physics A: Mathematical and Theoretical}, + publisher = {IOP Publishing}, + year = {2023}, + month = {February}, + number = {11}, + volume = {56}, + pages = {115003}, + url = {http://dx.doi.org/10.1088/1751-8121/acb742}, + doi = {10.1088/1751-8121/acb742}, + issn = {1751-8121} +} + +@unpublished{Urbani_2024_Statistical, + author = {Urbani, Pierfrancesco}, + title = {Statistical physics of complex systems: glasses, spin glasses, continuous constraint satisfaction problems, high-dimensional inference and neural networks}, + year = {2024}, + month = {may}, + url = {http://arxiv.org/abs/2405.06384v1}, + note = {}, + archiveprefix = {arXiv}, + eprint = {2405.06384v1}, + eprintclass = {cond-mat.dis-nn}, + eprinttype = {arxiv} +} + +@unpublished{Vivo_2024_Random, + author = {Vivo, Pierpaolo}, + title = {Random Linear Systems with Quadratic Constraints: from Random Matrix Theory to replicas and back}, + year = {2024}, + month = {jan}, + url = {http://arxiv.org/abs/2401.03209v2}, + archiveprefix = {arXiv}, + eprint = {2401.03209v2}, + eprintclass = {cond-mat.stat-mech}, + eprinttype = {arxiv} +} + diff --git a/topology.tex b/topology.tex index 84b871d..de4576c 100644 --- a/topology.tex +++ b/topology.tex @@ -34,33 +34,77 @@ exponentially large in $N$, indicating a shattering transition in the space of solutions. Finally, when $\alpha_\mathrm a^*\leq\alpha$, the number of solutions vanish. We further compute the average logarithm of the Euler - characteristic, which is representative of typical manifolds. + characteristic, which is representative of typical manifolds. We compare + these results with the analogous calculation for the topology of level sets + of the spherical spin glasses, whose connected phase has a negative Euler + characteristic indicative of many holes. \end{abstract} \maketitle -$\Omega=\{\mathbf x\in\mathbb R^N\mid \|\mathbf x\|^2=N,0=V_k(\mathbf x)\text{ for all $1\leq k\leq M$}\}$. -$\Omega$ is almost always a manifold without singular points due to -intersections. The conditions of a singular point are that +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$ +nonlinear constraints $V_k(\mathbf x)=0$ for $1\leq k\leq M$. The nonlinear +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 +\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}. + + +This problem or small variations thereof have attracted attention recently for +their resemblance to encryption, optimization, and vertex models of confluent +tissues \cite{Fyodorov_2019_A, Fyodorov_2020_Counting, + Fyodorov_2022_Optimization, Urbani_2023_A, Kamali_2023_Dynamical, + Kamali_2023_Stochastic, Urbani_2024_Statistical, Montanari_2023_Solving, +Montanari_2024_On}. In each of these cases, the authors studied properties of +the cost function +\begin{equation} + \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 +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\} +\end{equation} +$\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 unlikely, requiring $NM$ independent equations to be simultaneously satisfied. - -The Euler characteristic $\chi$ of a manifold is a topological invariant. It is -perhaps most familiar in the context of connected compact 2-manifolds, where it -characterizes the number of holes in the surface: $\chi=2(1-\#)$ for $\#$ -holes. +This means that different connected components of the set of solutions do not +intersect, nor are there self-intersections, without extraordinary fine-tuning. + +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 +characterizes the number of handles in the surface: $\chi=2(1-\#)$ for $\#$ +handles. For general $d$, the Euler characteristic of the $d$-sphere is $2$ if $d$ is even and 0 if $d$ is odd. The canonical method for computing the Euler characteristic is done by +defining a complex on the manifold in question, essentially a +higher-dimensional generalization of a polygonal tiling. Then $\chi$ is given +by an alternating sum over the number of cells of increasing dimension, which +for 2-manifolds corresponds to the number of vertices, minus the number of +edges, plus the number of faces. Morse theory offers another way to compute the Euler characteristic using the -statistics of stationary points of function $H$ defined on the manifold. For -function $H$ without any symmetries with respect to the manifold, the surfaces -of gradient flow between adjacent stationary points form a complex, i.e., a -higher-dimension polygonization of the surface. The standard counting argument -to compute $\chi$ of vertices minus edges plus faces generalizes to an -alternating sum over the counts of stationary points that make up the complex, -or +statistics of stationary points of a function $H:\Omega\to\mathbb R$ \cite{Audin_2014_Morse}. For +functions $H$ without any symmetries with respect to the manifold, the surfaces +of gradient flow between adjacent stationary points form a complex. The +alternating sum over cells to compute $\chi$ becomes an alternating sum over +the count of stationary points of $H$ with increasing index, or \begin{equation} \chi=\sum_{i=0}^N(-1)^i\mathcal N_H(\text{index}=i) \end{equation} @@ -69,20 +113,27 @@ using a small variation on the Kac--Rice formula for counting stationary points. Since the sign of the determinant of the Hessian matrix of $H$ at a stationary point is equal to its index, if we count stationary points including the sign of the determinant, we arrive at the Euler characteristic, or -\begin{equation} +\begin{equation} \label{eq:kac-rice} \chi=\int_\Omega d\mathbf x\,\delta\big(\nabla H(\mathbf x)\big)\det\operatorname{Hess}H(\mathbf x) \end{equation} When the Kac--Rice formula is used to \emph{count} stationary points, the sign of the determinant is a nuisance that one must take pains to preserve \cite{Fyodorov_2004_Complexity}. Here we are correct to exclude it. +We treat the integral over the implicitly defined manifold $\Omega$ using the +method of Lagrange multipliers. We introduce one multiplier $\omega_0$ to +enforce the spherical constraint and $M$ multipliers $\omega_k$ to enforce the vanishing of +each of the $V_k$, resulting in the Lagrangian \begin{equation} L(\mathbf x,\pmb\omega) =H(\mathbf x)+\frac12\omega_0\big(\|\mathbf x\|^2-N\big) - +\sum_{k=1}^M\omega_iV_k(\mathbf x) + +\sum_{k=1}^M\omega_kV_k(\mathbf x) \end{equation} +The integral over $\Omega$ in \eqref{eq:kac-rice} then becomes \begin{equation} - \chi=\int_{\mathbb R^N} d\mathbf x\,d\pmb\omega\,\delta\big(\partial L(\mathbf x,\pmb\omega)\big)\det\partial\partial L(\mathbf x,\pmb\omega) + \chi=\int_{\mathbb R^N} d\mathbf x\int_{\mathbb R^{M+1}}d\pmb\omega + \,\delta\big(\partial L(\mathbf x,\pmb\omega)\big) + \det\partial\partial L(\mathbf x,\pmb\omega) \end{equation} where $\partial=[\frac\partial{\partial\mathbf x},\frac\partial{\partial\pmb\omega}]$ is the vector of partial derivatives with respect to all $N+M+1$ variables. @@ -104,7 +155,7 @@ Using standard manipulations, we find \end{equation} Now we are forced to make a decision about the function $H$. Because $\chi$ is a topological invariant, any choice will work so long as it does not share some -symmetry with the underlying manifold. Because our manifold of random +symmetry with the underlying manifold, i.e., that it $H$ satisfies the Smale condition. Because our manifold of random constraints has no symmetries, we can take a simple height function $H(\mathbf x)=\mathbf x_0\cdot\mathbf x$ for some $\mathbf x_0\in\mathbb R^N$ with $\|\mathbf x_0\|^2=N$. $H$ is a height function because when $\mathbf x_0$ is @@ -117,25 +168,13 @@ $\mathbb M(1)=\frac1N\phi(1)\cdot\mathbf x_0$, the result is \overline{\chi}&=\int d\mathbb Q\,d\mathbb M\,d\sigma_0\,\exp\Bigg\{ \frac N2\log\operatorname{sdet}(\mathbb Q-\mathbb M\mathbb M^T) -\frac M2\log\operatorname{sdet}f(\mathbb Q) \notag \\ - &+N\int d1\,\left[ - (1+\hat\beta\bar\theta_1\theta_1)\mathbb M(1)+\frac12\sigma_0(1)\big(\mathbb Q(1,1)-1\big) + &\quad+N\int d1\,\left[ + \mathbb M(1)+\frac12\sigma_0(1)\big(\mathbb Q(1,1)-1\big) \right] \Bigg\} \end{align} \begin{equation} - 0=\int d2\,(\mathbb Q(1,2)-\mathbb M(1)\mathbb M(2)^T)(1+\bar\theta_2\theta_2\hat\beta)+\mathbb M(1) -\end{equation} - -\[ - D=\beta R - \quad - \beta=-\frac{m+\sum_aR_{1a}}{\sum_aC_{1a}} - \quad - \hat m=0 -\] - -\begin{equation} \begin{aligned} &\frac1N\log\overline\chi =\frac12\Bigg[ @@ -152,8 +191,19 @@ $\mathbb M(1)=\frac1N\phi(1)\cdot\mathbf x_0$, the result is \end{equation} + +\begin{equation} + D=\beta R + \qquad + \beta=-\frac{m+\sum_aR_{1a}}{\sum_aC_{1a}} + \qquad + \hat m=0 +\end{equation} + + \begin{acknowledgements} JK-D is supported by a \textsc{DynSysMath} Specific Initiative of the INFN. + The authors thank Pierfrancesco Urbani for helpful conversations on these topics. \end{acknowledgements} \bibliography{topology} |