cs.LGJan 17, 2025

Mean and Variance Estimation Complexity in Arbitrary Distributions via Wasserstein Minimization

Authors: Valentio Iverson, Stephen Vavasis

Organizations: Department of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

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 μ∈Rl\boldsymbolμ \in \mathbb{R}^l and shrinkage σ∈R++σ\in \mathbb{R}_{++} parameters for a distribution of the form 1σlf0(x−μσ)\frac{1}{σ^l} f_0 \left( \frac{\boldsymbol{x} - \boldsymbolμ}σ \right), where f0f_0 is a known density in Rl\mathbb{R}^l given nn samples. We highlight that while the problem is NP-hard for Maximum Likelihood Estimation (MLE), it is possible to obtain ε\varepsilon-approximations for arbitrary ε>0\varepsilon > 0 within poly(1ε)\text{poly} \left( \frac{1}{\varepsilon} \right) time using the Wasserstein distance.

Explore similar work

CardsList
  1. Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

    May 19, 2026Peter Matthew Jacobs, Jeff M. PhillipsRandomized SketchingApproximation Algorithms

  2. A Gradient Flow Perspective on Minimum MMD Estimation

    Jul 4, 2026Sophia Seulkee Kang, Louis Sharrock, Xiaoyuan Cheng +2Parameter EstimationMaximum Mean Discrepancy