We show that the Hedge Algorithm, a method widely used in Machine Learning, can be interpreted as a particular subgradient algorithm for minimizing a well-chosen convex function, namely a Mirror Descent Scheme. Using this reformulation, we can improve slightly the worst-case convergence guarantees of the Hedge Algorithm.
Recently, Nesterov has introduced the class of Primal-Dual Subgradient Algorithms for convex optimization, which generalizes Mirror Descent Schemes. Using Nesterov’s insights, we derive new update rules for the Hedge Algorithm. Our numerical experiments show that these new update rules perform consistently better than the standard Hedge Algorithm.