###### tags: `one-offs` `stochastic processes` `transport` # Forwards, Backwards, and Stochastic Formulations of Optimal Transport **Overview**: In this note, I discuss some appealing aspects of i) viewing deterministic systems as special cases of stochastic systems, and ii) considering the time-reversal of stochastic systems. ## Thinking Forward and Backward Coming from the world of MCMC algorithms, in which most algorithms are constructed to be invariant under time-reversal (or at least to admit some symmetry under time-reversal), I tend to like the idea that in order to understand (stochastic) dynamical systems, it is often very helpful to think about how they behave when run backwards in time. Perhaps this seems natural after the fact, but I think that it's not so obvious on the way in. The brief idea is that 1. if the system looks the same forwards and backwards, then there are various aspects of the system which become easier to study (for an analogy, consider how useful it is to know that a matrix or operator is self-adjoint), and 2. if it does **not** look the same in both directions, then the differences between them can be informative about e.g. the flux of probability mass around the state space. Additionally, it can be fruitful to combine the forward and backward modes of the system in interesting ways. ## Thinking Deterministic and Stochastic A related observation is that I have come to find that most of my current interest in topics surrounding Optimal Transport has seeped towards the { Schrödinger Bridge, Stochastic Control, ... } side of things. The field of OT is generally very cool, but from the perspective of somebody who likes Markov processes a great deal, these particular aspects have a lot to offer. One potential cause is that standard OT theory has many links to geometry and metric structures, which I have historically not understood so well, whereas the stochastic formulations are easier to generalise to arbitrary spaces (e.g. discrete spaces), and this has long held great appeal to me. Another byproduct is the recurring perspective that deterministic processes are 'special cases' of random processes. Sometimes this distinction is actually quite useful to remember, but it's easy to see how it could become an annoying reflex. One certainly needs to be a bit careful about such habits.
Last changed by  
 
sp-monte-carlo
465

Read more

Denoising Diffusions

Overview: In this note, I log some basic observations about diffusion-based generative models.

8/14/2023
Nested Structure in MCMC Algorithms

Overview: In this note, I describe some aspects of hierarchical structure in MCMC algorithms, and how they can be of theoretical and practical relevance.

8/9/2023
The "Approximation to What?" Principle

Overview: In this note, I discuss a recurrent question which can be used to generate research questions about methods of all sorts. I then discuss a specific instance of how this question has proved fruitful in the theory of optimisation algorithms. Methods and Approximations A nice story is that when Brad Efron derived the bootstrap, it was done in service of the question “What is the jackknife an approximation to?”. I can't help but agree that there's something quite exciting about research questions which have this same character of ''What is (this existing thing) an approximation to?''. One bonus tilt on this which I appreciate is that there can be multiple levels of approximation, and hence many answers to the same question. One well-known example is gradient descent, which can be viewed as an approximation to the proximal point method, which can then itself be viewed as an approximation to a gradient flow. There are probably even more stops along the way here. In this case, there is even the perspective that from the perspective of mathematical theory, there may be at least as much to be gained by stopping off at the proximal point interpretation, as there is from the gradient flow perspective. My experience is that generalist applied mathematicians get to grips with the gradient flow quickly, but optimisation theorists can squeeze more out of the PPM formulation. There is thus some hint that using this 'intermediate' approximation can be particularly insightful in its own right. It would be interesting to collect more examples with this character.

5/22/2023
Hoeffding's Inequality by Convex Ordering

Overview: In this note, I prove Hoeffding's inequality from the perspectives of martingales and convex ordering. The Basic Construction Let $-\infty<a<x<b<\infty$, and define a random variable $M$ with law $M\left(x;a,b\right)$ by \begin{align} M=\begin{cases} a & \text{w.p. }\frac{b-x}{b-a}\ b & \text{w.p. }\frac{x-a}{b-a}. \end{cases}

5/22/2023
Read more from sp-monte-carlo
Published on HackMD