In statistics and learning one usually has access to \(N\)  samples \((x_1,\ldots ,x_N)\)  and \((y_1,\ldots ,y_N)\)  drawn from inaccessible probabilities \(\)  and \(\) .
A problem is to design finite estimators \(_N(x_1,\ldots ,x_N)\)  and \(_N(y_1,\ldots ,y_N)\)  of \((,)\)  such that \((_N,_N)\)  is a good approximation of \((,)\) .
An issue is that OT suffers from a curse of dimensionality with the naive plugin estimator [1]}, i.e. one has \([|(_N,_N) - (,)|]=O(N^{-1/d})\) , where \(_N=\tfrac{1}{N}\sum _{i=1}^N _{x_i}\)  and \(_N=\tfrac{1}{N}\sum _{i=1}^N _{y_i}\) .
The rate on \(N\)  depends on the dimension, so that the number of samples needed to reach a given tolerance grows exponentially fast with the dimension.
Furthermore, it is proved in [2]} that without any additional assumption, the above empirical estimators are optimal in the sense that there exists no other estimator of the form \(_N(x_1,\ldots ,x_N)\)  and \(_N(y_1,\ldots ,y_N)\)  yielding a better rate than \(O(N^{-1/d})\) .
