# Computationally efficient reductions between some statistical models

arXiv: https://arxiv.org/abs/2402.07717 · HTML: https://mlsanity.com/paper/2402.07717/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 108 references that are in the map.
- First posted on arXiv 12 Feb 2024.

## Builds on (most cited first, 29 of 29)

- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits](https://mlsanity.com/paper/2005.10743/) (2020)
- [PhaseMax: Convex Phase Retrieval via Basis Pursuit](https://mlsanity.com/paper/1610.07531/) (2016)
- [Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval](https://mlsanity.com/paper/1705.02356/) (2017)
- [Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow](https://mlsanity.com/paper/1506.03382/) (2015)
- [Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit](https://mlsanity.com/paper/2012.09996/) (2020)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [Phase Retrieval via Randomized Kaczmarz: Theoretical Guarantees](https://mlsanity.com/paper/1706.09993/) (2017)
- [Breaking the gridlock in Mixture-of-Experts: Consistent and Efficient Algorithms](https://mlsanity.com/paper/1802.07417/) (2018)
- [Universality of Computational Lower Bounds for Submatrix Detection](https://mlsanity.com/paper/1902.06916/) (2019)
- [Optimal Average-Case Reductions to Sparse PCA: From Weak Assumptions to Strong Hardness](https://mlsanity.com/paper/1902.07380/) (2019)
- [Isotonic regression with unknown permutations: Statistics, computation, and adaptation](https://mlsanity.com/paper/2009.02609/) (2020)
- [The Generalized Lasso for Sub-gaussian Measurements with Dithered Quantization](https://mlsanity.com/paper/1807.06976/) (2018)
- [Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization](https://mlsanity.com/paper/2207.09660/) (2022)
- [Hypothesis testing with low-degree polynomials in the Morris class of exponential families](https://mlsanity.com/paper/2011.03693/) (2020)
- [Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression](https://mlsanity.com/paper/2303.02118/) (2023)
- [Low-rank matrix completion and denoising under Poisson noise](https://mlsanity.com/paper/1907.05325/) (2019)
- [Algebraic and Analytic Approaches for Parameter Learning in Mixture Models](https://mlsanity.com/paper/2001.06776/) (2020)
- [Hyperparameter tuning via trajectory predictions: Stochastic prox-linear methods in matrix sensing](https://mlsanity.com/paper/2402.01599/) (2024)
- [Breaking the 1/√n Barrier: Faster Rates for Permutation-based Models in Polynomial Time](https://mlsanity.com/paper/1802.09963/) (2018)
- [A Dual Accelerated Method for Online Stochastic Distributed Averaging: From Consensus to Decentralized Policy Evaluation](https://mlsanity.com/paper/2207.11425/) (2022)
- [Noisy Matrix Completion under Sparse Factor Models](https://mlsanity.com/paper/1411.0282/) (2014)
- [Minimax Lower Bounds for Noisy Matrix Completion Under Sparse Factor Models](https://mlsanity.com/paper/1510.00701/) (2015)
- [A Cross Validation Framework for Signal Denoising with Applications to Trend Filtering, Dyadic CART and Beyond](https://mlsanity.com/paper/2201.02654/) (2022)
- [Do algorithms and barriers for sparse principal component analysis extend to other structured settings?](https://mlsanity.com/paper/2307.13535/) (2023)

## Abstract (arXiv)

We study the problem of approximately transforming a sample from a source statistical model to a sample from a target statistical model without knowing the parameters of the source model, and construct several computationally efficient such reductions between canonical statistical experiments. In particular, we provide computationally efficient procedures that approximately reduce uniform, Erlang, and Laplace location models to general target families. We illustrate our methodology by establishing nonasymptotic reductions between some canonical high-dimensional problems, spanning mixtures of experts, phase retrieval, and signal denoising. Notably, the reductions are structure-preserving and can accommodate missing data. We also point to a possible application in transforming one differentially private mechanism to another.