Regularization for Optimal Transport and Dynamic Time Warping Distances - Marco Cuturi

Explore the theoretical foundations of learning in this 44-minute conference talk focusing on regularization techniques for Optimal Transport and Dynamic Time Warping distances. Delve into the intersection of statistics, probability, and optimization as applied to structured mathematical objects like point clouds, histograms, and time series. Discover how early optimization methods, including linear and dynamic programming, have led to powerful distance metrics such as Wasserstein distances and dynamic time warping scores. Learn about two distinct smoothing strategies that improve these non-differentiable quantities for machine learning applications, with a focus on computing Fréchet means. Examine topics including dynamic time warping, pairwise distance matrices, alignment paths, Wasserstein distances for discrete measures, and the Kantorovich problem. Investigate the challenges of using DTW and OT as loss functions, and explore solutions like softmin of quadratic functions and recursive computations. Gain insights into fast and scalable algorithms, including the Sinkhorn algorithm, and understand their applications in interpolating between time series.

Intro
Dynamic Time Warping
Pairwise Distance Matrix
Alignment Path
Path Cost
Min Cost Alignment Matrix?
Best Alignment Matrix
Best Path: Bellman Recursion
Optimal Path
OT for Discrete Measures
Wasserstein on Discrete Measures
Dual Kantorovich Problem
Solving the OT Problem
In Summary
DTW as a Loss: Differentiability?
OT as a Loss: Differentiability?
Any way to fix this?
Example softmin of quadratic functions
Recursive Computation (Backward)
Computation Graph: Forward
Backward Recurrence
Generating Function for OT
Fast & Scalable Algorithm
Sinkhorn as a Dual Algorithm
Block Coordinate Ascent, a.k.a Sinkhorn
Differentiability of W
Algorithmic Formulation
Sinkhorn: A Programmer View
Interpolation Between 2 Time Series