Multiplicative Weights Flashcards
Describe the problem of Multiplicative Weights
- Every day it should be decided whether to invest in a share
- In each day t, expert i, predicts either 1 - to invest, or -1 to not invest.
- At the end of the day they find out whether they should have invested or not.
condition 1: one of the experts is never wrong.
algorithm: every day we listen to the majority. We never listen again to someone who’s been wrong.
Prove this algorithm is wrong at most log(n) times
In each day in which the algorithm is wrong, most of the experts are wrong, thus the number of expert is reduced by at least half. After log(n) mistakes we’re left with the always-right expert.
Condition 2: all the experts are wrong. we wish to mistake number of time proportional to the best expert - the one who mistakes least often.
Let’s denote M - the number of mistakes of the best expert.
Claim: there exists an algorithm which has at most (m+1)(log(n) + 1) mistakes.
Describe the weighted experts algorithm
Prove
describe the randomized weighted majority
What is the input for the randomized weighted majority, how do we usually percieve the adversary?
The input for the algorithm is:
- The choices of the experts on each day, {Xi,t}
- The results {0^t}
- Usually we percieve the adversary as the one who chooses the worst input for the algorithm
For randomized weighted majority, describe the two types of adversaries
- Oblivious - an adversary who doesn’t see the the actual results of each probability of the algorithm, but merely its code.
- Adaptive: the adversary at step t sees the result of the probabilites for the previous steps, and then he chooses 0^t, {Xi,t}
Generalization of MW.
Describe it
Each expert has a portfolio. On every Shekel that he invests he loses by the end of day t, Lt = {-1, 0 ,1}.
I guess -1 or 1 is determined by the day, or the by choice
How are we going to invest our money using the n experts?
First, write the algorithm
What is the probability of having gain 0 when T is even and Li is uniformly distributed over {0,1}?
What is the probability of having gain i?
what is the probability of having a gain/loss>= sqrt(kT)
Define R^T, regret at the end of the algorithm
Lower bound the expected value of R^T
