Exponentiated Gradient Versus Gradient Descent for Linear Predictors

By Jyrki Kivinen, Manfred K. Warmuth. 1997

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Trust Region Policy Optimization (2015, methodology): “The KL divergence arises as the Bregman divergence from the entropy regularizer; this form of online mirror descent is commonly used for optimizing over probability distributions [15].”
Generalization and Equilibrium in Generative Adversarial Nets (GANs) (2017, methodology): “We use exponentiated gradient [Kivinen and Warmuth, 1997]: store the log-probabilities { α u i , i ∈ [ T ] } , and then obtain the weights by applying soft-max function on them: Note that our algorithm is maintaining weights on diﬀerent generators and discriminators.”
A Reductions Approach to Fair Classification (2018, methodology): “The proof follows immediately from the analysis of Freund & Schapire (1996) applied to the Exponentiated Gradient (EG) algorithm (Kivinen & Warmuth, 1997), which in our speciﬁc case is also equivalent to Hedge (Freund & Schapire, 1997).”
Introduction to Online Convex Optimization (2016, background): “Precursors to this algorithm, albeit for less general settings, were introduced and analyzed in (66).”
Batch Policy Learning under Constraints (2019, methodology): “For our main Algorithm 2, similar to (Agarwal et al., 2018), we use Exponentiated Gradient (EG) (Kivinen & Warmuth, 1997), which has a regret bound of O( √ log(m)T ) instead of O( √ mT ) as in OGD.”
An Online Learning Approach to Generative Adversarial Networks (2017, methodology): “Instead, they advocate the use of mixed strategies, and suggest to do so by using the exponentiated gradient algorithm Kivinen and Warmuth (1997).”
Stochastic Mirror Descent on Overparameterized Nonlinear Models (2019, background): “Exponentiated Gradient Descent: For ψ(w) = ∑ j w j logw j , the Bregman divergence becomes the unnormalized relative entropy (Kullback–Leibler divergence) Dψ(w,w′) = ∑ j w j log(w j/wj ) − ∑ j w j + ∑ j wj , which corresponds to the exponentiated GD (also known as the exponential weights) algorithm ”
Variable Metric Stochastic Approximation Theory (2009, methodology): “Therefore, online optimization methods that work with small subsamples of training data have received considerable attention recently (Kivinen and Warmuth, 1997; Schraudolph, 2002; Azoury and Warmuth, 2001; Shalev-Shwartz et al., 2007; Schraudolph et al., 2007).”
A Framework for Collaborative, Content-Based and Demographic Filtering (1999, methodology): “In this case, rather than using the Winnow algorithm for creating a content-based profile, a related algorithm (EG) for regression could be used (Kivinen and Warmuth 1995).”
Differentially Private Online Learning (2011, unknown): “OLR is a practically important learning problem and have a variety o f practical applications in domains such as finance [26].”
Differentiable Sparse Coding (2008, methodology): “…function has long been used for approximation problems in Geophysics, Crystallography, Astronomy, and Physics, where it is commonly referred to as Maximum Entropy on the Mean (MEM) [7], and has been shown in the online setting to compete with low L1-norm solutions in terms of regret [11, 12].”