LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Chapter 1 - The Learning Problem (http://book.caltech.edu/bookforum/forumdisplay.php?f=108)
-   -   Problem 1.3 c (http://book.caltech.edu/bookforum/showthread.php?t=4648)

 henry2015 12-18-2015 03:26 AM

Problem 1.3 c

||w(t)||^2
= ||w(t-1) + y(t-1)x(t-1)||^2 <--- this is from the PLA iteration
<=(||w(t-1)|| + ||y(t-1)x(t-1)||)^2 <--- a property: ||a + b|| <= ||a|| + ||b||
= ||w(t-1)||^2 + 2y(t-1)||w(t-1)||||x(t-1)|| + y(t-1)^2||x(t-1)||^2
= ||w(t-1)||^2 + 2y(t-1)||w(t-1)||||x(t-1)|| + ||x(t-1)||^2

Now, it seems like 2y(t-1)||w(t-1)||||x(t-1)|| is somehow <= 0.

||w(t-1)||||x(t-1)|| is >= 0 tho.

hence, it seems like 2y(t-1) is somehow <= 0.

It seems like I am on the wrong track as I am not using the hint mentioned in the question at all.

Any pointer?

Thanks!

 htlin 12-19-2015 07:18 AM

Re: Problem 1.3 c

This inequality ||a + b|| <= ||a|| + ||b|| is quite loose in general and you may want to consider not using it. Hope this helps.

 henry2015 06-10-2016 02:19 AM

Re: Problem 1.3 c

Hi,

I just revisited this problem again.

If I substitute w(t-1) with x(t-1) with I could get   and then use the hint to get the answer.

However, the dimension of x and w can be more than 3. I just wonder whether there is a more generic proof.