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.
Why?
Such a control on the variance is often the main ingredient in obtaining sharperconcentration results.
to be noted for future ref.
hese have the property that∀t, ∀w ∈ S, E [f (w; Zt)] = F (w)
Why isn't this obvious, when is this not true?
But if we look at the difference, we are able to get sharperconcentration.
why?
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.
Look this up, build a flow of the problem from beginning.