Halving algorithm^[2]

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 log₂(N) mistakes.^[2]

Weighted majority algorithm^[1][7]

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.^[1] This would make fewer mistakes compared to halving algorithm.

   Initialization: 
      Fix an ${\displaystyle \eta \leq 1/2}$. For each expert, associate the weight ${\displaystyle {w_{i}}^{1}}$≔1.
   For ${\displaystyle t}$ = ${\displaystyle {\mathit {1}}}$, ${\displaystyle {\mathit {2}}}$,...,${\displaystyle T}$
      1. Make the prediction given by the weighted majority of the experts' predictions based on their weights${\displaystyle \mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}}$. 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-η):
           ${\displaystyle w_{i}^{t+1}}$=${\displaystyle (1-\eta )w_{i}^{t}}$ (update rule)

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

After ${\displaystyle T}$ steps, let ${\displaystyle m_{i}^{T}}$ be the number of mistakes of expert i and ${\displaystyle M^{T}}$ be the number of mistakes our algorithm has made. Then we have the following bound for every ${\displaystyle i}$:

    ${\displaystyle M^{T}\leq 2(1+\eta )m_{i}^{T}+{\frac {2\ln(n)}{\eta }}}$.

In particular, this holds for i which is the best expert. Since the best expert will have the least ${\displaystyle m_{i}^{T}}$, 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:^[2][8]

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:

predict

${\displaystyle f(x)={\begin{cases}1&{\text{with probability}}{\frac {q_{1}}{W}}\\0&{\text{otherwise}}\end{cases}}}$

where

 ${\displaystyle W=\sum _{i}{w_{i}}=q_{0}+q_{1}}$.

The number of mistakes made by the randomized weighted majority algorithm is bounded as:

 ${\displaystyle E\left[\#{\text{mistakes of the learner}}\right]\leq \alpha _{\beta }\left(\#{\text{ mistakes of the best expert}}\right)+c_{\beta }\ln(N)}$

where ${\displaystyle \alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}}$ and ${\displaystyle c_{\beta }={\frac {1}{1-\beta }}}$.

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, ${\displaystyle \alpha _{\beta }\rightarrow 1}$ if ${\displaystyle \beta \rightarrow 1}$. Compared to weighted algorithm, this randomness halved the number of mistakes the algorithm is going to make.^[9] However, it is important to note that in some research, people define ${\displaystyle \eta =1/2}$ in weighted majority algorithm and allow ${\displaystyle 0\leq \eta \leq 1}$ in randomized weighted majority algorithm.^[2]

Solving zero-sum games approximately (Oracle algorithm):^[1][9]

Suppose we were given the distribution ${\displaystyle P}$ on experts. Let ${\displaystyle A}$ = payoff matrix of a finite two-player zero-sum game, with ${\displaystyle n}$ rows.

When the row player ${\displaystyle p_{r}}$ uses plan ${\displaystyle i}$ and the column player ${\displaystyle p_{c}}$ uses plan ${\displaystyle j}$, the payoff of player ${\displaystyle p_{c}}$ is ${\displaystyle A\left(i,j\right)}$≔${\displaystyle A_{ij}}$, assuming ${\displaystyle A\left(i,j\right)\in \left[0,1\right]}$.

If player ${\displaystyle p_{r}}$ chooses action ${\displaystyle i}$ from a distribution ${\displaystyle P}$ over the rows, then the expected result for player ${\displaystyle p_{c}}$ selecting action ${\displaystyle j}$ is ${\displaystyle A\left(P,j\right)=E_{i\in P}\left[A\left(i,j\right)\right]}$.

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

                                          ${\displaystyle \min _{P}\max _{j}A\left(P,j\right)=\max _{Q}\min _{i}A\left(i,Q\right)}$

where P and i changes over the distributions over rows, Q and j changes over the columns.

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

                                                 ${\displaystyle \lambda ^{*}-\delta \leq \min _{i}A\left(i,q\right)}$
                                                 ${\displaystyle \max _{j}A\left(p,j\right)\leq \lambda ^{*}+\delta }$

So there is an algorithm solving zero-sum game up to an additive factor of δ using O(log₂(n)/${\displaystyle \delta ^{2}}$) 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.^[10]

Machine learning

In machine learning, Littlestone and Warmuth generalized the winnow algorithm to the weighted majority algorithm.^[11] Later, Freund and Schapire generalized it in the form of hedge algorithm.^[12] AdaBoost Algorithm formulated by Yoav Freund and Robert Schapire also employed the Multiplicative Weight Update Method.^[1]

                     ${\displaystyle \forall j=1,2,{\text{…}},m:a_{j}x\geq 0}$,
                     ${\displaystyle 1*x=1}$,
                     ${\displaystyle \forall i:x_{i}\geq 0}$.

                                ${\displaystyle \sum _{t\leq T}p^{t}m^{t}\leq \sum _{t\leq T}m_{i}^{t}+{\frac {\ln(N)}{\eta }}+\eta T}$

      1. Pick the distribution ${\displaystyle p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}}$ where ${\displaystyle \Phi t=\sum _{i}w_{i}^{t}}$.
      2. Observe the cost of the decision ${\displaystyle m^{t}}$. 
      3. Set 
                              ${\displaystyle w_{i}^{t+1}=w_{i}^{t}\exp(-\eta m_{i}^{t}}$).

Input: 
      Sequence of ${\displaystyle N}$ labeled examples (${\displaystyle x_{1}}$,${\displaystyle y_{1}}$),...,(${\displaystyle x_{N}}$, ${\displaystyle y_{N}}$)
      Distribution ${\displaystyle D}$ over the ${\displaystyle N}$ examples
      Weak learning algorithm "'WeakLearn"'
      Integer ${\displaystyle T}$ specifying number of iterations
Initialize the weight vector: ${\displaystyle w_{i}^{1}=D(i)}$ for ${\displaystyle i=1,2,...,N}$.
Do for ${\displaystyle t=1,2,...,T}$
      1. Set ${\displaystyle p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}}$.
      2. Call WeakLearn, providing it with the distribution ${\displaystyle p^{t}}$; get back a hypothesis ${\displaystyle h_{t}:X\rightarrow }$ [0,1].
      3. Calculate the error of ${\displaystyle h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}|h_{t}(x_{i})-y_{i}|}$.
      4. Set ${\displaystyle \beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}}$.                                     
      5. Set the new weight vector to be ${\displaystyle w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}}$.

Output the hypothesis:

      ${\displaystyle 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}}}$

Solving linear programs approximately^[14]

                      ${\displaystyle \exists ?x:Ax\geq b}$              (1)

                     ${\displaystyle \exists ?x:p^{\textsf {T}}\!\!Ax\geq p^{\textsf {T}}\!b}$             (2)

Other applications

Evolutionary game theory

Multiplicative weights update is the discrete-time variant of the replicator equation (replicator dynamics), which is a commonly used model in evolutionary game theory. It converges to Nash equilibrium when applied to a congestion game.^[15]

Operations research and online statistical decision-making

In operations research and on-line statistical decision making problem field, the weighted majority algorithm and its more complicated versions have been found independently.^[1]

Computational geometry

The multiplicative weights algorithm is also widely applied in computational geometry,^[1] such as 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]

Gradient descent method^[1]

Matrix multiplicative weights update^[1]

Plotkin, Shmoys, Tardos framework for packing/covering LPs^[1]

Approximating multi-commodity flow problems^[1]

O (logn)- approximation for many NP-hard problems^[1]

Learning theory and boosting^[1]

Hard-core sets and the XOR lemma^[1]

Hannan's algorithm and multiplicative weights^[1]

Online convex optimization^[1]