Hedge algorithm and dual averaging schemes

DOI10.1007/S00186-012-0418-1MaRDI QIDQ2392814zbMATH OpenOpenAlexFDO

Authors Michel Baes, Michael Bürgisser

Publication date 2 August 2013

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.1275, http://hdl.handle.net/20.500.11850/58017

zbMATH Keywords

convex optimizationdual averaging methodsfirst-order methodshedge algorithm

Mathematics Subject Classification ID

Convex programming (90C25)

Abstract: We show that the Hedge algorithm, a method that is widely used in Machine Learning, can be interpreted as a particular instance of Dual Averaging schemes, which have recently been introduced by Nesterov for regret minimization. Based on this interpretation, we establish three alternative methods of the Hedge algorithm: one in the form of the original method, but with optimal parameters, one that requires less a priori information, and one that is better adapted to the context of the Hedge algorithm. All our modified methods have convergence results that are better or at least as good as the performance guarantees of the vanilla method. In numerical experiments, our methods significantly outperform the original scheme.

Recommendations

• scientific article; zbMATH DE number 7064063
• Follow the leader if you can, hedge if you must
• Unifying mirror descent and dual averaging
• Dual averaging methods for regularized stochastic learning and online optimization
• Logarithmic Regret Algorithms for Online Convex Optimization

Cites work

• A decision-theoretic generalization of on-line learning and an application to boosting
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• Prediction, Learning, and Games
• Primal-dual subgradient methods for convex problems
• The multiplicative weights update method: a meta-algorithm and applications

Describes a project that uses

Uses Software

• AdaBoost.MH

This page was built for publication: Hedge algorithm and dual averaging schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392814)