  Many popular adaptive gradient methods such as Adam and RMSProp rely on an
exponential moving average (EMA) to normalize their stepsizes. While the EMA
makes these methods highly responsive to new gradient information, recent
research has shown that it also causes divergence on at least one convex
optimization problem. We propose a novel method called Expectigrad, which
adjusts stepsizes according to a per-component unweighted mean of all
historical gradients and computes a bias-corrected momentum term jointly
between the numerator and denominator. We prove that Expectigrad cannot diverge
on every instance of the optimization problem known to cause Adam to diverge.
We also establish a regret bound in the general stochastic nonconvex setting
that suggests Expectigrad is less susceptible to gradient variance than
existing methods are. Testing Expectigrad on several high-dimensional machine
learning tasks, we find it often performs favorably to state-of-the-art methods
with little hyperparameter tuning.
