<p>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})$.</p>

<p>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): <a href="https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf" rel="nofollow">https://www.cs.princeton.edu/~arora/pubs/MWsurvey.pdf</a></p>

CC BY-SA 3.0
2015-12-24T01:38:39.450Z
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?
Neal Young
CC BY-SA 3.0
2015-12-24T22:53:58.527Z
@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...
usul
CC BY-SA 3.0
2015-12-23T02:29:49.900Z
2015-12-23T02:29:49.900Z
usul
<p>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.</p>

<p>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.</p>

<p>In the classic <a href="https://en.wikipedia.org/wiki/Weighted_Majority_Algorithm">Weighted Majority</a> algorithm, the algorithm makes $O(\log n + m)$ mistakes, where $m$ is the number of mistakes of the best expert.</p>

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

<p>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.</p>

<p>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|$$</p>

<blockquote>
  <p><strong>How would you minimize the regret, compared to $E$?</strong></p>
</blockquote>

<hr>

<p>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.</p>

CC BY-SA 3.0
2015-12-22T20:51:17.543Z
I think you are looking for the Exponentiated Gradient method: https://users.soe.ucsc.edu/~manfred/pubs/J36.pdf
Lev Reyzin
CC BY-SA 3.0
2016-03-22T03:56:13.103Z
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.
Thomas Steinke
CC BY-SA 3.0
2016-03-22T08:03:21.240Z
@Thomas - thought about it a while back. You'd have to set $N=n^{\Theta(n^2)}$, which is quite large: https://oeis.org/A000609.
R B
CC BY-SA 3.0
2016-03-22T17:18:26.183Z
$O(n \sqrt{T \log n})$ errors is a good start. What are you aiming for?
Thomas Steinke
CC BY-SA 3.0
2016-03-23T11:18:41.757Z
@Thomas - it's indeed a start. I was hoping for a $o(n\sqrt T)$ algorithm, and believe it should be feasible.
R B
CC BY-SA 3.0
2016-09-18T07:52:20.800Z
You need to compute the Littlestone dimension of your hypothesis class (the set of all weight vectors). See [this](http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf), page 291 for definition of Littlestone dimension and page 295 for the associated regret bound.
Vanessa
<ds.algorithms><machine-learning>
Competing against an optimal weighted majority in experts algorithm
R B
# Competing against an optimal weighted majority in experts algorithm

(Asked by: username_0 on 2015-12-22)

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](https://en.wikipedia.org/wiki/Weighted_Majority_Algorithm) 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.

**Tags:** ds.algorithms, machine-learning

> **Comments:**
> **username_1**: I think you are looking for the Exponentiated Gradient method: https://users.soe.ucsc.edu/~manfred/pubs/J36.pdf  
> **username_2**: 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.  
> **username_0**: @Thomas - thought about it a while back. You'd have to set $N=n^{\Theta(n^2)}$, which is quite large: https://oeis.org/A000609.  
> **username_2**: $O(n \sqrt{T \log n})$ errors is a good start. What are you aiming for?  
> **username_0**: @Thomas - it's indeed a start. I was hoping for a $o(n\sqrt T)$ algorithm, and believe it should be feasible.  
> **username_3**: You need to compute the Littlestone dimension of your hypothesis class (the set of all weight vectors). See [this](http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/understanding-machine-learning-theory-algorithms.pdf), page 291 for definition of Littlestone dimension and page 295 for the associated regret bound.  

---

## 1 answers

### Answer by username_4 on 2015-12-23. Score: 1

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>

> **Comments:**
> **username_5**: Usul, when you say "regret compared to the best distribution on experts", is that what username_0 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 username_0'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?  
> **username_4**: @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...  

---

