Resilience of the quadratic Littlewood-Offord problem
Elad Aigner-Horev Daniel Rozenberg Roi Weiss
We study the statistical resilience of high-dimensional data. Our results
provide estimates as to the effects of adversarial noise over the
anti-concentration properties of the quadratic Radamecher chaos
$\boldsymbol{\xi}^{\mathsf{T}} M \boldsymbol{\xi}$, where $M$ is a fixed
(high-dimensional) matrix and $\boldsymbol{\xi}$ is a conformal Rademacher
vector. Specifically, we pursue the question of how many adversarial sign-flips
can $\boldsymbol{\xi}$ sustain without "inflating" $\sup_{x\in \mathbb{R}}
\mathbb{P} \left\{\boldsymbol{\xi}^{\mathsf{T}} M \boldsymbol{\xi} = x\right\}$
and thus "de-smooth" the original distribution resulting in a more "grainy" and
adversarially biased distribution. Our results provide lower bound estimations
for the statistical resilience of the quadratic and bilinear Rademacher chaos;
these are shown to be asymptotically tight across key regimes.