Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912636327690240 |
|---|---|
| author | Lou, Mengqi Bresler, Guy Pananjady, Ashwin |
| author_facet | Lou, Mengqi Bresler, Guy Pananjady, Ashwin |
| contents | 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:\mathbb{R} \rightarrow \mathbb{R}$. 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-$k^2$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_07250 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs Lou, Mengqi Bresler, Guy Pananjady, Ashwin Statistics Theory Computational Complexity Information Theory Machine Learning 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:\mathbb{R} \rightarrow \mathbb{R}$. 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-$k^2$ 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. |
| title | Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs |
| topic | Statistics Theory Computational Complexity Information Theory Machine Learning |
| url | https://arxiv.org/abs/2510.07250 |