This is the seventh in a series of posts on online optimization, where we alternate one post explaining a result from the theory of online convex optimization and one post explaining an “application” in computational complexity or combinatorics. The first two posts were about the technique of Multiplicative Weights Updates and its application to “derandomizing” probabilistic arguments based on combining a Chernoff bound and a union bound. The third and fourth post were about the Follow-the-Regularized-Leader framework, which unifies multiplicative weights and gradient descent, and a “gradient descent view” of the Frieze-Kannan Weak Regularity Lemma. The fifth and sixth post were about the constrained version of the Follow-the-Regularized-Leader framework, and the Impagliazzo Hard-Core Set Lemma. Today we shall see the technique of Matrix Multiplicative Weights Updates.
1. Matrix Multiplicative Weights Update
In this post we consider the following generalization, introduced and studied by Arora and Kale, of the “learning from expert advice” setting and the multiplicative weights update method. In the “experts” model, we have a repeated game in which, at each time step , we have the option of following the advice of one of
experts; if we follow the advice of expert
at time
, we incur a loss of
, which is unknown to us (although, at time
we know the loss functions
). We are allowed to choose a probabilistic strategy, whereby we follow the advice of expert
with probability
, so that our expected loss at time
is
.
In the matrix version, instead of choosing an expert we are allowed to choose a unit
-dimensional vector
, and the loss incurred in choosing the vector
is
, where
is an unknown symmetric
matrix. We are also allowed to choose a probabilistic strategy, so that with probability
we choose the unit vector
, and we incur the expected loss