Hedge Algorithm and Subgradient Methods

Michel Baes (michel.baesifor.math.ethz.ch)
Michael Buergisser (michael.buergisserifor.math.ethz.ch)

Abstract: 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.

Keywords: Convex Optimization, Subgradient Schemes, Machine Learning, Hedge Algorithms

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: IFOR Internal report, December 2009, ETH Zurich, Raemistrasse 101, CH-8092 Zurich, Switzerland.

Download: [PDF]

Entry Submitted: 12/14/2009
Entry Accepted: 12/14/2009
Entry Last Modified: 02/16/2010

Modify/Update this entry