Hedge Algorithm and Subgradient Methods

Michel Baes (michel.baesifor.math.ethz.ch)
Michael Bürgisser (michael.buergisserifor.math.ethz.ch)

Abstract: We show that the Hedge Algorithm, a method that is widely used in Machine Learning, can be interpreted as a particular subgradient algorithm for minimizing a well-chosen convex function, namely as a Mirror Descent Scheme. Using this reformulation, we establish three modificitations and extensions of the Hedge Algorithm that are better or at least as good as the standard method with respect to worst-case guarantees. Numerical experiments show that the modified and extended methods that we suggest in this paper perform consistently better than the standard Hedge Algorithm.

Keywords: Hedge Algorithm, Subgradient Methods, Online Learning, Convex Optimization, Black-Box Model

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: 11/04/2010

Modify/Update this entry