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

May 19, 2026

Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation

Squared Wasserstein distance is a frequently used tool to measure discrepancy between probability distributions. This distance is typically computed between empirical measures of size nn from two underlying random samples. Unfortunately, even in lower dimensional Euclidean space problems (d∈{2,3})\left( d \in \{2,3\} \right), algorithms for Wasserstein distance computation with approximate or exact precision guarantees scale poorly in the runtime as a function of nn and the desired precision. In response, we consider the computational-statistical runtime, where the goal is to estimate from samples the Wasserstein distance between potentially smooth measures up to εε-additive error in expectation with respect to the sampling; we allow O(1)O(1) computational cost for collecting a sample. Towards this, we develop a Sample-Sketch-Solve paradigm where we introduce a regular cartesian grid sketch of the samples. We show that (especially under αα-Hölder smooth distributions) this can compress the data without increasing asymptotic error, and also regularizes the structure which enables faster exact algorithms. Ultimately, we approximate W22(P,Q)W_2^2(P,Q) within εε error in ε−max⁡(2,d+1+o(1)1+α)ε^{-\max(2,\frac{d+1+o(1)}{1+α})} time for 0<α<10 < α< 1 Hölder smooth distributions P,QP,Q on (0,1)d(0,1)^{d}; an optimal Θ(ε−2)Θ(ε^{-2}) for α>1/2α> 1/2 when d=2d=2 and nearly optimal as α→1α\to 1 when d=3d = 3.
Jun 5, 2026

A Temporal Spatial Minimax Rate for Smoothly-Varying Distributions in Wasserstein Space

We study the minimax rate of estimating a future value μtn+hμ_{t_n+h} of a curve t↦μtt\mapstoμ_t in the 22-Wasserstein space P2(Rd)\mathcal{P}_2(\mathbb{R}^d) from finitely many noisy snapshots of its past, under an adiabatic bound ∥∇tkv∥≤ε\|\nabla_t^k v\|\le\varepsilon on the kk-th covariant derivative of the velocity field. Our central result is a unified temporal-spatial minimax lower bound: over regular, locally transport-rich subclasses, every estimator incurs W2W_2-risk with MM-exponent γd(k+1)/(k+1+γd)γ_d(k+1)/(k+1+γ_d), γd=min⁡(1/d,1/2)γ_d=\min(1/d,1/2) (MM the total sample size). It follows from a temporal-to-spatial reduction: the smoothness budget defines a reachable W2W_2-ball into which a transport packing is embedded along the time axis, and the information of the entire snapshot experiment is controlled by a Fano argument -- the spatial packing is classical, but its smoothness-admissible temporal embedding and the full-window analysis are new. The bound interpolates a dimension-free extrapolation floor of order εhk+1\varepsilon h^{k+1} -- the irreducible cost of an unobserved future, present even with the exact past -- and the spatial estimation curse M−γdM^{-γ_d}, recovering the static distribution-estimation rate as k→∞k\to\infty. We state the lower bound in a design-dependent form -- with a design-weighted effective sample size -- valid for arbitrary observation times, and obtain the closed-form exponent in the dense (equispaced) regime. The matching upper bound is established at k=0k=0 (rate M−1/(d+1)M^{-1/(d+1)}, d≥3d\ge3) and, in a translation submodel, for all kk; for k≥1k\ge1 a covariant estimator attains the rate conditionally on two estimates (a comparison-geometry bias bound and an optimal-transport map-estimation rate), leaving the unconditional general-kk upper bound as an open problem. Numerical experiments on synthetic curved and flat families corroborate the predicted exponents.
Jul 4, 2026

A Gradient Flow Perspective on Minimum MMD Estimation

Minimum maximum mean discrepancy (MMD) estimation has emerged as a robust and likelihood-free alternative to maximum likelihood estimation for parameter estimation. Yet, despite its practical success, the associated optimization problem remains poorly understood, with theoretical guarantees for existing algorithms hinging on convexity assumptions that rarely hold in practice. We address this gap by proposing a preconditioned gradient descent (PGD) scheme, establishing its asymptotic global convergence under explicit gradient-dominance and projection-residual conditions. Our approach is inspired by recent progress on MMD gradient flows, a nonparametric descent scheme on the space of probability measures. We provide extensive empirical evidence that our PGD scheme outperforms standard gradient descent across a range of challenging parameter estimation and composite hypothesis testing problems.