8
$\begingroup$

In the experts problem, $n$ experts give you binary predictions on a daily basis, and you have to predict whether it's going to rain tomorrow.

That is, at day $t$, you know the past predictions of the experts, the actual weather for days $1,2,\ldots t$, and the predictions for tomorrows, and have to predict whether it will rain the next day.

In the classic Weighted Majority algorithm, the algorithm makes $O(\log n + m)$ mistakes, where $m$ is the number of mistakes of the best expert.

To me, this seems like an extremely weak promise, as it does not allow any benefit from combining predictions of several experts.

Assume that each outcome is $\{\pm 1\}$, prediction of expert $i$ on day $t$ is $p_{i,t}$, and the outcome of day $t$ is $o_t$. We can define an ``optimal weighted majority'' adversary as an optimal weight function $w\in\Delta([n])$, such that the decision made by the adversary on day $t$ is defined as $sign(w\cdot p_t)$, i.e. the weighted majority of the predictions, with respect to the vector $w$. Using this notation, the previous adversary (best expert) could only pick unit vectors.

We can then define the optimal error for days $1,2,\ldots T$ as: $$E = \frac{1}{2}\min_{w\in\Delta([n])} \sum_{t=1}^T|sign(w\cdot p_t)-o_t|$$

How would you minimize the regret, compared to $E$?

To see that this is a much more powerful adversary, consider the case of $3$ experts and $3$ days in which the outcome was always $1$. If $p_1=(1,1,-1), p_2 = (1,-1,1), p_3=(-1,1,1)$, then each expert had a mistake, but a weighted majority vector of $(1/3,1/3,1/3)$ had none.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I think you are looking for the Exponentiated Gradient method: users.soe.ucsc.edu/~manfred/pubs/J36.pdf $\endgroup$
    – Lev Reyzin ♦
    Dec 22, 2015 at 20:51
  • $\begingroup$ Multiplicative weights has error $O(\sqrt{T\log n})$ relative to the best single expert (out of $n$) over $T$ rounds. We could create $N$ "meta experts" corresponding to all possible weighted majorities and then run MW to get error $O(\sqrt{T \log N})$. Not sure how big $N$ needs to be - perhaps $N=n^{O(n)}$ suffices. $\endgroup$
    – Thomas
    Mar 22, 2016 at 3:56
  • $\begingroup$ @Thomas - thought about it a while back. You'd have to set $N=n^{\Theta(n^2)}$, which is quite large: oeis.org/A000609. $\endgroup$
    – R B
    Mar 22, 2016 at 8:03
  • $\begingroup$ $O(n \sqrt{T \log n})$ errors is a good start. What are you aiming for? $\endgroup$
    – Thomas
    Mar 22, 2016 at 17:18
  • $\begingroup$ @Thomas - it's indeed a start. I was hoping for a $o(n\sqrt T)$ algorithm, and believe it should be feasible. $\endgroup$
    – R B
    Mar 23, 2016 at 11:18

1 Answer 1

Reset to default
1
$\begingroup$

If you don't mind randomization, then standard online learning algorithms in the "online convex optimization framework" give you essentially what you ask for, in expectation. The reason is that these algorithms are required to output a distribution $w \in \Delta([n])$ on experts at each time step, suffering an expected loss equal to the expectation of picking an expert from this distribution. And they have low expected regret compared to the best distribution on experts, i.e. $O(\sqrt{\ln n / T})$.

For example, you can take the classic multiplicative weights algorithm, which is just weighted majority but picking an expert to follow with probability proportional to its "weight". This is mentioned in Arora's survey (Theorem 6): https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Usul, when you say "regret compared to the best distribution on experts", is that what R B is asking for? Isn't the standard way of using a distribution $w$ on experts to simply make fractional prediction $w\cdot p_t$ at each time $t$? Or (more or less equivalently) to predict 1 with probability $(w\cdot p_t + 1)/2$ and -1 otherwise. Then, there is always an optimal $w$ using only one expert, right? But as I understand R B's suggestion, it is slightly different: make the integer prediction: sign$(w\cdot p_t)$ at each time $t$. Is it clear this can't give substantially better predictions? $\endgroup$
    – Neal Young
    Dec 24, 2015 at 1:38
  • $\begingroup$ @NealYoung, good point, I didn't think it over that deeply. I implicitly assumed you can convexify this objective function and get good regret for it, but that could be wrong... $\endgroup$
    – usul
    Dec 24, 2015 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.