Online Convex Optimization

The online convex optimization is stated as a general repeated game between a player and an adversary as follows:

The performance of algorithms for the above problem is often measured by the regret, which is the difference between the cumulated loss derived by the algorithm and the best fixed action in hindsight: The goal of the player now is to keep the growth of sublinear in , so that the average regret per step goes to zero as .

Without assumptions on the loss function , the above problem is impossible to solve. Therefore, we need to restrict the adversary’s power in choosing the loss functions and also provide the player with some additional hints:

View 1: Subgradient algorithm with projection

Since is strictly convex, we know that is nonnegative and iff .

Let’s break down the projection operator above to get a handy result we will use later. For that purpose, define the indicator function We also have that the subdifferential is the normal cone to at , denoted by . Now, expanding the projection, we have By first-order optimality condition: Rearranging, it follows that Since the projection exists and unique, we can write, without any ambiguous,

We are now at the position to present our first view of the (Online) Mirror Descent algorithm. The algorithm is often written in the form of subgradient algorithm with projection as follows:

This is a generalization of the subgradient algorithm, where the projection can be based on any Bregman divergence rather than the Euclidean distance. Therefore, it captures the geometric properties of more effectively.

Let’s explain why this update procedure is called a subgradient algorithm with projection, i.e., where the “projection" comes from. We rewrite our algorithm as By the first-order optimality condition, we have Rearranging, we get Now, let be a point such that . We can then rewrite as By , is exactly the Bregman projection of onto . Moreover, this projection is guaranteed to exist and be unique, thus we can write In addition, by proposition , is guaranteed to be in the interior of . Therefore, our algorithm is well-defined.

View 2: Mirror descent

Now we move to the second view of the algorithm, the view of Mirror Descent introduced by Nemirovski and Yudin for convex optimization. Let first define the convex conjugate (or Legendre-Fenchel transformation) of the function , denoted by :

Intuitively, first maps from the primal space into its dual space, and the update is done in the dual space. Then, maps the new point from the dual space back into .

Now we show that this second view is equivalent to our first view, i.e. the sequences produced by the two algorithms are identical. Applying the first-order optimality condition to the definition of , we have , or . Moreover, by proposition and by the conjugacy, we have We can then rewrite our update as where is the point with . This is exactly the interpretation of our first view as showed in .