diff options
Diffstat (limited to 'topology.tex')
| -rw-r--r-- | topology.tex | 35 |
1 files changed, 17 insertions, 18 deletions
diff --git a/topology.tex b/topology.tex index 487b1e3..a55a5c4 100644 --- a/topology.tex +++ b/topology.tex @@ -172,17 +172,17 @@ studied properties of the cost function \end{equation} which achieves zero only for configurations that satisfy all the constraints. Introduced in Ref.~\cite{Fyodorov_2019_A}, the existence of solutions and the -geometric structure of the cost function were studied for the linear problem in +geometric structure of the cost function were studied for the problem with linear $V_k$ in a series of papers \cite{Fyodorov_2019_A, Fyodorov_2020_Counting, Fyodorov_2022_Optimization} and later reviewed \cite{Vivo_2024_Random}. Some -work on the equilibrium measure of the cost function in the nonlinear problem +work on the equilibrium measure of the cost function with nonlinear $V_k$ was made in Ref.~\cite{Tublin_2022_A}, and the problem was solved in Ref.~\cite{Urbani_2023_A}. Subsequent work has studied varied dynamics applied to the cost function, including gradient descent, Hessian descent, Langevin, stochastic gradient descent, and approximate message passing \cite{Kamali_2023_Dynamical, Kamali_2023_Stochastic, Montanari_2023_Solving, Montanari_2024_On}. Finally, some progress has been made on aspects of the -geometric structure of the cost function in the nonlinear problem +geometric structure of the cost function with nonlinear $V_k$ \cite{Kent-Dobias_2024_Conditioning, Kent-Dobias_2024_Algorithm-independent}. From the perspective of the cost function, the set of solutions looks like a network of flat canyons at the bottom of the cost landscape. @@ -261,7 +261,7 @@ points, one must take pains to eliminate the sign of the determinant \cite{Fyodorov_2004_Complexity}. Here it is correct to preserve it. We need to choose a function $H$ for our calculation. Because $\chi$ is -a topological invariant, any choice will work so long as it does not have degenerate stationary points on the manifold, i.e., that it is a Morse function, and does not share some +a topological invariant, any choice will work so long as it does not have degenerate stationary points on the manifold, i.e., that it is a Morse function, and that it does not share some symmetry with the underlying manifold, i.e., that it satisfies the Smale condition. Because our manifold is random and 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$. We call $H$ a height function because when $\mathbf x_0$ is @@ -354,36 +354,35 @@ parameters are varied. } \label{fig:action} \end{figure} -The order parameter $m$ may appear similar to the magnetization that appears in +\subsection{Features of the effective action} + +The order parameter $m$ is the overlap of the +configuration $\mathbf x$ with the height axis $\mathbf x_0$. Therefore, the +value $m$ that maximizes this action can be understood as the latitude on the +sphere at which most of the contribution to the Euler characteristic is made.\footnote{ +The order parameter $m$ may resemble the magnetization that appears in problems that have a signal or spike, where it gives the overlap of a configuration with the hidden signal. Here $\textbf x_0$ is no signal, but a -direction chosen uniformly at random and with no significance to the set of solutions. If in this problem a feature of the +direction chosen uniformly at random and with no significance to the set of solutions. Here, if a feature of the action is present at some value $m$, it should be interpreted as indicating -that, with overwhelming probability, the feature has a proximity to a typical +that, with overwhelming probability, the feature is found in proximity to a typical point in configuration space given by the overlap $m$. For instance, for $m$ -sufficiently close to one $\mathcal S_\chi(m)$ is always negative, which is a +sufficiently close to 1, $\mathcal S_\chi(m)$ is always negative, which is a result of the absence of any stationary points contributing to the Euler characteristic at those overlaps. Given a random height axis $\mathbf x_0$, the nearest point to $\mathbf x_0$ on the solution manifold will be the absolute maximum of the height function, and therefore contribute to the Euler -characteristic. Therefore, we can interpret the region of negative action in -the vicinity of $m=1$ to mean that there is a typical distance between the +characteristic. Hence the region of negative action in +the vicinity of $m=1$ implies there is a typical distance between the solution manifold and a randomly drawn point in configuration space, and that it is vanishingly unlikely to draw a point in configuration space uniformly at -random and find it any closer to the solution manifold than this.\footnote{ +random and find it any closer to the solution manifold than this. Other properties of the set of solutions could be studied by drawing $\mathbf x_0$ from an alternative distribution, like the Boltzmann distribution of the cost function, from the set of its stationary points, or from the solution manifold itself. While the value of the Euler characteristic would not change, the dependence of the effective action on $m$ would change. } - -\subsection{Features of the effective action} - -The order parameter $m$ is the overlap of the -configuration $\mathbf x$ with the height axis $\mathbf x_0$. Therefore, the -value $m$ that maximizes this action can be understood as the latitude on the -sphere at which most of the contribution to the Euler characteristic is made. The action $\mathcal S_\chi$ is extremized with respect to $m$ at $m=0$ or at $m=\pm m_*$ for \begin{equation} m_*=\sqrt{1-\frac{\alpha}{f'(1)}\big(V_0^2+f(1)\big)} |