Uniform concentration and symmetrization for weakly interacting statistics

The method which uses Rademacher or Gaussian averages to bound the expected suprema of empirical processes is extended to the case where the sample average is replaced by a nonlinear statistic. The bound is controlled by Lipschitz seminorms involving single and mixed partial differences of the function in question. Tight bounds are obtained for U-statistics, smoothened L-statistics and error functionals of l_2 regularized algorithms.