The Method of Averaged Bounded Differences
Sometimes, the function f for which we are trying to show a concentration result does not satisfy the conditions needed to apply the simple method of bounded differences: the Lipschitz coefficients are simply too large in the worst case. The function is not “smooth”. In such cases, the method of average bounded differences can be deployed, needing only an averaged smoothness condition. That is, we need a bound of the form
or the similar
At first glance, getting a handle ...