Average-Case Communication Complexity of Statistical Problems

Cyrus Rashtchian, David Woodruff, Peng Ye, Hanlin Zhu
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3859-3886, 2021.

Abstract

We study statistical problems, such as planted clique, its variants, and sparse principal component analysis in the context of average-case communication complexity. Our motivation is to understand the statistical-computational trade-offs in streaming, sketching, and query-based models. Communication complexity is the main tool for proving lower bounds in these models, yet many prior results do not hold in an average-case setting. We provide a general reduction method that preserves the input distribution for problems involving a random graph or matrix with planted structure. Then, we derive two-party and multi-party communication lower bounds for detecting or finding planted cliques, bipartite cliques, and related problems. As a consequence, we obtain new bounds on the query complexity in the edge-probe, vector-matrix-vector, matrix-vector, linear sketching, and $\mathbb{F}_2$-sketching models. Many of these results are nearly tight, and we use our techniques to provide simple proofs of some known lower bounds for the edge-probe model.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-rashtchian21a, title = {Average-Case Communication Complexity of Statistical Problems}, author = {Rashtchian, Cyrus and Woodruff, David and Ye, Peng and Zhu, Hanlin}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {3859--3886}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/rashtchian21a/rashtchian21a.pdf}, url = {https://proceedings.mlr.press/v134/rashtchian21a.html}, abstract = {We study statistical problems, such as planted clique, its variants, and sparse principal component analysis in the context of average-case communication complexity. Our motivation is to understand the statistical-computational trade-offs in streaming, sketching, and query-based models. Communication complexity is the main tool for proving lower bounds in these models, yet many prior results do not hold in an average-case setting. We provide a general reduction method that preserves the input distribution for problems involving a random graph or matrix with planted structure. Then, we derive two-party and multi-party communication lower bounds for detecting or finding planted cliques, bipartite cliques, and related problems. As a consequence, we obtain new bounds on the query complexity in the edge-probe, vector-matrix-vector, matrix-vector, linear sketching, and $\mathbb{F}_2$-sketching models. Many of these results are nearly tight, and we use our techniques to provide simple proofs of some known lower bounds for the edge-probe model.} }
Endnote
%0 Conference Paper %T Average-Case Communication Complexity of Statistical Problems %A Cyrus Rashtchian %A David Woodruff %A Peng Ye %A Hanlin Zhu %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-rashtchian21a %I PMLR %P 3859--3886 %U https://proceedings.mlr.press/v134/rashtchian21a.html %V 134 %X We study statistical problems, such as planted clique, its variants, and sparse principal component analysis in the context of average-case communication complexity. Our motivation is to understand the statistical-computational trade-offs in streaming, sketching, and query-based models. Communication complexity is the main tool for proving lower bounds in these models, yet many prior results do not hold in an average-case setting. We provide a general reduction method that preserves the input distribution for problems involving a random graph or matrix with planted structure. Then, we derive two-party and multi-party communication lower bounds for detecting or finding planted cliques, bipartite cliques, and related problems. As a consequence, we obtain new bounds on the query complexity in the edge-probe, vector-matrix-vector, matrix-vector, linear sketching, and $\mathbb{F}_2$-sketching models. Many of these results are nearly tight, and we use our techniques to provide simple proofs of some known lower bounds for the edge-probe model.
APA
Rashtchian, C., Woodruff, D., Ye, P. & Zhu, H.. (2021). Average-Case Communication Complexity of Statistical Problems. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:3859-3886 Available from https://proceedings.mlr.press/v134/rashtchian21a.html.

Related Material