Competing against an optimal weighted majority in experts algorithm 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.
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