Riemannopt@HSE === https://hackmd.io/@SomeoneS/manopt-slides It's a two-parts talk about optimization on manifolds and hyperbolic embeddings in deep learning. - The preliminary talk, read by [@SomeoneS](https://github.com/SomeoneSerge/), takes place on ~~March, 6~~ **March, 13** and covers the basics. - What are manifolds? Why Riemannian optimization? - What's it mean to make a "step in a direction" on a manifold? - How to differentiate functions between manifolds? - What's tricky about higher-order derivatives, and what do "acceleration" and "parallel" mean? - How to measure distances? - How to represent manifolds with numerical arrays? Embedded manifolds - How to get by without closed-form expressions? Retractions - How to speed up? Adaptive methods on product-manifolds and discussion. - Second talk, given by [@ferrine96](twitter.com/ferrine96/), is devoted to applications in deep learning, and in particular to graph embeddings. Date is ~~March, 13~~, **March, 20**. - Embedding graphs in hyperbolic spaces - Mixed curvature and [$\kappa$-stereographic model](https://andbloch.github.io/K-Stereographic-Model/) - [Hyperbolic neural networks](https://arxiv.org/abs/1805.09112) - Batch-Normalization on manifolds - Generalizing convolutional layers - And more Notes and slides: - [Notes](https://hackmd.io/@newkozlukov/manopt-notes) and [slides](https://hackmd.io/@newkozlukov/manopt-slides) for the first talk. The notes are a work-in-progress, many sections are still incomplete (some lack visualizations, some lack accompanying text, some both). We'll be updating the script as we approach the D-day. - Notes and slides for the second talk: coming soon References: - Gravity and Light workshop: https://gravity-and-light.herokuapp.com/tutorials - "Geometrical Anatomy of Theoretical Physics" by Frederic Schuller on [YouTube](https://youtu.be/V49i_LM8B0E?list=PLPH7f_7ZlzxTi6kS4vCmv4ZKm9u8g5yic) - Lee's series - Introduction to Topological Manifolds: https://archive.org/details/springer_10.1007-978-0-387-22727-6/mode/2up - Introduction to Smooth Manifolds: http://webmath2.unito.it/paginepersonali/sergio.console/lee.pdf - Riemannian Manifolds: https://www.maths.ed.ac.uk/~v1ranick/papers/leeriemm.pdf - - Absil's optimization on Matrix Manifolds: - Book online: https://press.princeton.edu/absil - Book: http://www.eeci-institute.eu/GSC2011/Photos-EECI/EECI-GSC-2011-M5/book_AMS.pdf - Slides, Feb, 2011: http://www.eeci-institute.eu/GSC2011/Photos-EECI/EECI-GSC-2011-M5/slides_lectures.pdf - Slides, Nov, 2014: http://gdr-mia.math.cnrs.fr/events/optimgeo-14/program/slides/absil.pdf Additional: - http://www.cnbc.cmu.edu/cns/papers/edelman98.pdf - https://arxiv.org/abs/1907.00949 - https://arxiv.org/abs/1607.02833 Starting point -- RAdam --- Let us first set the goals for to-day. Somewhat unconventionally, we jump off with the algorithm from <a href="https://openreview.net/forum?id=r1eiqi09K7&noteId=HygEnIClNE"> "Riemannian Adaptive Optimization Methods"</a> by Becigneul and Ganea. It might look scary at first, but what we're now going to do is iterate, decrypting it bit by bit. <!--<img src="https://i.imgur.com/pjKeUTZ.png" alt="RAMSGRAD" style="width: 60%" /> Let's take a closer look and see what terms we'd need to learn first: -->  Manifolds --- An $n$-dimensional manifold $M$ is a topological space $(M, \theta)$ that - is "nice": - Hausdorff (points have disjoint neighbourhoods) - second-countable (has countable basis for topology $\theta$) - at every point $p\in M$ has neighbourhood $U\subset M$ in which it looks like Euclidean space: there is a homeomorphism $x:U \to x(U)\subset \mathbb{R}^n$. - $x$ is called a (local) "chart" at $p$; it provides "coordinates" on that piece of manifold - "homeromorphism" means: continuous, invertible, with continuous inverse Roughly speaking, it's a "locally-Euclidean space". For instance, $\mathbb{R}^n$ itself is a manifold, with (global) chart being identity function. An additional piece of structure we're going to need (in addition to that of topology and local-Eucliddean-ness), is that of a **smooth manifold**. Consider two charts $(U, x)$, $(V, y)$ that share some part of their domains: $U\cap V \neq \varnothing.$ Both charts being invertible functions, we can construct a "**change of coordinates**", or "**transition map**" from $x$ to $y$ as $y\circ x^{-1}$. We say that $x$ and $y$ are **smoothly compatible**, if either $U\cap V = \varnothing$ or transition map is a **diffeomorphism** (in Euclidean sense): $$y\circ x^{-1}: x(U\cap V)\subset\mathbb{R}^n \to y(U\cap V)\subset\mathbb{R}^n.$$ Now, to endow $M$ with a **smooth structure**, means to provide a **maximal atlas** $A$ on $M$ -- a collection of *smoothly-compatible* charts, whose domains cover entire $M$, and such that this collection cannot be extended with a new chart in a smoothly-compatible way. <img src="https://i.imgur.com/F0NBjOs.jpg" style="width: 60%; margin: 1em; border-radius: 1em;"/> Now, we've done some hard work, we probably already want to see some benefits? What *smooth structure* allows us to define, is: what does it mean for a function to be a **smooth function between manifolds**? Given two **smooth manifolds** $(M, \theta_M, A_M)$ and $(N, \theta_N, A_N)$, we say that a function $F: M\to N$ is **smooth** (resp. $C^k$) if $$y\circ F\circ x^{-1}: x(U)\subset\mathbb{R}^m \to y(V)\subset\mathbb{R}^n$$ is smooth (resp. $C^k$) for every $(U, x)\in A_M$, $(V, y) \in A_N$. <img src="https://i.imgur.com/8BHgHRv.jpg" class="img-responsive" style="width: 60%; margin: 1em; border-radius: 1em;"/> ## Submanifolds, product manifolds, bundles, fibers, sections _On one hand, I want to introduce bundles&c after tangent spaces, in the context of vector fields&c; but on the other, it seems meaningful to introduce submanifolds&c at very beginning so that we have examples early on; this section will be probably split and moved later; this section follows Frederic Schuller's lecture_ _I also need bundles to try and introduce curvature learning on stereographic model spaces_ One way to construct manifolds, and the one that we're going to use the most, is from other manifolds. Given a topological $n$-manifold $(M, \theta)$, we call $(N, \left.\theta\right|_N)$, $N\subset M$, a **submanifold** of $M$ if $(N, \left.\theta\right|_N)$ is itself a manifold. Given $m$-manifold $M$ and $n$-manifold $N$, their **product manifold** is the manifold with underlying set the cartesian product and endowed with product topology: $(M{\times}N, \left.\theta\right._{M{\times}N})$. - $n$-torus $T^n$ is product $S^1{\times}\cdots{\times}S^1$. A **bundle** of topological manifolds is a triple $(E, \pi, M)$ of total space $E$, continuous surjective **projection** map $\pi:E\to M$, and base space $M$. Bundle is a weaker version of product: instead of saying that $E$ can be constructed from its components, we say that locally $E$ can be projected onto components - $\pi: E\to M$ - A **fiber** of $E$ at $p\in M$ is: $\pi^{-1}(p)$ - Future uses: vector bundles, tangent/cotangent bundle, sections Example: product manifold is a bundle (REMOVE?) - $E = M{\times}N,$ - $\pi: M{\times}N \to M,$ - $(p, q) \mapsto p$ (continuous w.r.t. product topology), Example: Mobius strip is a bundle, but not a product - TODO: PICTURE - $E$ -- Mobius Strip, - $M = S^1$, - $\pi^{-1}(p) = [-1, 1].$ A **fiber bundle** is a bundle $\pi:E\to M$ s.t. $\pi^{-1}(p) \cong F$ for all $p\in M$ and some ("typical fiber") manifold $F$. Lo and behold, given a bundle $\pi:E\to M,$ a **section** $\sigma: M\to E$ assigns to each point $p$ in manifold $M$ a point from its fiber $\sigma(p)\in \pi^{-1}(p)\subset E$. In other words, it's a map $\sigma: M\to E$ such that $\pi \circ \sigma = \operatorname{id}_M$. Example: vector fields. TODO - **Bundle morphisms** - **Bundle isomorphisms** - **Locally isomorphic bundles** - **Trivial bundles, locally trivial bundles**, and **local trivialization** - **Pullback bundle** Gradient descent, "step in a direction", and differentiation --- _In this section we talk about line-search along geodesics, derivations and differentiation of functions between manifolds_ **TODO:** actually, we need Riemannian metric before we can finish this section -- in order to convert derivative into a tangent vector. One of the simplest optimization methods one can think of is the gradient descent: given a (piecewise)-differentiable objective function $f:X\subset\mathbb{R}^n \to \mathbb{R}$ initial estimate $x_0 \in X$, and learning rate $\alpha\in\mathbb{R}$, we gradually improve our estimate, by making a small linear step in the direction of steepest descent of the loss function: $$x_t = x_{t-1} - \alpha \operatorname{grad} f (x_{t-1}).$$ One way to interpret such iteration, is that at step $t$, we approximate our objective $f$ Let's begin with the notion of "**direction**". The key observation for generalization of "directions" and "direction fields" to manifolds, is that "direction" attached to a point **acts** on **scalar functions** as a directional derivative at that point. Specifically, given a "test function" $f:\mathbb{R}^n \to \mathbb{R}$, a vector $X\in\mathbb{R}^n$ attached to point $p\in\mathbb{R}^n$ _acts_ on $f$ by computing $$(\lambda\mapsto f(x + \lambda X))'(0).$$ In fact, for a fixed $p$, there's one-to-one correspondence between such linear functionals and $\mathbb{R}^d$-vectors. For an abstract smooth manifold $M$, we can take $C^\infty(M)$ for the space of test functions, while "directional derivatives" would be _derivatives along smooth curves_. Given a smooth curve $\gamma: I\subset\mathbb{R}\to M$, passing through a point $p\in M$ (s.t. $\gamma(0)=p$), the derivative of a test function $f:M\to \mathbb{R}$ at $p$ along $\gamma$ is $$X_{\gamma, p}(f) = (f\circ \gamma)'(0).$$ We could read this formula as "initial velocity of $f$ along $\gamma$". There's a handful observations to be made about this concept: - Only local behaviour of $\gamma$ matters. Two curves may represent same directional derivative - $X_{\gamma, p}$ is a linear functional - It satisfies Leibniz rule: $X(fg) = X(f)g(p) + f(p)X(g)$. Such linear functionals are called **derivations**. <div style="margin: 1em;"> <img src="https://i.imgur.com/4Zu3yoc.jpg" style="border-radius: 1em; margin: 1em;" /> - The set $T_pM = \{X_{\gamma, p}:~\gamma~\text{smooth curve through}~p\}$ actually forms a linear space: the action of linear combinations of derivations is defined pointwise, and an example curve representing the combination may be constructed in a chart: <img src="https://i.imgur.com/mSv7diH.jpg" style="border-radius: 1em; margin: 1em" /> </div> **Leibniz rule and derivations** Derivatives --- _Total derivative, pullback, pushforward_ A $C^k$ function $F:M\to N$ between manifolds induces maps between (co-)tangent bundles of $M$ and $N$. The **push-forward** $F_*X_p$ of $X_p\in T_pM$ ("on the left") under $F$ is a tangent vector in $T_{F(p)}N$ such that for $f\in C^\infty(M)$ $$(F_*X_p)(f) = X_p(f\circ F).$$ Similarly, for a co-tangent $\omega\in T^*_{F(p)}N$ ("on the right"), its **pull-back** under $F$ is $F^*\omega \in T^*_pM$ such that for $X\in T_pM$ $$(F^*\omega)(X) = \omega(F_*X).$$ The notion of push-forward generalizes that of a derivative. In coordinate basis, push-forward corresponds to Jacobian matrix acting on column-vectors. _Hmm, pull-backs should correspond to Jacobian matrix too, matrix acting from the left, am I right? Yet we can't have correspondence between tangents and cotangents without metric tensor? Oh, wait, the derivative, apparently, should be a $(1,1)$-tensor?! Ah, not even so, it takes one index from left manifold and the other from the right mfd_ Coordinate frame in $T_pM$ --- _Push-forwards of inverse charts form a basis in $T_pM$. This also allows to specify the dimension of tangent bundle as a manifold_ Given a chart $(U, x)$, we can construct a basis in $T_p^M,~p\in\operatorname{dom}x$ from canonical basis in $T_{x(p)}\mathbb{R}^n \cong \mathbb{R}^n$, by push-forwarding it via inverse chart: $$E_i = \frac{\partial}{\partial x_i} = x^{-1}_* \partial_i,$$ where $\partial_i$ is the $i$'th partial derivative operator acting on functions on $\mathbb{R}^n$. This is visualized as follows: one can construct a curve $\gamma_i$ emanating from $p$ as following $i$'th coordinate in the chart $x$: $$\gamma_i(t)=x^{-1}(x(p) + t e_i).$$ Then $$\frac{\partial}{\partial x_i}(f) = \partial_i (f \circ x^{-1})(x(p)) = (t\mapsto f(x^{-1}(x(p) + te_i)))'(0) = X_{\gamma_i, p}(f).$$ In other words, $\frac{\partial}{\partial x_i}$ is represented by the curve $\gamma_i$. It now takes just a little exercise to show they are linearly independent a form a basis in $T_pM$. Distances, angles, isometry of $T_pM$ and $T_p^*M$ --- _So far, we've only built machinery for reasoning about **continuity** and **smoothness**. We still don't have any tools for discussing **geometry**. Now we introduce the notion of **Riemannian metric**, which will allow us to measure lengths of curves, compute angles, and, most importantly, convert the derivative of our objective function, which is a cotangent vector, into element of tangent space -- the **gradient**, that is, a direction to make a step in._ Roughly, a **metric** on $M$ is a smooth assignment of symmetric "_inner product_" $g_p = \langle\cdot,\cdot\rangle_p$ on each $T_pM$. Metric is **Riemannian**, if it's positive definite ($g(X, X)\geq 0$). _In fact, in the second talk on applications, we'll be more interested in **Lorentzian** metrics that have signature $(+--\cdots-)$ that correspond to hyperbolic spaces._ TLDR: - Now finally, given a curve, we can measure its _speeed_: $\|X\|_p^2 = \langle X, X \rangle_p,$ for $X\in\operatorname{T}_pM$. - We can measure cosangles. - We can now measure lengths: $L_{[a,b]}(\gamma) = \int_a^b \|\gamma'(t)\|_{\gamma(t)}\operatorname{d}t.$ - We can now convert elements of tangent and cotangent bundle back and forth: - $X\in T_pM$ now defines a linear functional $X^\flat=Y\mapsto \langle X, Y \rangle_p,$ - and a cotangent $\omega\in T_p^*M$ corresponds to tangent vector $\omega^\sharp\in T_pM$ satisfying equation $\langle \omega^\sharp, Y\rangle=\omega(Y)$ (i.e. resulting from application of inverse metric tensor) - TODO: Show in a chart and under change of coordinates? - This allows us to define, for $f:M\to\mathbb{R}$, $$\operatorname{grad}f = \operatorname{d}f^\sharp \in \Gamma(\operatorname{T}M).$$ Now, by a "smooth assignment" we mean that a **metric** on a smooth manifold $M$ is a smooth map $$g:\Gamma(\operatorname{T}M)\times\Gamma(\operatorname{T}M)\to C^\infty(M)$$ that takes two vector fields and produces a scalar function. _In other words, it's a $\operatorname{T}_0^2M$ field._ Comparing vectors from different tangent spaces --- _In this section we talk about differentiation of vector fields, linear connection, zero-acceleration, and parallel translation_ **NB**: in sssome of the following pictures we temporarily use the sometimes abusive and mostly obsolete notation from Absil et al.        Newton method --- _Now that we've learned to differentiate vector fields, we can generalize Newton's method to manifolds_ $$\nabla_{\eta, x_t}\operatorname{grad}f(x_t) = -\operatorname{grad}f(x_t)$$ Curvature --- _Not even sure if I should include it... would be useful to prepare for the second talk_ Hard truth -- we don't know closed-form expmaps and parallel translations --- _Here we discuss **retractions** and **vector transport** -- $1$'st order approximations to exponential map and parallel transport._