[yaser]

Originally Posted by diado

I've read the thread here, but still being confused
After using the union bound, we get the sum of individual terms and apply Hoeffding's inequality to each of them. Why is it valid? Aren't they still the multiple bins cases? It seems to me that they transfrom from multiple bins to single bin after using the union bound, but I don't know why.

Thanks!

Each term involves one fixed bin (hypothesis), so Hoeffding applies to it by itself, irrespective of what happens to the others. What the union bound does is to get the answer for the multiple bins if you know what happens to each bin by itself.