אי שוויון לא מובן שיעור 4

אי שוויון לא מובן שיעור 4

Yuval Lewi 30 Mar 2016 18:32

Multiplicative weight בשיעור הרביעי הוכחנו חסם על.
בהוכחה הזו היה מעבר מאי שוויון עם לוגריתם לפיתוח טור טיילור שלו.
לא הצלחתי להבין למה מעבר זה חוקי ואשמח אם תוכלי להרחיב את החלק הזה בהוכחה,

תודה

Re: אי שוויון לא מובן שיעור 4

Israela 01 Apr 2016 09:17

I'm not sure that I understood your question.
In the proof you bounded ln(1-\epsilon) using its Taylor expansion around 0.
Does that answer your question? If not, please be more specific.

Re: אי שוויון לא מובן שיעור 4

Yuval Lewi 02 Apr 2016 07:22

עשינו את הדבר הבא:
OPT * ln(1- eps) <= ln(n) + sum(ln(1- eps*ALG^t))
ואמרנו שמפיתוח טיילור נובע כי:
OPT*(-eps-eps^2) <= ln(n) + sum(-eps*ALG^t)

למה הדבר הזה חוקי? הרי לא ברור שהקטנו צד אחד של הא"ש ואת השני הגדלנו.
ככל הנראה רק הגדלנו את הא"ש בשני הצדדים ואפילו לא באותו קבוע

Re: אי שוויון לא מובן שיעור 4

Israela 02 Apr 2016 18:39

I'm not sure what is the context, but I'll try to answer.

For the left side:
ln(1-eps) = - eps - (eps^2)/2 - O(n^4) >= - eps - eps^2.
(note that esp^2 is divided by 2).

For the right side:
ln(1-eps*A) = - eps*A - O((eps*A)^2) <= - eps*A.

Does that fit?