Codes and Expansions (CodEx) Seminar

Joe Kileel (University of Texas at Austin)
Covering Number of Real Algebraic Varieties and Beyond

In this talk I will discuss covering numbers of real algebraic varieties and some applications to data science. Specifically, we control 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 at UT Austin (arXiv:2311.05116).