\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<D$: integral over $\boldsymbol s$, $\bar{\boldsymbol\eta}$, $\boldsymbol\eta$ gives determinant of matrix with rank less than dimension
      \end{itemize}
    \end{column}
  \end{columns}
\end{frame}

\end{document}
