Dimension-free Remez Inequalities and norm designs
Preprint
Abstract
The classical Remez inequality bounds the maximum of the absolute value of a polynomial of degree $d$ on a segment through the maximum of its absolute value on any subset $E$ of positive Lebesgue measure of this segment. Similarly, in several variables the maximum of the absolute value of a polynomial of degree $d$ over a larger set is bounded by the maximum of the absolute value of a polynomial on a subset. There are many such inequalities in the literature, but all of them get spoiled when dimension grows. This article is devoted to the dimension free estimates of this type, where a subset is a grid or a rather sparse subset of the grid. The motivation for the dimension free Remez inequality came very naturally from the quantum learning theory, where we need to approximately restore with large probability a big matrix by a relatively small number of random queries, see \cite{VZ22}, \cite{SVZ}. Our dimension free inequality gives time-efficient and sample-optimal algorithms for learning low-degree polynomials of astronomically large number of variables as well as low-degree quantum observables on qudit ensembles, see \cite{SVZ} for those applications.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Quantum Talagrand, KKL and Friedgut’s Theorems and the Learnability of Quantum Boolean FunctionsCommunications in Mathematical Physics, 2024
- Noncommutative Bohnenblust–Hille inequalitiesMathematische Annalen, 2023
- Pointwise Remez inequalityConstructive Approximation, 2021
- On the Fourier spectrum of functions on Boolean cubesMathematische Annalen, 2018
- The Bohr radius of the n-dimensional polydisk is equivalent toAdvances in Mathematics, 2014
- Pointwise Remez-Type Inequalities in the Unit DiskConstructive Approximation, 2005
- Local dimension-free estimates for volumes of sublevel sets of analytic functionsIsrael Journal of Mathematics, 2003
- Some Extremal Problems for Multivariate Polynomialson Convex BodiesJournal of Approximation Theory, 1997
- Multivariate Bernstein and Markov inequalitiesJournal of Approximation Theory, 1992
- Spherical codes and designsGeometriae Dedicata, 1977