Mean and Variance Estimation Complexity in Arbitrary Distributions via Wasserstein 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μ ∈ ℝl and shrinkage σ ∈ ℝ++ parameters for a distribution of the form frac1σl f0 left( fracboldsymbolx - boldsymbolμσ right), where f0 is a known density in ℝ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 poly left( frac1varepsilon right) time using the Wasserstein distance.