2019

Exponentiated Gradient Meets Gradient Descent

Ghai, Udaya, Hazan, Elad, Singer, Yoram

Understand

The (stochastic) gradient descent and the multiplicative update method are probably the most popular algorithms in machine learning.

We introduce and study a new regularization which provides a unification of the additive and multiplicative updates.
This regularization is derived from an hyperbolic analogue of the entropy function, which we call hypentropy.
It is motivated by a natural extension of the multiplicative update to negative numbers.

Exponentiated gradient versus gradient descent for linear predictors
J. Kivinen and M.K. Warmuth · 1997
Earlier work this paper cites.
General convergence results for linear discriminant updates
A.J. Grove, N. Littlestone, and D. Schuurmans · 2001
Earlier work this paper cites.
The robustness of the p-norm algorithms
C. Gentile · 2003
Earlier work this paper cites.
On the generalization ability of on-line learning algorithms
N. Cesa-Bianchi, A. Conconi, and C. Gentile · 2004
Earlier work this paper cites.
Matrix exponentiated gradient updates for on-line learning and bregman projection
K. Tsuda, G. Rätsch, and M.K. Warmuth · 2005
Earlier work this paper cites.
Prediction, learning, and games
N. Cesa-Bianchi and G. Lugosi · 2006
Earlier work this paper cites.
A combinatorial, primal-dual approach to semidefinite programs
S. Arora and S. Kale · 2007
Earlier work this paper cites.

Winnowing subspaces
M.K. Warmuth · 2007
Cited alongside, same era.
Large deviations of vector-valued martingales in 2-smooth normed spaces
Original
A. Juditsky and A.S. Nemirovski · 2008
Cited alongside, same era.
Applications of strong convexity–strong smoothness duality to learning with matrices
Original
S.M. Kakade, S. Shalev-Shwartz, and A. Tewari · 2009
Cited alongside, same era.
Learning multiple layers of features from tiny images
A. Krizhevsky and G. Hinton · 2009
Cited alongside, same era.
Personal communication (circa 2010)
Manfred Warmuth · 2010
Cited alongside, same era.
Adaptive subgradient methods for online learning and stochastic optimization
J. Duchi, E. Hazan, and Y. Singer · 2011
Cited alongside, same era.
https://goo.gl/8vmt1B
Advanced convolutional neural networks
Cited in the paper.
CIFAR-10
A. Krizhevsky, V. Nair, and G. Hinton
Cited in the paper.

The multiplicative weights update method: a meta-algorithm and applications
S. Arora, E. Hazan, and S. Kale · 2012
Later among the works it cites.
Near-optimal algorithms for online matrix prediction
E. Hazan, S. Kale, and S. Shalev-Shwartz · 2012
Later among the works it cites.
Regularization techniques for learning with matrices
Sham M Kakade, Shai Shalev-Shwartz, and Ambuj Tewari · 2012
Later among the works it cites.
Online learning and online convex optimization
S. Shalev-Shwartz · 2012
Later among the works it cites.
The strong convexity of von neumann’s entropy, June 2013
Yao-Liang Yu · 2013
Later among the works it cites.
Introduction to online convex optimization
E. Hazan · 2016
Later among the works it cites.

alphaXiv searches the wider corpus for related work and actual follow-ups.

alphaXiv is searching for related work…

Reading the bibliography…