Thanks for adding the reference. Are you sure McDiarmid’s inequality applies in the online learning case, though? The inequality you wrote down looks like a uniform convergence result, which as far as I’m aware still required an i.i.d. assumption somewhere (although uniform convergence results are also super-awesome; I was even considering including them in my post but removed them due to length reasons).
What he doesn’t tell you is that myth 5 (online learning) applies McDiarmid’s_inequality to derive the more precise bound
%20%14\le%20R_{emp}(f_n)%20+%20\sqrt{log(N)%20+%20log(1/\delta)\over{2n}}%0A)R is the real regret, R_emp the empirical regret (measured) and delta is the variance above.
This is derived e.g. in Introduction to Statistical Learning Theory, 2004, Bousquet et al
And you can get even better convergence if you know more about the distribution e.g. its VC dimension (roughly how difficult it is to decompose).
EDIT: LaTeX math in comment fixed.
Thanks for adding the reference. Are you sure McDiarmid’s inequality applies in the online learning case, though? The inequality you wrote down looks like a uniform convergence result, which as far as I’m aware still required an i.i.d. assumption somewhere (although uniform convergence results are also super-awesome; I was even considering including them in my post but removed them due to length reasons).
Yes the formula is for the i.i.d case. See section 3.4 in the ref.