Up next
Learning Convex Bodies in High Dimensions: Asymptotic vs. Non-AsymptoticWednesday, 12-1pm, GHC 4405
How do rates for learning convex bodies depend on dimension, accuracy, and the underlying measure? We will discuss learning and approximation under Gaussian and non-Gaussian measures, their connections to log-concave density estimation, and the distinction between asymptotic rates and non-asymptotic behavior. A central theme is that these perspectives can lead to surprisingly different conclusions. While the cube admits much faster asymptotic approximation than the Euclidean ball in a fixed dimension, their relative difficulty can reverse in high dimensions at fixed accuracy. We will present a rigorous example under relative volume error: the ball admits polytope approximations with sub-exponentially many vertices in the dimension, whereas the cube requires exponentially many. This contrast illustrates how asymptotic rates can give an incomplete picture of high-dimensional representation complexity. Along the way, we will discuss surprising phenomena and a range of open problems connecting convex geometry, probability, and statistical estimation. The talk will be accessible to a broad audience and will not require any prior background. Based on joint work with Yegor Gorodzha (ETH Zürich) and Steven Hoehner (Longwood University).