diff options
author | Jaron Kent-Dobias <jaron@kent-dobias.com> | 2025-09-05 15:19:29 +0200 |
---|---|---|
committer | Jaron Kent-Dobias <jaron@kent-dobias.com> | 2025-09-05 15:19:29 +0200 |
commit | 7cf3469d7bf2717b5c45346222391bd4ee50ce56 (patch) | |
tree | f2d769eb2b54d29663685c25f65f664ef0b1a5de | |
parent | c927abe4379b796ec67cf9cc225833a256076737 (diff) | |
download | zif-7cf3469d7bf2717b5c45346222391bd4ee50ce56.tar.gz zif-7cf3469d7bf2717b5c45346222391bd4ee50ce56.tar.bz2 zif-7cf3469d7bf2717b5c45346222391bd4ee50ce56.zip |
Many changes
-rw-r--r-- | basin.xcf | bin | 0 -> 130284 bytes | |||
-rw-r--r-- | figs/annealed_compare.pdf | bin | 0 -> 17695 bytes | |||
-rw-r--r-- | figs/basin_1.png | bin | 0 -> 69429 bytes | |||
-rw-r--r-- | figs/basin_2.png | bin | 0 -> 87437 bytes | |||
-rw-r--r-- | figs/curvature_demo_1.pdf | bin | 0 -> 137410 bytes | |||
-rw-r--r-- | figs/curvature_demo_2.pdf | bin | 0 -> 118199 bytes | |||
-rw-r--r-- | figs/curvature_demo_3.pdf | bin | 0 -> 246756 bytes | |||
-rw-r--r-- | figs/margin_rainbow.pdf | bin | 0 -> 20841 bytes | |||
-rw-r--r-- | figs/margin_rainbow_points-2.pdf | bin | 0 -> 605530 bytes | |||
-rw-r--r-- | figs/margin_rainbow_points.pdf | bin | 0 -> 603270 bytes | |||
-rw-r--r-- | figs/phase_diagram_detail_1.pdf | bin | 0 -> 48252 bytes | |||
-rw-r--r-- | figs/phase_diagram_detail_2.pdf | bin | 0 -> 55667 bytes | |||
-rw-r--r-- | figs/phase_diagram_inscribed.pdf | bin | 0 -> 32365 bytes | |||
-rw-r--r-- | figs/phase_diagram_rs.pdf | bin | 0 -> 40260 bytes | |||
-rw-r--r-- | zif.bib | 6 | ||||
-rw-r--r-- | zif.tex | 441 |
16 files changed, 331 insertions, 116 deletions
diff --git a/basin.xcf b/basin.xcf Binary files differnew file mode 100644 index 0000000..14df19d --- /dev/null +++ b/basin.xcf diff --git a/figs/annealed_compare.pdf b/figs/annealed_compare.pdf Binary files differnew file mode 100644 index 0000000..5ab46fb --- /dev/null +++ b/figs/annealed_compare.pdf diff --git a/figs/basin_1.png b/figs/basin_1.png Binary files differnew file mode 100644 index 0000000..fe73e15 --- /dev/null +++ b/figs/basin_1.png diff --git a/figs/basin_2.png b/figs/basin_2.png Binary files differnew file mode 100644 index 0000000..c517ba9 --- /dev/null +++ b/figs/basin_2.png diff --git a/figs/curvature_demo_1.pdf b/figs/curvature_demo_1.pdf Binary files differnew file mode 100644 index 0000000..e4277d2 --- /dev/null +++ b/figs/curvature_demo_1.pdf diff --git a/figs/curvature_demo_2.pdf b/figs/curvature_demo_2.pdf Binary files differnew file mode 100644 index 0000000..d4a09ce --- /dev/null +++ b/figs/curvature_demo_2.pdf diff --git a/figs/curvature_demo_3.pdf b/figs/curvature_demo_3.pdf Binary files differnew file mode 100644 index 0000000..6911fad --- /dev/null +++ b/figs/curvature_demo_3.pdf diff --git a/figs/margin_rainbow.pdf b/figs/margin_rainbow.pdf Binary files differnew file mode 100644 index 0000000..818c170 --- /dev/null +++ b/figs/margin_rainbow.pdf diff --git a/figs/margin_rainbow_points-2.pdf b/figs/margin_rainbow_points-2.pdf Binary files differnew file mode 100644 index 0000000..1a2cd2b --- /dev/null +++ b/figs/margin_rainbow_points-2.pdf diff --git a/figs/margin_rainbow_points.pdf b/figs/margin_rainbow_points.pdf Binary files differnew file mode 100644 index 0000000..e497a24 --- /dev/null +++ b/figs/margin_rainbow_points.pdf diff --git a/figs/phase_diagram_detail_1.pdf b/figs/phase_diagram_detail_1.pdf Binary files differnew file mode 100644 index 0000000..ae70869 --- /dev/null +++ b/figs/phase_diagram_detail_1.pdf diff --git a/figs/phase_diagram_detail_2.pdf b/figs/phase_diagram_detail_2.pdf Binary files differnew file mode 100644 index 0000000..4d97489 --- /dev/null +++ b/figs/phase_diagram_detail_2.pdf diff --git a/figs/phase_diagram_inscribed.pdf b/figs/phase_diagram_inscribed.pdf Binary files differnew file mode 100644 index 0000000..0f7cdac --- /dev/null +++ b/figs/phase_diagram_inscribed.pdf diff --git a/figs/phase_diagram_rs.pdf b/figs/phase_diagram_rs.pdf Binary files differnew file mode 100644 index 0000000..e6ddcd0 --- /dev/null +++ b/figs/phase_diagram_rs.pdf @@ -42,7 +42,7 @@ } @unpublished{Kent-Dobias_2024_Algorithm-independent, - author = {Kent-Dobias, Jaron}, + author = {JK-D}, title = {Algorithm-independent bounds on complex optimization through the statistics of marginal optima}, year = {2024}, month = {July}, @@ -54,7 +54,7 @@ } @article{Kent-Dobias_2024_Conditioning, - author = {Kent-Dobias, Jaron}, + author = {JK-D}, title = {Conditioning the complexity of random landscapes on marginal optima}, journal = {Physical Review E}, publisher = {American Physical Society (APS)}, @@ -69,7 +69,7 @@ } @article{Kent-Dobias_2025_On, - author = {Kent-Dobias, Jaron}, + author = {JK-D}, title = {On the topology of solutions to random continuous constraint satisfaction problems}, journal = {SciPost Physics}, publisher = {Stichting SciPost}, @@ -1,4 +1,4 @@ -\documentclass[aspectratio=169,dvipsnames]{beamer} +\documentclass[fleqn,aspectratio=169,dvipsnames]{beamer} \setbeamerfont{title}{family=\bf} \setbeamerfont{frametitle}{family=\bf} @@ -126,11 +126,11 @@ \bigskip - High-dimensional landscapes differ from cartoons in important ways + \alert<2-3>{High-dimensional landscapes differ from cartoons in important ways} \bigskip - Generic rugged landscapes covered mostly by basins attached to marginal optima + \alert<4-6>{Generic rugged landscapes covered mostly by basins attached to marginal optima} \bigskip @@ -138,17 +138,19 @@ \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} + \onslide<1>\begin{minipage}[c][0.3\height][c]{\textwidth}\includegraphics[width=\textwidth]{figs/complex_landscapes.png}\centering\\\tiny C Cammarota\end{minipage} + \onslide<2>\begin{minipage}[c][0.3\height][c]{\textwidth}\includegraphics[width=\textwidth]{figs/fake_landscape.png}\\\tiny S Martiniani, YouTube\end{minipage} + \onslide<3>\begin{minipage}[c][0.3\height][c]{\textwidth}\includegraphics[width=\textwidth]{figs/real_landscape.png}\smallskip\\\tiny\fullcite{Suryadevara_2024_The}\end{minipage} + \onslide<4>\begin{minipage}[c][0.3\height][c]{\textwidth}\includegraphics[width=\textwidth]{figs/basin_1.png}\end{minipage} + \onslide<5>\begin{minipage}[c][0.3\height][c]{\textwidth}\includegraphics[width=\textwidth]{figs/basin_2.png}\end{minipage} + \onslide<6>\begin{minipage}[c][0.3\height][c]{\textwidth}\includegraphics[width=\textwidth]{figs/eigenvalue_convergence.pdf}\smallskip\\\tiny\fullcite{Kent-Dobias_2024_Algorithm-independent}\end{minipage} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} - \frametitle{How to count: Kac--Rice} + \frametitle{Typical complexity} Number of stationary points with $\nabla H(\boldsymbol x)=0$ given by integral over Kac--Rice measure @@ -171,10 +173,16 @@ \end{frame} \begin{frame} - \frametitle{Conditioning on the type of minimum: the spherical models} + \frametitle{Conditioning on the type of point: 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 + In spherical spin glasses with + \[ + H(\boldsymbol x)=\sum_pa_pH_p(\boldsymbol x) + \qquad + H_p(\boldsymbol x)=\frac1{p!}\sum_{i_1\cdots i_p}J_{i_1\cdots i_p}x_{i_1}\cdots x_{i_p} + \] + 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) \] @@ -200,8 +208,7 @@ \end{frame} \begin{frame} - \frametitle{Less simple mean-field models} - \framesubtitle{The mixed spherical spin glasses} + \frametitle{Out of equilibrium dynamics and complexity: spherical models} \begin{columns} \begin{column}{0.41\textwidth} @@ -372,8 +379,8 @@ { \small \begin{align*} - \hspace{0em}&\delta(\lambda_\text{min}(A)) \\ - \hspace{0em}&=\lim_{\beta\to\infty}\int + \hspace{-3em}&\delta(\lambda_\text{min}(A)) \\ + \hspace{-3em}&=\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) @@ -464,9 +471,9 @@ \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} + \onslide<1>\begin{minipage}[c][0.3\height][c]{\textwidth}\includegraphics[width=\textwidth]{figs/neural_landscape_1.png}\smallskip\\\tiny\fullcite{Liu_2022_Loss}\end{minipage} + \onslide<2>\begin{minipage}[c][0.3\height][c]{\textwidth}\includegraphics[width=\textwidth]{figs/neural_landscape_2.png}\smallskip\\\tiny\fullcite{Liu_2022_Loss}\end{minipage} + \onslide<3>\begin{minipage}[c][0.3\height][c]{\textwidth}\includegraphics[width=\textwidth]{figs/draxler_2018.png}\smallskip\\\tiny\fullcite{Draxler_2018_Essentially}\end{minipage} \end{overprint} \end{column} \end{columns} @@ -600,8 +607,7 @@ \end{frame} \begin{frame} - \frametitle{The Euler characteristic \boldmath{$\chi$}} - \framesubtitle{Computing the Euler characteristic} + \frametitle{Computing the Euler characteristic} \begin{columns} \begin{column}{0.5\textwidth} Morse theory: gradient flow on an arbitrary ``height'' function $h$ makes a complex @@ -664,8 +670,6 @@ \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) @@ -679,6 +683,7 @@ \end{overprint} \end{column} \end{columns} + \vspace{-1em} \[ \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) @@ -687,13 +692,13 @@ \end{frame} \begin{frame} - \frametitle{Computing the Euler characteristic} + \frametitle{Computing the Euler characteristic: example} \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}$ + $M$ data points, $N$ parameters, $\alpha=M/N$, $y^\mu=V_0$, $\boldsymbol a^\mu$ spherical $p$-spin coefficients, \[ - 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} + f_{\boldsymbol x}(\boldsymbol a^\mu) + =H^{(\mu)}_p(\boldsymbol x) \] Average Euler characteristic reduced to integral over $m=\frac1N\boldsymbol x\cdot\boldsymbol x_0$, \[ @@ -701,6 +706,10 @@ =\left(\frac N{2\pi}\right)^{\frac12} \int dm\,g(m)e^{N\mathcal S_\chi(m)} \] + + \smallskip\tiny + + \fullcite{Kent-Dobias_2025_On} \end{column} \begin{column}{0.5\textwidth} \begin{overprint} @@ -712,26 +721,25 @@ \end{frame} \begin{frame} - \frametitle{A simple model of nonlinear least squares} - \framesubtitle{Results} + \frametitle{Computing the Euler characteristic: example} \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}$ + $M$ data points, $N$ parameters, $\alpha=M/N$, $y^\mu=V_0$, $\boldsymbol a^\mu$ spherical $p$-spin coefficients, \[ - 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} + f_{\boldsymbol x}(\boldsymbol a^\mu) + =H^{(\mu)}_p(\boldsymbol x) \] 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 + Results in $\overline{\chi(\Omega)}=0$ or $\overline{\chi(\Omega)}=2$ depending on whether solutions exist \medskip - \hspace{2em}\includegraphics[width=0.33\textwidth]{figs/connected.pdf} + \hspace{2em}\includegraphics[width=0.33\textwidth]{figs/gone.pdf} \hfill - \includegraphics[width=0.33\textwidth]{figs/gone.pdf}\hspace{2em} + \includegraphics[width=0.33\textwidth]{figs/connected.pdf}\hspace{2em} \end{column} \begin{column}{0.5\textwidth} \begin{overprint} @@ -748,8 +756,14 @@ \end{frame} \begin{frame} + \frametitle{Computing the Euler characteristic: example} \begin{columns} \begin{column}{0.5\textwidth} + $M$ data points, $N$ parameters, $\alpha=M/N$, $y^\mu=V_0$, $\boldsymbol a^\mu$ spherical $p$-spin coefficients, + \[ + f_{\boldsymbol x}(\boldsymbol a^\mu) + =H^{(\mu)}_p(\boldsymbol x) + \] For $p>1$, new phases possible \medskip @@ -785,34 +799,39 @@ \end{frame} \begin{frame} - \frametitle{A simple model of nonlinear least squares} - \framesubtitle{Results} + \frametitle{Computing the Euler characteristic: example} + \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} - \] + \begin{column}{1.1\textwidth} + \hspace{1em}Phases for inhomogeneous models: $1-\lambda$ parts linear ($p=1$) plus $\lambda$ quadratic ($p=2$) + + \medskip - For $p\geq2$, different phases with $|\chi(\Omega)|\gg1$ with varying sign + \includegraphics[width=0.21\columnwidth]{figs/phases_12_0.pdf} + \nolinebreak\hspace{-2.5em} + \includegraphics[width=0.21\columnwidth]{figs/phases_12_1.pdf} + \nolinebreak\hspace{-2.5em} + \includegraphics[width=0.21\columnwidth]{figs/phases_12_2.pdf} + \nolinebreak\hspace{-2.5em} + \includegraphics[width=0.21\columnwidth]{figs/phases_12_3.pdf} + \nolinebreak\hspace{-2.5em} + \includegraphics[width=0.21\columnwidth]{figs/phases_12_4.pdf} + \nolinebreak\hspace{-2.5em} + \includegraphics[width=0.21\columnwidth]{figs/phases_12_5.pdf} \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} + \hspace{5em} + \includegraphics[width=0.13\textwidth]{figs/connected.pdf} + \hfill + \includegraphics[width=0.13\textwidth]{figs/middle.pdf} + \hfill + \includegraphics[width=0.13\textwidth]{figs/complex.pdf} + \hfill + \includegraphics[width=0.13\textwidth]{figs/shattered.pdf} + \hfill + \includegraphics[width=0.13\textwidth]{figs/gone.pdf} + \hspace{5em} \end{column} \end{columns} \end{frame} @@ -825,50 +844,43 @@ \[ 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} + \onslide<2>\includegraphics[width=\textwidth]{figs/max_size_zoom.pdf} \end{overprint} \end{column} \end{columns} \end{frame} \begin{frame} - \frametitle{Wedged spheres} + \frametitle{Non manifolds: 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)$ + $h^\mu(\boldsymbol x)\geq r$ for the other $M-D$ constraints + \begin{align*} + \hspace{-2em}\#_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{align*} + \alert<3>{With margin, $\#_r(\kappa)=\#_0(r+\kappa)$} \end{column} \begin{column}{0.5\textwidth} \begin{overprint} @@ -881,35 +893,33 @@ \end{frame} \begin{frame} - \frametitle{Inscribed spheres} + \frametitle{Non manifolds: 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} - \] + \begin{align*} + \hspace{-2em}&\#_\text{insc} + = + \int_0^\infty dr\int_{\mathbb R^D} d\boldsymbol x + \sum_{\substack{\sigma\subset[M]\\|\sigma|=D+1}} + \\ + \hspace{-2em}&\times\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) + \\ + \hspace{-2em}&\hspace{4em}\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{align*} \end{column} \begin{column}{0.5\textwidth} \begin{overprint} @@ -920,7 +930,7 @@ \end{frame} \begin{frame} - \frametitle{Treating the determinant} + \frametitle{Practical considerations: treating the determinant} \begin{columns} \begin{column}{0.9\textwidth} \[ @@ -952,7 +962,7 @@ \end{frame} \begin{frame} - \frametitle{Treating the sum over subsets} + \frametitle{Practical considerations: treating the sum over subsets} \begin{columns} \begin{column}{0.9\textwidth} \begin{align*} @@ -993,7 +1003,7 @@ \end{columns} \end{frame} \begin{frame} - \frametitle{Treating the sum over subsets} + \frametitle{Practical considerations: treating the sum over subsets} \begin{columns} \begin{column}{0.9\textwidth} Why does this work? Expand the product: @@ -1034,4 +1044,209 @@ \end{columns} \end{frame} +\begin{frame} + \frametitle{Practical considerations: treating the sum over subsets} + \begin{columns} + \begin{column}{0.9\textwidth} + \includegraphics[width=\textwidth]{figs/annealed_compare.pdf} + \end{column} + \end{columns} +\end{frame} + +\begin{frame} + \frametitle{Application to the spherical perceptron} + \begin{columns} + \begin{column}{0.6\textwidth} + $M$ data points, $N$ parameters, $\alpha=M/N$ + \[ + h^\mu(\boldsymbol x)=\boldsymbol\xi^\mu\cdot\boldsymbol x-\kappa + \] + $\boldsymbol\xi^\mu$ normally distributed + + \bigskip + + \alert<2>{$\kappa < 0$ : spherical obstacles have positive curvature} + + \medskip + + \alert<3>{$\kappa = 0$ : spherical obstacles have zero curvature} + + \medskip + + \alert<4>{$\kappa > 0$ : spherical obstacles have negative curvature} + + \bigskip + + $N\to\infty$ gives asymptotically zero curvature for all $\kappa$ + \end{column} + \begin{column}{0.27\textwidth} + \begin{overprint} + \onslide<1-2>\includegraphics[width=\textwidth]{figs/curvature_demo_1.pdf} + \onslide<3>\includegraphics[width=\textwidth]{figs/curvature_demo_2.pdf} + \onslide<4>\includegraphics[width=\textwidth]{figs/curvature_demo_3.pdf} + \end{overprint} + \end{column} + \end{columns} +\end{frame} + +\begin{frame} + \frametitle{Application to the spherical perceptron} + \begin{columns} + \begin{column}{0.95\textwidth} + Typical statistics of wedged spheres given by + \[ + \frac1N\overline{\log\#_0} + =\lim_{n\to0}\frac\partial{\partial n}\operatorname{extr}_{Q\alert<2>{,\rho}}\mathcal S_0(Q\alert<2>{,\rho}) + \] + for effective action + \[ + \hspace{-2em} + \mathcal S_0(Q\alert<2>{,\rho})= + \frac12\log\det Q\alert<2>{-\frac n2\log\frac{\rho^2}{2\pi}}+\alpha\log\bigg( + e^{\frac12\sum_{ab} + Q_{ab}\frac{\partial^2}{\partial y_a\partial y_b} + } + \prod_{a=1}^n + \big[ + \theta(y_a) + \alert<2>{+ + \rho\delta(y_a)} + \big] + \bigg|_{y_a=-\kappa} + \bigg) + \] + depending on + \[ + Q_{ab}=\frac1N\boldsymbol x_a\cdot\boldsymbol x_b + \hspace{3em} + \rho + =\frac1{\sqrt N}\lim_{\omega\to\infty}\omega^{-\alpha}\sqrt{\boldsymbol s_a^T\boldsymbol s_a} + =\frac1{\sqrt N}\lim_{\omega\to\infty}\omega^{-\alpha}\sqrt{\boldsymbol\eta^T_a\bar{\boldsymbol\eta}_a} + \] + \end{column} + \end{columns} +\end{frame} + +\begin{frame} + \frametitle{Application to the spherical perceptron} + \begin{columns} + \begin{column}{0.7\textwidth} + \includegraphics[width=\textwidth]{figs/phase_diagram_rs.pdf} + \end{column} + \begin{column}{0.3\textwidth} + \includegraphics[width=\textwidth]{figs/fixed_size_zoom_points.pdf} + \end{column} + \end{columns} +\end{frame} + +\begin{frame} + \frametitle{Application to the spherical perceptron} + \begin{columns} + \begin{column}{0.7\textwidth} + \begin{overprint} + \onslide<1>\includegraphics[width=\textwidth]{figs/phase_diagram_inscribed.pdf} + \onslide<2>\includegraphics[width=\textwidth]{figs/phase_diagram_detail_1.pdf} + \onslide<3>\includegraphics[width=\textwidth]{figs/phase_diagram_detail_2.pdf} + \end{overprint} + \end{column} + \begin{column}{0.3\textwidth} + \vspace{-5.5em} + + \[\hspace{-2em}\overline{\log\#_\text{insc}}=\max_{r\geq0}\overline{\log\#_r(\kappa)}\] + + \includegraphics[width=\textwidth]{figs/max_size_zoom.pdf} + \end{column} + \end{columns} +\end{frame} + +\begin{frame} + \frametitle{Application to the spherical perceptron} + \begin{columns} + \begin{column}{0.5\textwidth} + Why does the structure of the distribution of wedged points differ from that of all solutions? + + \medskip + + `Equilibrium' calculations averages over solutions at all larger margin with diverse, inequivalent geometries + + \medskip + + \alert<2>{Sphere-counting isolates properties of the solution set at each specific margin} + + \medskip + + \alert<3>{Relationship between $\#_r$, $\#_\text{insc}$, and solution topology} + \end{column} + \begin{column}{0.5\textwidth} + \begin{overprint} + \onslide<1>\includegraphics[width=\textwidth]{figs/margin_rainbow.pdf} + \onslide<2>\includegraphics[width=\textwidth]{figs/margin_rainbow_points.pdf} + \onslide<3>\includegraphics[width=\textwidth]{figs/margin_rainbow_points-2.pdf} + \end{overprint} + \end{column} + \end{columns} +\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} + + Conditioning stationary point complexity on marginal optima + + \bigskip + + \centering + \includegraphics[height=10pc]{figs/msg_marg_spectra.pdf} + + \smallskip\raggedright\tiny + + \fullcite{Kent-Dobias_2024_Conditioning} + \end{column} + \begin{column}{0.66\textwidth} + \textbf{Really flat parts} + + \vspace{-0.75em} + + \rule{\columnwidth}{1pt} + + \medskip + + \begin{minipage}{0.49\columnwidth} + \raggedright + Topology of solution manifolds via the average Euler characteristic + + \bigskip + + \centering + \includegraphics[height=10pc]{figs/function_2.png} + + \smallskip\raggedright\tiny + + \fullcite{Kent-Dobias_2025_On} + \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} + + \smallskip\raggedright\tiny + + Work in progress, expect something on the arXiv in the coming weeks!\\ + \vspace{10pt} + \end{minipage} + \end{column} + \end{columns} +\end{frame} + \end{document} |