This was part of Bayesian Statistics and Statistical Learning

Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications

Joe Kileel, University of Texas at Austin

Friday, December 15, 2023


In this talk I will discuss covering numbers of real algebraic varieties and applications to data science.  Specifically, we upper bound the number of balls of radius epsilon needed to cover a real variety, image of a polynomial map or semialgebraic set in Euclidean space, in terms of the degrees of the relevant polynomials and number of variables.  The bound remarkably improves the best known general bound, and its proof is much more straightforward.  On the application side, we control covering numbers of low rank CP tensors, bound the sketching dimension for polynomial optimization problems, and bound the generalization error for deep rational and ReLU neural networks.  Joint work with Yifan Zhang (UT Austin), see arXiv:2311.05116.