English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper develops several average-case reduction techniques to show newhardness results for three central high-dimensional statistics problems,implying a statistical-computational gap induced by robustness, adetection-recovery gap and a universality principle for these gaps. A mainfeature of our approach is to map to these problems via a common intermediateproblem that we introduce, which we call Imbalanced Sparse Gaussian Mixtures.We assume the planted clique conjecture for a version of the planted cliqueproblem where the position of the planted clique is mildly constrained, andfrom this obtain the following computational lower bounds: (1) a $k$-to-$k^2$statistical-computational gap for robust sparse mean estimation, providing thefirst average-case evidence for a conjecture of Li (2017) and Balakrishnan etal. (2017); (2) a tight lower bound for semirandom planted dense subgraph,which shows that a semirandom adversary shifts the detection threshold inplanted dense subgraph to the conjectured recovery threshold; and (3) auniversality principle for $k$-to-$k^2$ gaps in a broad class of sparse mixtureproblems that includes many natural formulations such as the spiked covariancemodel.  Our main approach is to introduce several average-case techniques to producestructured and Gaussianized versions of an input graph problem, and then torotate these high-dimensional Gaussians by matrices carefully constructed fromhyperplanes in $\mathbb{F}_r^t$. For our universality result, we introduce anew method to perform an algorithmic change of measure tailored to sparsemixtures. We also provide evidence that the mild promise in our variant ofplanted clique does not change the complexity of the problem.

Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries