View source for Multiplicative weight update method

{{Short description|Algorithmic technique}}
The '''multiplicative weights update method''' is an [[Algorithmic technique|algorithmic technique]] most commonly used for decision making and prediction, and also widely deployed in game theory and algorithm design. The simplest use case is the problem of prediction from expert advice, in which a decision maker needs to iteratively decide on an expert whose advice to follow. The method assigns initial weights to the experts (usually identical initial weights), and updates these weights multiplicatively and iteratively according to the feedback of how well an expert performed: reducing it in case of poor performance, and increasing it otherwise.<ref name = ref1>{{cite journal
| first2=Elad | last2=Hazan
| first3=Satyen | last3=Kale
| title=The Multiplicative Weights Update Method: A Meta-Algorithm and Applications
| journal=Theory of Computing
| volume=8
| year=2012
| pages=121–164
| doi=10.4086/toc.2012.v008a006 | doi-access=free
}}</ref> It was discovered repeatedly in very diverse fields such as machine learning ([[AdaBoost]], [[Winnow (algorithm)|Winnow]], Hedge), [[Mathematical optimization|optimization]] (solving [[Linear programming|linear programs]]), theoretical computer science (devising fast algorithm for [[Linear programming|LPs]] and [[Semidefinite programming|SDPs]]), and [[Game theory|game theory]].

==Name==
"Multiplicative weights" implies the iterative rule used in algorithms derived from the multiplicative weight update method.<ref name=ref2>{{cite web |url=https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture16.pdf |title= The Multiplicative Weights Algorithm* |access-date=2016-11-09}}</ref> It is given with different names in the different fields where it was discovered or rediscovered.

==History and background==
The earliest known version of this technique was in an algorithm named "[[Fictitious play|fictitious play]]" which was proposed in [[Game theory|game theory]] in the early 1950s. Grigoriadis and Khachiyan<ref>{{cite journal
| first1=Michael D. | last1=Grigoriadis
| title= A sublinear-time randomized approximation algorithm for matrix games
| year=1995
| journal=[[Engineering:Operations Research Letters|Operations Research Letters]]
| volume=18
| issue=2
| pages=53–58
| doi=10.1016/0167-6377(95)00032-0
}}</ref> applied a randomized variant of "fictitious play" to solve two-player zero-sum games efficiently using the multiplicative weights algorithm. In this case, player allocates higher weight to the actions that had a better outcome and choose his strategy relying on these weights. In [[Machine learning|machine learning]], Littlestone applied the earliest form of the multiplicative weights update rule in his famous [[Winnow (algorithm)|winnow algorithm]], which is similar to Minsky and Papert's earlier [[Perceptron|perceptron learning algorithm]]. Later, he generalized the winnow algorithm to weighted majority algorithm. Freund and Schapire followed his steps and generalized the winnow algorithm in the form of hedge algorithm.

The multiplicative weights algorithm is also widely applied in [[Computational geometry|computational geometry]] such as [[Biography:Kenneth L. Clarkson|Kenneth Clarkson's]] algorithm for [[Linear programming|linear programming (LP)]] with a bounded number of variables in linear time.<ref name="Kenneth L. Clarkson pp. 452">Kenneth L. Clarkson. ''A Las Vegas algorithm for linear programming when the dimension is small.'', In Proc. 29th FOCS, pp. 452–456. IEEE Comp. Soc. Press, 1988.[doi:10.1109/SFCS.1988.21961] 123, 152.</ref><ref name="Kenneth L. Clarkson 1995">Kenneth L. Clarkson. ''A Las Vegas algorithm for linear and integer programming when the dimension is small.'', Journal of the ACM, 42:488–499, 1995. [doi:10.1145/201019.201036] 123, 152.</ref> Later, Bronnimann and Goodrich employed analogous methods to find [[Set cover problem|set covers]] for [[Hypergraph|hypergraph]]s with small [[VC dimension]].<ref name="M.T. GOODRICH. 1995">{{cite journal
| last1=Bronnimann | first1=H.
| last2=Goodrich | first2=M. T.
| title=Almost optimal set covers in finite VC-dimension
| journal=Discrete & Computational Geometry
| volume=14
| pages=463–479
| date=1995
| issue=4
| doi=10.1007/BF02570718 | doi-access=free}} Preliminary version in 10th Ann. Symp. Comp. Geom. (SCG'94).</ref>

In [[Operations research|operation 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.<ref name=ref1/>

The Hedge algorithm is a special case of [[Mirror descent|mirror descent]].

==General setup==
A binary decision needs to be made based on n experts’ opinions to attain an associated payoff. In the first round, all experts’ opinions have the same weight. The decision maker will make the first decision based on the majority of the experts' prediction. 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.

==Algorithm analysis==

===Halving algorithm<ref name=ref2>{{cite web |url=https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture16.pdf |title= The Multiplicative Weights Algorithm* |access-date=2016-11-09}}</ref>===

Given a sequential game played between an adversary and an aggregator who is advised by N experts, the goal is for the aggregator to make as few mistakes as possible. Assume there is an expert among the N experts who always gives the correct prediction. In the halving algorithm, only the consistent experts are retained. Experts who make mistakes will be dismissed. 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. The aggregator makes at most  {{math|log<sub>''2''</sub>(''N'')}} mistakes.<ref name=ref2>{{cite web |url=https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture16.pdf |title= The Multiplicative Weights Algorithm* |access-date=2016-11-09}}</ref>

===Weighted majority algorithm<ref name=ref1 /><ref name=ref5>{{cite web |url=https://www.cs.princeton.edu/courses/archive/fall13/cos521/lecnotes/lec8.pdf |title= Lecture 8: Decision-making under total uncertainty: the multiplicative weight algorithm |date=2013}}</ref>===

Unlike halving algorithm which dismisses experts who have made mistakes, weighted majority algorithm discounts their advice. Given the same "expert advice" setup, suppose we have n decisions, and we need to select one decision for each loop. In each loop, every decision incurs a cost. All costs will be revealed after making the choice. The cost is 0 if the expert is correct, and 1 otherwise. this algorithm's goal is to limit its cumulative losses to roughly the same as the best of experts.
The very first algorithm that makes choice based on majority vote every iteration does not work since the majority of the experts can be wrong consistently every time. The weighted majority algorithm corrects above trivial algorithm by keeping a weight of experts instead of fixing the cost at either 1 or 0.<ref name=ref1 /> This would make fewer mistakes compared to halving algorithm.

    '''Initialization''': 
       Fix an <math>\eta \le 1/2</math>. For each expert, associate the weight <math>{w_i}^1</math>≔1.
    '''For''' <math>t</math> = <math>\mathit{1}</math>, <math>\mathit{2}</math>,...,<math>T</math>
       '''1'''. Make the prediction given by the weighted majority of the experts' predictions based on their weights<math>\mathbb{w_1}^t,..., \mathbb{w_n}^t</math>. That is, choose 0 or 1 depending on which prediction has a higher total weight of experts advising it (breaking ties arbitrarily). 
       '''2'''. For every expert i that predicted wrongly, decrease his weight for the next round by multiplying it by a factor of (1-η):
            <math>w_{i}^{t+1}</math>=<math>(1-\eta) w_{i}^{t}</math> (update rule)

If <math>\eta =0</math>, the weight of the expert's advice will remain the same. When <math>\eta</math> increases, the weight of the expert's advice will decrease. Note that some researchers fix <math>\eta =1/2</math> in weighted majority algorithm.

After <math>T</math> steps, let <math>m_i^T</math> be the number of mistakes of expert i and <math>M^T</math> be the number of mistakes our algorithm has made. Then we have the following bound for every <math>i</math>:

     <math>M^T \leq 2(1+\eta) m_i^T+ \frac{2 \ln(n)}{\eta}</math>.

In particular, this holds for i which is the best expert. Since the best expert will have the least <math>m_i^T</math>, it will give the best bound on the number of mistakes made by the algorithm as a whole.

===Randomized weighted majority algorithm===
This algorithm can be understood as follows:<ref name=ref2 /><ref name=ref6>{{cite web |url=http://www.cs.princeton.edu/courses/archive/spr06/cos511/scribe_notes/0330.pdf |title=COS 511: Foundations of Machine Learning |date=20 March 2006}}</ref>

Given the same setup with N experts. Consider the special situation where the proportions of experts predicting positive and negative, counting the weights, are both close to 50%. Then, there might be a tie. Following the weight update rule in weighted majority algorithm, the predictions made by the algorithm would be randomized. The algorithm calculates the probabilities of experts predicting positive or negatives, and then makes a random decision based on the computed fraction:{{Explain|reason=Some variables remain undefined and unexplained such as q_0,q_1 and beta|date=August 2021}}

predict  
:<math>
f(x) = \begin{cases}1 & \text{with probability} \frac{q_1}{W}\\0 & \text{otherwise}\end{cases}
</math>

where    
  <math>W= \sum_{i} { w_i} = q_0 + q_1</math>.

The number of mistakes made by the randomized weighted majority algorithm is bounded as: 
  <math>E\left [ \# \text{mistakes of the learner} \right ] \leq \alpha_\beta \left ( \# \text{ mistakes of the best expert} \right ) + c_\beta \ln(N) </math>

where     <math>\alpha_\beta= \frac{\ln(\frac{1}{\beta})}{1-\beta}</math> and          <math>c_\beta=\frac{1}{1-\beta}</math>.

Note that only the learning algorithm is randomized. The underlying assumption is that the examples and experts' predictions are not random. The only randomness is the randomness where the learner makes his own prediction.
In this randomized algorithm, <math>\alpha_\beta \rightarrow 1</math> if <math>\beta \rightarrow 1</math>. Compared to weighted algorithm, this randomness halved the number of mistakes the algorithm is going to make.<ref name=ref7 /> However, it is important to note that in some research, people define <math>\eta =1/2</math> in weighted majority algorithm and allow <math>0\leq \eta \leq 1</math> in [[Randomized weighted majority algorithm|randomized weighted majority algorithm]].<ref name=ref2 />

==Applications==
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. The punishment of the expert corresponds to how well its corresponding constraint is satisfied on the point represented by an event.<ref name=ref1 />

===Solving zero-sum games approximately (Oracle algorithm):<ref name=ref1 /><ref name=ref7>{{cite web |url= https://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-computer-science-an-algorithmists-toolkit-fall-2009/lecture-notes/MIT18_409F09_scribe24.pdfformat=PDF |title= An Algorithmist's Toolkit |date=8 December 2009 |access-date=2016-11-09}}</ref>===

Suppose we were given the distribution <math>P</math> on experts. Let <math>A</math> = payoff matrix of a finite two-player zero-sum game, with <math>n</math> rows.

When the row player <math>p_r</math> uses plan <math>i</math> and the column player <math>p_c</math> uses plan <math>j</math>, the payoff of player <math>p_c</math> is <math>A \left ( i, j \right)</math>≔<math>A_{ij}</math>, assuming <math>A \left( i, j\right ) \in \left [ 0, 1 \right ]</math>.

If player <math>p_r</math> chooses action <math>i</math> from a distribution <math>P</math> over the rows, then the expected result for player <math>p_c</math> selecting action <math>j</math> is <math>A \left (P, j \right )=E_{i \in P} \left [A \left(i,j \right) \right]</math>.

To maximize <math>A \left (P, j \right)</math>, player <math>p_c</math> should choose plan <math>j</math>. Similarly, the expected payoff for player <math>p_l</math> is <math>A \left (i,P\right )=E_{j\in P} \left [A \left(i,j \right) \right ]</math>. Choosing plan <math>i</math> would minimize this payoff. By John Von Neumann's Min-Max Theorem, we obtain:

                                           <math>\min_P \max_j A\left( P, j \right) = \max_Q \min_i A\left( i, Q \right) </math>
where P and i changes over the distributions over rows, Q and j changes over the columns.

Then, let <math>\lambda^*</math> denote the common value of above quantities, also named as the "value of the game". Let <math>\delta>0</math> be an error parameter. To solve the zero-sum game bounded by additive error of <math>\delta</math>,

                                                  <math>\lambda^* - \delta \leq \min_i  A \left (i,q \right ) </math>
                                                  <math>\max_j A \left(p, j \right) \leq \lambda^* +\delta </math>

So there is an algorithm solving zero-sum game up to an additive factor of δ using O({{math|log<sub>''2''</sub>(''n'')}}/<math>\delta^2</math>) calls to ORACLE, with an additional processing time of O(n) per call<ref name =ref7 />

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.<ref name="Bailey and Piliouras EC18">Bailey, James P., and Georgios Piliouras. "Multiplicative weights update in zero-sum games." Proceedings of the 2018 ACM Conference on Economics and Computation. ACM, 2018.</ref>

===Machine learning===
In machine learning, Littlestone and Warmuth generalized the winnow algorithm to the weighted majority algorithm.<ref>{{cite journal
| first1=Dean P. | last1=Foster
| first2=Rakesh | last2=Vohra
| year=1999
| title=Regret in the on-line decision problem
| journal=Games and Economic Behavior
| volume=29
| issue=1–2
| pages=7–35
| doi=10.1006/game.1999.0740| url=http://www.dklevine.com/archive/refs4569.pdf
}}</ref> Later, Freund and Schapire generalized it in the form of hedge algorithm.<ref name=ref8 /> AdaBoost Algorithm formulated by Yoav Freund and Robert Schapire also employed the Multiplicative Weight Update Method.<ref name=ref1 />

====Winnow algorithm====
Based on current knowledge in algorithms, the multiplicative weight update method was first used in Littlestone's winnow algorithm.<ref name=ref1 /> It is used in machine learning to solve a linear program.

Given <math>m</math> labeled examples <math> \left (a_1, l_1 \right ),\text{…} ,\left (a_m, l_m \right ) </math> where <math>a_j \in \mathbb{R}^n</math> are feature vectors, and <math>l_j \in \left \{-1,1 \right \} \quad</math> are their labels.

The aim is to find non-negative weights such that for all examples, the sign of the weighted combination of the features matches its labels. That is, require that <math>l_j a_j x \geq 0</math> for all <math>j</math>. Without loss of generality, assume the total weight is 1 so that they form a distribution. Thus, for notational convenience, redefine <math>a_j</math> to be <math>l_j a_j</math>, the problem reduces to finding a solution to the following LP:

                      <math>\forall j=1,2,\text{…}, m : a_j x \geq 0</math>,
                      <math>1*x=1</math>,
                      <math>\forall i : x_i \geq 0</math>.

This is general form of LP.

====Hedge algorithm <ref name=ref2 />====
The hedge algorithm is similar to the weighted majority algorithm. However, their exponential update rules are different.<ref name=ref2 />
It is generally used to solve the problem of binary allocation in which we need to allocate different portion of resources into N different options. The loss with every option is available at the end of every iteration. The goal is to reduce the total loss suffered for a particular allocation. The allocation for the following iteration is then revised, based on the total loss suffered in the current iteration using multiplicative update.<ref name=ref16>{{cite web |url=http://www.shivani-agarwal.net/Teaching/E0370/Aug-2011/Lectures/20-scribe1.pdf |title= Online Learning from Experts: Weighed Majority and Hedge |access-date=2016-12-07}}</ref>

=====Analysis=====
Assume the learning rate <math>\eta > 0</math> and for <math>t \in [T]</math>, <math>p^t</math> is picked by Hedge. Then for all experts <math>i</math>,

                                 <math>\sum_{t \leq T} p^t m^t \leq \sum_{t \leq T} m_i^t +\frac{\ln(N)}{\eta}+\eta T</math>

'''Initialization''': Fix an <math>\eta > 0</math>. For each expert, associate the weight <math>w_i^1</math> ≔1
'''For''' t=1,2,...,T:
       1. Pick the distribution <math>p_i^t= \frac{w_i^t}{\Phi t}</math> where <math>\Phi t=\sum_i w_i^t</math>.
       2. Observe the cost of the decision <math>m^t</math>. 
       3. Set 
                               <math>w_i^{t + 1} = w_i^t \exp(-\eta m_i^t</math>).

====AdaBoost algorithm====

[[AdaBoost|This algorithm]]<ref name=ref8>Yoav, Freund. Robert, E. Schapire (1996). ''TA Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting*'', p. 55. journal of computer and system sciences.</ref> maintains a set of weights <math>w^t</math> over the training examples. On every iteration <math>t</math>, a distribution <math>p^t</math> is computed by normalizing these weights. This distribution is fed to the weak learner WeakLearn which generates a hypothesis <math>h_t</math> that (hopefully) has small error with respect to the distribution. Using the new hypothesis <math>h_t</math>, AdaBoost generates the next weight vector <math>w^{t+1}</math>. The process repeats. After T such iterations, the final hypothesis <math>h_f</math> is the output. The hypothesis <math>h_f</math> combines the outputs of the T weak hypotheses using a weighted majority vote.<ref name=ref8 />

 '''Input''': 
       Sequence of <math>N</math> labeled examples (<math>x_1</math>,<math>y_1</math>),...,(<math>x_N</math>, <math>y_N</math>)
       Distribution <math>D</math> over the <math>N</math> examples
       Weak learning algorithm "'WeakLearn"'
       Integer <math>T</math> specifying number of iterations
 '''Initialize''' the weight vector: <math>w_{i}^{1} = D(i)</math> for <math>i=1, 2,..., N</math>.
 '''Do for''' <math>t=1, 2,..., T</math>
       '''1'''. Set <math>p^t=\frac{w^t}{\sum_{i=1}^{N} w_{i}^{t}}</math>.
       '''2'''. Call '''WeakLearn''', providing it with the distribution <math>p^t</math>; get back a hypothesis <math>h_t: X\rightarrow</math> [0,1].
       '''3'''. Calculate the error of <math>h_t:\epsilon_t = \sum_{i=1}^{N} p_{i}^{t}|h_t(x_i)-y_i|</math>.
       '''4'''. Set <math>\beta_t = \frac{\epsilon_t}{1-\epsilon_t}</math>.                                     
       '''5'''. Set the new weight vector to be <math>w_{i}^{t+1}=w_{i}^{t}\beta_{t}^{1-|h_t(x_i)-y_i|}</math>.
 
 '''Output''' the hypothesis:

       <math>
        f(x) = h_f(x) = \begin{cases}1 & \text{if} \sum_{t=1}^{T} (\log(1/\beta_t)) h_{t}(x) \geq \frac{1}{2}\sum_{t=1}^{T} \log(1/\beta_t) \\0 & \text{otherwise}\end{cases}
        </math>

===Solving linear programs approximately<ref name=ref11>{{cite web |url=http://tcs.epfl.ch/files/content/sites/tcs/files/Lec2-Fall14-Ver2.pdf |title= Fundamentals of Convex Optimization |access-date=2016-11-09}}</ref>===

====Problem====
Given a <math>m \times n</math> matrix <math>A</math> and <math>b \in \mathbb{R}^n</math>, is there a <math>x</math> such that <math>A x \geq b</math>?

                       <math>\exists ? x: A x \geq b </math>              (1)

====Assumption====
Using the oracle algorithm in solving zero-sum problem, with an error parameter <math> \epsilon > 0</math>, the output would either be a point <math>x</math> such that <math>A x \geq b-\epsilon</math> or a proof that <math>x</math> does not exist, i.e., there is no solution to this linear system of inequalities.

====Solution====
Given vector <math>p \in \Delta_n</math>, solves the following relaxed problem

                      <math>\exists ? x: p^{\textsf T}\!\!A x\geq p^\textsf{T}\!b</math>             (2)

If there exists a x satisfying (1), then x satisfies (2) for all <math> p\in \Delta_n</math>. The contrapositive of this statement is also true.
Suppose if oracle returns a feasible solution for a <math>p</math>, the solution <math>x</math> it returns has bounded width <math>\max_i |{(A x)}_i - b_i | \leq 1</math>.
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 <math>2\epsilon</math>. The algorithm makes at most <math>\frac{\ln(m)}{\epsilon^2}</math> calls to a width-bounded oracle for the problem (2). The contrapositive stands true as well. The multiplicative updates is applied in the algorithm in this case.

===Other applications===

;Evolutionary game theory: Multiplicative weights update is the discrete-time variant of the [[Replicator equation|replicator equation]] (replicator dynamics), which is a commonly used model in [[Evolutionary game theory|evolutionary game theory]]. It converges to [[Nash equilibrium]] when applied to a congestion game.<ref name="Kleinberg, Piliouras, Tardos 09">Kleinberg, Robert, Georgios Piliouras, and Eva Tardos. "Multiplicative updates outperform generic no-regret learning in congestion games." Proceedings of the forty-first annual ACM symposium on Theory of computing. ACM, 2009.</ref>

;Operations research and online statistical decision-making: In [[Operations research|operations research]] and on-line statistical decision making problem field, the weighted majority algorithm and its more complicated versions have been found independently.<ref name =ref1 />

;Computational geometry: The multiplicative weights algorithm is also widely applied in [[Computational geometry|computational geometry]],<ref name =ref1 /> such as [[Biography:Kenneth L. Clarkson|Clarkson]]'s algorithm for [[Linear programming|linear programming (LP)]] with a bounded number of variables in linear time.<ref name="Kenneth L. Clarkson pp. 452"/><ref name="Kenneth L. Clarkson 1995"/> Later, Bronnimann and Goodrich employed analogous methods to find [[Set cover problem|Set Covers]] for [[Hypergraph|hypergraph]]s with small [[VC dimension]].<ref name="M.T. GOODRICH. 1995"/>

;[[Gradient descent|Gradient descent method]]<ref name=ref1 />

;[[Matrix (mathematics)|Matrix]] multiplicative weights update<ref name=ref1 />

;Plotkin, Shmoys, Tardos framework for [[Packing problems|packing]]/[[Covering problems|covering LPs]]<ref name=ref1 />

;Approximating multi-commodity flow problems<ref name=ref1 />

;O (logn)- approximation for many [[NP-hardness|NP-hard problems]]<ref name=ref1 />

;[[Philosophy:Learning theory (education)|Learning theory]] and [[Boosting (machine learning)|boosting]]<ref name=ref1 />

;Hard-core sets and the XOR lemma<ref name=ref1 />

;Hannan's algorithm and multiplicative weights<ref name=ref1 />

;Online [[Convex optimization|convex optimization]]<ref name=ref1 />

==References==
{{Reflist}}

==External links==
* [https://www.quantamagazine.org/game-theory-makes-new-predictions-for-evolution-20140618 The Game Theory of Life] a Quanta Magazine article describing the use of the method to evolutionary biology in a paper by Erick Chastain, Adi Livnat, [[Biography:Christos Papadimitriou|Christos Papadimitriou]], and [[Biography:Umesh Vazirani|Umesh Vazirani]]

[[Category:Algorithms]]
[[Category:Machine learning]]
[[Category:Randomized algorithms]]

{{Sourceattribution|Multiplicative weight update method}}