Optimal Confidence Bounds for Sparse Random Projections

Random projections enable efficient dimensionality reduction while preserving geometric structure, with applications spanning accelerating linear algebra computations, differential privacy, and fine-tuning large language models. Variants of the Johnson-Lindenstrauss lemma quantify confidence bounds via Chernoff-type inequalities, yet despite sustained effort, theoretical guarantees remain exponentially weaker than what both known limits and empirical behaviour suggest-gaps often exceeding few orders of magnitude. Closing this gap is both challenging and essential for applicability in non-asymptotic regimes, where precise bounds directly determine computational requirements and guarantees. This paper establishes optimal non-asymptotic concentration bounds for sparse Rademacher projections, achieving the sharp threshold of Burr et al. and improving upon previous results through exponentially better confidence, or equivalently reducing required dimensions by a large factor-observed to be even larger in applications, with extensions to non-oblivious bounds for structured inputs. These results follow from a unified analytical framework of independent interest to probability theory and its applications: a) negative association of moments; b) refined Hanson-Wright-type concentration bounds for randomly masked quadratic chaos achieving optimal constants via rational approximants; and c) precise methods for aggregating conditional Bernstein-type bounds.