Estimating Certain Integral Probability Metric (IPM) is as Hard as Estimating under the IPM
This is an incremental theoretical result for researchers in statistics and machine learning, clarifying computational hardness in metric estimation.
The paper tackles the problem of estimating Integral Probability Metrics (IPMs) between unknown probability measures from samples, showing that estimating the IPM is nearly as hard as estimating the measures themselves under the IPM, with minimax optimal rates differing only by a log-log/log factor.
We study the minimax optimal rates for estimating a range of Integral Probability Metrics (IPMs) between two unknown probability measures, based on $n$ independent samples from them. Curiously, we show that estimating the IPM itself between probability measures, is not significantly easier than estimating the probability measures under the IPM. We prove that the minimax optimal rates for these two problems are multiplicatively equivalent, up to a $\log \log (n)/\log (n)$ factor.