The multiplicative weights update method is an algorithmic technique most commonly used for decision making and prediction, and also widely deployed in game theory and algorithm design.
[1] It was discovered repeatedly in very diverse fields such as machine learning (AdaBoost, Winnow, Hedge), optimization (solving linear programs), theoretical computer science (devising fast algorithm for LPs and SDPs), and game theory.
The earliest known version of this technique was in an algorithm named "fictitious play" which was proposed in game theory in the early 1950s.
Grigoriadis and Khachiyan[3] applied a randomized variant of "fictitious play" to solve two-player zero-sum games efficiently using the multiplicative weights algorithm.
In machine learning, Littlestone applied the earliest form of the multiplicative weights update rule in his famous winnow algorithm, which is similar to Minsky and Papert's earlier perceptron learning algorithm.
The multiplicative weights algorithm is also widely applied in computational geometry such as Kenneth Clarkson's algorithm for linear programming (LP) with a bounded number of variables in linear time.
[4][5] Later, Bronnimann and Goodrich employed analogous methods to find set covers for hypergraphs with small VC dimension.
[6] In operations research and on-line statistical decision making problem field, the weighted majority algorithm and its more complicated versions have been found independently.
In computer science field, some researchers have previously observed the close relationships between multiplicative update algorithms used in different contexts.
Young discovered the similarities between fast LP algorithms and Raghavan's method of pessimistic estimators for derandomization of randomized rounding algorithms; Klivans and Servedio linked boosting algorithms in learning theory to proofs of Yao's XOR Lemma; Garg and Khandekar defined a common framework for convex optimization problems that contains Garg-Konemann and Plotkin-Shmoys-Tardos as subcases.
A binary decision needs to be made based on n experts’ opinions to attain an associated payoff.
Then, in each successive round, the decision maker will repeatedly update the weight of each expert's opinion depending on the correctness of his prior predictions.
Real life examples includes predicting if it is rainy tomorrow or if the stock market will go up or go down.
For every decision, the aggregator decides by taking a majority vote among the remaining experts.
Therefore, every time the aggregator makes a mistake, at least half of the remaining experts are dismissed.
this algorithm's goal is to limit its cumulative losses to roughly the same as the best of experts.
, it will give the best bound on the number of mistakes made by the algorithm as a whole.
Consider the special situation where the proportions of experts predicting positive and negative, counting the weights, are both close to 50%.
The algorithm calculates the probabilities of experts predicting positive or negatives, and then makes a random decision based on the computed fraction:[further explanation needed] predict where The number of mistakes made by the randomized weighted majority algorithm is bounded as: where
[2] The multiplicative weights method is usually used to solve a constrained optimization problem.
Let each expert be the constraint in the problem, and the events represent the points in the area of interest.
By John Von Neumann's Min-Max Theorem, we obtain: where P and i changes over the distributions over rows, Q and j changes over the columns.
, So there is an algorithm solving zero-sum game up to an additive factor of δ using O(log2(n)/
) calls to ORACLE, with an additional processing time of O(n) per call[9] Bailey and Piliouras showed that although the time average behavior of multiplicative weights update converges to Nash equilibria in zero-sum games the day-to-day (last iterate) behavior diverges away from it.
[12] AdaBoost Algorithm formulated by Yoav Freund and Robert Schapire also employed the Multiplicative Weight Update Method.
Without loss of generality, assume the total weight is 1 so that they form a distribution.
This distribution is fed to the weak learner WeakLearn which generates a hypothesis
combines the outputs of the T weak hypotheses using a weighted majority vote.
Using the oracle algorithm in solving zero-sum problem, with an error parameter
So if there is a solution to (1), then there is an algorithm that its output x satisfies the system (2) up to an additive error of