Average-Case Communication Complexity of Statistical Problems
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
This is a survey on the use of low-degree polynomials to predict and explain the apparent statistical-computational tradeoffs in a variety of average-case computational problems. In a nutshell, this framework measures th…
SurveyComputational-Statistical Tradeoffs from NP-hardness
A central question in computer science and statistics is whether efficient algorithms can achieve the information-theoretic limits of statistical problems. Many computational-statistical tradeoffs have been shown under a…
Computational EfficiencyPAC learningAverage-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries
This paper develops several average-case reduction techniques to show new hardness results for three central high-dimensional statistics problems, implying a statistical-computational gap induced by robustness, a detecti…
Fast Composite Optimization and Statistical Recovery in Federated Learning
As a prevalent distributed learning paradigm, Federated Learning (FL) trains a global model on a massive amount of devices with infrequent communication. This paper investigates a class of composite optimization and stat…
Federated LearningStochastic Distributed Optimization under Average Second-order Similarity: Algorithms and Analysis
We study finite-sum distributed optimization problems involving a master node and $n-1$ local nodes under the popular $\delta$-similarity and $\mu$-strong convexity conditions. We propose two new algorithms, SVRS and Acc…
Distributed Optimization