# Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications arXiv: https://arxiv.org/abs/2311.05116 · HTML: https://mlsanity.com/paper/2311.05116/ ## Key facts - Cited by 8 papers in the map (data through 14 Oct 2026). - Builds on 30 of its 88 references that are in the map. - First posted on arXiv 9 Nov 2023. ## Builds on (most cited first, 30 of 30) - [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017) - [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017) - [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014) - [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016) - [Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networks](https://mlsanity.com/paper/2101.12365/) (2021) - [Rational neural networks](https://mlsanity.com/paper/2004.01902/) (2020) - [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015) - [Pad'e Activation Units: End-to-end Learning of Flexible Activation Functions in Deep Networks](https://mlsanity.com/paper/1907.06732/) (2019) - [Generalization bounds for deep convolutional neural networks](https://mlsanity.com/paper/1905.12600/) (2019) - [Neural networks and rational functions](https://mlsanity.com/paper/1706.03301/) (2017) - [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019) - [Persistence Fisher Kernel: A Riemannian Manifold Kernel for Persistence Diagrams](https://mlsanity.com/paper/1802.03569/) (2018) - [Stochastic Block BFGS: Squeezing More Curvature out of Data](https://mlsanity.com/paper/1603.09649/) (2016) - [Generalization Bounds for Convolutional Neural Networks](https://mlsanity.com/paper/1910.01487/) (2019) - [An Investigation of Newton-Sketch and Subsampled Newton Methods](https://mlsanity.com/paper/1705.06211/) (2017) - [Adaptive Metric Dimensionality Reduction](https://mlsanity.com/paper/1302.2752/) (2013) - [Polynomial time guarantees for the Burer-Monteiro method](https://mlsanity.com/paper/1912.01745/) (2019) - [Near Optimal Sketching of Low-Rank Tensor Regression](https://mlsanity.com/paper/1709.07093/) (2017) - [Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares](https://mlsanity.com/paper/1912.08294/) (2019) - [Scalable Subspace Methods for Derivative-Free Nonlinear Least-Squares Optimization](https://mlsanity.com/paper/2102.12016/) (2021) - [On Fast Simulation of Dynamical System with Neural Vector Enhanced Numerical Solver](https://mlsanity.com/paper/2208.03680/) (2022) - [Dimensionality reduction with subgaussian matrices: a unified theory](https://mlsanity.com/paper/1402.3973/) (2014) - [Isometric sketching of any set via the Restricted Isometry Property](https://mlsanity.com/paper/1506.03521/) (2015) - [Finding stationary points on bounded-rank matrices: A geometric hurdle and a smooth remedy](https://mlsanity.com/paper/2107.03877/) (2021) - [Hausdorff approximations and volume of tubes of singular algebraic sets](https://mlsanity.com/paper/2104.05053/) (2021) - [Moment Estimation for Nonparametric Mixture Models Through Implicit Tensor Decomposition](https://mlsanity.com/paper/2210.14386/) (2022) - [Randomised subspace methods for non-convex optimization, with applications to nonlinear least-squares](https://mlsanity.com/paper/2211.09873/) (2022) - [On Fast Johnson-Lindenstrauss Embeddings of Compact Submanifolds of ℝN with Boundary](https://mlsanity.com/paper/2110.04193/) (2021) - [Scalable Derivative-Free Optimization for Nonlinear Least-Squares Problems](https://mlsanity.com/paper/2007.13243/) (2020) - [Computing geometric feature sizes for algebraic manifolds](https://mlsanity.com/paper/2209.01654/) (2022) ## Built on by (most cited first, 8 of 8) - [Algebra Unveils Deep Learning -- An Invitation to Neuroalgebraic Geometry](https://mlsanity.com/paper/2501.18915/) (2025) - [Learning on a Razor's Edge: Identifiability and Singularity of Polynomial Neural Networks](https://mlsanity.com/paper/2505.11846/) (2025) - [Rational Neural Networks have Expressivity Advantages](https://mlsanity.com/paper/2602.12390/) (2026) - [Understanding Generalization in Physics Informed Models through Affine Variety Dimensions](https://mlsanity.com/paper/2501.18879/) (2025) - [Testing the variety hypothesis](https://mlsanity.com/paper/2507.16705/) (2025) - [Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements](https://mlsanity.com/paper/2502.05134/) (2025) - [Tubular Neighbourhoods of Pfaffian Sets and Applications to Neural Networks](https://mlsanity.com/paper/2607.08370/) (2026) - [A Comparative Analysis of Attention versus State-Space Models for In-Context Learning](https://mlsanity.com/paper/2609.32341/) (2026) ## Abstract (arXiv) Covering numbers are a powerful tool used in the development of approximation algorithms, randomized dimension reduction methods, smoothed complexity analysis, and others. In this paper we prove upper bounds on the covering number of numerous sets in Euclidean space, namely real algebraic varieties, images of polynomial maps and semialgebraic sets in terms of the number of variables and degrees of the polynomials involved. The bounds remarkably improve the best known general bound by Yomdin-Comte, and our proof is much more straightforward. In particular, 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 and Basu-Lerario are not directly applicable. We illustrate the power of the result on three computational applications. Firstly, we derive a near-optimal bound on the covering number of tensors with low canonical polyadic (CP) rank, quantifying their approximation properties and filling in an important missing piece of theory for tensor dimension reduction and reconstruction. Secondly, we prove a bound on dimensionality reduction of images of polynomial maps via randomized sketching, which has direct applications to large scale polynomial optimization. Finally, we deduce generalization error bounds for deep neural networks with rational or ReLU activation functions, improving or matching the best known results in the machine learning literature while helping to quantify the impact of architecture choice on generalization error.