Multiplicative Weight Updates

Problem

Let $X_1, X_2, ..., X_T$ be a sequence of $T$ binary values. We predict at each $t \in [T]$, the value of $X_t$. Our predictions are based on the ones from a set of $n$ experts. At each time $t \in [T]$, each expert $i \in [n]$ generates a prediction $p_i^t$ of $X_t$. Based on the experts' predictions, we make our own $p_A^t$. The goal to minimize the number of wrong predictions/mistakes.

Measurement of Error

The first question is how good can we do?

Define

1. $L_i^t:$ the indicator for the expert $i$ making a mistake at round $t$.
2. $L_i = \sum_{t \in [T] } L_i^t:$ the total number of mistakes expert $i$ makes.
3. $L_A:$ the mistakes by our algorithm (denoted as $A$).

Ideally, we would like achieve as few mistakes as

However, this is impossible. To see this, let $\{ X_t , t \in [T] \}$ be independent Bernoulli random variables with equal probability taking $1$ and $0$. Whatever our strategy is, the expected number of mistakes is $T / 2$. On the other hand, it is possible that $\sum_{t \in [T] } \min_{i \in [n]} L_i^t = 0$.

Despite this negative result, there is hope to achieve as few mistakes as the best expert (up to some constant), that is

Algorithms

Follow the Majority

We start with an easy case where an expert who always predicts correctly. In such case, we can maintain a set of experts who do not make any mistake so far. Each time we make a decision, we follow the majority of the set.

Theorem. If there is a perfect expert, the algorithm Follow the Majority achieves

$$L_A \le \min_{i \in [n] } L_i + \log n.$$

Algorithm 1. Follow the Majority

1. Let $E_0 \leftarrow [n]$ be the set of all experts.
2. For $t \leftarrow 1$ to $T$
3. $\qquad$ Let $S$ be the subset of $E_{t - 1}$ that predicts 0 at time $t$.
4. $\qquad$ Let $\bar S$ be the subset of $E_{t - 1}$ that predicts 1 at time $t$.
5. $\qquad$ If $|S| > |\bar S|$, then predict $0$ ($p_A^t \leftarrow 0$);
6. $\qquad\qquad\qquad\quad\,$ else predict $1$ ($p_A^t \leftarrow 1$).
7. $\qquad$ Reveal $X_t$.
8. $\qquad$ If $X_t = 0$, then $E_t \leftarrow S$;
9. $\qquad\qquad\qquad\,$ else $\,E_t \leftarrow \bar S$.

The key observation is that the set we maintain halves each time we make a mistake. Halving the set can happen at most $\log n$ times, as there are only $n$ experts. Further, we need the assumption of a perfect expect, as otherwise $E_t$ can be empty.

Proof. Let $M$ be the number of mistakes the algorithm makes. Each time it makes a mistake, the size of $E_{t}$ shrink by half. Hence,

The first inequality follows from the existence of perfect expert. It concludes that

$\square$

Follow the Majority With Reset

Without the assumption of perfect expert, one simple modification we can make to Follow the Majority is resetting $E_t = [n]$, if it is assigned an empty set. We call such an algorithm Follow the Majority With Reset.

Theorem. If there isn't a perfect expert, the algorithm Follow the Majority With Reset achieves

$$L_A \le \left( \min_{i \in [n] } L_i + 1 \right) \cdot \log n.$$

Proof. As analysed before, between two consecutive resets of $E_t$, the algorithm makes at most $\log n$ mistakes while the best expert makes at least one mistake. Therefore,

$\square$

Follow the Weighted Majority

The previous algorithm forgets the historical performance of the experts each time it resets $E_t$, which might contain helpful information. To fix this, we assign each expert $i$ a weight $w_i^t$, follow the weighted majority at time $t$.

Theorem. The algorithm Follow the Weighted Majority achieves

$$L_A \le 2.41 \cdot \left( \min_{i \in [n]} L_i + \log n \right).$$

Algorithm 3. Follow the Weighted Majority

1. Set $w_i^1 \leftarrow 1, \forall i \in [n].$
2. For $t \leftarrow 1$ to $T$
3. $\qquad$ Let $S$ be the set of experts who predict $0$.
4. $\qquad$ Let $\bar S$ be the set of experts who predict $1$.
5. $\qquad$ If $\sum_{i \in S} w_i^t > \sum_{i \in \bar S} w_i^t$, then predict $0$ ($p_A^t \leftarrow 0$);
6. $\qquad\qquad\qquad\qquad\qquad\qquad$ else predict $1$ ($p_A^t \leftarrow 1$).
7. $\qquad$ Reveal $X_t$.
8. $\qquad$ For each expert $i \in [n]$
9. $\qquad\qquad$ If it predicts wrong then $w_i^{t + 1} \leftarrow w_i^t / 2$
10. $\qquad\qquad$ $\qquad\qquad\qquad\quad$ else $w_i^{t + 1} \leftarrow w_i^t$

Intuition on Why the Algorithm Works. Assume that expert $i$ is the one that minimizes the loss $L_i$. At round $T$, its weight $w_i^T$ is given by $(1/2)^{L_i}$. The total weight at round $T$, denoted by $W^T$, can be lower bounded using $w_i^T$.Specifically, if $W^t$ becomes too small for some $t \in [T]$, then $w_i^t$ will constitute the majority of the weights. As a result, the algorithm should not incur significantly more errors than expert $i$. This ensures that the algorithm’s performance is competitive with the best expert while adapting over time.

Proof. Let $W^t = \sum_{i \in [n] } w_i^t$. Each round $t$ the algorithms make a mistake, the sum of weights of experts who predict wrong is at least $0.5 \cdot W^t$. Such weights halve at this round. Hence

Fix an $i \in [n]$. Recall $L_i$ is the number of mistakes experts $i$ makes throughout the $T$ rounds. It follows that,

which implies

$\square$

Remark. It is not necessary to halve an expert's weight when it makes a mistake. We can decrease it by any factor $(1 - \epsilon)$ for $\epsilon \in (0, 1)$. In such case, we get

We have used the fact that $\ln(1 - \epsilon ) \ge - \epsilon - \epsilon^2$ for $\epsilon \in [0, 2 / 3]$.

Multiplicative Weight Updates

We are in good shape so far. Let's extend the problem to more general settings. In this cases, the experts interact with the environment in round-robin fashion. At each round $t$,

1. The expert $i$ performs action, termed $a_i^t$.
2. The environment returns the loss of performing $a_i^t$, denoted as $\ell_i^t \in [0, 1]$.

Note that there is no restriction of the experts' actions and their losses (as long as they are within $[0, 1]$). We will present an algorithm, called Multiplicative Weight Update, which is almost as good as the best expert.

Theorem. The algorithm Multiplicative Weight Update achieves

$$L_A \le \min_{i \in [n] } L_i + 2 \sqrt{ T \ln n },$$

where $L_i \doteq \sum_{t \in [T] } \ell_i^t$ is the loss of expert $i$.

This implies that the average expected loss converges at a rate of $\sqrt{1 / T}$ to the best one.

Algorithm 4. Multiplicative Weight Update

1. Set $w_i^1 \leftarrow 1, \forall i \in [n]$.
2. For $t \leftarrow 1$ to $T$
3. $\qquad$ Let $W^t = \sum_{i \in [n] } w_i^t$.
4. $\qquad$ Follow action $a_i^t$ with probability $w_i^t / W^t$.
5. $\qquad$ For each expert $i \in [n]$:
6. $\qquad\qquad$ $w_i^{t + 1} \leftarrow w_i^t \cdot (1 - \epsilon \cdot \ell_i^t)$

At a high level, at each round,

1. the algorithm follows expert $i$ with probability proportional to $w_i^t$.
2. the weight $w_i^t$ is decreased proportionally to $\ell_i^t$.

Proof. Let $\ell_A^t$ be the loss of the algorithm at round $t$, and $L_A \doteq \sum_{t \in [T] } \ell_A^t$.

Claim 1. $\,\ln W^{T + 1}$ is inversely proportional to $\mathbb{E} \big[ L_A \big]$.

Observe

By the update rule of the $w_i$'s, we see

By induction and noting that $W^1 = n$, we have

Claim 2. $\,\ln W^{T + 1}$ is lower bounded by $\sum_{t \in [T] } \ln (1 - \epsilon \cdot \ell_i^t)$.

For each expert $i \in [n]$, its final weight is given by

Noting that $w_i^{T + 1} \le W^{T + 1}$ proves the claim.

Putting the Claims Together. For each $i \in [n]$, we have

Therefore,

Via the fact that $\ln(1 - \epsilon ) \ge - \epsilon - \epsilon^2$ for $\epsilon \in [0, 2 / 3]$, we know that $\forall i \in [n]$,

Dividing both sides by $\epsilon$,

There are various ways to upper bound $\sum_{i \in [T] } (\ell_i^t)^2$. Naively, we observe that $(\ell_i^t)^2 \le \ell_i^t$, since $\ell_i^t \in [0, 1]$. Therefore,

Setting $\epsilon = \sqrt{ (\ln n) / T }$, we get

Remark: if we know the value of $\min_{i \in [n]} L_i$, or we can guess $\Theta \left( \min_{i \in [n]} L_i \right)$, then we can achieve

$\blacksquare$

Reference

[1]. Arora, Sanjeev, Elad Hazan, and Satyen Kale. "The multiplicative weights update method: a meta-algorithm and applications." Theory of computing 8, no. 1 (2012): 121-164.

[2] Aaron Roth, “The Polynomial Weights Algorithm”, NETS 412: Algorithmic Game Theory