View Single Post
  #2  
Old 11-20-2012, 02:46 PM
htlin's Avatar
htlin htlin is offline
NTU
 
Join Date: Aug 2009
Location: Taipei, Taiwan
Posts: 601
Default Re: Proof of Hoeffding's inequality is required

Quote:
Originally Posted by eakarahan View Post
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 z_i or in the learning context [ y_n \neq h(\mathbf{x}_n) ]) to be "fixed" before starting the proof, and of course z_i needs to come independently from the distribution. If a different h is used, P(z) is different, and if many different h are considered altogether, we need to be cautious about the independence assumption. Hope this helps.
__________________
When one teaches, two learn.
Reply With Quote