Computationally Efficient Reductions Between Some Statistical Models
- 10 July 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (9) , 7097-7133
Abstract
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.Keywords
All Related Versions
Funding Information
- ARC-ACO Fellowship through the Algorithms and Randomness Center at Georgia Tech
- NSF (CCF-2107455, DMS-2210734)
- Adobe, Amazon, and Mathworks
- NSF CAREER (CCF-1940205)
This publication has 75 references indexed in Scilit:
- Notes on Computational Hardness of Hypothesis Testing: Predictions Using the Low-Degree Likelihood Ratio2022
- On Concentration for (Regularized) Empirical Risk MinimizationSankhya A, 2017
- Strong Data-Processing Inequalities for Channels and Bayesian Networks2017
- Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds2016
- Sharp MSE Bounds for Proximal DenoisingFoundations of Computational Mathematics, 2015
- Robust mixture regression model fitting by Laplace distributionComputational Statistics & Data Analysis, 2014
- ℓ1-penalization for mixture regression modelsTEST, 2010
- Differential Privacy2006
- Asymptotics in Statistics2000
- A note on a partial ordering for communication channelsInformation and Control, 1958