Mean and Variance Estimation Complexity in Arbitrary Distributions via Wasserstein Minimization
This addresses a fundamental challenge in machine learning for tasks like neural network fitting and Bayesian inference, offering a polynomial-time solution to an NP-hard estimation problem.
The paper tackles the NP-hard problem of estimating translation and shrinkage parameters for arbitrary distributions by proposing a method that achieves ε-approximations in polynomial time using Wasserstein distance minimization.
Parameter estimation is a fundamental challenge in machine learning, crucial for tasks such as neural network weight fitting and Bayesian inference. This paper focuses on the complexity of estimating translation $\boldsymbolμ \in \mathbb{R}^l$ and shrinkage $σ\in \mathbb{R}_{++}$ parameters for a distribution of the form $\frac{1}{σ^l} f_0 \left( \frac{\boldsymbol{x} - \boldsymbolμ}σ \right)$, where $f_0$ is a known density in $\mathbb{R}^l$ given $n$ samples. We highlight that while the problem is NP-hard for Maximum Likelihood Estimation (MLE), it is possible to obtain $\varepsilon$-approximations for arbitrary $\varepsilon > 0$ within $\text{poly} \left( \frac{1}{\varepsilon} \right)$ time using the Wasserstein distance.