Resilience of Rademacher chaos of low degree
This work addresses a theoretical problem in probability theory and random matrix theory, offering incremental advances by extending resilience guarantees from linear to low-degree Rademacher chaos.
The paper tackles the problem of determining how many adversarial sign-flips a Rademacher chaos can withstand without significantly changing its largest atom probability, providing probabilistic lower-bound guarantees for chaos of low degree, with results distinguishing between order two and higher orders and offering instance-dependent computations for constant-order chaos.
The resilience of a Rademacher chaos is the maximum number of adversarial sign-flips that the chaos can sustain without having its largest atom probability significantly altered. Inspired by probabilistic lower-bound guarantees for the resilience of linear Rademacher chaos, obtained by Bandeira, Ferber, and Kwan (Advances in Mathematics, Vol. $319$, $2017$), we provide probabilistic lower-bound guarantees for the resilience of Rademacher chaos of arbitrary yet sufficiently low degree. Our main results distinguish between Rademacher chaos of order two and those of higher order. In that, our first main result pertains to the resilience of decoupled bilinear Rademacher forms where different asymptotic behaviour is observed for sparse and dense matrices. For our second main result, we bootstrap our first result in order to provide resilience guarantees for quadratic Rademacher chaos. Our third main result, generalises the first and handles the resilience of decoupled Rademacher chaos of arbitrary yet sufficiently low order. Our results for decoupled Rademacher chaos of order two and that of higher order whilst are established through the same conceptual framework, differ substantially. A difference incurred due to the implementation of the same conceptual argument. The order two result is established using Dudley's maximal inequality for sub-Gaussian processes, the Hanson-Wright inequality, as well as the Kolmogorov-Rogozin inequality. To handle higher order chaos, appeals to Dudley's inequality as well as the Hanson-Wright inequality are replaced with tools suited for random tensors. Appeals to the Hanson-Wright inequality are replaced with appeals to a concentration result for random tensors put forth by Adamczak and Wolff. Our results are instance-dependent and thus allow for the efficient computation of resilience guarantees provided the order of the chaos is constant.