main.knit

# Research Overview

## Siddharth Vishwanath

### .bolder[IBM Research]

#### 1st October, 2021

---
class: inverse, center, middle, animated slideInUp
count: false

# Outline

---
class: left, animated slideInLeft

### .dblue[Robust TDA]

.large[&nbsp;&nbsp;&nbsp;&nbsp; 2. Efficient and Robust Topological Inference]
   
### .dblue[Statistical Inference using TDA]

### .dblue[Differential Privacy under TDA Lens]
.large[&nbsp;&nbsp;&nbsp;&nbsp; 4. The Shape of Edge Differential Privacy]

### .dblue[Geometry in Multimodal Sampling and Non-convex Optimization]

<div style="display:none">
$$
\newcommand{\defeq}{\stackrel{\small\bullet}{=}}
\newcommand{\ra}{\rangle}
\newcommand{\la}{\langle}
\newcommand{\norm}[1]{\left\|#1\right\|}
\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\Abs}[1]{\Bigl\lvert#1\Bigr\rvert}
\newcommand{\pr}{{\mathbb P}}
\newcommand{\qr}{{\mathbb Q}}
\newcommand{\xv}{{\boldsymbol{x}}}
\newcommand{\av}{{\boldsymbol{a}}}
\newcommand{\bv}{{\boldsymbol{b}}}
\newcommand{\cv}{{\boldsymbol{c}}}
\newcommand{\dv}{{\boldsymbol{d}}}
\newcommand{\ev}{{\boldsymbol{e}}}
\newcommand{\fv}{{\boldsymbol{f}}}
\newcommand{\gv}{{\boldsymbol{g}}}
\newcommand{\hv}{{\boldsymbol{h}}}
\newcommand{\nv}{{\boldsymbol{n}}}
\newcommand{\sv}{{\boldsymbol{s}}}
\newcommand{\tv}{{\boldsymbol{t}}}
\newcommand{\uv}{{\boldsymbol{u}}}
\newcommand{\vv}{{\boldsymbol{v}}}
\newcommand{\wv}{{\boldsymbol{w}}}
\newcommand{\zerov}{{\mathbf{0}}}
\newcommand{\onev}{{\mathbf{0}}}
\newcommand{\phiv}{{\boldsymbol{\phi}}}
\newcommand{\cc}{{\check{C}}}
\newcommand{\xv}{{\boldsymbol{x}}}
\newcommand{\Xv}{{\boldsymbol{X}\!}}
\newcommand{\yv}{{\boldsymbol{y}}}
\newcommand{\Yv}{{\boldsymbol{Y}}}
\newcommand{\zv}{{\boldsymbol{z}}}
\newcommand{\Zv}{{\boldsymbol{Z}}}
\newcommand{\Iv}{{\boldsymbol{I}}}
\newcommand{\Jv}{{\boldsymbol{J}}}
\newcommand{\Cv}{{\boldsymbol{C}}}
\newcommand{\Ev}{{\boldsymbol{E}}}
\newcommand{\Fv}{{\boldsymbol{F}}}
\newcommand{\Gv}{{\boldsymbol{G}}}
\newcommand{\Hv}{{\boldsymbol{H}}}
\newcommand{\alphav}{{\boldsymbol{\alpha}}}
\newcommand{\epsilonv}{{\boldsymbol{\epsilon}}}
\newcommand{\betav}{{\boldsymbol{\beta}}}
\newcommand{\deltav}{{\boldsymbol{\delta}}}
\newcommand{\gammav}{{\boldsymbol{\gamma}}}
\newcommand{\etav}{{\boldsymbol{\eta}}}
\newcommand{\piv}{{\boldsymbol{\pi}}}
\newcommand{\thetav}{{\boldsymbol{\theta}}}
\newcommand{\tauv}{{\boldsymbol{\tau}}}
\newcommand{\muv}{{\boldsymbol{\mu}}}
\newcommand{\phiinv}{\Phi^{-1}}
\newcommand{\Fiinv}{F^{-1}}
\newcommand{\giinv}{g^{-1}}
\newcommand{\fhat}{\hat{f}}
\newcommand{\ghat}{\hat{g}}
\newcommand{\ftheta}{f_\theta}
\newcommand{\fthetav}{f_{\thetav}}
\newcommand{\gtheta}{g_\theta}
\newcommand{\gthetav}{g_{\thetav}}
\newcommand{\ztheta}{Z_\theta}
\newcommand{\xtheta}{\Xv_\theta}
\newcommand{\ytheta}{\Yv_\theta}
\newcommand{\p}{\partial}
\newcommand{\f}{\frac}
\newcommand{\cf}{\cfrac}
\newcommand{\e}{\epsilon}
\newcommand{\indep}{\perp\kern-5pt \perp}
\newcommand{\inner}[1]{\langle#1\rangle}
\newcommand{\pa}[1]{\left(#1\right)}
\newcommand{\pb}[1]{\left\{#1\right\}}
\newcommand{\pc}[1]{\left[#1\right]}
\newcommand{\pA}[1]{\Big(#1\Big)}
\newcommand{\pB}[1]{\Big\{#1\Big\}}
\newcommand{\pC}[1]{\Big[#1\Big]}
\newcommand{\ty}[1]{\texttt{#1}}
\newcommand{\borel}[1]{\mathscr{B}\pa{#1}}
\newcommand{\scr}{\mathcal}
\newcommand{\scrb}{\mathscr}
\newcommand{\argmin}{\mathop{\text{arg}\ \!\text{min}}}
\newcommand{\arginf}{\mathop{\text{arg}\ \!\text{inf}}}
\newcommand{\argmax}{\mathop{\text{arg}\ \!\text{max}}}
\newcommand{\argsup}{\mathop{\text{arg}\ \!\text{sup}}}
\newcommand{\bigo}[1]{\mathcal{O}_{p}\!\left(#1\right)}
\newcommand{\f}{\frac}
\newcommand{\e}{\epsilon}
\newcommand{\inv}{^{-1}}
\newcommand{\phiinv}{\Phi^{-1}}
\newcommand{\Fiinv}{F^{-1}}
\newcommand{\giinv}{g^{-1}}
\newcommand{\fhat}{\hat{f}}
\newcommand{\ghat}{\hat{g}}
\newcommand{\ftheta}{f_\theta}
\newcommand{\fthetav}{f_{\thetav}}
\newcommand{\gtheta}{g_\theta}
\newcommand{\gthetav}{g_{\thetav}}
\newcommand{\ztheta}{Z_\theta}
\newcommand{\xtheta}{\Xv_\theta}
\newcommand{\ytheta}{\Yv_\theta}
\newcommand{\absdet}[1]{\abs{\det\pa{#1}}}
\newcommand{\jac}[1]{\Jv_{#1}}
\newcommand{\absdetjx}[1]{\abs{\det\pa{\Jv_{#1}}}}
\newcommand{\absdetj}[1]{\norm{\Jv_{#1}}}
\newcommand{\sint}{sin(\theta)}
\newcommand{\cost}{cos(\theta)}
\newcommand{\sor}[1]{S\mathcal{O}(#1)}
\newcommand{\ort}[1]{\mathcal{O}(#1)}
\newcommand{\A}{{\mathcal A}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\E}{{\mathbb E}}
\newcommand{\F}{{\mathcal{F}}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\X}{{\scr{X}}}
\newcommand{\Y}{{\mathbb{Y}}}
\newcommand{\G}{{\mathcal{G}}}
\newcommand{\M}{{\mathcal{M}}}
\newcommand{\betaequivalent}{\beta\text{-equivalent}}
\newcommand{\betaequivalence}{\beta\text{-equivalence}}
\newcommand{\Mb}{{\boldsymbol{\mathsf{M}}}}
\newcommand{\Br}{{\mathbf{\mathsf{Bar}}}}
\newcommand{\dgm}{{\mathbf{\mathsf{Dgm}}}}
\newcommand{\Db}{{\mathbf{\mathsf{D}}}}
\newcommand{\Img}{{\mathbf{\mathsf{Img}}}}
\newcommand{\mmd}{{\mathbf{\mathsf{MMD}}}}
\newcommand{\Xn}{{\mathbb{X}_n}}
\newcommand{\Yn}{{\mathbb{Y}_n}}
\newcommand{\Xb}{{\mathbb{X}}}
\newcommand{\Yb}{{\mathbb{Y}}}
\newcommand{\s}{{{\sigma}}}
\newcommand{\fnsbar}{{\bar{f}^n_\s}}
\newcommand{\fns}{{f^n_\s}}
\newcommand{\fs}{{f_\s}}
\newcommand{\fsbar}{{\bar{f}_\s}}
\newcommand{\barfn}{{{f}^n_\sigma}}
\newcommand{\barfnm}{{{f}^{n+m}_\sigma}}
\newcommand{\barfo}{{{f}_\sigma}}
\newcommand{\fn}{{f^n_{\rho,\sigma}}}
\newcommand{\fnm}{{f^{n+m}_{\rho,\sigma}}}
\newcommand{\fo}{{f_{\rho,\sigma}}}
\newcommand{\K}{{{K_{\sigma}}}}
\newcommand{\barpn}{{\bar{p}^n_\sigma}}
\newcommand{\barpo}{{\bar{p}_\sigma}}
\newcommand{\pn}{{p^n_\sigma}}
\newcommand{\po}{{p_\sigma}}
\newcommand{\J}{{\mathcal{J}}}
\newcommand{\B}{{\mathcal{B}}}
\newcommand{\pt}{{\tilde{\mathbb{P}}}}
\newcommand{\Winf}{{W_{\infty}}}
\newcommand{\HH}{{{\scr{H}_{\sigma}}}}
\newcommand{\D}{{{\scr{D}_{\sigma}}}}
\newcommand{\Ts}{{T_{\sigma}}}
\newcommand{\Phis}{{\Phi_{\sigma}}}
\newcommand{\nus}{{\nu_{\sigma}}}
\newcommand{\Qs}{{\mathcal{Q}_{\sigma}}}
\newcommand{\ws}{{w_{\sigma}}}
\newcommand{\vs}{{v_{\sigma}}}
\newcommand{\ds}{{\delta_{\sigma}}}
\newcommand{\fp}{{f_{\pr}}}
\newcommand{\prs}{{\widetilde{\pr}_{\sigma}}}
\newcommand{\qrs}{{\widetilde{\qr}_{\sigma}}}
\newcommand{\Inner}[1]{\Bigl\langle#1\Bigr\rangle}
\newcommand{\innerh}[1]{\langle#1\rangle_{\HH}}
\newcommand{\Innerh}[1]{\Bigl\langle#1\Bigr\rangle_{\HH}}
\newcommand{\normh}[1]{\norm{#1}_{\HH}}
\newcommand{\norminf}[1]{\norm{#1}_{\infty}}
\newcommand{\gdelta}{{\G_{\delta}}}
\newcommand{\supgdelta}{{\sup\limits_{g\in\gdelta}\abs{\Delta_n(g)}}}
\newcommand{\id}{\textup{id}}
\newcommand{\supp}{\text{supp}}
\newcommand{\cech}{\v{C}ech}
\newcommand{\Zz}{{\scr{Z}}}
\newcommand{\psis}{\psi_\s}
\newcommand{\phigox}{\Phis(\xv)-g}
\newcommand{\phigoy}{\Phis(\yv)-g}
\newcommand{\fox}{{f^{\epsilon,{\xv}}_{\rho,\sigma}}}
\newcommand{\prx}{{\pr^{\epsilon}_{\xv}}}
\newcommand{\pro}{{\pr_0}}
\newcommand{\dotfo}{\dot{f}_{\!\!\rho,\s}}
\newcommand{\phifo}{{\Phis(\yv)-\fo}}
\newcommand{\phifox}{{\Phis(\xv)-\fo}}
\newcommand{\kinf}{{\norm{\K}_{\infty}}}
\newcommand{\half}{{{\f{1}{2}}}}
\newcommand{\Jx}{\J_{\epsilon,{\xv}}}
\newcommand{\dpy}{\text{differential privacy}}
\newcommand{\edpy}{$\epsilon$--\text{differential privacy}}
\newcommand{\eedpy}{$\epsilon$--edge \text{differential privacy}}
\newcommand{\dpe}{\text{differentially private}}
\newcommand{\edpe}{$\epsilon$--\text{differentially private}}
\newcommand{\eedpe}{$\epsilon$--edge \text{differentially private}}
\newcommand{\er}{Erdős-Rényi}
\newcommand{\krein}{Kreĭn}
% \newcommand{\grdpg}{\mathsf{gRDPG}}
% \newcommand{\rdpg}{\mathsf{RDPG}}
% \newcommand{\eflip}{{\textsf{edgeFlip}}}
\newcommand{\grdpg}{\text{gRDPG}}
\newcommand{\rdpg}{\text{RDPG}}
\newcommand{\eflip}{{\text{edgeFlip}}}
\newcommand{\I}{{\mathbb I}}
\renewcommand{\pa}[1]{\left(#1\right)}
\renewcommand{\pb}[1]{\left\{#1\right\}}
\renewcommand{\pc}[1]{\left[#1\right]}
$$
</div>

---

# Background
## (⚡️ Speed)

---
class: left
# .left[.orange[Persistent] Homology]

Given a collection of points `$\Xn = \pb{\xv_1, \xv_2, \dots, \xv_n} \subseteq \R^d$`, what is the shape of `$\Xn$`?

--
.center[
`$\Xn$` intrinsically has no shape
]

---
count:false
# .orange[Persistent] Homology

Given a collection of points `$\Xn = \pb{\xv_1, \xv_2, \dots, \xv_n} \subseteq \R^d$`, what is the shape of `$\Xn$`?
.center[
<img src="code/images/lem-r1.svg" width=550>
]

.center[
The shape of `$\Xn$` at resolution `$\e$` is encoded in `$\color{orange}{\bigcup\limits_{i=1}^n B(\xv_i,\e)}$`
]

---
count:false
# .orange[Persistent] Homology

Given a collection of points `$\Xn = \pb{\xv_1, \xv_2, \dots, \xv_n} \subseteq \R^d$`, what is the shape of `$\Xn$`?

---
class: center
count:false

The birth and death of the topological features is summarized in a .bolder[persistence diagram] `$\dgm\pa{\Xn}$`

---

# Equivalent Formulation using the Distance Function

Given `$\Xn \subset \R^d$` and `$\yv \in \R^d$`, the .bolder[distance function] to `$\Xn$` is given by `${d_{\Xn}}(\color{red}{\yv}) := \inf\limits_{\color{green}{\xv \in \Xn}}\norm{\xv-\yv}$`

The .bolder.orange[sublevel] set at resolution `$\e$` is given by `$d_{\Xn}\inv\Big([0,\e]\Big):= \pb{\yv \in \R^d: d_{\Xn}(\yv) \le \e }$`
--
`$=\bigcup\limits_{i=1}^{n}B(\xv_i,\e)$`

---

# Functional Persistence

For a .bolder.dblue[filter function] `$\phi_n$` constructed using `$\Xn$`, the shape is encoded in the superlevel set `$\phi_n\inv\pA{[\e,\infty)}$`

---
count: false
# Functional Persistence

For a .bolder.dblue[filter function] `$\phi_n$` constructed using `$\Xn$`, the shape is encoded in the superlevel set `$\phi_n\inv\pA{[\e,\infty)}$`

---
count: false
# Functional Persistence

For a .bolder.dblue[filter function] `$\phi_n$` constructed using `$\Xn$`, the shape is encoded in the superlevel set `$\phi_n\inv\pA{[\e,\infty)}$`

---
count: false
# Functional Persistence

For a .bolder.dblue[filter function] `$\phi_n$` constructed using `$\Xn$`, the shape is encoded in the superlevel set `$\phi_n\inv\pA{[\e,\infty)}$`

.center[
The resulting persistence diagram is given by `$\dgm\pa{\phi_n} = \dgm\pA{\text{Sup}\pa{\phi_n}}$`
]

---
class: center
count:true
# .left[Examples of Filter Functions ]

`$d_{\Xn}(\boldsymbol y)= \mathop{\text{inf}}\limits_{\boldsymbol \xv_i \in \mathbb X_n} || \boldsymbol{y -\xv_i} ||_2$`

---
class: center
count:false
# .left[Examples of Filter Functions ]

`$d^2_{m,n}(\boldsymbol x) = \frac{1}{k}\sum\limits_{\boldsymbol{x_i} \in \text{NN}_k(\boldsymbol{x})} || \boldsymbol x - \boldsymbol x_i ||_2^2, \hspace{1cm}$` where `$m>0$` and `$k = \lfloor mn \rfloor$`

---
class: center
count:false
# .left[Examples of Filter Functions ]

`$\fns(\yv) = \f{1}{n}\sum\limits_{i=1}^{n}\K(\yv,\xv_i), \hspace{1cm}$` where `$\sigma > 0$` and `$\K$` is a kernel

---

# Robust TDA
## .small[Robust Persistence Diagrams using Reproducing Kernels]
## .tiny.tiny.tiny[S.V., Fukumizu, Kuriki, Sriperumbudur. *Advances in Neural Information Processing Systems 33* (2020)]

---
count: false
# Stability `$\neq$` Robustness

.content-box-psu3[<body> .bolder[Theorem (Stability)]: Given two tame filter functions `$f$` and `$g$`, `$W_{\infty}\Big( \dgm(f), \dgm(g) \Big) \le ||f-g||_{\infty}$` </body>]

.pull-left[
<img src="code/images/signal.svg", height="350">
]
.pull-right[<img src="code/images/signal-dgm.svg", height="350">
]

---
count: false
# Stability `$\neq$` Robustness

.content-box-psu3[<body> .bolder[Theorem (Stability)]: Given two tame filter functions `$f$` and `$g$`, `$W_{\infty}\Big( \dgm(f), \dgm(g) \Big) \le ||f-g||_{\infty}$` </body>]

.pull-left[
<img src="code/images/signal1.svg", height="350">
]
.pull-right[<img src="code/images/signal1-dgm.svg", height="350">
]

---
count: false
# Stability `$\neq$` Robustness

.content-box-psu3[<body> .bolder[Theorem (Stability)]: Given two tame filter functions `$f$` and `$g$`, `$W_{\infty}\Big( \dgm(f), \dgm(g) \Big) \le ||f-g||_{\infty}$` </body>]

.pull-left[
<img src="code/images/X.svg", height="350">
]
.pull-right[<img src="code/images/X-dgm.svg", height="350">
]

---
count: false
# Stability `$\neq$` Robustness

.center[.content-box-orange[Can we construct robust persistence diagrams without compromising on statistical efficiency?]]

.pull-left[
<img src="code/images/X.svg", height="350">
]
.pull-right[<img src="code/images/X-dgm.svg", height="350">
]

---

# Robust Persistence Diagrams

.panelset.sideways[
.panel[.panel-name[Formulation]

* `$K_\sigma$` is a radial kernel and `$\mathcal{H}_\sigma$` is its reproducing kernel Hilbert space

* Given `$\mathbb X_n$` and a robust loss `$\rho: \mathbb{R}_+ \rightarrow \mathbb R_+$` the robust KDE is given by

`$f^n_{\rho,\sigma} \stackrel{\small\bullet}{=} \mathop{\text{arg inf}}\limits_{g \in \mathcal{H}_\sigma}\displaystyle\int\limits_{\mathbb R^d}\rho\Big( || g - K_\sigma(\cdot,\boldsymbol{y}) ||_{\mathcal{H}_\sigma} \Big) \ d\mathbb{P}_n(\boldsymbol{y})  = \sum\limits_{i=1}^n w_\sigma({X_i}) K_\sigma(\cdot,\boldsymbol{X_i})$`

* The .dblue.bolder.text-shadow[<body> weight function `$w_\sigma$` </body>] weighs-down extreme outliers

* `$\fn$` and `$w_\sigma$` .dorange[do not] have closed form solutions. 
 * But, they can be solved via iteratively reweighted least squares

.center[
.content-box-orange[<body> `$\dgm(f^n_{\rho,\sigma}) = \dgm\big( \text{Sup}(f^n_{\rho,\sigma}) \big)$` is the robust persistence diagram </body>]
]

]

.panel[.panel-name[Example]
<iframe src="https://rstudio.aws.science.psu.edu:3838/suv87/comps/kde_big/" width="500" height="500"></iframe>
]

* Vanilla persistence diagram `$\dgm\pa{\fns}$`

]

* Robust persistence diagram `$\dgm\pa{\fn}$`

]

---

# Sensitivity Analysis using Influence Functions

* Given a .bolder.dblue[statistical functional] `$T: \mathcal{P}\pa{\X} \rightarrow \pa{V, \norm{\cdot}_V}$`, the .bolder.dblue[influence function] associated with `$\xv \in \X$` is
.content-box-blue.center[
 <body> $\text{IF}(T; \mathbb P, \boldsymbol x) = \lim\limits_{\epsilon \rightarrow 0}\frac{1}{\epsilon}\Big( T\big(\big (1-\e)\pr + \e \delta_{\xv} \big) - T(\mathbb P) \Big) $</body>
]

--
* But the space of diagrams is not a normed space 🙁 
--
&nbsp;&nbsp;&nbsp; 👉🏽 &nbsp;&nbsp;&nbsp; Generalize via metric derivative 🙂
--

.content-box-blue.center[
 <body> $\Psi\Big( \phi_{\mathbb P}; \mathbb{P}, \boldsymbol{x} \Big) \stackrel{\small\bullet}{=} \lim\limits_{\epsilon \rightarrow 0}\frac{1}{\epsilon} W_{\infty}\Big( \dgm\big(\phi_{\mathbb{P}^{\epsilon}_{\boldsymbol x}}\big), \dgm\big( \phi_{\mathbb P} \big) \Big) $ </body>]

--
.theorem1[For a robust loss `$\rho$`, bandwidth `$\sigma > 0$`, and smoothing parameter `$m > 0$`:
1. **RKDE:** .center[<body>
`$\Psi\Big( f_{\rho,\sigma}; \mathbb{P}, \boldsymbol{x} \Big) \le \sigma^{-d/2} \color{#1058ad}{\boldsymbol{w_{\sigma}(\boldsymbol x)}} || K(\cdot,\boldsymbol{x}) - f_{\rho,\sigma} ||_{\mathcal{H}_\sigma}$`
</body>]

1. **KDE:** .center[<body>
`$\Psi\Big( f_{\sigma}; \mathbb{P}, \boldsymbol{x} \Big) \le \sigma^{-d/2} || K(\cdot,\boldsymbol{x}) - f_{\sigma} ||_{\mathcal{H}_\sigma}$`
</body>]

1. **DTM:** .center[<body>
`$\Psi\Big( d_{m}; \mathbb{P}, \boldsymbol{x} \Big) \le \frac{2}{\sqrt{m}} \sup \Big\{ \big\vert f(\boldsymbol x) - \int f(\boldsymbol y)d\mathbb{P}(\boldsymbol{y}) \big\vert : || \nabla f ||_{L_2(\mathbb P)} \le 1 \Big\}$`
</body>]
</body>]

---

# Highlights

.panelset.sideways[
.panel[.panel-name[Convergence Rates]

.bolder.text-shadow[Assumption:] For `$a_\sigma > 1$` and `$p \in (0,1)$`, the entropy numbers of `$K_\sigma$` satisfy `$e_n(\mathcal H_\sigma) \le a_\sigma n^{-{1}/{2p}}$`

.theorem2[
Given `$\mathbb X_n$` observed i.i.d. from `$\mathbb P$` with density `$f$`, a bandwidth `$\sigma > 0$`, and a convex loss `$\rho$` :
 
With probability greater than `$1- \alpha$`, and uniformly over `$\mathbb P$`
`\begin{align}
W_{\infty}\Big( \textbf{Dgm}\big(f^n_{\rho,\sigma}\big), \textbf{Dgm}\big( f_{\rho,\sigma} \big) \Big) \le 2C \sigma^{-d/2} \Bigg( \xi(n,p) + \sqrt{\frac{2\log(1/\alpha)}{n}} \Bigg)
\end{align}`
where
`\begin{align}
 \xi(n,p) = \begin{cases} \mathcal{O}(n^{-1/2}) & \text{ if } p \in (0,\frac{1}{2})\\
 \mathcal{O}(n^{-1/2} \log n) & \text{ if } p = \frac{1}{2}\\
 \mathcal{O}(n^{-1/4p}) & \text{ if } p \in (\frac{1}{2},1)
 \end{cases}
\end{align}`

]
]

.panel[.panel-name[Confidence Sets]
 .pull-left[
`$\Xn$`
<img src="code/images/points-extreme.svg", width="500">
]
.pull-right[
`$\dgm\pa{\fn}$`
<img src="code/images/dgm-extreme.svg", width="500">
]
]

* .orchid[<body> `$\Xn$` ( `$\large\bullet$` ) </body>] is sampled from .orchid[<body> `$\pr_{\text{signal}}$` </body>] and `$\Yb_m$` ( `$\large\circ$` ) from `$\pr_{\text{noise}}$`, with `$\f{m}{n} = \pi$` 
.pull-left[
<img src="images/expts/cloud.svg", width="320">
 
.center[
 `$\color{#db43d5}\Xn \cup \Yb_m$`
]
]
.pull-right[
<img src="images/expts/box4.svg", width="320">
 
.center.small[
`$\color{#3e9cfa}{\Winf\pa{\Db_{\rho,\s},D^\#}}$` vs `$\color{red}{\Winf\pa{\Db_\s,D^\#}}$`
]
]
.center[
`$\pi = 50\%$` and `$\boldsymbol{p-value} = 2.5 \times 10^{-75}$`
]
]

.panel[.panel-name[Clustering]
* `$25$` point-clouds are sampled from each of `$6$` objects:
* Classes: `cube, circle, sphere, torus, 3clust, 3clustIn3clust`

* Points are sampled with additive Gaussian noise (SD=0.1) and ambient Matérn cluster noise

* Spectral clustering is performed to benchmark against persistence images.
  
  .content-box-blue[Distance Matrix | Robust PD | Persistence Image
--- | --- | ----
Rand Index | `$94.44\%$` | `$79.78\%$`

]
]

* For `$\boldsymbol{N} \sim \text{Unif}\pb{1\dots,5}$` generate random circles `$\mathbb S_1 \dots \mathbb S_{\boldsymbol N} \subset [0,2]^2$`

* `$\Xn$` is sampled i.i.d. from `$\half\text{Unif}\pb{\mathbb S_1 \cup \dots \cup \mathbb S_{\boldsymbol N}} + \half \text{Unif}\pa{[0,2]^2}$`

* `$\Db_\s$` and `$\Db_{\rho,\s}$` are computed from `$\Xn$` using `$\fns$` and `$\fn$`

* SVM is trained on vectorizations `$\Img\pa{\Db_\s;h}$` and `$\Img\pa{\Db_{\rho,\s};h}$` for varying `$h$` to predict `$\boldsymbol N$`

`$\Xn$` when `$\boldsymbol{N}=5$` | Bandwidth `$\s_1$` | Bandwidth `$\s_2$`
--- | --- | ----
<img src="images/expts/n23.svg", width="290"> | <img src="images/expts/lines-k5.svg", width="290"> | <img src="images/expts/lines-k7.svg", width="290"> 
]

* For each image `$\mathcal{I}$` from the `mpeg7` dataset, the boundary `$\partial\mathcal{I}$` is extracted

* `$\Xn$` is sampled from `$0.85\times\text{Unif}\pa{\p\mathcal I} + 0.15 \times \text{Unif}(\mathcal I)$`

* We compute `$\dgm\pa{\fn}$`, `$\dgm\pa{\fns}$` and `$\dgm\pa{d_{n,m}}$` using `$\Xn$`

* SVM is trained on persistence images `$\Img\pa{\dgm;h}$` for varying `$h$` so as to classify the images `$\mathcal I$`

`$\Xn$` when `$\mathcal I = \texttt{bone}$` | `$3$`-class SVM | `$5$`-class SVM
--- | --- | ----
<img src="images/expts/bone.svg", width="290"> | <img src="images/expts/3-class-lines.svg", width="290"> | <img src="images/expts/5-class-lines.svg", width="290"> 
]

]

---

# Robust TDA
## .small[Efficient and Outlier Robust Topological Inference]
## .tiny.tiny.tiny[<body> S.V., Fukumizu, Kuriki, Sriperumbudur. (In Preparation) </body>]

---

# Shortcomings of Previous Work

* In practice, `$\dgm\pa{\phi}$` is computed using .bolder[cubical homology] on a grid `$G(r)$` of resolution `$r$`

* The topological accuracy becomes sensitive to the choice of grid resolution `$r$`

* Computing `$\dgm\pa{\phi}$` is prohibitively expensive in high-dimensions. Space complexity is `$\mathcal O(r^{-d})$`

---
count: false
# Efficient and Robust Persistence Diagrams

### .orange.bolder[Solution \#1: KDE Filtration]
* Compute the sublevel/superlevel filtration using the .bolder[nerve of the cover] for `$\Xn$` directly

`\begin{align}
\pB{\yv \in G(r) : \phi_n(\yv) \ge \epsilon } \rightarrow \mathcal{K}\pA{\pb{\Xv_i \in \Xn : \phi_n(\Xv_i) \ge \epsilon}, \delta}
\end{align}`

---
count: false
# Efficient and Robust Persistence Diagrams

### .orange.bolder[Solution \#2: Weighted Rips Filtrations]

* Construct a robust persistence diagram using a robust Median-of-Means (MoM) filtration

* The kernel `$\K$` induces a Hilbertian metric on the base space `$\R^d$`, i.e.

`\begin{align}
  d_{\HH}(\xv, \yv) = \normh{\mu_{\delta_{\xv}} - \mu_{\pr_{q}}} = \normh{\K(\cdot, \xv) - \K(\cdot, \yv)}
\end{align}`

* Suppose `$\Xn$` is partitioned into `$\pb{S_q}_{q=1}^Q$` disjoint blocks, and `$\pr_q$` is the empirical measure for `$S_q$`
* The .dblue.bolder.text-shadow[MoM kernel distance] as the filter function, given by
.content-box-blue[
`\begin{align}
  D^n_{Q,\s}(\xv) = \text{median}\pB{\normh{\mu_{\delta_\xv} - \mu_{\pr_q}}}_{q=1}^{Q}
\end{align}`
]

.center[
.content-box-orange[<body> `$\dgm\pa{\text{Rips}\pa{\Xn; \ D^n_{Q,\s}, \ d_{\HH}}}$` is the Median of Means `$D^n_{Q,\s}-$`weighted Filtration </body>]
]

---
count: false
# Efficient and Robust Persistence Diagrams
.pull-left[
.h-center[
![](images/animation/filt.gif)
]
]
.pull-right[
.h-center[
![](images/animation/rkde-filt.gif)
]
]

---

# Advantages

.panelset.sideways[

.orange[<body> `$\dgm\pa{\text{Sup}\pa{\fn}}$` </body>]
* Computational: `$\mathcal{O}(n\ell)$`
* Memory: `$\mathcal{O}(r^{-d})$`

.orange[<body> `$\dgm\pa{\text{Sub}\pa{D^n_{Q,\s}}}$` </body>]
* Computational: `$\mathcal{O}(n)$`
* Memory: `$\mathcal{O}(r^{-d})$`

.orange[<body> `$\dgm\pa{\text{Rips}\pa{\Xn; D^n_{Q,\s}, d_{\HH}}}$` </body>]
* Computational: `$\mathcal{O}(n)$`
* Memory: `$\mathcal{O}(n^3)$`

]

* `$\mathfrak{D}=\dgm\pa{\text{Rips}\pa{\Xn; D^n_{Q,\s}, d_{\HH}}}$`
* `$\mathfrak{D}_1 = \dgm\pa{\text{Rips}\pa{\Xn; D^n_{Q,\s}, \norm{\cdot}_2}}, \mathfrak{D}_2 = \dgm\pa{\text{Sub}\pa{D^n_{Q,\s}}}$`

.dblue.text-shadow[<body> `$d_{\HH} vs. \norm{\cdot}_2$` </body>]

* Every point `$(b,d) \in \mathfrak{D}$` is matched with `$(b',d') \in \mathfrak{D}_1$` such that

.content-box-blue[
`\begin{align}
 \f{\sigma}{\sqrt{2\mu}} (b,d) \le (b', d') \le \f{\sigma}{\sqrt{\mu}} (b,d)
\end{align}`
]
.dblue.text-shadow[<body> Sublevel Filtration vs. Weighted Rips Filtration </body>]

.content-box-blue[
`\begin{align}
  \Winf\pa{ \log\cdot \mathfrak{D}, \log\cdot \mathfrak{D}_2 } \le \pa{1 - \f{1}{p}}\log{2}
\end{align}`
]

]

* `$\Xn$` contains `$m < n/2$` outliers and `$n-m$` samples iid from `$\pr$` 
* `$\mathfrak{D}_{n, Q}=\dgm\pa{\text{Rips}\pa{\Xn; D^n_{Q,\s}, d_{\HH}}}$`
* `$\mathfrak{D}_{\pr} = \dgm\pa{\text{Sub}\pa{\R^d; D_{\pr}}}$`

* If `$2m < Q < n$` where `$m = \mathcal{O}(n^{\e})$` then

.content-box-blue[
`\begin{align}
\E \pc{\Winf\pa{ \log\cdot \mathfrak{D}_{n, Q}, \  \log\cdot \mathfrak{D}_{\pr} }} = \mathcal{O}_{\pr}\pa{n^{(\e-1)/2}}
\end{align}`
]

]

.panel[.panel-name[Refined Influence]
* `$\Xn$` contains `$n$` samples iid from `$\pr$`
* `$m<n$` outliers are added at a point `$\xv_0$` 
* MoM KDist: `$\mathfrak{D}_{n+m, Q}=\dgm\pa{\text{Rips}\pa{\Xn; D^{n+m}_{Q,\s}, d_{\HH}}}$`
* KDist: `$\mathfrak{D}_{n+m}=\dgm\pa{\text{Rips}\pa{\Xn; D^{n+m}_{\s}, d_{\HH}}}$`

* <body> If `$m = \omega(\sqrt{n})$`then with probability greater than $1 - \delta$ </body>

`\begin{align}
b^{n}_Q(\pb{\xv_0}) - b^{n+m}_Q(\pb{\xv_0}) < b^{n}(\pb{\xv_0}) - b^{n+m}(\pb{\xv_0})
\end{align}`
]
* where `$b^{n}_Q(\pb{\xv_0})$` and `$b^{n+m}_Q(\pb{\xv_0})$` are the birth times for the topological feature from the outlier `$\xv_0$` in `$\mathfrak{D}_{n, Q}$` and `$\mathfrak{D}_{n+m, Q}$`.

* Similarly `$b^{n}(\pb{\xv_0})$` and `$b^{n+m}(\pb{\xv_0})$` are the birth times in `$\mathfrak{D}_{n}$` and `$\mathfrak{D}_{n+m}$`
]

]

---

# Statistical Inference using TDA

## .small[Statistical Invariance of Betti Numbers]
## .tiny.tiny.tiny[<body> S.V., Fukumizu, Kuriki, Sriperumbudur. arXiv:2001.00220 (2020) </body>]

---
count: false
layout: true
class: split-five with-border border-black

.column[.content[
.split-five[
.row.bg-main1[.content.center.vmiddle[
# Space
]]
.row.bg-main2[.content.center[
## Circle
]]
.row.bg-main3[.content.center[
## Sphere
]]
.row.bg-main4[.content.center[
## Torus
]]
.row.bg-main5[.content.center[
## `$3d_{z^2}$`
]]
]]]
.column[.content[
.split-five[
.row.bg-main1[.content.center.vmiddle[
# Shape
]]
.row.bg-main2[.content.center[
<img src="images/regimes/circle.svg" width="100",height="100">
]]
.row.bg-main3[.content.center[
<img src="images/regimes/sphere.svg" width="100",height="100">
]]
.row.bg-main4[.content.center[
<img src="images/regimes/torus.svg" width="100",height="100">
]]
.row.bg-main5[.content.center[
<img src="images/regimes/orbital.png" width="100",height="100">
]]
]]]
.column[.content[
.split-five[
.row.bg-main1[.content.center.vmiddle[
# `$\beta_0$` 
]]
.row.bg-main2[.content.center[
## 1
]]
.row.bg-main3[.content.center[
## 1
]]
.row.bg-main4[.content.center[
## 1
]]
.row.bg-main5[.content.center[
## 1
]]
]]]
.column[.content[
.split-five[
.row.bg-main1[.content.center.vmiddle[
# `$\beta_1$`
]]
.row.bg-main2[.content.center[
## 1
]]
.row.bg-main3[.content.center[
## 0
]]
.row.bg-main4[.content.center[
## 2
]]
.row.bg-main5[.content.center[
## 1
]]
]]]
.column[.content[
.split-five[
.row.bg-main1[.content.center.vmiddle[
# `$\beta_2$` 
]]
.row.bg-main2[.content.center[
## 0
]]
.row.bg-main3[.content.center[
## 1
]]
.row.bg-main4[.content.center[
## 1
]]
.row.bg-main5[.content.center[
## 3
]]
]]]

---
count: false
class: fade-row2 fade-row3 fade-row4 fade-row5 gray-row2 gray-row3 gray-row4 gray-row5

---
count: false
class: fade-row3 fade-row4 fade-row5 gray-row3 gray-row4 gray-row5

---
count: false
class: fade-row2 fade-row4 fade-row5 gray-row2 gray-row4 gray-row5

---
count: false
class: fade-row2 fade-row3 fade-row5 gray-row2 gray-row3 gray-row5

---
count: false
class: fade-row2 fade-row3 fade-row4 gray-row2 gray-row3 gray-row4

---
layout: false
# Random Topology

* What are the properties of these **.dblue[random]** topological summaries?
`\begin{align}
\text{(LLN)} & & \lim\limits_{n\rightarrow \infty}\frac{1}{n}\beta_k\left( \mathcal{K}(\mathbb{X}_n,r) \right) = \color{#db43d5}{\gamma_k(\mathbb{P})} \ \ \text{a.s.} \hspace{2cm}\\ \\
\text{(CLT)} & & \lim\limits_{n\rightarrow \infty}\frac{\beta_k\left( \mathcal{K}(\mathbb{X}_n,r) \right) - \mathbb{E}(\beta_k\left( \mathcal{K}(\mathbb{X}_n,r) \right))}{\sqrt{n}}  \sim \color{#db43d5}{\mathcal{N}(0,\sigma^2)}
\end{align}`

---
layout: true
class: left,split-three

# Random Topology

* For `$\mathbb{X}_n$` observed iid from `$\mathbb{P}$`, a simplicial complex, `$\mathcal{K}(\mathbb{X}_n,r)$`, is a random-variable measurable w.r.t. `$\mathbb{P}^{\otimes n}$` 
 * The Betti numbers, `$\beta_k \left( \mathcal{K}(\mathbb{X}_n,r) \right) : \mathcal{X}^n \rightarrow \mathbb{N}$`, are topological summaries 
* What are the properties of these **.dblue[random]** topological summaries?
 * .orchid[<body> The asymptotic behaviour of `$\mathcal{K}(\mathbb{X}_n,r_n)$` depends on `$r_n = r(n)$` </body>]

.column[.content[
 
.center[
Dense
<img src="images/regimes/dense.gif" width="250",height="250">
`$nr_n^d \rightarrow \infty$`
]
]]

.column[.content[
 
.center[
Sparse
<img src="images/regimes/sparse.gif" width="250",height="250">
`$nr_n^d \rightarrow 0$`
]
]]

.column[.content[
 
.center[
Thermodynamic
<img src="images/regimes/thermodynamic.gif" width="250",height="250">
`$nr_n^d \rightarrow t \in (0,\infty)$`
]
]]

---

---
class: show-100
count: false

---

---
class: show-111
count: false

---
layout: false
count: false

# Statistical Invariance of Betti Numbers

* Consider a family of distributions `$\mathcal{P} = \{\mathbb{P}_\theta : \theta \in \Theta \}$` and `$\mathbb{X}^\theta_n = \{\mathbf{X}^\theta_1,\mathbf{X}^\theta_2,\dots,\mathbf{X}^\theta_n\} \sim \mathbb{P}_\theta$` for `$\theta \in \Theta$`

.content-box-blue[
`\begin{align}
\mathbf{S}(\mathbb{P}_{\theta}^{\otimes n})\!:= \mathbf{S}(\mathbb{X}^\theta_n)\!= \frac{1}{n} \Big( \beta_0\big( \mathcal{K}(\mathbb{X}^\theta_n,r_n) \big), \beta_1\big( \mathcal{K}(\mathbb{X}^\theta_n,r_n) \big), \dots , \beta_d\big( \mathcal{K}(\mathbb{X}^\theta_n,r_n) \big) \Big)
\end{align}`
]

As `$n \rightarrow \infty$` and `$nr_n^d \rightarrow t$`, the **.dblue[thermodynamic limit]** is the statistical functional 
`\begin{align}
\mathbf{S}(\mathbb{P}_\theta; t) = \lim_{n \rightarrow\infty}\mathbf{S}(\mathbb{P}_{\theta}^{\otimes n})
\end{align}`

* **.dblue.bolder.text-shadow[Statistical invariance.]** 
.center[<body> `$\bbox[20px, border: 2px solid orange]{ \text{For } \theta_1,\theta_2 \in \Theta, \text{ can we have that } \lim\limits_{n\rightarrow \infty}\mathbf{S}(\mathbb{P}_{\theta_1}^{\otimes n}) {=} \lim\limits_{n\rightarrow \infty}\mathbf{S}(\mathbb{P}_{\theta_2}^{\otimes n}) \text{ ? } }$`</body>]

.content-box-blue[
**.bolder.text-shadow[Definition.]** `$\mathcal{P} = \{\mathbb{P}_\theta : \theta \in \Theta \}$` is said to admit .dorange.bolder[<body> `$\beta$`-equivalence </body>] if `$\mathbf S(\mathbb{P}_\theta; t)$` doesn't depend on `$\theta \in \Theta$`
]

---
count: true

# Statistical Invariance of Betti Numbers

1. .bolder[<body> Can we characterize .dblue[necessary and sufficient] conditions for invariance à la `$\beta$`-equivalence? </body>]
--
 
 * Yes. When `$\mathcal{P}$` has some algebraic structure, i.e., 
 .center[<body>
 `$\mathcal{P}$` is generated by a parametrized group `$\G = \pb{g_\theta: \theta \in \Theta}$`
 </body>]
 `$\mathcal{P}$` admits `$\beta$`-equivalence .bolder.text-shadow[iff] the PDFs satisfy a Jacobian constraint w.r.t. the `$\G$`-maximal invariant
--
 
1. .bolder[<body> If we relax the algerbraic constraint, can we characterize .dblue[ sufficient] conditions for `$\beta$`-equivalence? </body>]
--
 
 * Yes. When `$\X$` admits a smooth fiber bundle structure, i.e., 
 .center[<body>
 `$\mathfrak{X} = \mathcal{Y} \rightarrow \X \stackrel{\pi}{\hookrightarrow} \scr{Z}$`, with base manifold `$\scr{Z}$` and canonical fiber space `$\mathcal{Y}$`
 </body>]
 We can transport mass along the fibers `$\mathcal{Y}_{\zv}$` using the local-trivializations such that it preserves the excess mass function. This, in turn, guarantees `$\beta$`-equivalence.
--
 
1. .bolder[<body> Given `$\mathcal P = \{\mathbb{P}_\theta : \theta \in \Theta \}$`, is there a simple way to .dblue[verify] if `$\mathcal P$` admits `$\beta$`-equivalence? </body>]
--
 
 * Yes. If `$\mathcal P$` satisfies standard *stochastic regularity assumptions*, it suffices to check the following orthogonality condition for the score function

`\begin{align}
\Inner{p_{\theta}^k, \f{\partial}{\partial \theta}\log p_\theta}_{L^2(\X)} = 0, \ \ \ \forall k \in \N_0
\end{align}`

---

# Differential Privacy under TDA Lens

## .small[The Shape of Edge Differential Privacy]
## .tiny.tiny.tiny[<body> S.V., Jonathan Hehir. Theory and Practice of Differential Privacy (2021) </body>]

---
# Introduction

.panelset.sideways[

* Given `$\pr$` on `$\R^d$` and `$p+q=d$` such that
  1. For all `$\Xv, \Yv \sim \pr$` such that `$\Xv \perp \Yv$`
   $$
    \big\langle\Xv, \I_{p,q}\Yv\big\rangle_2 \in [0,1] \ \ \text{a.s.}
   $$

* Then `$G\sim g\rdpg(\pr)$` if, for all `${\pb{\Xv_1,\Xv_2 \dots \Xv_n}\sim\pr}$`
    
`\begin{align}
\text{edge}(\Xv_i,\Xv_j) \Big\vert \Xv_1 \dots \Xv_n \sim \text{Bernoulli}\pa{\big\langle\Xv_i, \I_{p,q}\Xv_j\big\rangle_2}
\end{align}`

]

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="./figures/venn.png" height="450">

]

* Let `$\G^n = \pb{(V,E): \abs{V} = n}$` be the class of graphs with `$n$` vertices

.content-box-blue[<body> .bold[(Edge Differential Privacy).]
$\scrb{M}: \G^n \rightarrow \G^n$ satisfies $\e-$edge DP if for all graphs $G_1\!\stackrel{e}{\sim}{}\!G_2$ differing in a single edge, i.e. ${E_1 \Delta E_2\!\!=\!\pb{e}}$

\[\pr\pa{\scrb{M}(G_1) \in S} \le e^\e\  \pr\pa{\scrb{M}(G_2) \in S}  \ \ \forall S \subseteq \G^n$ \]

</body>]

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="./figures/edge-dp.png" width="400",height="400">

]

---
class: left,split-three
# Motivation

* If `$G \sim g\rdpg(\pr)$`, then the spectral embedding of `$G$` recovers the topological information underlying `$\pr$`

--
.center[
 
 
.content-box-orange[<body> Can we release a differentially-private `$\mathcal{M}_{\e}(G)$` without destroying the downstream topological inference? </body>]
]

---

# Highlights

.panelset.sideways[

.panel[.panel-name[EdgeFlip]
Given:
* A graph `$G$`
* A privacy budget `$\e$` and
* `$\pi(\e) := \pa{1+e^\e}^{-1} \in (0,1)$`

.content-box-orange[
`\begin{align}
  \A_\e\pa{\text{e}(i, j)} \big\vert \text{e}(i, j) = \begin{cases} \text{e}(i, j) & \text{w.p.  } 1-\pi(\e)\\ \\
  1-\text{e}(i, j) & \text{w.p.  } \pi(\e)
  \end{cases}
\end{align}`
]

]

]

* `$\Xn$` is sampled from a `$3$`-class Stochastic Block Model 
* `$\A_\e(G)$` is the edgeFlip mechanism
* `$\mathcal{B}_\e(G)$` is the LaplaceFlip - another differentially private mechanism

Non-private Embedding | Private Embedding | Spectral Clustering
--- | --- | ----
<img src="figures/dgms/embedding-sbm.png", width="250"> | <img src="figures/dgms/embedding-sbm-private.png" width="250"></iframe> | <img src="figures/dgms/sbm-bottleneck.png", width="250">

* log-bottleneck distance between `$\A_\e(G)$` and `$G$` vs `$\mathcal{B}_\e(G)$` and `$G$`
]

.panel[.panel-name[Guarantees]
For `$\e>0$` and `$G\!\sim g\rdpg(\pr)$`,  where `$\supp(\pr) = \M \subset \R^d$`

1. .green[(Closure)] `$\A_\e(G)\!\sim\!g\rdpg(\pr_\e)$` with `${\supp(\pr_\e)\!=\!\M_\e\!\subset\!\R^{d+1}}$` s.t. `$\M_\e = \xi(\M)$` and `$\pr_\e = \xi_{\sharp}\pr$` is the pushforward of `$\pr$` via
`\begin{align}
\xi(x) = \sqrt{1-2\pi(\e)}x \oplus \sqrt{\pi(e)}
\end{align}`

2. .green[(Preservation)] `$W^{SI}_{\infty}\pa{\log\cdot\dgm(\M), \log\cdot\dgm(\M_\e)} = 0$`

3. .green[(Privacy Limit)] When `$\e=0$` then `$g\rdpg(\pr_\e) = \text{Erdös-Rényi}\pa{\half}$`

4. .green[(Convergence)] As `$n \rightarrow \infty$` and `$\e \rightarrow 0$`
`\begin{align}
W^{SI}_{\infty}\pa{\log\cdot\dgm\pa{\A_\e(G_n)}, \log\cdot\dgm(G_n)} = \mathcal{O}_{\pr}\pa{ \sqrt{\f{e^\e + 1}{e^\e - 1}}\pa{ \f{\log n}{n}}^{1/b} }
\end{align}`

]

#### .orange[ToMATo Clustering]

* Topology aware spectral clustering algorithms are more suited for inference

#### .orange[Privacy budget vs. Accuracy]
* For a network with `$n$` vertices, consistent inference is possible only when

`\begin{align}
    \e(n) = \omega\pa{\log\pa{ 1 + \pa{\f{\log n}{n}}^{2/b} } }
\end{align}`

]

---

# Geometry in Multimodal Sampling

## .small[Repelling-Attracting Hamiltonian Monte Carlo]
## .tiny.tiny.tiny[<body> S.V., Hyungsuk Tak. (In Preparation) </body>]

---

# Hamiltonian Monte Carlo

.orange[**Objective:**] Generate samples `$\pb{q_1, q_2, \cdots q_n}$` from a distribution `$q \sim \pi(q) \propto \exp(-U(q))$`

.green[**Hamiltonain Monte Carlo:**]
1. Augment state space with auxiliary variables `$p \sim N(\boldsymbol{0}, M)$`
   
2. Joint distribution `$(q,p) \sim \exp(-H(q,p))$` where `$H(q,p)$` is given by
`\begin{align}
H(q,p) = U(q) + \f{1}{2} p^{\top}M^{-1}p
\end{align}`

3. Treat `$H(q,p)$` as the Hamiltonian of a system and generate trajectories using Hamiltonian flows
`\begin{align}
(q_t, p_t) = \Phi_t(q_0, p_0)
\end{align}`

4. Accept/reject state `$(q_t, p_t)$` with MH probability `$1 \wedge \exp\pa{H(q_0, p_0) - H(q_t, p_t)}$`

.content-box-orange.center[

Markov chain mixes well only when U(q) is strongly convex. Terrible for multimodal distributions

]

---

# Repelling-Attracting Hamiltonian Monte Carlo

1. Choose a hypothetical friction parameter `$\gamma \in [0, \infty)$`, and integration time `$T$`
   
2. Let `$\Omega = \begin{bmatrix}\boldsymbol{0} & I\\ -I & \boldsymbol{0}\end{bmatrix}$` and `$\Gamma = \begin{bmatrix} \boldsymbol{0} & \boldsymbol{0} \\ \boldsymbol{0} & \gamma \end{bmatrix}$`
   
3. For time `$t \in [0, T/2]$` generate .dblue[conformal Hamiltonian dynamics] using .red[negative friction]
`\begin{align}
\f{\partial}{\partial t} (q_t, p_t) = \Omega \nabla H(q_t, p_t) + \Gamma (q_t, p_t)
\end{align}`

3. For time `$t \in [T/2, T]$` generate .dblue[conformal Hamiltonian dynamics] using .green[positive friction]
`\begin{align}
\f{\partial}{\partial t} (q_t, p_t) = \Omega \nabla H(q_t, p_t) - \Gamma (q_t, p_t)
\end{align}`

4. Accept/reject state `$(q_T, p_T)$` with MH probability `$1 \wedge \exp\pa{H(q_0, p_0) - H(q_T, p_T)}$`

---
count: false
# Repelling-Attracting Hamiltonian Monte Carlo

---
count: false
# Repelling-Attracting Hamiltonian Monte Carlo

---

# Highlights

.panelset.sideways[

* Let `$\Psi_T : \R^{2d} \rightarrow \R^{2d}$` be the integral operator taking `$(q_0, p_0) \mapsto (q_T, p_T)$`
* `$R(q,p) = (q, -p)$` is the momentum-flip operator

#### .orange[Involution]
`\begin{align}
R \circ \Psi_T \circ R \circ \Psi_T = \text{id}
\end{align}`

#### .orange[Energy conservation]
`\begin{align}
\int_{0}^T \f{\partial}{\partial t}H(q_t, p_t) = 0
\end{align}`

#### .orange[Volume preservation]
* Using conformal symplectic geometry `$\omega_T(q_T, p_T) = \omega_0(q_0, p_0)$`
* Fokker-Planck evolution from `$[0, T/2]$` and Feynman-Kač for `$[T/2, T]$` have the same solution

]

---

# Thank you for listening!