Abstract
Covering numbers are a powerful tool used in the development of approximationalgorithms, randomized dimension reduction methods, smoothed complexityanalysis, and others. In this paper we prove upper bounds on the coveringnumber of numerous sets in Euclidean space, namely real algebraic varieties,images of polynomial maps and semialgebraic sets in terms of the number ofvariables and degrees of the polynomials involved. The bounds remarkablyimprove the best known general bound by Yomdin-Comte, and our proof is muchmore straightforward. In particular, our result gives new bounds on the volumeof the tubular neighborhood of the image of a polynomial map and asemialgebraic set, where results for varieties by Lotz and Basu-Lerario are notdirectly applicable. We illustrate the power of the result on threecomputational applications. Firstly, we derive a near-optimal bound on thecovering number of tensors with low canonical polyadic (CP) rank, quantifyingtheir approximation properties and filling in an important missing piece oftheory for tensor dimension reduction and reconstruction. Secondly, we prove abound on dimensionality reduction of images of polynomial maps via randomizedsketching, which has direct applications to large scale polynomialoptimization. Finally, we deduce generalization error bounds for deep neuralnetworks with rational or ReLU activation functions, improving or matching thebest known results in the machine learning literature while helping to quantifythe impact of architecture choice on generalization error.