Estimating Normalizing Constants for Log-Concave Distributions - Algorithms and Lower Bounds

Explore algorithms and lower bounds for estimating normalizing constants of log-concave distributions in this 26-minute ACM conference talk. Delve into problem statement, upper bounds using annealing and multilevel Monte Carlo techniques, and regular Monte Carlo methods. Examine sampling algorithms, focusing on Langevin dynamics, its discretization, and coupling. Investigate lower bounds for both low and high dimensions, including proof ideas and distinguishing biased coins. Conclude with insights on partitioning dimensions and key takeaways for computational statistics and machine learning applications.