@cardinal Thanks for the pointer to U-statistic. The function is basically a V-statistic (in this case, it is same as the U-statistic barring a normalization factor). The results for the concentration of U-statistics (and V-statistics) generally show that $\epsilon \sim O(1/\sqrt{n})$ but can be improved to $O(1/n)$ at best with Berstein style results. It appears that I might not be able to do better than $\epsilon \sim O(1/n)$.