Hedge Algorithm and Subgradient Methods
Michel Baes (michel.baesifor.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.
Entry Submitted: 12/14/2009
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|