Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs

Given a single observation from a Gaussian distribution with unknown mean θ, we design computationally efficient procedures that can approximately generate an observation from a different target distribution Qθ uniformly for all θ in a parameter set. We leverage our technique to establish reduction-based computational lower bounds for several canonical high-dimensional statistical models under widely-believed conjectures in average-case complexity. In particular, we cover cases in which: 1. Qθ is a general location model with non-Gaussian distribution, including both light-tailed examples (e.g., generalized normal distributions) and heavy-tailed ones (e.g., Student's t-distributions). As a consequence, we show that computational lower bounds proved for spiked tensor PCA with Gaussian noise are universal, in that they extend to other non-Gaussian noise distributions within our class. 2. Qθ is a normal distribution with mean f(θ) for a general, smooth, and nonlinear link function f:ℝ rightarrow ℝ. Using this reduction, we construct a reduction from symmetric mixtures of linear regressions to generalized linear models with link function f, and establish computational lower bounds for solving the k-sparse generalized linear model when f is an even function. This result constitutes the first reduction-based confirmation of a k-to-k2 statistical-to-computational gap in k-sparse phase retrieval, resolving a conjecture posed by Cai et al. (2016). As a second application, we construct a reduction from the sparse rank-1 submatrix model to the planted submatrix model, establishing a pointwise correspondence between the phase diagrams of the two models that faithfully preserves regions of computational hardness and tractability.