The Multiplicative Weights Update Method: a Meta-Algorithm and Applications

By Sanjeev Arora, Elad Hazan, Satyen Kale. 2012

1,187 citations recorded by the source corpus.

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."

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Introduction to Online Convex Optimization (2016, methodology): “See also the survey (11) and more recent developments that give rise to sublinear time algorithms (30; 59).”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “In this case we denote by ℓi,t the loss of arm i at time step t, and the regret rewrites as Rn = n∑ t=1 ℓIt,t − min i=1,...,K n∑ t=1 ℓi,t .”
The geometry of differential privacy: the sparse and approximate cases (2012, methodology): “ategy that guarantees payo at most ‘(opt 1(A))2. By the minimax theorem, this also upper bounds the value of the game. Moreover, using standard constructive versions of the minimax theorems (see e.g. [AHK12]), one can come up with such a distribution Dover O(dlogd) (";)-DP mechanisms, and a Psu”
Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals (2018, methodology): “ptimization of constrained subproblems, such as Frank-Wolfe (Hazan and Kale, 2012; Jaggi, 2013; Garber and Hazan, 2013)). Another strategy for constrained optimization is to penalize violations (e.g. Arora et al., 2012; Rakhlin and Sridharan, 2013; Mahdavi et al., 2012; Cotter et al., 2016; Yang et ”
A unified view of entropy-regularized Markov decision processes (2017, positive): “In particular, entropy regularization has proven to be one of the most successful tools of machine learning and related ﬁelds (Littlestone and Warmuth, 1994; Vovk, 1990; Freund and Schapire, 1997; Kivinen and Warmuth, 2001; Arora et al., 2012).”
Proving Differential Privacy in Hoare Logic (2014, background): “On a more practical side, it would be interesting to implement our transformation for a realistic setting, for instance modeling thePINQ language [30].”
Private Multiplicative Weights Beyond Linear Queries (2014, neutral): “If n ≥ 256 · S · √ T · log(2/δ) · log(4k/β) εα , then Pr ThresholdGamen,T,k,τ [SV,B] (ACC ) ≥ 1− β, where ACC = { ∀j ∈ [k], q j(D) ≥ α =⇒ aj = > qj(D) ≤ α/2 =⇒ aj = ⊥ }”
On Oracle-Efficient PAC RL with Rich Observations (2018, neutral): “See [40] for more details.”
The Algorithmic Foundations of Differential Privacy (2014, methodology): “The regret bound that we use for the randomized weighted majority algorithm is given in [1].”
Generalize Across Tasks: Efficient Algorithms for Linear Representation Learning (2019, methodology): “Theorem 9 (Tsuda et al. (2005); Arora et al. (2012), Theorem 5.1) Let {Pt}Tt=1 be an arbitrary sequence of cost matrices, let K = {B : B 0, ‖B‖tr = 1}, let ft(B) = B • Pt, and let {Bt}Tt=1 be the matrices played by the matrix multiplicative weights algorithm.”
On the Instability of Bitcoin Without the Block Reward (2016, background): “in a number of rounds sublinear in the number of possible strategies) [5, 6, 4, 14].”
Robust Optimization for Non-Convex Objectives (2017, background): “In particular it is known that the regret of EWU, when run on a sequence of rewards that lie in [ − 1 , 1] is at most [2]: where the second inequality follows from the fact that L i ( x ) ∈ [0 , 1] .”
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations (2013, methodology): “A matrix ˜P ∈ R E × E is a circulation projection matrix if it is a projection matrix onto the circulation space, i.e. it satisﬁes the following Then, the problem becomes min Applying gradient descent on this problem is similar to applying projected gradient method on the original problem.”
Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU (2017, methodology): “The multiplicative weight update (MWU) method is a simple but extremely powerful algorithmic tool that has been repeatedly discovered in theory of computation, machine learning, optimization, and game theory (see for instance the survey (Arora et al., 2012) and the book (Cesa-Bianchi & Lugosi, 2006)”