pdf icon
Volume 8 (2012) Article 6 pp. 121-164 [Research Survey]
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications
Received: July 22, 2008
Revised: July 2, 2011
Published: May 1, 2012
Download article from ToC site:
[PDF (377K)] [PS (1733K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: algorithms, game theory, machine learning
Categories: algorithms, game theory, machine learning, boosting, online algorithms, online decision making, regret, convex optimization, linear programming duality, potential function, research surveys
ACM Classification: G.1.6
AMS Classification: 68Q25

Abstract: [Plain Text Version]

Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analyses are usually very similar and rely on an exponential potential function.

In this survey we present a simple meta-algorithm that unifies many of these disparate algorithms and derives them as simple instantiations of the meta-algorithm. We feel that since this meta-algorithm and its analysis are so simple, and its applications so broad, it should be a standard part of algorithms courses, like “divide and conquer.”