Beyond Johnson-Lindenstrauss: Uniform Bounds for Sketched Bilinear Forms

Rohan Deb, Qiaobo Li, Mayank Shrivastava, Arindam Banerjee
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:4474-4482, 2026.

Abstract

Uniform bounds on sketched inner products underpin several important computational and statistical results in machine learning and randomized algorithms, including the Johnson-Lindenstrauss (J-L) lemma, the Restricted Isometry Property (RIP), randomized sketching, etc. However, many modern analyses involve \emph{sketched bilinear forms}, for which existing uniform bounds either do not apply or are not sharp on general sets. In this work, we develop a general framework to analyze such sketched bilinear forms, and derive uniform bounds in terms of geometric complexities of the associated sets. Our approach relies on \emph{generic chaining} and introduces new techniques for handling suprema over pairs of sets. We further extend our results to (i) sketch matrices with conditionally independent entries, e.g., as in CountSketch and SRHT (Subsampled Randomized Hadamard Transform), and (ii) bilinear forms involving a sum of $T$ sketch matrices, showing that the deviation scales as $\sqrt{T}$. This unified analysis recovers known results such as the J-L lemma as special cases, while extending RIP guarantees. Using our new bounds, we give tighter convergence bounds for sketched federated learning, and develop sketched bandits whose regret depends on the geometric complexity of the action and parameter sets rather than the ambient dimension.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-deb26a, title = { Beyond Johnson-Lindenstrauss: Uniform Bounds for Sketched Bilinear Forms }, author = {Deb, Rohan and Li, Qiaobo and Shrivastava, Mayank and Banerjee, Arindam}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {4474--4482}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/deb26a/deb26a.pdf}, url = {https://proceedings.mlr.press/v300/deb26a.html}, abstract = { Uniform bounds on sketched inner products underpin several important computational and statistical results in machine learning and randomized algorithms, including the Johnson-Lindenstrauss (J-L) lemma, the Restricted Isometry Property (RIP), randomized sketching, etc. However, many modern analyses involve \emph{sketched bilinear forms}, for which existing uniform bounds either do not apply or are not sharp on general sets. In this work, we develop a general framework to analyze such sketched bilinear forms, and derive uniform bounds in terms of geometric complexities of the associated sets. Our approach relies on \emph{generic chaining} and introduces new techniques for handling suprema over pairs of sets. We further extend our results to (i) sketch matrices with conditionally independent entries, e.g., as in CountSketch and SRHT (Subsampled Randomized Hadamard Transform), and (ii) bilinear forms involving a sum of $T$ sketch matrices, showing that the deviation scales as $\sqrt{T}$. This unified analysis recovers known results such as the J-L lemma as special cases, while extending RIP guarantees. Using our new bounds, we give tighter convergence bounds for sketched federated learning, and develop sketched bandits whose regret depends on the geometric complexity of the action and parameter sets rather than the ambient dimension. } }
Endnote
%0 Conference Paper %T Beyond Johnson-Lindenstrauss: Uniform Bounds for Sketched Bilinear Forms %A Rohan Deb %A Qiaobo Li %A Mayank Shrivastava %A Arindam Banerjee %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-deb26a %I PMLR %P 4474--4482 %U https://proceedings.mlr.press/v300/deb26a.html %V 300 %X Uniform bounds on sketched inner products underpin several important computational and statistical results in machine learning and randomized algorithms, including the Johnson-Lindenstrauss (J-L) lemma, the Restricted Isometry Property (RIP), randomized sketching, etc. However, many modern analyses involve \emph{sketched bilinear forms}, for which existing uniform bounds either do not apply or are not sharp on general sets. In this work, we develop a general framework to analyze such sketched bilinear forms, and derive uniform bounds in terms of geometric complexities of the associated sets. Our approach relies on \emph{generic chaining} and introduces new techniques for handling suprema over pairs of sets. We further extend our results to (i) sketch matrices with conditionally independent entries, e.g., as in CountSketch and SRHT (Subsampled Randomized Hadamard Transform), and (ii) bilinear forms involving a sum of $T$ sketch matrices, showing that the deviation scales as $\sqrt{T}$. This unified analysis recovers known results such as the J-L lemma as special cases, while extending RIP guarantees. Using our new bounds, we give tighter convergence bounds for sketched federated learning, and develop sketched bandits whose regret depends on the geometric complexity of the action and parameter sets rather than the ambient dimension.
APA
Deb, R., Li, Q., Shrivastava, M. & Banerjee, A.. (2026). Beyond Johnson-Lindenstrauss: Uniform Bounds for Sketched Bilinear Forms . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:4474-4482 Available from https://proceedings.mlr.press/v300/deb26a.html.

Related Material