Mean and Variance Estimation Complexity in Arbitrary Distributions via Wasserstein Minimization

Abstract

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 R^l and shrinkage R_++ parameters for a distribution of the form 1^l f_0 ( x - ), where f_0 is a known density in R^l given n samples. We highlight that while the problem is NP-hard for Maximum Likelihood Estimation (MLE), it is possible to obtain -approximations for arbitrary > 0 within poly ( 1 ) time using the Wasserstein distance.

Tasks

Reproductions