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).
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.