n contrast to the previous reduction, smoothing cannot be obtainedby simple addition of a smooth (or any other) function. Instead, we needa smoothing operation. The one we describe is particularly simple andamounts to taking a local integral of the function. More sophisticated,but less general, smoothing operators exist that are based on the Moreau-Yoshida regularization, see bibliographic section for more details.

Such a control on the variance is often the main ingredient in obtaining sharperconcentration results.

hese have the property that∀t, ∀w ∈ S, E [f (w; Zt)] = F (w)

But if we look at the difference, we are able to get sharperconcentration.

This paper continues the line of research initiated by several researchers [Littlestone, 1989, Cesa-Bianchi et al., 2004, Zhang, 2005, Cesa-Bianchi and Gentile, 2008] which looks at how to convertonline algorithms into batch algorithms with provable guarantees.