Algebra and Combinatorics Seminar

Date: March 22, 2024

Time: 3:00PM - 4:00PM

Location: BLOC 302

Speaker: Yifan Zhang, UT Austin

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

Abstract: In this talk, I will prove a new upper bound on the covering number of real algebraic varieties, images of polynomial maps and semialgebraic sets. The bound remarkably improves the best known general bound by Yomdin and Comte (2004), and its proof is much more straightforward. As a consequence, our result gives new bounds on the volume of the tubular neighborhood of the image of a polynomial map and a semialgebraic set, where results for varieties by Lotz (2015) and Basu, Lerario (2022) are not directly applicable. I will first use this result to derive a near-optimal bound on the covering number of low rank CP tensors. Then I will discuss applications on sketching (general) polynomial optimization problems as well as controlling the generalization error for deep neural networks with rational or ReLU activations.