Quote:
Originally Posted by eakarahan
Ref: Page 22, Chp 1, last paragraph.
What are the assumptions that are needed to prove Hoeffding's inequality that no longer hold if we are allowed to change h after we generate the data set? Please give a proof of Hoeffding inequality in this context, explicitly showing these assumptions.

You can refer to homework e/2 of my current class
http://www.csie.ntu.edu.tw/~htlin/co...oc/hw0_5_e.pdf
for guided steps of the proof. The proof needs the distribution that generates the random variable (in the problem
or in the learning context
) to be "fixed" before starting the proof, and of course
needs to come independently from the distribution. If a different
is used,
is different, and if many different
are considered altogether, we need to be cautious about the independence assumption. Hope this helps.