Sketching Techniques for Kernel Density Estimation or for Optimal Transport Computations
summary
Replaces the Earth Mover objective with an L_rho relaxation (raise gamma entries to rho>1) and optimizes the dual via first‑order methods, estimating gradients with kernel density estimation subroutines. Result: an algorithm that outputs a multiplicative 1±ε estimate of the cost (not a sparse transport) in time roughly n · polylog n · exp(poly(1/(rho−1))) / poly(ε), so it is near‑linear when rho is just above 1 (e.g. 1+1/√log n) but blows up as rho→1. The approach sidesteps spanner barriers but does not solve exact EMD, which remains hardness‑constrained.
AI-written summary · about
chapters (8)
- 0:00Introduction to the problem
- 2:52Defining geometric problems
- 8:26Complexity and open problems
- 12:38Spanner and synchron approaches
- 19:17New relaxation formulation
- 25:05Main theorem and algorithm
- 31:32Kernel density estimation
- 39:13Conclusion and Q&A
related talks
01h 22mComputational Optimal Transport
15mGraphical Optimal Transport and Its Applications
11mOptimal Transport for Inverse Problems
28mSketching for M-Estimators: A Unified Approach to Robust Regression
01h 18mOptimization I
09mA Fast Algorithm for Optimal Transport
09mPrimal--Dual Optimization and Application to Sampling
01h 08mData Driven Optimization Models and Algorithms