Dimension-free Remez Inequalities and norm designs

• URL: http://arxiv.org/abs/2310.07926v5
• Date: Wed, 20 Dec 2023 18:35:23 GMT
• Title: Dimension-free Remez Inequalities and norm designs
• Authors: Lars Becker, Ohad Klein, Joseph Slote, Alexander Volberg, Haonan Zhang
• Abstract summary: A class of domains $X$ and test sets $Y$ -- termed emphnorm -- enjoy dimension-free Remez-type estimates. We show that the supremum of $f$ does not increase by more than $mathcalO(log K)2d$ when $f$ is extended to the polytorus.
• Score: 48.5897526636987
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classical Remez inequality bounds the supremum of a bounded-degree polynomial on an interval $X$ by its supremum on any subset $Y\subset X$ of positive Lebesgue measure. There are many multivariate generalizations of the Remez inequality, but most have constants that depend strongly on dimension. Here we show that a broad class of domains $X$ and test sets $Y$ -- termed \emph{norm designs} -- enjoy dimension-free Remez-type estimates. Instantiations of this theorem allow us for example \emph{a}) to bound the supremum of an $n$-variate degree-$d$ polynomial on the solid cube $[0,1]^n$ by its supremum on the regular grid $\{0,1/d,2/d,\ldots, 1\}^n$ independent of dimension; and \emph{b}) in the case of a degree-$d$ polynomial $f:\mathbf{Z}_K^n\to\mathbf{C}$ on the $n$-fold product of cyclic groups of order $K$, to show the supremum of $f$ does not increase by more than $\mathcal{O}(\log K)^{2d}$ when $f$ is extended to the polytorus as $f:\mathbf{T}^n\to\mathbf{C}$.

Related papers

• An in-depth study of the power function $x^{q+2}$ over the finite field $\mathbb{F}_{q^2}$: the differential, boomerang, and Walsh spectra, with an application to coding theory [28.489574654566677]
  We examine the finite field $mathbbF_q2$, which consists of $q2$ elements. We first present an alternative method to determine the differential spectrum of the power function $f(x) = xq+2$ on $mathbbF_q2$, incorporating several key simplifications.
  arXiv  Detail & Related papers  (2024-07-08T14:01:06Z)
• Some new infinite families of non-$p$-rational real quadratic fields [0.0]
  We give a simple methodology for constructing an infinite family of simultaneously non-$p_j$-rational real fields, unramified above any of the $p_j$. One feature of these techniques is that they may be used to yield fields $K=mathbbQ(sqrtD)$ for which a $p$-power cyclic component of the torsion group of the Galois groups of the maximal abelian pro-$p$-extension of $K$ unramified outside primes above $p$, is of size $pa
  arXiv  Detail & Related papers  (2024-06-20T18:00:51Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Monogamy of entanglement between cones [68.8204255655161]
  We show that monogamy is not only a feature of quantum theory, but that it characterizes the minimal tensor product of general pairs of convex cones. Our proof makes use of a new characterization of products of simplices up to affine equivalence.
  arXiv  Detail & Related papers  (2022-06-23T16:23:59Z)
• Mutually unbiased bases: polynomial optimization and symmetry [1.024113475677323]
  A set of $k$ orthonormal bases of $mathbb Cd$ is called mutually unbiased $|langle e,frangle |2 = 1/d$ whenever $e$ and $f$ are basis vectors in distinct bases. We exploit this symmetry (analytically) to reduce the size of the semidefinite programs making them tractable.
  arXiv  Detail & Related papers  (2021-11-10T14:14:53Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Learning sums of powers of low-degree polynomials in the non-degenerate case [2.6109033135086777]
  We give a learning algorithm for an arithmetic circuit model from a lower bound for the same model, provided certain non-degeneracy conditions hold. Our algorithm is based on a scheme for obtaining a learning algorithm for an arithmetic circuit model from a lower bound for the same model.
  arXiv  Detail & Related papers  (2020-04-15T06:18:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.