Multiplicative Weights

Five forecasts, one ferry

A small ferry company has to decide every morning whether to cancel its afternoon crossing, and it has to decide before anyone knows what the sea will do. Five marine forecast services, A to E, each send a one-word call: rough or calm. In the evening the company sees what the sea did. Here are twelve days.

Looking back, C was the one to follow: wrong twice, while every other service was wrong at least seven times. But on day 1 nobody knew that, and next month a different service may be the good one, or none may be. The company wants a rule it can follow day by day that is wrong not many more times than the best service in hindsight, whatever the sea and the services do.

This is the experts problem. There are $n$ experts and $T$ rounds. In each round every expert predicts, the algorithm predicts, and then the outcome is revealed. Nothing is assumed about where the outcomes or the predictions come from: an adversary may choose them. As with the online problems of module 19, the algorithm commits before it sees the future and is judged against a benchmark that saw everything. Here the benchmark is the best single expert, with $m$ mistakes, and the algorithm's extra cost over it is its regret. A stronger benchmark, a forecaster who is right every day, is out of reach: the adversary below makes any deterministic rule wrong every day.

from fractions import Fraction as F
import math

sea = [int(c) for c in "101001010111"]                 # 1 = rough, 0 = calm
calls = {k: [int(c) for c in s] for k, s in zip("ABCDE", [
    "010000100001", "101100101010", "001001011111", "000000111010", "000000001100"])}
T, n = len(sea), len(calls)
wrong = {k: [calls[k][t] != sea[t] for t in range(T)] for k in calls}
assert {k: sum(w) for k, w in wrong.items()} == {"A": 8, "B": 7, "C": 2, "D": 7, "E": 7}

Two obvious rules

Majority vote. Call whatever most services call. It ignores their records, and on these days three or four mediocre services often agree: the vote is wrong 8 times out of 12.

Follow the leader. Call whatever the service with the fewest mistakes so far calls. It uses the records, but it puts all its trust in one service, and a later section shows that an adversary can make any deterministic rule like it wrong every day, while the better of two services is wrong only half the time.

majority = [int(2 * sum(calls[k][t] for k in calls) > n) for t in range(T)]
assert sum(majority[t] != sea[t] for t in range(T)) == 8

One case has a clean answer. If some service is known to be perfect, vote only among the services that have made no mistake yet. Each time the vote is wrong, at least half of those services were wrong and are dropped, and the perfect one never is, so the vote is wrong at most ${\log }_{2}n$ times. When nobody is perfect this drops everyone. The fix is to shrink a service that errs instead of dropping it.

Weighted majority

Give each service a weight, 1 at the start. Each morning, add up the weights of the services that say rough and of those that say calm, and call the heavier side (a tie goes to rough). Each evening, multiply the weight of every service that was wrong by $\beta =1/2$. After $m_i$ mistakes, service $i$ weighs $2^{-m_i}$.

On day 1 four services say calm, so the algorithm says calm and is wrong. A, C, D and E halve. On day 3, B (weight 1) and C (weight 1/2) say rough, against 5/4 for calm: the algorithm says rough and is right, while the plain majority is wrong. The weights of the frequent offenders fall quickly. From day 8 on, C alone outweighs the other four, so the algorithm follows C, including on day 9, when C is wrong. In all it is wrong 3 times: once more than C, and 5 times fewer than the majority.

def weights(t, beta=F(1, 2)):
    """Each service's weight at the start of day t (0-based): beta to the power of its mistakes."""
    return {k: beta ** sum(wrong[k][:t]) for k in calls}

def wm_call(t):
    w = weights(t)
    rough = sum(w[k] for k in calls if calls[k][t] == 1)
    calm = sum(w[k] for k in calls if calls[k][t] == 0)
    assert rough != calm                               # no ties on these days
    return int(rough >= calm)

wm_wrong = [t + 1 for t in range(T) if wm_call(t) != sea[t]]
assert wm_wrong == [1, 6, 9]
assert all(weights(t)["C"] > sum(weights(t).values()) - weights(t)["C"] for t in range(7, 12))
assert weights(6)["C"] < sum(weights(6).values()) - weights(6)["C"]      # not yet on day 7

Why it works: watch the total weight

Let $W$ be the total weight of all services. It starts at $n$ and never grows. The whole analysis follows it.

Proof. When the algorithm is wrong, the side it followed was wrong and carried at least half of $W$. That half is halved, so the new total is at most $W/2+W/4=3W/4$. After $M$ mistakes, $W\le n(3/4{)}^M$, and every single weight is at most $W$. $◻$

Proof. From the invariant, $2^{-m_i}\le n(3/4{)}^M$. Take ${\log }_2$ of both sides and rearrange. $◻$

On the ferry days, with $m=2$ and $n=5$, the bound allows 10 mistakes, and the algorithm made 3. The bound is a guarantee over every sequence, not a prediction for this one.

The same argument works for any penalty $\beta =1-\epsilon$. A mistake now multiplies $W$ by at most $1-\epsilon /2$, and a service with $m_i$ mistakes weighs $(1-\epsilon {)}^{m_i}$, so

$$M\le \frac{m_i\ln \frac{1}{1-\epsilon }+\ln n}{\ln \frac{1}{1-\epsilon /2}}\le 2(1+\epsilon )m_i+\frac{2\ln n}{\epsilon }$$

for $0<\epsilon \le 1/2$, using $\ln \frac{1}{1-\epsilon }\le \epsilon +{\epsilon }^2$ and $\ln \frac{1}{1-\epsilon /2}\ge \epsilon /2$. A small $\epsilon$ brings the factor close to 2, at the price of a larger additive term.

assert F(71, 256) == sum(weights(T).values())        # the total after day 12
assert F(1, 4) <= F(71, 256) <= 5 * F(3, 4) ** 3       # 2^(-m_C) <= W <= n (3/4)^M
assert math.floor((2 + math.log2(5)) / math.log2(4 / 3)) == 10
for k in range(1, 501):                                # the two logarithm facts on a grid
    e = k / 1000
    assert math.log(1 / (1 - e)) <= e + e * e and math.log(1 / (1 - e / 2)) >= e / 2

No deterministic rule beats a factor of 2

Could a cleverer deterministic rule get the factor below 2? No.

Claim. For every deterministic algorithm and every $T$, there is a sequence with two experts on which the algorithm is wrong all $T$ times and the better expert at most $\lfloor T/2\rfloor$ times.

Proof. One expert always says rough and the other always says calm. The algorithm is deterministic, so its call on each day is a function of what it has seen, and the adversary can compute it. Make the sea do the opposite. The algorithm is wrong every day. On each day exactly one of the two experts is right, so their mistakes add up to $T$, and the better one has at most $\lfloor T/2\rfloor$. $◻$

So a deterministic algorithm can be forced to $M\ge 2m$, and weighted majority's factor $2(1+\epsilon )$ is as good as a deterministic rule gets, up to the $\epsilon$. Follow the leader is deterministic, so the same adversary beats it.

def adversary_days(days):
    """The adversary against weighted majority (beta = 1/2) with two fixed experts."""
    m_rough = m_calm = mistakes = 0
    for _ in range(days):
        call = int(F(1, 2) ** m_rough >= F(1, 2) ** m_calm)    # weighted vote, tie -> rough
        mistakes += 1                                          # the sea does the opposite
        m_rough, m_calm = m_rough + (call == 1), m_calm + (call == 0)
    return mistakes, min(m_rough, m_calm)

assert adversary_days(8) == (8, 4) and adversary_days(21) == (21, 10)

Randomize: follow an expert chosen by weight

The adversary had to know the call before the sea turned. So don't let it: keep the same weights, and each day follow one expert, chosen at random with probability proportional to its weight. Now the expected number of mistakes on a day is the fraction of the weight on wrong experts.

The same idea works for any costs, not just mistakes. Let expert $i$ have a loss ${\ell }_i^t\in [0,1]$ in round $t$, and let $L_i$ be its total. The multiplicative weights algorithm (also called Hedge, or randomized weighted majority) keeps weights $w_i$, starting at 1, plays the distribution $p^t=w^t/W^t$, and after the round updates

$$w_i\leftarrow w_i(1-\epsilon {\ell }_i^t).$$

The left side is the algorithm's expected loss over its own coins, against an oblivious adversary: one that fixes the whole sequence in advance, knowing the algorithm but not its coins.

Proof. After round $t$ the total weight is

$$W^{t+1}=\sum _i{w}_i^t(1-\epsilon {\ell }_i^t)=W^t(1-\epsilon p^t·{\ell }^t),$$

and $1-x\le e^{-x}$, so after $T$ rounds $W^{T+1}\le n{e}^{-\epsilon L}$, where $L$ is the left side of the theorem. For a single expert, $1-\epsilon x\ge (1-\epsilon {)}^x$ when $0\le x\le 1$ (the right side is convex in $x$ and the two agree at 0 and 1), so $w_i^{T+1}\ge (1-\epsilon {)}^{L_i}$. A single weight is at most the total, so $(1-\epsilon {)}^{L_i}\le n{e}^{-\epsilon L}$. Take logarithms:

$$\epsilon L\le \ln n+L_i\ln \frac{1}{1-\epsilon }\le \ln n+(\epsilon +{\epsilon }^2)L_i.$$

Divide by $\epsilon$. $◻$

With $\epsilon =1/2$ and losses of 0 or 1, the weights are exactly weighted majority's. On the ferry days the randomized rule expects 4.80 mistakes, within its bound $3+2\ln 5\approx 6.22$. That is more than the deterministic vote's 3 on this particular sequence. The theorems compare worst cases: the deterministic rule's factor can be forced up to 2, while the randomized rule's is at most $1+\epsilon$, plus the additive term.

def expected_mistakes(eps):
    total = F(0)
    for t in range(T):
        w = weights(t, 1 - eps)
        total += sum(w[k] for k in calls if wrong[k][t]) / sum(w.values())
    return total

assert round(float(expected_mistakes(F(1, 2))), 2) == 4.80
assert float(expected_mistakes(F(1, 2))) <= 1.5 * 2 + math.log(5) / 0.5

Regret. Every $L_i\le T$, so the theorem gives $L-L_i\le \epsilon T+(\ln n)/\epsilon$. The right side is smallest at $\epsilon =\sqrt{\ln n/T}$, which is at most $1/2$ once $T\ge 4\ln n$, and then

$$L-{min}_i{L}_i\le 2\sqrt{T\ln n}.$$

The regret per round, $2\sqrt{\ln n/T}$, goes to zero: the algorithm does, on average, as well as the best expert. This choice of $\epsilon$ needs $T$ in advance. Without it, one can restart with doubled guesses of $T$ at a constant-factor cost (the standard doubling trick, not proved here).

If the decision itself can be divided (a portfolio split across funds, say), putting the fraction $p_i^t$ on expert $i$ costs exactly $p^t·{\ell }^t$. Then no coins are needed at all, and the theorem holds against an adversary that sees the split before it picks the losses.

No algorithm avoids √T regret

Take two experts, one always saying rough and one always calm, and let the sea be a fair coin each day, independent of everything before. Whatever an algorithm does, deterministic or not, it is right on each day with probability 1/2, so it expects $T/2$ mistakes. If $X$ is the number of rough days, the better expert makes $min(X,T-X)$ mistakes, which is $T/2-|X-T/2|$. So the regret averaged over all sequences is $𝔼|X-T/2|$, and some fixed sequence has at least that much expected regret (the averaging step of Yao's principle, module 14). For even $T$,

$$𝔼|X-T/2|=\frac{T}{2}\left(\genfrac{}{}{0ex}{}{T}{T/2}\right)2^{-T}\approx \sqrt{T/(2\pi )},$$

which is 3.98 for $T=100$ and 12.61 for $T=1000$. So regret $\Omega (\sqrt{T})$ is unavoidable for every algorithm. With $n$ experts the known lower bound, as $T$ and $n$ grow, is $\Omega (\sqrt{T\ln n})$ (cited, not proved here), so multiplicative weights is optimal up to the constant.

def spread(T):
    """E|X - T/2| for X ~ Binomial(T, 1/2), exactly, by summing over X."""
    return sum(F(math.comb(T, x), 2 ** T) * abs(F(x) - F(T, 2)) for x in range(T + 1))

for days in (100, 1000):
    assert spread(days) == F(days // 2 * math.comb(days, days // 2), 2 ** days)
assert round(float(spread(100)), 2) == 3.98 and round(float(spread(1000)), 2) == 12.61

Measure the claim

Here is multiplicative weights with $\epsilon =\sqrt{\ln n/T}$ on $n=4$ experts whose losses are independent fair coins (0 or 1), ten sequences per length (seeds 451 to 460). The ratio divides the regret by $\sqrt{T\ln n}$, so the theorem says it never exceeds 2.

The ratio stays flat, well below 2. On these sequences every algorithm expects to lose $T/2$, as in the previous section, so the regret measures how lucky the best of four coins was: this is the lower-bound side, and it grows like $\sqrt{T}$ for everyone. The constant 2 is the price of the worst sequence. These are sample means of ten runs on these instances, not expectations; the course's verification script recomputes them.

Solving a zero-sum game with multiplicative weights

Module 14's game $H$ has rows $(3,-1,1)$ and $(-2,4,0)$: Rowan picks a row, Cole a column, and Cole pays Rowan the entry. Its value is $2/3$. Solving it took module 14's lower envelope; a general $m\times n$ game took a linear program. Multiplicative weights gives an approximate answer with nothing but best responses.

Rowan runs multiplicative weights over her rows. In round $t$ she plays the mix $p^t$, and Cole answers with a best response $j_t$, a pure column minimizing $(p^{t\mathsf{T}}M{)}_j$ (module 14: against a known mix, a pure reply is enough). Rowan's loss on row $i$ is $(b-M_{i{j}_t})/R$, where the entries lie in $[a,b]$ and $R=b-a$, so that losses lie in $[0,1]$. After $T$ rounds, let $\overline{p}$ be the average of Rowan's mixes and $\overline{q}$ the frequencies of Cole's answers.

Proof. Let $g^t={min}_j(p^{t\mathsf{T}}M{)}_j$, what Cole's answer leaves Rowan in round $t$. Rewrite the regret bound $L-L_i\le 2\sqrt{T\ln m}$ in payoffs: Rowan's losses are $(b-g^t)/R$ and row $i$'s are $(b-M_{i{j}_t})/R$, so for every row $i$

$$\frac{1}{T}\sum _t{g}^t\ge (M\overline{q}{)}_i-2R\sqrt{\ln m/T}.$$

And ${min}_j({\overline{p}}^{\mathsf{T}}M{)}_j\ge \frac{1}{T}{\sum }_t{g}^t$, because the minimum of an average is at least the average of the minima. Combine the two. $◻$

Weak duality (module 14) says every guarantee is at most every hold-down, ${min}_j({\overline{p}}^{\mathsf{T}}M{)}_j\le v\le {max}_i(M\overline{q}{)}_i$. So the two numbers bracket the value, both strategies are within the gap of optimal, and anyone can check the bracket without trusting the run. Here is $H$ ($m=2$, $R=6$, Cole taking the lowest column on ties), with lower $={min}_j({\overline{p}}^{\mathsf{T}}H{)}_j$ and upper $={max}_i(H\overline{q}{)}_i$:

After 10,000 rounds, $\overline{p}\approx (0.662,0.338)$ and $\overline{q}\approx (0,0.159,0.841)$, close to module 14's exact $(2/3,1/3)$ and $(0,1/6,5/6)$. As $T$ grows the gap goes to zero, which proves the hard direction of the minimax theorem, ${max}_p{min}_q={min}_q{max}_p$ (sketch: a compactness step turns "within every $\delta$" into exact optimal strategies).

H = [[3, -1, 1], [-2, 4, 0]]

def bracket(M, p, q):
    lower = min(sum(p[i] * M[i][j] for i in range(len(M))) for j in range(len(M[0])))
    upper = max(sum(M[i][j] * q[j] for j in range(len(M[0]))) for i in range(len(M)))
    return lower, upper

lower, upper = bracket(H, [F(2, 3), F(1, 3)], [0, F(1, 6), F(5, 6)])
assert lower == upper == F(2, 3)                        # module 14's exact strategies: no gap
lower, upper = bracket(H, [F(662, 1000), F(338, 1000)], [0, F(159, 1000), F(841, 1000)])
assert lower <= F(2, 3) <= upper and upper - lower < F(3, 100)
assert [round(2 * 6 * math.sqrt(math.log(2) / t), 2) for t in (10, 100, 1000, 10000)] == [3.16, 1.0, 0.32, 0.1]

Cost

Experts. One round costs $O(n)$ arithmetic operations (the sum $W$, the update, and a random choice or a split), and the algorithm stores $n$ weights. It never looks at old rounds again.

Games. One round computes $p^{\mathsf{T}}M$ for Cole's best response, $mn$ multiplications and additions, plus $O(m)$ for the update. To reach a gap of $\delta$ the theorem needs $T=\lceil 4R^2\ln m/{\delta }^2\rceil$ rounds, so the total is

$$O\left(\frac{mn{R}^2\log m}{{\delta }^2}\right)$$

arithmetic operations on real numbers. Linear programming (modules 15 and 17) finds the exact value in time polynomial in the bits of $M$. Multiplicative weights is only approximate and pays $1/{\delta }^2$, but its count does not depend on the bits, and Cole never has to list his columns: it is enough that someone can compute a best response.

Floating point. The weights shrink geometrically. In IEEE double precision the smallest positive number is $2^{-1074}$, so a weight halved 1,075 times becomes exactly 0 and can never recover, and if every weight reaches 0 the total $W$ is 0. Dividing every weight by the largest after each round leaves $p^t$ unchanged and keeps the numbers near 1; storing $\ln w_i$ instead works too.

assert 0.5 ** 1074 > 0 and 0.5 ** 1075 == 0.0

A problem that looks different

A school's timetabling office has 300 soft rules: no teacher teaches three periods in a row, the chemistry lab is not double-booked, and so on. It owns a solver that, given any weighting of the rules, returns a timetable that satisfies their weighted average. No single call satisfies every rule. Can a sequence of calls, with the weights changing between them, produce a mix of timetables that nearly satisfies all 300, and who plays the part of the experts? The lab's last problem is a different one.

Practise

In the lab you draw weighted majority day by day and watch the total weight obey its bound; predict and then trace the multiplicative weights distribution on a new instance; solve zero-sum games approximately, with a bracket anyone can check; measure regret against an adversary and on random losses at three lengths; and solve a problem that doesn't say what it is.

Recap

You can now: state the experts problem and its benchmark; run weighted majority and prove its mistake bound from the total weight; prove that no deterministic rule beats a factor of 2; prove the $(1+\epsilon )L_i+(\ln n)/\epsilon$ bound for multiplicative weights and tune $\epsilon$ for regret $2\sqrt{T\ln n}$; and solve a zero-sum game to within a gap $\delta$ with a checkable bracket.

Invariant: the total weight $W$ falls by a factor tied to the algorithm's own loss, and never falls below the best expert's weight, which depends only on that expert's loss.

Complexity achieved: weighted majority, $M\le 2.41(m+{\log }_{2}n)$ mistakes on every sequence; multiplicative weights, expected regret at most $2\sqrt{T\ln n}$ against an oblivious adversary (or exactly, for a split decision against an adaptive one), which is optimal up to the constant; $O(n)$ time per round. A zero-sum game to gap $\delta$ in $O(mn{R}^2\log m/{\delta }^2)$ arithmetic operations.

Failure mode: trusting one expert completely, as follow the leader does: any deterministic rule can be forced to twice the best expert's mistakes. A fixed $\epsilon$ that ignores $T$ fails more quietly: its bound, $\epsilon T+(\ln n)/\epsilon$, grows in proportion to $T$.

In real software: scikit-learn's AdaBoostClassifier (version 1.8) reweights its training examples multiplicatively: after each round it multiplies the weight of every misclassified example by $e^{\alpha }$, computing it as the exponential of the log-weight plus $\alpha$, rescales the weights to sum to 1, and before each round raises any weight that has shrunk below machine epsilon back to that value, so that no weight vanishes.

Retrieval (module 14): why is it enough for Cole to answer a known mix $p$ with a single column, and never with a mix of his own?

Check yourself

1. Why does each mistake of weighted majority multiply the total weight by at most $3/4$, and how does that become $M\le 2.41(m+{\log }_{2}n)$?
2. Run weighted majority on the ferry days with $\beta =0$, so that a service is dropped at its first mistake. What happens, and what does the bound say?
3. The randomized rule expects 4.80 mistakes on the ferry days, the deterministic vote makes 3. Which is better, and why does this not contradict the theorems?

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.