Problem 1.3 c

[henry2015]

||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]

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

[henry2015]

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.

Thanks in advance.