A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
The multiplicative weights (MW) method is a meta-algorithm for online decision-making where, in each round, the learner maintains a weight for each option and selects (or randomizes) proportionally to these weights. After observing the loss, weights of poorly performing options are multiplicatively decreased: w_i <- w_i * (1 - eta * loss_i). This achieves O(sqrt(T * ln N)) regret over T rounds with N options. The method is a universal primitive that appears independently across computer science — as the Hedge algorithm in online learning, the Winnow algorithm in machine learning, boosting in ensemble methods, and equilibrium computation in game theory.
The multiplicative weights method is one of the most versatile algorithmic primitives in theoretical computer science. Its core idea is simple: maintain a weight for each option, use the weights to make decisions, then update by multiplicatively penalizing options that performed poorly. Despite this simplicity, the method achieves near-optimal regret bounds and appears as a key ingredient in algorithms across diverse fields.
The algorithm proceeds as follows. Initialize weights w_i = 1 for each of N options. At each round t: (1) Select option i with probability proportional to w_i, or deterministically choose the highest-weight option; (2) Observe losses l_1, ..., l_N for all options; (3) Update w_i <- w_i * (1 - eta * l_i) for each option, where eta is the learning rate. The multiplicative update means that options consistently performing poorly see their weights shrink exponentially — after k rounds of high loss, a weight is roughly (1 - eta)k, which decays rapidly. Options consistently performing well maintain or grow their relative weight.
The regret analysis reveals why the method works. The key potential function is the total weight W_t = sum_i w_i(t). On one hand, the total weight cannot decrease too fast because the learner randomizes proportionally to weights, linking the weight decrease to the learner's expected loss. On the other hand, the best expert's weight is at most W_T, providing a lower bound. Combining these bounds gives: learner's total loss <= (best expert's total loss) + (ln N)/eta + eta * T, and setting eta = sqrt(ln(N)/T) yields regret O(sqrt(T * ln N)). The logarithmic dependence on N is remarkable — with 1 million experts, the regret only grows by a factor of sqrt(ln(106)) ≈ 3.7 compared to 2 experts.
The universality of multiplicative weights is its most striking feature. In online learning, it is the Hedge algorithm. In machine learning, AdaBoost's training-example weighting is MW applied to a game between the booster and the weak learner. In game theory, MW converges to minimax equilibria in zero-sum games (each player runs MW, and the time-averaged strategies converge to a Nash equilibrium). In combinatorial optimization, it appears in the Plotkin-Shmoys-Tardos framework for approximately solving linear programs. In information theory, it relates to universal coding and the exponential weights forecaster. This convergence of independently discovered techniques to the same multiplicative update is evidence that the method captures something fundamental about decision-making under uncertainty.