On the Minimax Optimality of Estimating the Wasserstein Metric

Tengyuan Liang

REVIEW 2 major objections 5 minor 16 references

On the Minimax Optimality of Estimating the Wasserstein Metric

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Estimating the Wasserstein-1 distance between smooth distributions is essentially as hard as estimating the distributions themselves.

desk verdict Clever lower bound for an important question, but the proof as written needs an explicit disjoint-support basis; likely fixable and worth refereeing. read the letter →

arxiv 1908.10324 v1 pith:4GB5KMJM submitted 2019-08-27 math.ST cs.LGstat.MLstat.TH

Tengyuan Liang This is my paper · ORCID

classification math.STcs.LGstat.MLstat.TH MSC 62G0562G2062G0760B10

keywords Wasserstein-1metricminimaxestimationHöldersmoothnessBesovspaceswaveletthresholdingplug-inestimatoroptimaltransportempiricalmeasures

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that the minimax risk of estimating the Wasserstein-1 metric $W(\mu,\nu)$ between two unknown probability measures on $[0,1]^d$ ($d\ge 2$) with $\beta$-Hölder smooth densities is, up to a factor $\log\log(\min(n,m))/\log(\min(n,m))$, the same as the risk of estimating the measures themselves under the metric. In concrete terms, no estimator can beat a rate of about $(\min(n,m))^{-(\beta+1)/(2\beta+d)}$, and a plug-in estimator built from smoothed empirical measures achieves that rate. The consequence is that estimating this particular scalar functional is not significantly easier than estimating the underlying density. The result matters because it closes a natural question in nonparametric two-sample testing and optimal transport: for the Wasserstein-1 metric, the plug-in approach is essentially optimal.

What carries the argument

The argument runs on four linked pieces: (i) the wavelet multiresolution expansion of densities on $[0,1]^d$, which turns the Wasserstein-1 distance into a weighted $\ell^1$ sum of wavelet coefficients; (ii) the single-scale perturbation family $\nu_\theta=\mu+n^{-1/2}\sum_{k}\theta_k h_{Jk}$ with $2^{dJ}\asymp n^{1/(2\beta/d+1)}$, for which the paper verifies $W(\mu,\nu_\theta)=d_B^{1,q}(\mu,\nu_\theta)=(2^{-dJ})^{-(\beta+1)/d}(2^{-dJ})\sum_k|\theta_k|$; (iii) two symmetric priors $q_0,q_1$ on $[-\tau,\tau]$ whose moments match through order $2K$ but whose first absolute moments differ by about $K^{-1}$, making the null and alternative Wasserstein values differ by the target rate while the induced sample distributions stay close in total variation; (iv) a telescoping product inequality plus an $\ell^2$ computation that bounds the total variation by $2^{dJ}\cdot 2\tau^{2K}/\sqrt{(2K)!}$, which forces $K\asymp \log n/\log\log n$ and produces the $\log\log/\log$ correction.

What would settle it

Take $\beta=1$, $d=2$, fix $J$ and coefficients $\theta_k$ at the paper's maximal allowed size, and compute the Lipschitz constant of $\nu_\theta=1+n^{-1/2}\sum_k \theta_k h_{Jk}$ across the boundary between two adjacent wavelet supports. If the constant exceeds the $C^1$ bound $M$, the constructed measures leave $G^\beta$ and the lower-bound family collapses; conversely, a uniform bound over all such $\theta$ would resolve the integer-smoothness gap.

Watch

Extended reading notes

Core claim

Formally, Theorem 1 establishes that for $d\ge 2$ and $\beta\ge 0$, $$\frac{\log\log(\min(n,m))}{\log(\min(n,m))}\,(\min(n,m))^{-\frac{\$\beta$+1}{2\$\beta$+d}} \;\lesssim\; \inf_{\widehat T}\sup_{\mu,\nu\in G^\$\beta$}\mathbb{E}\,|\widehat T - W(\mu,\nu)| \;\lesssim\; (\min(n,m))^{-\frac{\$\beta$+1}{2\$\beta$+d}},$$ where $G^\beta$ is the class of probability measures whose densities lie in the Hölder space $C^\beta(M)$. The lower bound is the paper's main technical contribution: it constructs two composite hypotheses on the density $\nu$ (with $\mu$ fixed as the uniform measure) using single-scale wavelet perturbations $\nu_\theta = \mu + n^{-1/2}\sum_k \theta_k h_{Jk}$, chooses priors on $\theta$ whose moments match through order $2K$, and relies on the equality $W(\mu,\nu_\theta)=d_B^{1,q}(\mu,\nu_\theta)$ holding on these hard instances. The upper bound is achieved by plugging in wavelet-truncated empirical measures. Together these bounds show that the plug-in estimator is minimax optimal up to the $\log\log/\log$ factor.

Load-bearing premise

The lower bound rests on the claim that every perturbed density built from a single scale of wavelet bumps lies in the Hölder class $C^\beta$ for every $\beta\ge 0$, including integer $\beta$, although the paper's stated Besov–Hölder embedding covers only non-integer $\beta$.

Editorial extensions

If this is right

Plug-in estimation is essentially optimal: using the smoothed empirical measures in place of the unknown densities attains the minimax rate up to the $\log\log/\log$ factor, so any improved estimator can only remove a logarithmic factor.
Knowing one of the two measures exactly does not break the rate: with $\mu$ fixed and only $\nu$ unknown, the minimax rate for estimating the transport cost is governed by the smoothness of the unknown measure.
When the two measures have different smoothness levels $\beta_1,\beta_2$, the estimation rate is governed by the smaller smoothness $\beta=\min(\beta_1,\beta_2)$.
In dimension $d\ge 2$, raw empirical plug-in attains only $n^{-1/d}$ even for smooth measures, while the paper's smoothed estimator improves to $n^{-(\beta+1)/(2\beta+d)}$, so smoothing matters.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial extension: the $\log\log/\log$ gap appears to be an artifact of the moment-matching construction, which can only match moments up to $K\asymp \log n/\log\log n$; a different hypothesis pair might close the gap and yield a minimax rate of exactly $(\min(n,m))^{-(\beta+1)/(2\beta+d)}$.
Editorial extension: the same single-scale wavelet construction should transfer to other integral probability metrics whose dual balls are Besov balls, provided the equality between the metric and the Besov norm holds on the hard instances; the paper's argument gives a template rather than a Wasserstein-specific trick.
Editorial extension: if the Besov–Hölder inclusion fails at integer $\beta$, the lower bound as stated would only cover non-integer smoothness; a direct check for $\beta=1$ is a small calculation and would settle the gap.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

The paper asks a good question: when µ and ν are β-Hölder smooth, can we estimate W1(µ,ν) faster than we can estimate µ and ν themselves? Liang answers no, up to a loglog n / log n factor. The upper bound is the usual plug-in rate; the real contribution is the lower bound, built from Lepski-style moment-matching priors and a telescoping TV calculation. The idea is clean and the exposition is honest—no fitted constants, no circularity. The author cites the relevant plug-in literature (Weed–Bach, Liang, Singh et al., Weed–Berthet), and the upper bound is derived in Section 2.2 rather than imported.

The lower bound has two soft spots. The minor one, which the reader's report caught, is that the Besov–Hölder embedding is only quoted for non-integer β. The theorem covers all β ≥ 0, so the integer case needs an argument. That's probably a small fix. The larger problem is in Eq. (2.12): the density is factored as ∏(1 + θ_k n^{-1/2} h_{Jk}), which is only true if the supports of the h_{Jk} at scale J are pairwise disjoint. Standard smooth wavelet bases don't have disjoint supports—Haar does, but Haar isn't C^β for β>0. The paper never specifies a basis that has both disjointness and smoothness. Without that, the product factorization, the likelihood separation, and the TV bound don't go through. This is the load-bearing step. I think the construction is repairable: take smooth zero-mean bump functions on disjoint dyadic cubes instead of an orthonormal wavelet basis, and check that the Besov/Hölder norm bounds still hold. But that has to be written down.

So my read is more skeptical than the reader's: not 7/10 soundness, more like 5/10 as written. Not because the theorem looks false—I suspect it's true—but because the proof currently has a hole at its center. I'd still send it to peer review. The question is worth settling, the technique is interesting, and the gap is the kind a good referee can push the author to close.

If you're working on minimax rates for Wasserstein estimation, this is worth reading and discussing, just with a careful eye on Section 2.1.

Referee Report

2 major / 5 minor

Summary. The paper studies the minimax rate of estimating the Wasserstein-1 distance W(μ,ν) between two unknown probability measures on [0,1]^d whose densities belong to a Hölder class Gβ. Theorem 1 claims that the minimax risk is n^{-(β+1)/(2β+d)} up to a multiplicative factor of order loglog(n)/log(n), so that plug-in estimation of the metric is essentially as hard as estimating the measures themselves under W1. The upper bound is obtained by a wavelet-thresholded plug-in estimator and is derived in Section 2.2. The lower bound is constructed in Section 2.1 through composite hypotheses: perturbations νθ = μ + n^{-1/2} Σ_k θ_k h_{Jk}, priors on θ with matching moments up to order 2K, a direct total-variation bound on the induced likelihoods, and Le Cam's argument.

Significance. If the theorem is correct, it resolves a natural question in nonparametric functional estimation: for the Wasserstein-1 metric, estimating the value of the functional is not significantly easier than estimating the underlying distributions, in contrast to known results for quadratic functionals. The proof strategy is conceptually attractive, and the upper-bound part is a useful self-contained derivation of the plug-in rate. The lower-bound framework using moment-matched priors and a telescoping TV bound is elegant and transparent. However, the lower-bound construction as written contains a load-bearing gap concerning the supports of the wavelets used in Eq. (2.12), and the treatment of integer smoothness is not fully justified. The result is plausible and likely repairable, but the proof is currently incomplete.

major comments (2)

[Section 2.1, Eqs. (2.12), (2.26)-(2.29)] The factorization dνθ/dx = ∏_k (1 + θ_k n^{-1/2} h_{Jk}(x)) is asserted 'due to the separation of support for wavelets,' but standard compactly supported orthonormal wavelet bases at a fixed scale do not have pairwise disjoint supports; the Haar basis is disjoint but is not smooth enough for the C^β construction when β>0. The manuscript does not specify a wavelet basis with pairwise disjoint C^r elements and the required coefficient decay. This product identity is used in Eqs. (2.13)-(2.15) to factor the likelihood over k and in Step 4 to replace νθ_{-k} by μ when averaging functions of h_{Jk}(Y_i). Without the product factorization, the likelihood does not split into a product of single-coordinate factors, the telescoping TV bound does not follow, and the entire Le Cam argument collapses. The gap is likely repairable by explicitly constructing smooth zero-mean functions supported on disjoint dyadic cubes, but such a construction is not an orthonormal wavelet basis in the standard sense, so the identification of W with the Besov-type norm d_B in Step 1 would also need to be rederived for the new basis. This is a load-bearing omission rather than a cosmetic issue.
[Section 2.1, Eqs. (2.3), (2.10)-(2.11)] Proposition 2.1 states the Besov-Hölder equivalence B^{β,∞}_∞ = C^β only for β not an integer, while Theorem 1 claims the full range β ≥ 0. In Step 2 the text asserts 'dνθ/dx ∈ B^{β,∞}_1 ⊆ C^β' without proof. For integer β this inclusion is not covered by the stated proposition, and it depends on the nonstandard definition of C^β in Eq. (1.4), where β - ⌊β⌋ = 0. Since the lower bound for integer smoothness is part of the theorem, the embedding and the convention for Hölder regularity at integer exponents must be stated and proved, or the theorem must be restricted to non-integer β. This issue is separate from the disjoint-support gap but also affects the validity of the hard-instance construction for the full parameter range.

minor comments (5)

[Section 2.1, notation] The notation for the spaces d_B^{γ,p}_q is inconsistent: the printed text mixes the symbol ∞ printed as 8 with subscripts and superscripts, making the definition of d_B^{γ,∞}_1 versus d_B^{γ,∞}_∞ hard to parse. Please define the Besov norm once with unambiguous indices and use that notation consistently throughout.
[References] The reference to 'Tribel' should be 'Triebel'; this typo appears both in the text and in the bibliography entry.
[Section 2.1, Step 2, Eq. (2.7)] The notation 'τ — 1' is informal; please state explicitly that τ = 1 or that any fixed positive τ works after rescaling.
[Section 2.1, Step 2, nonnegativity of νθ] The proof that dνθ/dx ≥ 1 − √(2^{dJ}/n) implicitly uses a sup-norm bound on the functions h_{Jk} that is never stated. Please state the normalization and sup-norm bound for the chosen basis or family of functions.
[Section 2.1, Step 6, Eq. (2.39)] The expression 'inf_{pTn}' appears to be a typo for 'inf_{\hat T_n}'; please correct it.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower bound is built from explicit hard instances and the external Lepski et al. moment-matching lemma, and the upper bound is derived in the text rather than assumed.

full rationale

The paper's central claim is the minimax lower and upper bounds in Theorem 1. The lower bound is not circular: it constructs explicit hard instances νθ = μ + n^{-1/2} Σ θ_k h_{Jk}, invokes the moment-matching measure pair q0, q1 from Lepski et al. (1999) as Proposition 2.2, and then bounds the total variation separation of the induced composite hypotheses by a telescoping argument. The target rate emerges from the explicit choice K ≈ log n / log log n and from the separation |E_{q0}|θ| − E_{q1}|θ|| ≈ K^{-1}, not from any fitted constant that is later reported as a prediction. The upper bound is also derived in Section 2.2 for a wavelet-threshold plug-in estimator; the references to Liang (2018), Singh et al. (2018), and Weed and Berthet (2019) are acknowledgments that the technique is known, not load-bearing substitutions for the displayed calculation. The Besov–Hölder embedding is attributed to Triebel and Donoho et al., which are external references. The skeptical concerns about the integer-β Besov–Hölder statement and the disjoint-support factorization of Eq. (2.12) are mathematical correctness or gap issues, not circularity: they do not reduce the theorem's conclusion to its own assumptions. Thus no circular step is present, and the score is 0.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

No data-fitted parameters appear in the paper; the listed constants are proof-construction choices. The statistical assumptions are imported from the wavelet, Besov, and Lepski et al. literature rather than derived in the note.

free parameters (4)

K = c/2 * log n / log log n
Moment-matching order in the lower bound; chosen to make the total variation bound vanish while keeping the separation in E|theta| of order K^{-1}. Proof construction, not data-fitted.
J = 2^{dJ} ~ n^{1/(1+2beta/d)}
Wavelet resolution in both bounds; balances variance and bias terms. Standard minimax bandwidth choice.
tau = 1
Support bound for the coefficient priors; set to keep constructed densities nonnegative. Any sufficiently small constant works.
c = >2
Free exponent in choosing K; makes the two hypothesis mixtures asymptotically indistinguishable.

assumptions (4)

standard math Wavelet basis on [0,1]^d with disjoint supports at each scale, L2 normalization, and vanishing moments.
Used in Eq. (2.10)-(2.12) to construct hard densities and to factor the likelihood as a product over coefficients.
domain assumption Besov-Holder embedding B^{beta,8}_8 = C^beta for beta not an integer, with B^{1,8}_8 containing Lip and B^{1,8}_1 contained in Lip for beta = 1.
Proposition 2.1 (Eq. 2.3) ensures constructed densities lie in G_beta. Extension to all integer beta is asserted without proof.
standard math Lepski et al. moment-matching lemma: for any K and tau there exist symmetric q0, q1 on [-tau,tau] matching moments up to 2K and with |E_q1|theta| - E_q0|theta|| = 2 kappa K^{-1} tau.
Imported as Proposition 2.2; drives the log log n / log n factor in the lower bound.
standard math Wasserstein-1 dual representation W1(mu,nu) = sup_{f Lip <= 1} integral f d(mu-nu).
Used throughout to relate W to the Besov surrogate norms.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the Minimax Optimality of Estimating the Wasserstein Metric." pith.science (2026). https://pith.science/paper/4GB5KMJM

@misc{pith2026190810324,
  author       = {Pith},
  title        = {Pith review of: On the Minimax Optimality of Estimating the Wasserstein Metric},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4GB5KMJM}},
  note         = {Machine review of arXiv:1908.10324}
}

abstract

We study the minimax optimal rate for estimating the Wasserstein-$1$ metric between two unknown probability measures based on $n$ i.i.d. empirical samples from them. We show that estimating the Wasserstein metric itself between probability measures, is not significantly easier than estimating the probability measures under the Wasserstein metric. We prove that the minimax optimal rates for these two problems are multiplicatively equivalent, up to a $\log \log (n)/\log (n)$ factor.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 12 canonical work pages

[1]

Estimating integrated squared density derivatives: sharp best order of convergence estimates

Peter J Bickel and Yaacov Ritov. Estimating integrated squared density derivatives: sharp best order of convergence estimates. Sankhy \=a : The Indian Journal of Statistics, Series A , pages 381--393, 1988

work page 1988
[2]

Some regularity properties of solutions of monge ampere equation

Luis A Caffarelli. Some regularity properties of solutions of monge ampere equation. Communications on pure and applied mathematics, 44 0 (8-9): 0 965--969, 1991

work page 1991
[3]

The regularity of mappings with a convex potential

Luis A Caffarelli. The regularity of mappings with a convex potential. Journal of the American Mathematical Society, 5 0 (1): 0 99--104, 1992

work page 1992
[4]

Boundary regularity of maps with convex potentials--ii

Luis A Caffarelli. Boundary regularity of maps with convex potentials--ii. Annals of mathematics, 144 0 (3): 0 453--496, 1996

work page 1996
[5]

Minimax quadratic estimation of a quadratic functional

David L Donoho and Michael Nussbaum. Minimax quadratic estimation of a quadratic functional. Journal of Complexity, 6 0 (3): 0 290--323, 1990

work page 1990
[6]

Density estimation by wavelet thresholding

David L Donoho, Iain M Johnstone, G \'e rard Kerkyacharian, and Dominique Picard. Density estimation by wavelet thresholding. The Annals of Statistics, pages 508--539, 1996

work page 1996
[7]

The speed of mean glivenko-cantelli convergence

Richard Mansfield Dudley. The speed of mean glivenko-cantelli convergence. The Annals of Mathematical Statistics, 40 0 (1): 0 40--50, 1969

work page 1969
[8]

On estimation of the l r norm of a regression function

Oleg Lepski, Arkady Nemirovski, and Vladimir Spokoiny. On estimation of the l r norm of a regression function. Probability theory and related fields, 113 0 (2): 0 221--253, 1999

work page 1999

Show all 16 references

[9]

How well can generative adversarial networks learn densities: A nonparametric view

Tengyuan Liang. How well can generative adversarial networks learn densities: A nonparametric view. arXiv preprint arXiv:1712.08244, 2017

2017 arXiv
[10]

On how well generative adversarial networks learn densities: Nonparametric and parametric results

Tengyuan Liang. On how well generative adversarial networks learn densities: Nonparametric and parametric results. arXiv preprint arXiv:1811.03179, 2018

2018 arXiv
[11]

On minimax optimality of estimating the adversarial losses

Tengyuan Liang and Veeranjaneyulu Sadhanala. On minimax optimality of estimating the adversarial losses. Technical report, University of Chicago, 2019

2019
[12]

Nonparametric density estimation under adversarial losses

Shashank Singh, Ananya Uppal, Boyue Li, Chun-Liang Li, Manzil Zaheer, and Barnab \'a s P \'o czos. Nonparametric density estimation under adversarial losses. In Advances in Neural Information Processing Systems, pages 10225--10236, 2018

2018
[13]

Theory of interpolation, functional spaces and differential operators

H Tribel. Theory of interpolation, functional spaces and differential operators. 1980

1980
[14]

Optimal transport: old and new, volume 338

C \'e dric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008

2008
[15]

Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance

Jonathan Weed and Francis Bach. Sharp asymptotic and finite-sample rates of convergence of empirical measures in wasserstein distance. arXiv preprint arXiv:1707.00087, 2017

2017 arXiv
[16]

Estimation of smooth densities in wasserstein distance

Jonathan Weed and Quentin Berthet. Estimation of smooth densities in wasserstein distance. arXiv preprint arXiv:1902.01778, 2019

1902 arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Estimating integrated squared density derivatives: sharp best order of convergence estimates

Peter J Bickel and Yaacov Ritov. Estimating integrated squared density derivatives: sharp best order of convergence estimates. Sankhy \=a : The Indian Journal of Statistics, Series A , pages 381--393, 1988

work page 1988

[2] [2]

Some regularity properties of solutions of monge ampere equation

Luis A Caffarelli. Some regularity properties of solutions of monge ampere equation. Communications on pure and applied mathematics, 44 0 (8-9): 0 965--969, 1991

work page 1991

[3] [3]

The regularity of mappings with a convex potential

Luis A Caffarelli. The regularity of mappings with a convex potential. Journal of the American Mathematical Society, 5 0 (1): 0 99--104, 1992

work page 1992

[4] [4]

Boundary regularity of maps with convex potentials--ii

Luis A Caffarelli. Boundary regularity of maps with convex potentials--ii. Annals of mathematics, 144 0 (3): 0 453--496, 1996

work page 1996

[5] [5]

Minimax quadratic estimation of a quadratic functional

David L Donoho and Michael Nussbaum. Minimax quadratic estimation of a quadratic functional. Journal of Complexity, 6 0 (3): 0 290--323, 1990

work page 1990

[6] [6]

Density estimation by wavelet thresholding

David L Donoho, Iain M Johnstone, G \'e rard Kerkyacharian, and Dominique Picard. Density estimation by wavelet thresholding. The Annals of Statistics, pages 508--539, 1996

work page 1996

[7] [7]

The speed of mean glivenko-cantelli convergence

Richard Mansfield Dudley. The speed of mean glivenko-cantelli convergence. The Annals of Mathematical Statistics, 40 0 (1): 0 40--50, 1969

work page 1969

[8] [8]

On estimation of the l r norm of a regression function

Oleg Lepski, Arkady Nemirovski, and Vladimir Spokoiny. On estimation of the l r norm of a regression function. Probability theory and related fields, 113 0 (2): 0 221--253, 1999

work page 1999