  We propose a "decomposition method" to prove non-asymptotic bound for the
convergence of empirical measures in various dual norms. The main point is to
show that if one measures convergence in duality with sufficiently regular
observables, the convergence is much faster than for, say, merely Lipschitz
observables. Actually, assuming $s$ derivatives with $s < d/2$ ($d$ the
dimension) ensures an optimal rate of convergence of $1/\sqrt{n}$ ($n$ the
number of samples). The method is flexible enough to apply to Markov chains
which satisfy a geometric contraction hypothesis, assuming neither stationarity
nor reversibility, with the same convergence speed up to a power of logarithm
factor. Our results are stated as controls of the expected distance between the
empirical measure and its limit, but we explain briefly how the classical
method of bounded difference can be used to deduce concentration estimates.
