Minimax statistical learning with Wasserstein distances
As opposed to standard empirical risk minimization (ERM), distributionally robust optimization aims to minimize the worst-case risk over a larger ambiguity set containing the original empirical distribution of the training data. In this work, we describe a minimax framework for statistical learning with ambiguity sets given by balls in Wasserstein space. In particular, we prove generalization bounds that involve the covering number properties of the original ERM problem. As an illustrative example, we provide generalization guarantees for transport-based domain adaptation problems where the Wasserstein distance between the source and target domain distributions can be reliably estimated from unlabeled samples.
This paper studies the problem of minimizing the worst-case risk over a Wasserstein ball around the underlying distribution. General risk upper bounds are provided for the procedure which minimizes the error over the Wasserstein ball around empirical distribution, which directly leads to excess risk results for Lipschitz classes. The paper also applies this result for specific model classes such as simple neural network class, RKHS, etc. And the results are also applied to domain adaptation.  The key idea in the proof of main theorems (Thm 1~3) is based on the strong duality for distributional robust stochastic optimization. Once we write it in dual form, standard Dudley chaining bounds lead to the desired result. This part is very simple but there're something smart happening here: we only need to consider the distribution class within a Wasserstein ball around empirical distribution, and to compare with best local minimax risk within this class, we don't need to pay for the constant depending on $\rho$ which does not go to zero with n.  However, since the proof of this abstract result is pretty standard, and the key ingredient (duality) is directly from previous works, I doubt if the contribution is strong enough for NIPS. The author also provides examples, but they are simply plugging existing covering number results into the bound. It would be much better if the authors can illustrate through some examples about the surprising properties of distributional robust setup. The domain adaptation part seems even less satisfactory. An important point in previous sections is that, the risk does not depend on Wasserstein distance between empirical measure and the underlying measure, which has exponential dependence on dimension. But the domain adaptation part gets back this dependence, losing the merits of previous bounds.  Detailed comments: In Theorem 2, the excess risk blows up when $\rho$ goes to zero, for $p>1$. This contradicts the intuition that less adversarial noise makes the problem easier. And the choice of $\lambda$ and the resulting risk cannot be always optimal.