\documentclass[aspectratio=169,dvipsnames]{beamer} \setbeamerfont{title}{family=\bf} \setbeamerfont{frametitle}{family=\bf} \setbeamerfont{normal text}{family=\rm} \setbeamertemplate{navigation symbols}{} \setbeamercolor{titlelike}{parent=structure,fg=cyan} \usepackage{enumitem} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{pifont} \usepackage{graphicx} \usepackage{xcolor} \usepackage{tikz} \definecolor{ictpblue}{HTML}{0471b9} \definecolor{ictpgreen}{HTML}{0c8636} \definecolor{mb}{HTML}{5e81b5} \definecolor{my}{HTML}{e19c24} \definecolor{mg}{HTML}{8fb032} \definecolor{mr}{HTML}{eb6235} \setbeamercolor{titlelike}{parent=structure,fg=ictpblue} \setbeamercolor{itemize item}{fg=ictpblue} \usepackage[ style=phys, eprint=true, maxnames = 100, terseinits=true ]{biblatex} \addbibresource{zif.bib} \title{ Understanding the flat parts of random landscapes } \author{\textbf{Jaron Kent-Dobias}} \date{9 September 2025} \begin{document} \begin{frame} \maketitle \vspace{-8pc} \begin{minipage}[c]{10pc} \centering \includegraphics[height=6pc]{figs/logo-ictp-saifr.jpg} \vspace{2em} \includegraphics[height=1.5pc]{figs/Simons-Foundation-Logo_blue.png} \end{minipage} \hfill\begin{minipage}[c]{10pc} \centering \includegraphics[height=6pc]{figs/ift-unesp.png} \vspace{2em} \includegraphics[height=1.5pc]{figs/fapesp.png} \end{minipage} \vspace{2pc} \end{frame} \begin{frame} \frametitle{Understanding the flat parts of random landscapes} \begin{columns} \begin{column}{0.33\textwidth} \textbf{Nearly flat parts} \vspace{-0.75em} \rule{\columnwidth}{1pt} \medskip Conditioning stationary point complexity on marginal optima \bigskip \centering \includegraphics[height=10pc]{figs/msg_marg_spectra.pdf} \end{column} \begin{column}{0.66\textwidth} \textbf{Really flat parts} \vspace{-0.75em} \rule{\columnwidth}{1pt} \bigskip \begin{minipage}{0.49\columnwidth} \raggedright Topology of solution manifolds via the average Euler characteristic \bigskip \centering \includegraphics[height=10pc]{figs/function_2.png} \end{minipage} \hfill \begin{minipage}{0.49\columnwidth} \raggedright Geometry of solution sets via the statistics of wedged and inscribed spheres \bigskip \centering \includegraphics[height=10pc]{figs/max_size_zoom.pdf} \end{minipage} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Marginal complexity} \begin{columns} \begin{column}{0.5\textwidth} Statistics of local optima imagined to govern behavior in rugged optimisation \bigskip High-dimensional landscapes differ from cartoons in important ways \bigskip Generic rugged landscapes covered mostly by basins attached to marginal optima \bigskip Understanding marginal optima is more important for typical dynamics than understanding typical optima \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\textwidth]{figs/complex_landscapes.png}\centering\\\tiny C Cammarota \onslide<2>\includegraphics[width=\textwidth]{figs/fake_landscape.png}\\\tiny S Martiniani, YouTube \onslide<3>\includegraphics[width=\textwidth]{figs/real_landscape.png}\smallskip\\\tiny\fullcite{Suryadevara_2024_The} \onslide<4>\includegraphics[width=\textwidth]{figs/eigenvalue_convergence.pdf}\smallskip\\\tiny\fullcite{Kent-Dobias_2024_Algorithm-independent} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{How to count: Kac--Rice} Number of stationary points with $\nabla H(\boldsymbol x)=0$ given by integral over Kac--Rice measure \begin{align*} \#_\text{points} &=\int_\Omega d\boldsymbol x\,\delta\big(\nabla H(\boldsymbol x)\big)\,\big|\det\operatorname{Hess}H(\boldsymbol x)\big| \end{align*} Note absolute value of the determinant: want to account for curvature but not add $-1$ \bigskip Can specify properties of points by inserting $\delta$-functions: \begin{align*} \#_\text{points}\alert<2>{(E)} &=\int_\Omega d\boldsymbol x\,\delta\big(\nabla H(\boldsymbol x)\big)\,\big|\det\operatorname{Hess}H(\boldsymbol x)\big| \alert<2>{\,\delta\big(H(\boldsymbol x)-NE\big)} \end{align*} \emph{How do we condition on marginal minima?} \end{frame} \begin{frame} \frametitle{Conditioning on the type of minimum: the spherical models} \begin{columns} \begin{column}{0.5\textwidth} In spherical spin glasses, all points have the same Hessian spectral density: semicircle with radius $\mu_\text m$, but different shifts \[ \mu=\frac1N\operatorname{Tr}\operatorname{Hess} H(\boldsymbol x) \] \bigskip Condition on marginal minima by inserting \[ \delta\big(\operatorname{Tr}\operatorname{Hess}H(\boldsymbol x)-N\mu_\text{m}\big) \] \end{column} \begin{column}{0.5\textwidth} \begin{overlayarea}{\textwidth}{14.5em} \only<1-2>{\includegraphics[width=\columnwidth]{figs/mu_0.75.pdf}\\\hphantom{ello}\includegraphics[width=0.8\columnwidth]{figs/land_0.75.pdf}} \only<3>{\includegraphics[width=\columnwidth]{figs/mu_1.5.pdf}\\\hphantom{ello}\includegraphics[width=0.8\columnwidth]{figs/land_1.5.pdf}} \only<4>{\includegraphics[width=\columnwidth]{figs/mu_2.25.pdf}\\\hphantom{ello}\includegraphics[width=0.8\columnwidth]{figs/land_2.25.pdf}} \only<5>{\includegraphics[width=\columnwidth]{figs/mu_3.5.pdf}\\\hphantom{ello}\includegraphics[width=0.8\columnwidth]{figs/land_3.5.pdf}} \only<6>{\includegraphics[width=\columnwidth]{figs/mu_2.pdf}\\\hphantom{ello}\includegraphics[width=0.8\columnwidth]{figs/land_2.pdf}} \end{overlayarea} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Less simple mean-field models} \framesubtitle{The mixed spherical spin glasses} \begin{columns} \begin{column}{0.41\textwidth} \alert<1-2>{Pure: all procedures reach $E_\text{th}$} \medskip \alert<3-4>{Mixed: different procedures reach different energies} \medskip Dynamical endpoints bounded by complexity of marginal minima \bigskip \tiny \fullcite{Folena_2020_Rethinking} \smallskip \fullcite{Folena_2021_Gradient} \smallskip \fullcite{Kent-Dobias_2023_How} \end{column} \begin{column}{0.59\textwidth} \begin{overlayarea}{\columnwidth}{0.8\textheight} \only<1>{% \includegraphics[width=0.8\columnwidth]{figs/complexity_3_marginal.pdf} }% \only<2>{% \bigskip \begin{minipage}[b]{0.83\columnwidth} \centering \includegraphics[width=0.18\columnwidth]{figs/land_0.75.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_0.75.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_0.75.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_0.75.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_0.75.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_1.5.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_1.5.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_1.5.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_1.5.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_2.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_2.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_2.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_2.25.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_2.25.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_3.5.pdf} \end{minipage} \raisebox{0.75em}{\includegraphics[width=0.15\columnwidth]{figs/energy_arrow.pdf}} } \only<3>{% \includegraphics[width=0.8\columnwidth]{figs/complexity_34_marginal.pdf} }% \only<4>{% \bigskip \begin{minipage}[b]{0.83\columnwidth} \centering \includegraphics[width=0.18\columnwidth]{figs/land_0.75.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_0.75.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_0.75.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_1.5.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_1.5.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_0.75.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_1.5.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_1.5.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_2.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_1.5.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_2.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_2.25.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_2.25.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_3.5.pdf} \includegraphics[width=0.18\columnwidth]{figs/land_2.25.pdf} \end{minipage} \raisebox{0.75em}{\includegraphics[width=0.15\columnwidth]{figs/energy_arrow_o1.pdf}} }% \end{overlayarea} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Marginal minima in generic models} \begin{columns} \begin{column}{0.5\textwidth} \alert<1>{In spherical spin glasses, all points have the same Hessian spectral density: semicircle with radius $\mu_\text m$, but different shifts} \bigskip In generic models, spectral density depends on stationarity, energy, etc! \bigskip \alert<2>{Example: multi-spherical model \[ H(\{\boldsymbol x_1,\boldsymbol x_2\}) =H_p^{(1)}(\boldsymbol x_1)+H_p^{(2)}(\boldsymbol x_2)+\epsilon\boldsymbol x_1\cdot\boldsymbol x_2 \]} \hspace{-0.25em}In most models we don't understand the Hessian at all \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\columnwidth]{figs/mu_0.75.pdf} \onslide<2>\includegraphics[width=0.9\columnwidth]{figs/msg_marg_spectra.pdf} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Towards generic marginal complexity} \begin{columns} \begin{column}{0.6\textwidth} \begin{itemize}[leftmargin=4em] \item[\color{ictpgreen}\bf Trick \#1:] condition stationary points on \emph{value of smallest eigenvalue} \end{itemize} { \small \begin{align*} \hspace{0em}&\delta(\lambda_\text{min}(A)) \\ &=\lim_{\beta\to\infty}\int \frac{d\boldsymbol s\,\delta(N-\|\boldsymbol s\|^2)e^{-\beta\boldsymbol s^TA\boldsymbol s}} {\int d\boldsymbol s'\,\delta(N-\|\boldsymbol s'\|^2)e^{-\beta\boldsymbol s'^TA\boldsymbol s'}} \delta\left(\frac{\boldsymbol s^TA\boldsymbol s}N\right) \end{align*} } \bigskip Only works if you happen to have the correct shift $\mu$ \bigskip \tiny \fullcite{Kent-Dobias_2024_Conditioning} \end{column} \begin{column}{0.4\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\textwidth]{figs/spectrum_less.pdf} \onslide<2>\includegraphics[width=\textwidth]{figs/spectrum_more.pdf} \onslide<3>\includegraphics[width=\textwidth]{figs/spectrum_eq.pdf} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Towards generic marginal complexity} \begin{columns} \begin{column}{0.5\textwidth} \begin{itemize}[leftmargin=4em] \item[\color{ictpgreen}\bf Trick \#1:] condition stationary points on \emph{value of smallest eigenvalue} \end{itemize} { \small \begin{align*} \hspace{0em}&\delta(\lambda_\text{min}(A)) \\ \hspace{0em}&=\lim_{\beta\to\infty}\int \frac{d\boldsymbol s\,\delta(N-\|\boldsymbol s\|^2)e^{-\beta\boldsymbol s^TA\boldsymbol s}} {\int d\boldsymbol s'\,\delta(N-\|\boldsymbol s'\|^2)e^{-\beta\boldsymbol s'^TA\boldsymbol s'}} \delta\left(\frac{\boldsymbol s^TA\boldsymbol s}N\right) \end{align*} } \medskip \begin{itemize}[leftmargin=4em] \item[\color{ictpgreen}\bf Trick \#2:] adjust $\mu\propto\operatorname{Tr}\operatorname{Hess}H$ until order-$N$ large deviation breaks \end{itemize} \bigskip \tiny \fullcite{Kent-Dobias_2024_Conditioning} \end{column} \begin{column}{0.5\textwidth} \hspace{0.9em} \includegraphics[scale=0.8]{figs/spectrum_less.pdf} \hspace{-1.6em} \includegraphics[scale=0.8]{figs/spectrum_eq.pdf} \hspace{-1.6em} \includegraphics[scale=0.8]{figs/spectrum_more.pdf} \\ \includegraphics[scale=0.8]{figs/large_deviation.pdf} \vspace{-1em} \small \begin{align*} \hspace{-0.5em}G_0(\mu)=\frac 1N\log\Big\langle\delta\big(\lambda_\text{min}(A-\mu I)\big)\Big\rangle_{A\in\text{GOE}(N)} \end{align*} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Marginal complexity: example} \begin{columns} \begin{column}{0.5\textwidth} Example: model of nonlinear least squares: \[ H(\boldsymbol x)=\frac12\sum_{i=1}^{M}V_i(\boldsymbol x)^2 \] for spherical $\boldsymbol x\in\mathbb R^N$ and $M=\alpha N$ inhomogeneous random functions $V_i$ \[ V_i(\boldsymbol x)=H_2^{(i)}(\boldsymbol x)+H_3^{(i)}(\boldsymbol x) \] \bigskip \tiny \fullcite{Kent-Dobias_2024_Conditioning} \smallskip \fullcite{Kent-Dobias_2024_Algorithm-independent} \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\vspace{4em}\includegraphics[width=\textwidth]{figs/most_squares_complex.pdf} \onslide<2>\vspace{-1.75em}\includegraphics[width=\textwidth]{figs/most_squares_complexity.pdf} \vspace{-1.95em} \hspace{-0.25em}\colorbox{white}{\includegraphics[width=\textwidth]{figs/most_squares_stability.pdf}} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Really flat parts: zero-cost sets} \begin{columns} \begin{column}{0.5\textwidth} Diverse optimization problems exactly fit data or satisfy constraints, reach zero cost \bigskip Stationary point technology useless for describing zero-cost sets \bigskip Mostly understood by pointwise sampling or interpolation between pairs of sampled points \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\textwidth]{figs/neural_landscape_1.png}\smallskip\\\tiny\fullcite{Liu_2022_Loss} \onslide<2>\includegraphics[width=\textwidth]{figs/neural_landscape_2.png}\smallskip\\\tiny\fullcite{Liu_2022_Loss} \onslide<3>\includegraphics[width=\textwidth]{figs/draxler_2018.png}\smallskip\\\tiny\fullcite{Draxler_2018_Essentially} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Zero cost manifolds vs.\ zero cost non-manifolds} \begin{columns} \begin{column}{0.5\textwidth} \textbf{Manifolds} \medskip Defined by sets of \emph{analytic equalities} \medskip Network $f_{\boldsymbol x}:\mathbb R^P\to\mathbb R$, $\boldsymbol x\in S^{N-1}\subset\mathbb R^N$, with analytic activations (e.g.\ $\tanh$): \[ y^\mu=f_{\boldsymbol x}(\boldsymbol a^\mu)\qquad\mu=1,\ldots,M \] \smallskip \textbf{(Usual) Non-manifolds} \medskip Defined by sets of \emph{inequalities} \medskip Jamming of disks in $d$ dimensions: \[ \|\boldsymbol x^i-\boldsymbol x^j\|\geq 2R\qquad i,j=1,\ldots,P \] \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\textwidth]{figs/intersections_3.pdf} \onslide<2>\includegraphics[width=\textwidth]{figs/nothing_zoom.pdf} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{The Euler characteristic \boldmath{$\chi$}} \begin{columns} \begin{column}{0.5\textwidth} The Euler characteristic $\chi(\Omega)$ is a topological invariant of a manifold $\Omega$ \medskip Defined by tiling the manifold, then taking the alternating sum \begin{align*} \chi(\Omega_{\text{cow}}) &= {\only<2,5->{\color{Red}}\#_\text{vertices}} &&\hspace{-1em}- {\only<3,5->{\color{ictpgreen}}\#_\text{edges}} &&\hspace{-1em}+ {\only<4,5->{\color{ictpblue}}\#_\text{faces}} \\ &\color{White}\only<2->{\color{Black}}= {\only<2,5->{\color{Red}}2904} &&\hspace{-1em}\color{White}\only<3->{\color{Black}}- {\only<3,5->{\color{ictpgreen}}8706} &&\hspace{-1em}\color{White}\only<4->{\color{Black}}+ {\only<4,5->{\color{ictpblue}}5804} \\ &\color{White}\only<5->{\color{Black}}=2 \end{align*} \[ \color{White}\only<6->{\color{Black}}\chi(\Omega_\text{football}) ={\only<6->{\color{Red}}60}-{\only<6->{\color{ictpgreen}}90}+{\only<6->{\color{ictpblue}}32}=2 \] \color{White}\only<7>{\color{Black}}Cow is homeomorphic to a sphere \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1,5>\includegraphics[width=\textwidth]{figs/cow.png} \onslide<2>\includegraphics[width=\textwidth]{figs/cow_vert.png} \onslide<3>\includegraphics[width=\textwidth]{figs/cow_edge.png} \onslide<4>\includegraphics[width=\textwidth]{figs/cow_face.png} \onslide<6->\hspace{2em}\includegraphics{figs/Football_Pallo_valmiina-cropped.jpg} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{The Euler characteristic \boldmath{$\chi$}} \framesubtitle{Characteristics of the characteristic} \begin{columns} \begin{column}{0.5\textwidth} For closed, connected 2-dimensional manifolds, related to genus $g$ by $\chi=2-2g$ \medskip General properties: \vspace{-0.5em} \[ \chi(\Omega)=0 \text{ for odd-dimensional $\Omega$} \] \vspace{-1.6em} \[ \chi(S^D)=2\text{ for even }D \] \[ \chi(\Omega_1\sqcup\Omega_2)=\chi(\Omega_1)+\chi(\Omega_2) \] \[ \chi(\Omega_1\times\Omega_2)=\chi(\Omega_1)\times\chi(\Omega_2) \] \smallskip Examples: \vspace{-0.5em} \[\chi(M\text{ even-$D$ spheres})=2M\] \vspace{-1.6em} \[\chi(S^1\times\text{anything})=0\] \end{column} \begin{column}{0.5\textwidth} \includegraphics[width=\textwidth]{figs/genus.png} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{The Euler characteristic \boldmath{$\chi$}} \framesubtitle{Computing the Euler characteristic} \begin{columns} \begin{column}{0.5\textwidth} Morse theory: gradient flow on an arbitrary ``height'' function $h$ makes a complex \begin{align*} \chi(\Omega) &= {\only<2,5>{\color{Red}}\#_\text{vertices}} - {\only<3,5>{\color{ictpgreen}}\#_\text{edges}} + {\only<4,5>{\color{ictpblue}}\#_\text{faces}} +\cdots \\ &= {\only<6>{\color{ictpblue}}\#_\text{index 0}} - {\only<6>{\color{ictpgreen}}\#_\text{index 1}} + {\only<6>{\color{Red}}\#_\text{index 2}} +\cdots \\ &=\sum_{i=0}^D(-1)^i\#_\text{index i} \end{align*} \[ \hspace{-1em}\operatorname{sgn}\big(\det\operatorname{Hess}(\pmb x)\big) = \operatorname{sgn}\left(\prod_{i=1}^D\lambda_i\right) =(-1)^{\text{index}} \] \[ \chi(\Omega) =\int_\Omega d\pmb x\,\delta\big(\nabla h(\pmb x)\big) \,\det\operatorname{Hess}h(\pmb x) \] \emph{Kac--Rice without the absolute value!} \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\textwidth]{figs/other_sphere.png} \onslide<2>\includegraphics[width=\textwidth]{figs/other_sphere_vert.png} \onslide<3>\includegraphics[width=\textwidth]{figs/other_sphere_edge.png} \onslide<4>\includegraphics[width=\textwidth]{figs/other_sphere_face.png} \onslide<5>\includegraphics[width=\textwidth]{figs/other_sphere_all.png} \onslide<6>\includegraphics[width=\textwidth]{figs/other_sphere_crit.png} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Computing the Euler characteristic} \begin{columns} \begin{column}{0.6\textwidth} Pick whatever height function $h:\Omega\to\mathbb R$ you like: $h(\pmb x)=\frac1N\pmb x_0\cdot\pmb x$ for arbitrary $\pmb x_0$. \[ \chi(\Omega) =\int_\Omega d\pmb x\,\delta\big(\nabla h(\pmb x)\big)\,\det\operatorname{Hess}h(\pmb x) \] \[ \Omega=\{\boldsymbol x\in S^{N-1}\subset\mathbb R^N\mid f_{\boldsymbol x}(\boldsymbol a^\mu)=y^\mu,1\leq\mu\leq M\} \] \bigskip Lagrange multipliers replace differential geometry: \[ L(\boldsymbol x,\boldsymbol \omega)=h(\boldsymbol x)+\omega^0(\|\boldsymbol x\|^2-N)+\sum_{\mu=1}^M\omega^\mu(f_{\boldsymbol x}(\boldsymbol a^\mu)-y^\mu) \] \end{column} \begin{column}{0.4\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\textwidth]{figs/function-1.png} \onslide<2>\includegraphics[width=\textwidth]{figs/function-2.png} \onslide<3>\includegraphics[width=\textwidth]{figs/function-3.png} \end{overprint} \end{column} \end{columns} \[ \chi(\Omega) =\int_{\mathbb R^{N+M+1}} d\boldsymbol x\,d\boldsymbol \omega\,\delta\big(\begin{bmatrix}\frac{\partial L}{\partial\boldsymbol x}&\frac{\partial L}{\partial\boldsymbol \omega}\end{bmatrix}\big) \,\det\begin{bmatrix}\frac{\partial^2L}{\partial\boldsymbol x^2}&\frac{\partial^2L}{\partial\boldsymbol x\partial\boldsymbol \omega}\\\frac{\partial^2L}{\partial\boldsymbol x\partial\boldsymbol \omega}&\frac{\partial^2L}{\partial\boldsymbol \omega^2}\end{bmatrix} \] \end{frame} \begin{frame} \frametitle{Computing the Euler characteristic} \begin{columns} \begin{column}{0.5\textwidth} $M$ data points, $N$ parameters, $\alpha=M/N$, $\boldsymbol J^\mu\in\mathbb R^{N^p}$, $\overline{J^2}=\frac{p!}{2N^p}$ \[ V_0=f_{\boldsymbol x}(\boldsymbol J^\mu) =\frac1{p!}\sum_{i_1=1}^N\cdots\sum_{i_p=1}^NJ ^\mu_{i_1,\ldots,i_p}x_{i_1}\cdots x_{i_p} \] Average Euler characteristic reduced to integral over $m=\frac1N\boldsymbol x\cdot\boldsymbol x_0$, \[ \overline{\chi(\Omega)} =\left(\frac N{2\pi}\right)^{\frac12} \int dm\,g(m)e^{N\mathcal S_\chi(m)} \] \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\textwidth]{figs/action_1.pdf} \onslide<2>\includegraphics[width=\textwidth]{figs/action_3.pdf} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{A simple model of nonlinear least squares} \framesubtitle{Results} \begin{columns} \begin{column}{0.5\textwidth} $M$ data points, $N$ parameters, $\alpha=M/N$, $\boldsymbol J^\mu\in\mathbb R^{N^p}$, $\overline{J^2}=\frac{p!}{2N^p}$ \[ V_0=f_{\boldsymbol x}(\boldsymbol J^\mu) =\frac1{p!}\sum_{i_1=1}^N\cdots\sum_{i_p=1}^NJ ^\mu_{i_1,\ldots,i_p}x_{i_1}\cdots x_{i_p} \] Simplest case: $p=1$, $\Omega$ is intersection of random hyperplanes with the sphere \medskip Results in $\chi(\Omega)=2$ or $\chi(\Omega)=0$ depending on whether solutions exist \medskip \hspace{2em}\includegraphics[width=0.33\textwidth]{figs/connected.pdf} \hfill \includegraphics[width=0.33\textwidth]{figs/gone.pdf}\hspace{2em} \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\textwidth]{figs/intersections_1.pdf} \onslide<2>\includegraphics[width=\textwidth]{figs/intersections_2.pdf} \onslide<3>\includegraphics[width=\textwidth]{figs/action_phase_1.pdf} \onslide<4>\includegraphics[width=\textwidth]{figs/intersections_3.pdf} \onslide<5>\includegraphics[width=\textwidth]{figs/intersections_4.pdf} \onslide<6>\includegraphics[width=\textwidth]{figs/action_phase_2.pdf} \onslide<7>\includegraphics[width=\textwidth]{figs/phases_1.pdf} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \begin{columns} \begin{column}{0.5\textwidth} For $p>1$, new phases possible \medskip \alert<2>{\textbf{\boldmath{$m^*=0$, $\mathcal S_\chi(m^*)$ complex, $\overline{\chi(\Omega)}\ll0$, local maximum exists}}} \medskip \alert<3>{\textbf{\boldmath{$m^*=0$, $\mathcal S_\chi(m^*)$ complex, $\overline{\chi(\Omega)}\ll0$, no local maximum}}} \medskip \alert<4>{\textbf{\boldmath{$m^*=0$, $\mathcal S_\chi(m^*)$ real, $\overline{\chi(\Omega)}\gg0$}}} \medskip \includegraphics[width=0.23\textwidth]{figs/middle.pdf} \includegraphics[width=0.23\textwidth]{figs/complex.pdf} \includegraphics[width=0.23\textwidth]{figs/shattered.pdf} \includegraphics[width=0.23\textwidth]{figs/gone.pdf} \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1-2>\includegraphics[width=\textwidth]{figs/action_phase_3.pdf} \onslide<3>\includegraphics[width=\textwidth]{figs/action_phase_4.pdf} \onslide<4>\includegraphics[width=\textwidth]{figs/action_phase_5.pdf} \onslide<5>\includegraphics[width=\textwidth]{figs/phases_2.pdf} \onslide<6>\includegraphics[width=\textwidth]{figs/phases_3.pdf} \onslide<7>\includegraphics[width=\textwidth]{figs/phases_4.pdf} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{A simple model of nonlinear least squares} \framesubtitle{Results} \begin{columns} \begin{column}{0.5\textwidth} $M$ data points, $N$ parameters, $\alpha=M/N$ \[ V_0=\hat f(J\mid \pmb a) =\sum_{i_1=1}^N\cdots\sum_{i_p=1}^NJ_{i_1,\ldots,i_p}a_{i_1}\cdots a_{i_p} \] For $p\geq2$, different phases with $|\chi(\Omega)|\gg1$ with varying sign \medskip \includegraphics[width=0.23\textwidth]{figs/middle.pdf} \includegraphics[width=0.23\textwidth]{figs/complex.pdf} \includegraphics[width=0.23\textwidth]{figs/shattered.pdf} \includegraphics[width=0.23\textwidth]{figs/gone.pdf} \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\centering\includegraphics[width=0.8\textwidth]{figs/middle.pdf}\\$\chi(\Omega)\ll0$ \onslide<2>\centering\includegraphics[width=0.8\textwidth]{figs/complex.pdf}\\$\chi(\Omega)\ll0$ \onslide<3>\centering\includegraphics[width=0.8\textwidth]{figs/shattered.pdf}\\$\chi(\Omega)\gg0$ \onslide<4>\includegraphics[width=\textwidth]{figs/phases_2.pdf} \onslide<5>\includegraphics[width=\textwidth]{figs/phases_3.pdf} \onslide<6>\includegraphics[width=\textwidth]{figs/phases_4.pdf} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Non manifolds: constraint satisfaction} \begin{columns} \begin{column}{0.5\textwidth} Continuous constraint satisfaction problems with $\boldsymbol x\in\Omega\subseteq\mathbb R^N$, with $\Omega$ $D$-dimensional \[ h^\mu(\boldsymbol x)\geq0 \qquad 1\leq\mu\leq M \] Spherical perceptron: $M$ patterns $\boldsymbol\xi^\mu\in\mathbb R^N$, \[ h^\mu(\boldsymbol x)=\boldsymbol\xi^\mu\cdot\boldsymbol x-\kappa \] \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\textwidth]{figs/nothing_zoom.pdf} \onslide<2>\includegraphics[width=\textwidth]{figs/fixed_size_zoom_points.pdf} \onslide<3>\includegraphics[width=\textwidth]{figs/max_size_zoom.pdf} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Wedged spheres} \begin{columns} \begin{column}{0.5\textwidth} Sphere of radius $r$ uniquely defined by $h^\mu(\boldsymbol x)=r$ for $D$ constraints, $h^\mu(\boldsymbol x)\geq r$ for other $M-D$ constraints \[ \begin{aligned} \#_r = \int_{\mathbb R^D} d\boldsymbol x \sum_{\substack{\sigma\subset[M]\\|\sigma|=D}} \bigg(\prod_{\mu\in[M]\backslash\sigma}\theta\big(h^\mu(\boldsymbol x)-r\big)\bigg) \\ \times\bigg(\prod_{\mu\in\sigma}\delta\big(h^\mu(\boldsymbol x)-r\big)\bigg) \\ \times\left| \det\begin{bmatrix} \frac\partial{\partial\boldsymbol x}h^{\sigma_1}(\boldsymbol x) & \cdots & \frac\partial{\partial\boldsymbol x}h^{\sigma_D}(\boldsymbol x) \end{bmatrix} \right| \end{aligned} \] With margin, $\#_r(\kappa)=\#_0(r+\kappa)$ \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\textwidth]{figs/nothing_zoom.pdf} \onslide<2>\includegraphics[width=\textwidth]{figs/fixed_size_zoom_r.pdf} \onslide<3>\includegraphics[width=\textwidth]{figs/fixed_size_zoom_0.pdf} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Inscribed spheres} \begin{columns} \begin{column}{0.5\textwidth} Sphere of maximal radius uniquely defined by $h^\mu(\boldsymbol x)=r$ for $D+1$ constraints, $h^\mu(\boldsymbol x)\geq r$ for other $M-D-1$ constraints \[ \begin{aligned} \#_\text{insc} = \int_0^\infty dr\int_{\mathbb R^D} d\boldsymbol x \sum_{\substack{\sigma\subset[M]\\|\sigma|=D+1}} \\ \bigg(\prod_{\mu\in[M]\backslash\sigma}\theta\big(h^\mu(\boldsymbol x)-r\big)\bigg) \bigg(\prod_{\mu\in\sigma}\delta\big(h^\mu(\boldsymbol x)-r\big)\bigg) \\ \times\left| \det\begin{bmatrix} \frac\partial{\partial\boldsymbol x}h^{\sigma_1}(\boldsymbol x) & \cdots & \frac\partial{\partial\boldsymbol x}h^{\sigma_{D+1}}(\boldsymbol x) \\ -1 & \cdots & -1 \end{bmatrix} \right| \end{aligned} \] \end{column} \begin{column}{0.5\textwidth} \begin{overprint} \onslide<1>\includegraphics[width=\textwidth]{figs/max_size_zoom.pdf} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Treating the determinant} \begin{columns} \begin{column}{0.9\textwidth} \[ |\det M|=\sqrt{\det MM^T} =\int\frac{d\boldsymbol s}{(2\pi)^{D/2}}\,d\bar{\boldsymbol\eta}\,d\boldsymbol\eta\, e^{-\frac12\boldsymbol s^TMM^T\boldsymbol s-\bar{\boldsymbol\eta}^TMM^T\boldsymbol\eta} \] \begin{align*} &\#_r = \int\frac{d\boldsymbol x\,d\boldsymbol s}{(2\pi)^{D/2}}d\bar{\boldsymbol\eta}\,d\boldsymbol\eta \sum_{\substack{\sigma\subset[M]\\|\sigma|=D}} \bigg(\prod_{\mu\in[M]\backslash\sigma}\theta\big(h^\mu(\boldsymbol x)-r\big)\bigg) \\ &\hspace{8em} \times \bigg( \prod_{\mu\in\sigma} \delta\big(h^\mu(\boldsymbol x)-r\big) e^{ -\frac12[\boldsymbol s\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)]^2 -[\bar{\boldsymbol\eta}\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)] [\boldsymbol\eta\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)] } \bigg) \end{align*} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Treating the sum over subsets} \begin{columns} \begin{column}{0.9\textwidth} \begin{align*} &\#_r = \int\frac{d\boldsymbol x\,d\boldsymbol s}{(2\pi)^{D/2}}d\bar{\boldsymbol\eta}\,d\boldsymbol\eta \\ &\times \sum_{\substack{\sigma\subset[M]\\|\sigma|=D}} \bigg(\prod_{\mu\in[M]\backslash\sigma}\theta\big(h^\mu(\boldsymbol x)-r\big)\bigg) \bigg( \prod_{\mu\in\sigma} \delta\big(h^\mu(\boldsymbol x)-r\big) e^{ -\frac12[\boldsymbol s\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)]^2 -[\bar{\boldsymbol\eta}\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)] [\boldsymbol\eta\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)] } \bigg) \end{align*} \begin{align*} &\#_r = \lim_{\omega\to\infty}\int\frac{d\boldsymbol x\,d\boldsymbol s}{(2\pi)^{D/2}}d\bar{\boldsymbol\eta}\,d\boldsymbol\eta \\ & \times\prod_{\mu=1}^M\bigg(\omega\theta\big(h^\mu(\boldsymbol x)-r\big) + \omega^{1-\frac MD}\delta\big(h^\mu(\boldsymbol x)-r\big) e^{ -\frac12[\boldsymbol s\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)]^2 -[\bar{\boldsymbol\eta}\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)] [\boldsymbol\eta\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)] } \bigg) \end{align*} \end{column} \end{columns} \end{frame} \begin{frame} \frametitle{Treating the sum over subsets} \begin{columns} \begin{column}{0.9\textwidth} Why does this work? Expand the product: \begin{align*} &\prod_{\mu=1}^M \bigg( \omega\theta\big(h^\mu(\boldsymbol x)-r\big) + \omega^{1-\frac MD}\delta\big(h^\mu(\boldsymbol x)-r\big) e^{ -\frac12[\boldsymbol s\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)]^2 -[\bar{\boldsymbol\eta}\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)] [\boldsymbol\eta\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)] } \bigg) \\ &=\sum_{d=0}^M\omega^{M(1-\frac dD)} \sum_{\substack{\sigma\subset[M]\\|\sigma|=d}} \bigg(\prod_{\mu\in[M]\backslash\sigma}\theta\big(h^\mu(\boldsymbol x)-r\big)\bigg) \\ & \hspace{8em}\times\bigg( \prod_{\mu\in\sigma} \delta\big(h^\mu(\boldsymbol x)-r\big) e^{ -\frac12[\boldsymbol s\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)]^2 -[\bar{\boldsymbol\eta}\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)] [\boldsymbol\eta\cdot\frac\partial{\partial\boldsymbol x}h^\mu(\boldsymbol x)] } \bigg) \end{align*} Our term is $d=D$, giving $\omega^0$. For the undesired terms: \begin{itemize} \item $d>D$: $\omega$ raised to a negative power, limit kills term \item $d