Primal--Dual Optimization and Application to Sampling

on YouTube ↗09m

" summary

Recasts sampling as minimizing KL over probability measures, analyzes Stein Variational Gradient Descent in the infinite‑particle (population) limit using the Wasserstein gradient and the RKHS kernel operator, and measures error by the kernelized Stein discrepancy (KSD). Under smooth nonconvex potential and a T1/Talagrand moment bound, the paper proves convergence: about D^{1.5}/ε iterations suffice to get KSD^2 ≤ ε. The result is a rigorous complexity bound for SVGD.

AI-written summary · about

" chapters (6)

1. 0:00Introduction
2. 1:14Sampling basics
3. 3:23Sampling as optimization
4. 4:43Population limit dynamics
5. 6:17Kernelized discrepancy
6. 7:14Complexity results

" related talks

• 58mFirst-Order Stochastic OptimizationRachel Ward · Foundations of Data Science Boot Camp 2018
• 01h 18mOptimization IBen Recht · Big Data Boot Camp 2013
• 01h 07mOptimization Crash Course (continued)Ashia Wilson · Geometric Methods in Optimization and Sampling Boot Camp
• 01h 07mStochastic Second Order Optimization Methods IFred Roosta · Foundations of Data Science Boot Camp 2018
• 33mStochastic Optimization for Big Data Machine Learning ProblemsTong Zhang · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 22mGeneralization IVPeter Bartlett, Sasha Rakhlin · Deep Learning Boot Camp 2019
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 02mImportance Sampling in High Dimensions via HashingMoses Charikar · Sublinear Algorithms and Nearest-Neighbor Search