Adaptivity and Optimism: An Improved Exponentiated Gradient Algorithm

Abstract

We present an adaptive variant of the exponen-tiated gradient algorithm. Leveraging the opti-mistic learning framework of Rakhlin & Sridha-ran (2012), we obtain regret bounds that in the learning from experts setting depend on the vari-ance and path length of the best expert, improv-ing on results by Hazan & Kale (2008) and Chi-ang et al. (2012), and resolving an open problem posed by Kale (2012). Our techniques naturally extend to matrix-valued loss functions, where we present an adaptive matrix exponentiated gradi-ent algorithm. To obtain the optimal regret bound in the matrix case, we generalize the Follow-the-Regularized-Leader algorithm to vector-valued payoffs, which may be of independent interest. 1.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 46 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.