Sparsity-adaptive concentration inequalities for random polynomials

Abstract

We prove concentration inequalities for polynomials of independent, sparse $\hat{I}\pm$-sub-exponential random variables. Specifically, we consider $X_i=\hat{I}{´}_i\hat{I}{¾}_i$, where the Bernoulli selectors $\hat{I}{´}_i$ are independent with parameters $p_i$, and the variables $\hat{I}{¾}_i$ are independent \(α\)-sub-exponential random variables (not necessarily centered). For any polynomial $f:{\mathbb{R}}^n\to \mathbb{R}$ of degree at most $D$ and any $0<\hat{I}\pm \le 1$, we establish an $L_r$-moment bound for \(f(X)-\mathbb E f(X)\) in terms of partition norms of sparsity-weighted expected derivative tensors. The weights count distinct coordinates rather than multiplicities and therefore distinguish diagonal, partially diagonal, and off-diagonal contributions. This captures the sparse scaling in both collective fluctuation regimes and extreme-coordinate regimes. When all sparsity parameters are equal to one, our result recovers the polynomial concentration inequality of Götze, Sambale, and Sinulis. In degree two, it recovers sparse Hanson-Wright bounds. As applications, we derive deviation inequalities for the distance between a sparse simple random tensor and a fixed subspace, and obtain lower bounds for the smallest singular value of matrices whose columns are independent sparse simple random tensors.