Expectigrad: Fast Stochastic Optimization with Robust Convergence Properties
Authors: Brett Daley
Christopher Amato
Venue:  (2021)
Keywords: deep learning
gradient descent
optimization

Abstract: 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.

Under review as a conference paper at ICLR 2021
EXPECTIGRAD: FAST STOCHASTIC OPTIMIZATION WITH ROBUST CONVERGENCE PROPERTIES
Anonymous authors Paper under double-blind review
ABSTRACT
Many popular adaptive gradient methods such as Adam and RMSProp rely on an exponential moving average (EMA) normalize their stepsizes. While the EMA makes these methods highly responsive to new gradient information, recent research has shown that also causes divergence on at least one convex optimization problem. We propose novel method called Expectigrad, which adjusts stepsizes according to a per-component unweighted mean of all historical gradients and computes 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 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 ohetterartt methods with little hyperparameter tuning.
INTRODUCTION
Efficiently training deep neural networks has proven crucial for achieving state-of-the-ard results in machine learning (e.g. Krizhevsky et al. 2012 Graves et al. 2013) Karpathy et al. 2014: Mnih
al.
2015 Silver et al. 2016 Vaswani et al. 2017 Radford et al. 2019; Schrittwieser et al. 2019
Vinyals et al. 2019). At the core of these successes lies the backpropagation algorithm (Rumelhart ctt al., 1986). which provides a general procedure for computing the gradient of a loss measure with respect the parameters of arbitrary network. Because exact gradient computation over an entire dataset is expensive, training is often conducted using randomly sampled minibatches of data instead ! Consequently, training can be modeled the loss is minimized in expectation. A natural algorithmic choice for this type of optimization problem is Stochastic Gradient Descent (SGD) (Robbins & Monro 195T) due its relatively cheap computational cost and its reliable convergence when the learning rate is appropriately annealed.
stochastic optimization problem where
major drawback of SGD is that its convergence rate is highly dependent on the condition number of the loss function (Boyd& & Vandenberghe 2004). ill-conditioned loss functions are nearly inevitable in deep learning due to the digh-dimmnsional nature of the models; pathological features such as plateaus, sharp nonlinearities, and saddle points become increasingly probable as the number of model parameters grows-all all which can interfere with learning (Pascanu et al., 2013) Dauphin et al. 2014; Goodfellow et al. 2016 Gohl (017). Enhancements to SGD such as momentum (Polyak 1964) and Nesterov momentum [Nesterov] 1983, /Sutskever et al. 2013) can help, but they still largely suffer from the same major shortcoming: namely, any particular choice of hyperparameters typically does not generalize well to a variety of different network topologies, and therefore costly hyperparameter searches must be conducted.
This problem has motivated significant research into adaptive methods for deep learning, which dynamically modify learning rates per-component basis with the goal of accelerating learning without tuning hyperparameters. AdaGrad (Duchi et al.) 2011) was an early success in this area that (in its simplest form) divides each step by running sum of gradient magnitudes, but this can cause its empirical performance to degrade noticeably in the presence of dense gradients. Later methods such ADADELTA (Zeiler 2012). RMSProp (Tieleman Hinton 2012). and Adam (Kingma & Ba 2014) remedied this by instead normalizing stepsizes by an exponential moving average (EMA).
Training small minibatches also improve generalization WWilsnn & Martinez. 2003).

---

Under review as a conference paper at ICLR 2021
Such methods are able to increase their learning rates after encountering regions of small gradients and have enjoyed widespread adoption due to their consistent empirical performance. Unfortunately, the EMA has recently been shown to cause divergence on certain convex optimization problem (Reddi et al. 2019) that we refer to as the Reddi Problem. This finding has severe implications because points to underlying flaw shared by the most widely used adaptive methods.
Recent attempts to resolve this EMM--iivegencc issue have been unsatisfying. Proposed methods invariably begin with Adam, and then apply a minor adjustment aimed suppressing divergence. Specifically, they either suddenly or gradually transition from Adam to SGD during training (Keskar & Socher 2017: Luo al., 2019), or clip certain quantities in the Adam update rule to limit the EMA's sensitivity (Zaheer et al. 2018: Reddi et al. 2019). While these methods technically do prevent divergence on the Reddi Problem, they fail to address the fundamental issue that the EMA can be unreliable, and they do not advance our theoretical understanding of alternatives that are inherently robust to divergence. Furthermore, by intentionally reducing the responsiveness of Adam, these modifications do not always translate into better empirical performance for problems of practical interest-yet they come at the expense of increased complexity.
The principal objective of this work is to therefore develop novel adaptive method that provides stronger convergence guarantees than EMA- methods while retaining fast learning speed. Towards this, we propose the Expectigrad algorithm, which introduces two major innovations: (1) normalization by the arithmetic mean instead of the EMA, and (2) "outer momentum" in which bias-corrected momentum is applied jointly to the numerator and denominator. Expectigrad provably converges on all instances of the Reddi Problem that causes Adam to diverge, and minimizes the function significantly faster than related methods using the same hyperparameters. We also derive regret bound for Expectigrad that establishes a convergence rate comparable to the best known rate for Adam. Our bounds also indicate that Expectigrad is less susceptible to noisy gradients. Finally, we test Expectigrad by training various neural network architectures with millions of learnable parameters; we show that consistently outperforms Adam and is competitive with other state-of-the-an methods.
2 PRELIMINARIES
We begin with some notational remarks. We always typeset vectors x, y in boldface avoid confusion with scalars x, y. We represent the j-th component of vector x; as X.J. The Euclidean norm is denoted by ||||| and the inner product is denoted by (x, y). All arithmetic operations can be assumed to be element- wise: c.g. x y for addition and subtraction, xy for multiplication, */y for division, x" for exponentiation by a scalar, /x for square root, and
We now consider the optimization setting that is the focus of this paper. Let 1: Rd x RD + R be (nonconvex) function that we seek to (locally) minimize in expectation over some distribution P on E C Rmm. Precisely, we must locate point x" E Rd with the property ff(x*) = 0, where fx) = B[[((, {) All expectations in our work are implicitly taken over & P(E). Direct
computation of (x) is assumed to be infeasible, but repeated calculation of Vl(x, {) is permitted. We also assume that has the following properties:
Assumption 1. [ is bounded below.
Assumption 2. 7. is Lipschitz continuous: ((xxE) ((y, S T.||- yll. Vx,y E Rd, AA E
Assumption 3. 1 is Lipschitz smooth: ||V[(x, E) - Vi(y, E)Il S L|[x - yll. Vx.y E Rd. Ag E E. Assumption D guarantees the existence of a well-defined set of minima (Nocedal & Wright 2006). While Assumptions 2 and need not share the same Lipschitz constant L > O in general, we assume that sufficiently large to satisfy both criteria simultaneously. These conditions are often met in practice, making our assumptions amenable to the deep learning setting that is the focus of this we prove three lemmas from Assumptions and that are necessary for our later theorems. With these results, we are ready to present Expectigrad in the following section.
paperE] In Appendix [B]
3 ALGORITHM
Our motivation for Expectigrad comes from the observation that successful adaptive methods are normalized by an EMA of past gradient magnitudes. This normalization process serves two important
We note that the commonly used ReLU activation is unfortunately not Lipschitz smooth, but smooth approximations such as the softplus function (Dugas al. (000) can be substituted. This limitation is not specific to our work but affects convergence results for all first-order methods, including SGD.
2

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Expectigrad
Select learning rate a >
> Default: a = 10-3
Select momentum constant E [0, 1)
>> Default: / = 0.9
Select denominator constant
P Default: e 10-
Initialize parameters Xo E Rd arbitrarily
Initialize rumning sum So + 0x
Initialize running counter no +- 0 X0
Initialize momentum mg + 0 XD for t 1,2...., .., do
Compute gradient estimate: g: t- VI(xx-1,E)) with & P(E)
Update running sum: St f 8 + g:
Update running counter: n2 < n + sign(g?)
Update momentum: m, fm,-1
-3
Define
/
Update parameters: X, X 1-3 m,
end for return Xy
benefits. First, stepsizes become scale invariant; the numerator and denominator are equally affected when the objective function is multiplied by constant, meaning a particular choice of learning rate is more likely to work well for wide array of tasks. Second, dividing by the recent gradient magnitude acts preconditioner, making the loss function more amenable to first-order optimization. One possible explanation for this is that dividing by the EMA inMA-rnoffar as it estimates the (diagonal) Fisher information matrix for a log- likelihood function acts as approximation natural gradient descent (Amari 1997 Pascanu Bengio 2013: Kingma & Ba 2014). A more recent hypothesis is that the EMA equalizes the stochastic gradient noise (Balles & Hennig. 2017), and that this isotropic noise is beneficial for escaping saddle points (Staib et al. 2019)).
These properties help explain why EMA-based adaptive methods like RMSProp and Adam successful on a variety of machine learning problems with relatively little hyperparameter tuning. Nevertheless, the EMA itself has been shown cause divergence the Reddi Problem-a synthetic online optimization problem proposed by Reddi et al. (2019). The rapidly decaying nature of the EMA reduces the influence of large yet infrequent gradients, which can cause the optimization to progress in an arbitrarily poor direction. Various related works have proposed to clip terms in the Adam update rule induce convergence on the Reddi Problem; we discuss them in Section 4.1
We argue that the approach of constraining EMA-based methods like Adam in an effort to force convergence is counterproductive. Doing so not only risks impacting performance, but it also points to a lack of theoretical understanding, While limiting the adaptation of the EMA may prevent divergence on the Reddi Problem, it does not address the root cause of divergence itself. We are instead interested in algorithms that automatically robust to rare, high-magnitudd gradients that characteristic of the Reddi Problem. We begin our search by considering the following update rule in which stepsizes normalized by an arithmetic mean of all gradient samples up the current timestep l:
g:
X
D B
Here, a > is the learning rate and 6 > positive constant that prevents division by zero. Crucially, this update retains the scale-invariance property of EMA-based methods discussed the beginning of this section: multiplying the gradient by a scalar does not affect the stepsizes (assuming is small). Furthermore, the denominator becomes less responsive proceeds, but never becomes completely static. This is precisely the behavior we want for a method that balances empirical speed with theoretical convergence.
gradients training
To improve the performance of the algorithm, we will want to make some modifications to I First, note that the explicit summation is unnecessary. If we store the s, each time i, then we can
3

---

Under review as a conference paper at ICLR 2021
efficiently compute it from the previous sum: S₃ <- 8 g. Second, observe that dividing by t to compute the mean could be problematic when gradients are very sparse commonlyy the case when using Rectified Linear Unit (ReLU) activations (Nair & Hinton 2010). Consider what happens when a component of the gradient is zero for a very long time: as increments unconditionally, the ratio #t approaches zero. When nonzero component is suddenly encountered, the algorithm will take a large-and and potentially catastrophic- along that dimension. We can mitigate this by introducing auxiliary variable n, that counts the number of nonzero gradients that have occurred. Note that we can concisely update n by simply adding the element- wise sign of the squared gradient: n, f- n sign Putting these two changes together (and defining 0),
g
X X
(2)
This new algorithm tracks a per-component arithmetic mean where each component may have distinct number of counts, thereby ignoring sparsity in the optimization problem. Thus, with some additional memory, we have made the update highly efficient and less prone to numerically instability.
Finally, we can also apply momentum to help accelerate learning when the gradient signal is weak. Traditionally, momentum is first applied to the gradient estimator, and then is scaled by the adaptive method (e.g. Adam). In our work, we propose to reverse the order by computing the adaptive steps first and then applying momentum to them. This is important to satisfy the superposition principle: the momentum step "scheduled" at the current timestep is not re realed by future changes in the denominator. Letting [0,1] 1) be the momentum constant, we arrive at our final update:
X₁ 1
1 g m
where m, = -mmm1 (1 3)
St
We call this "outer" momentum as it applies to the entire update rule and not just the numerator. The coefficient 1/(1-8") ) is a bias-correctivn factor introduced by Kingma & Ba (2014). We refer to (3) as Expectigrad and formally present it in Algorithm [] While we have only intuitively justified our design choices far, will spend the next few sections rigorously analyzing their theoretical and empirical implications.
4 COMPARISON WITH RELATED METHODS
Expectigrad eschews the familiar EMA in favor the arithmetic average, and utilizes a newly formulated momentum that incorporates adaptive stepsizes. It is not immediately apparent that these particular choices are better; this section is devoted to illuminating the benefits of these substitutions by comparing them with other approaches in the literature.
4.1 ARITHMETIC MEAN NORMALIZATION
Unlike existing adaptive methods, Expectigrad is normalized by non-exponential mean. Perhaps the most salient concern with this is that the denominator becomes insensitive new gradients as the algorithm progresses. It turns out that this behavior is beneficial, not harmful. To see this, we formally introduce the Reddi Problem, the online optimization problem from Reddi et al. (2019):
hx(x) = Ca if {{Cx
(mod N)
(4)
otherwise
It is assumed that C >>>>>>> N and therefore moving towards -o minimizes this function In- triguingly, Adam incorrectly proceeds towards -00 when N = 3 when its EMA adapts too quickly (Reddi et al. 2019). This explains why its EMA constant B3 is typically very close in practice. In Figure we replicate the experiment from Reddi et al. (2019) and show that Expectigrad can indeed minimize (z(x) while Adam cannot. RMSProp and ADADELTA diverge too because they utilize EMAs for normalization.
We also compare against recent methods AMSGrad (Reddi al. 2019) and Yogi (Zaheer et al. 2018 that have been proposed to fix divergence by modifying the Adam update rule. Specifically, AMSGrad
Thhe domain of h, was restricted [-1, 1] in Reddi et al. 2019), making the optimal solution x² -1 We will not impose this restriction; therefore suffices to show that lim 34 -oc prove non-divergence.
4

---

Under review as a conference paper at ICLR 2021
Reddi Problem (online)
Reddi Problem (online)
Reddi Problem (stochestic)
Reddi Problem (stochastic)
Average Regree
Postoon
1.0
4MG5red
AMSSres
4P5Grd Poantiiion
-1.2
Peamt giaal
EIGOS To.
-1.99
logl
840
Tog
-2.00
22'
22
10
22"
Timestops
Timestops
Timestops
Timestops
Figure 1: We replicated the synthetic convex optimization problem from Reddi et al. (2019) that causes Adam to diverge. We also tested RMSProp and ADADELTA, two other EMA-based methods, and found that they diverge too. Compared to AMSGrad and Yogi, Expectigrad minimizes both functions about 10 times faster despite using the same hyperparameters. (Note that AMSGrad is partially occluded by Yogi in the graphs.) We clipped the domain to [-1, 1] for graphical purposes.
normalizes stepsizes using the maximum past EMA value, thereby enforcing a monotonically non- decreasing denominator. Yogi similarly limits the effective rate of change of its EMA. While both of these approaches succeed in preventing divergence on the Reddi Problem, simply constraining the EMA in this manner is not an ideal solution; it sacrifices not only scale invariance but also the ability to respond quickly to sudden topological changes when necessary. Figure illlsttrates the major consequence of these harmful effects: slow learning. Despite having identical hyperparameters, AMSGrad and Yogi require nearly 10 times more experience than Expectigrad does to reach æ = -1.
In addition to our experiments, we can prove analytically that Expectigrad will never diverge on the Reddi Problem. For simplicity, we let 3 = 0 for all theorems in our paper.
Theorem 1. (Non- -iverriveeeeece of Expectigrad on the Reddi Problem.) Let he be the function defined in f and let ( j be sequence of points generuted by Expectigrad. For any integer N > 2 and any real number C > N 1, lim It = -x0. Hence, Expectigrad never diverges on this problem.
t-
We relegate the proof Appendix In brief, we show that the displacement of Expectigrad over any period of hy (z:) is bounded above by a negative constant. This implies that the total displacement of Expectigrad after an arbitrarily large number of periods must approach - co. An important corollary of Theorem D is that there exists at least one problem where Adam diverges but Expectigrad does not.
That Expectigrad always converges on this problem holds practical significance. The Reddi Problem mimics a dataset where few training samples are highly informative but rare-a setting that commonly arises in practical machine learning problems. While EMA-based methods tend to diminish the importance of these rare samples, and clipped-EMA methods tend to learn slowly, Expectigrad converges both quickly and reliably.
4.2 OUTER MOMENTUM
We now study the effect of outer momentum learning speed by conducting experiments on the classic MNIST handwriting recognition task (LeCun et al., 1998). The training and test sets respectively consist of 60,000 and 10,000 grayscale images of size 28 28 that must be classified according to which digit between 0 and 9 they contain. Following Kingma & Ba 2014)) we trained a 2-layer fully connected network with 1,000 ReLU units per layer.
In our first experiment, we analyze the impact of substituting various forms of momentum into Expectigrad: classic "inner" momentum (Polyak 1964). bias-corrected "inner" momentum (Kingma & Ba 2014), and our bias-corrected "outer" momentum in (3). Appendix A providds their update equations for reference. For each variant, we tested a range of f-values and measured the training loss after exactly one epoch of training (Figure 2 left). This offers insight into how different momenta impact performance early in training. We see that bias correction is crucial for fast learning, evidenced by the poor performance of the uncorrected baseline. Simultancously, for every choice of 3, our birs-coreected outer momentum performs at least as well as bias-corrected inner momentum. Notably, the performance gap widens quickly as 8 approaches 1. As discussed earlier, we attribute the improvement of outer momentum to its preservation of linear superposition. Formally, linear superposition holds when De d. Ein m, for momentum m, fm--1 + (1 - B) Outer
5

---

Under review as a conference paper at ICLR 2021
Comparison of Different Momentum Formulations in Expectigrad
MNIST
0.46
Inser
Training Loss After Eppcc
0.42
Inner corractes tourst
Training Loss
10-4
0.36
10'
Lohy
0.36
10-4
0.34
ADADELTA
0.32
10-4
RMSProp
Adam
Expecing rad
0.30
0.0
0.2
0.4 0.5
1.0
10-1
50
75
Momentum Constant (8)
Epoch
Figure 2: Using the MNIST dataset, we explored the effects of different momenta Expectigrad by training for single epoch (left). We swept the momentum constant 3 E 1) for three variants: inner (Polyak 1964), bias-corrected inner (Kingma Ba 2014), and bias-corrected outer (ours). The dashed vertical line represents 3 = 0.9, the commonly used default value for Adam and its extensions. Outer momentum always outperforms inner momentum, and the improvement becomes highly pronounced as 3 + 1. Results were averaged over 10 runs.
momentum clearly obeys this because all adaptation occurs before the momentum update; on the other hand, inner momentum adapts m, directly, implicitly re-scaling previous impulses and therefore violating the equality.
Because the first epoch of training may not be indicative of overall performance, we next test Expectigrad's performance over 150 epochs of training. We compared against three EMA-based methods- Brrthods-RMSPrrppe RMSProp. ADADELTA, and Adam using their default hyperparameter values from TensorFlow (Abadi et al. 2016) (see Appendix A). For Expectigrad, we adopted Adam's 's default values: 10-3 tude below that of the other methods (Figure [ right). These results demonstrate that Expectigrad performs very well empirically despite borrowing hyperparameter values from an existing method.
0.9, 10-8, Expectigrad achieves training loss several orders of magni-
5 CONVERGENCE ANALYSIS
Theorem asssrtss that Expectigrad cannot diverge on the Reddi Problem, but does not guarantee that Expectigrad converges for wide class of functions. Our next step to establish regret bounds for the general case of a smooth, nonconvex function. We define the cumulative regret at time T in
terms of the gradient norm: R(T) = Σi= (x)]). Under analysis similar to that of Zaheer ct al. (2018), we arrive at the next theorem.
Theorem 2. (Regrel Bound for Expectigrad.) Let be a function satisfying Assumptions) 7 3 and let (xx )T= be sequence of points in I. generated by Expectigrad with learning rate S and denominator constant e >> Given gradient variance o² and minibatch size 2 1. the average regret incurred by Expectigrad has the following upper bound:
f(x)) f(x)) - f(xx)
2L
1
T R(T) (e+ L)
L2 12
0
aT'
22T
2eb
VT
The proof is in Appendix D Like other stochastic first-order methods, Expectigrad approaches but does not truly reach a stationary point due to the variance of the gradient estimator. The regret vanishes when utilizing time-increasing batch size (Zaheer et al. 2018) annealed learning rate.
Comparing this bound to those of Adam and Yogi derived in Zaheer et al. (2088) offers some insights. First, Expectigrad achieves the same asymptotic convergence rate these methods do. Second, Expectigrad converges for a much larger set of hyperparameter values; whereas Adam and Yogi both require 2f. and 2 4LV1- B2, Expectigrad needs only < f. and > O. Thus, Expectigrad entirely removes the unrealistic limitation on c and doubles the maximum permissible value of a.
Third, the right-most term of our bound in Theorem is O(2), while the analogous term for Adam and Yogi is ((+) This term accounts for the irreducible regret due to the statistical variance of the gradient estimate. The denominator constant is typically chosen to be very small in practice, which

---

Under review as a conference paper at ICLR 2021
CIFAR-10: VGGNet-16
CIFAR-10 10: VGGNet-116
CIFAR-10: Res No
CIFAR-10: ResNet-50
101
AdaCcad
AceSre
Add
save
Max Teu Tepeotyu4
Bran
Top Error
Tay
Top-1 Traniing Errur
Traiiing Less
Eepelbouad
Peantiqua
Training
10-11
Epoch
Epach
Epoch
Epoch
Figure 3: We compared five adaptive methods on CIFAR-10 by training two large convolutional models, VGGNet-16 16 (left, center-left) and ResNet-50 (center-right, right). Hyperparameters were chosen by a small grid search (A (Appendix Aj.. Expectigrad outperformed the baseline methods for both models with respect to training loss and top-1 error rate. Results were averaged over 10 runs.
implies < 1 and in turn suggests that Expectigrad is less susceptible to gradient noise than Adam and Yogi are. These results may hold empirical significance, which we evaluate in Section 6
22
EXPERIMENTS
In this section, conduct variety of experiments study the empirical performance of Expectigrad. Details for preprocessing, augmentation, and hyperparameter selection are provided in Appendix [
CIFAR-10 We begin with challenging image classification benchmark, the CIFAR-10 10 dataset (Krizhevsky et al. 2009), where colored 32 x 32 images of various objects must be classified into one of 10 categories. The training and test sets have 50,000 and 10,000 images, respectively. We trained two models for 250 epochs: a 16-layer VGGNet (Simonyan & Zisserman 2014) with 33.6 million parameters and a 50-layer ResNet (He al. 2016) with 23.5 million parameters. We conducted a small grid search for a- and e-values. In Figure 3 we compare five adaptive methods: AdaGrad, Adam, AMSGrad, Yogi, and Expectigrad. For both network architectures, Expectigrad achieves lower training loss and error than the other methods do, demonstrating that Expectigrad is competitive with the best methods from the deep learning literature.
Vietta--eee Translation The IWSLT' 15 English- Vietnamese translation task features a training set of over 133,000 sentence pairs and a test set of 1.268 sentence pairs. We implemented 4-layer, 1024-unit LSTM (Hochreiter & Schmidhuber) 1997) and a Transformer (Vaswani et al., 2017) using the tensor2tenso library Vaswani et al. (2018). These models are significantly different from the feedforward architectures we have tested so far, and are both highly non-trivial to optimize. We compared Expectigrad against four "Adam-like" methods: Yogi, AMSGrad, Adafactor (Shazeer & Stern 2018), and Adam. The final BLEU scores (Papineni al. 2002) the test data reported in Table Expectigrad, Yogi. and AMSGrad all performed well on both tasks. Expectigrad did the best with the Transformer, and achieves scores near the saate-of-the-eae
results from Zaheer let al. (2188) without any learning rate annealing. Despite training for twice as long with the LSTMM, these three methods achieved only about half of the Transformer's score- likely because the LSTM model is less expressive. Adafactor performed somewhat worse for both models but still achieved decent performance. To our surprise, Adam failed completely at both tasks. We speculate that its poor performance could be related to its divergent behavior on the Reddi Problem; perhaps these translation tasks also exhibit large, rare gradients that are critical for learning. This would explain why Expectigrad, Yogi. and AMSGrad all outperform Adam so significantly, but further empirical evidence would be needed to conclusively determine this.
ImageNet For our final experiment, we compare Expectigrad and Yogi on the massive ILSVRC 2012 classification task. This dataset features more than 1.3M training images and 50,000 validation images from the ImageNet database (Russakovsky et al. 2015) divided into 1,000 classes. We trained a MobileNetV2 (Sandler et al., 2018)) for 300 epochs. We plot training loss, top-1 training error rate, and top-5 validation error rate in Figure 4 While both optimization methods perform reasonably well, Expectigrad achieves lower error rates on the training and test data than Yogi does. This is in spite of using the recommended hyperparameters for Yogi. We note that specific learning rate annealing schedule for Yogi was used by Zaheer et al. (2018) to outperform a highly-tunee R.MPrrp implementation; our results here suggest that Yogi's empirical success in that instance may be due
7

---

Under review as a conference paper at ICLR 2021
LSTM
Transformer
Method
Cased
Uncased
Cased
Uncased
Expectigrad
13.68 + 0.28
14.18 + 0.27
28.33 + 0.17
29.12 + 0.16
Yogi
13.86 + 0.20
14.39 0.22
2
29.07 0.15
AMSGrad
14.00 0.23
14.50 0.25
28.27 1
29.04 + 0.29
Adafactor
12.65 + 0.15
13.11 = 0.13
24.36 = 0.53
25.05 + 0.52
Adam
0.03 + 0.01
0.06 + 0.01
0.30 = 0.09
0.38 0.09
Table 1: BLEU scores for the IWSLT"15 15 Vigeta--eie translation task with LSTM and Transformer. Results were averaged over 10 random seeds with standard deviation reported. Bold values represent the best model scores that overlap within one standard deviation. While Adam could not succeed at either task, Expectigrad achieved performances competitive with AMSGrad and Yogi.
ImageNet
ImageNet
ImageNet
3x
10
10
Yog!
Yng!
Yog!
Expectigrb0
Exoectigrod
Expectigaa
Top-1 Training Error
Top-5 Valldation Errar
2x 10f
8xx10"
6
Training
4x 10
4x100
50
1.00
150
200
250
300
50
100
150
200
250
300
50
100
150
200
250
300
Epoch
Epoch
Epoch
Figure 4: We compared Expectigrad and Yogi training a MobileNetV2 on the ImageNet classification task. Despite using the 10x larger learning rate for Yogi recommended by Zaheer al. (2018). Expectigrad achieves lower loss and training/validate error rates in the same amount of training. Results were averaged over runs.
more to its initially large learning rate and sophisticated annealing schedule rather than its particular adaptation scheme.
Summary We tested Expectigrad on diverse array of deep learning architectures: fully con- nected (Section :): convolutional (with and without residual connections); recurrent; and attention networks. Despite significant differences in these network topologies, Expectigrad was among the top-performing methods for each task- especilllyy for the CIFAR-10 10 experiments, where Expectigrad was the best method with respect to both training loss and top-1 error. In the English- Vietnamese translation tasks, Adam was unsuccessful in training either language model while Expectigrad achieved results competitive with the most recent methods from the literature. Finally, the large-scale ImageNet experiment affirms that Expectigrad's arithmetic mean remains effective when training for millions of steps.
CONCLUSION
We introduced Expectigrad, an adaptive gradient method that normalizes stepsizes with an arithmetic mean instead of an EMA and computes momentum jointly between its numerator and denominator. We proved that Expectigrad converges for smooth (possibly nonconvex) functions including the Reddi Problem where EMA-based methods like Adam, RMSProp, and ADADELTA fail. Expectigrad performed competitively across wide variety of high-dimensional neural network architectures, often outperforming state-of of-the-rrt methods, Our machine translation experiments revealed practical problems where Adam diverges yet Expectigrad achieves very strong performance, providing potential affirmation of our thcoretical predictions. Ultimately, Expectigrad's fast performance refutes any notion that adaptive methods must rely EMA be responsive to recent gradient information.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A system for large-scale machine learning. In /2th {USENIX) Symposium on Operating Systems Design and Implementation ((OSD/) 16), pp. 265-283, 2016.
Shun-ichi Amari. Neural learning in structured parameter spaces-natural riemannian gradient. In Advances in neural information processing systems, pp. 127-133, 1997.
Lukas Balles and Philipp Hennig. Dissecting adam: The sign, magnitude and variance of stochastic gradients. arXiv preprint
2017.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensions non-convex optimization. In Advances in neural information processing systems, pp. 2933-2941, 2014.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(1u1)2121-2155, 2011.
Charles Dugas, Yoshua Bengio, François Bélisle, Claude Nadeau, and René Garcia. Incorporating second-order functional knowledge for better option pricing. In Advances in neural information processing systems, pp. 472-478, 2001.
Gabriel Goh. Why momentum really works. Distill, 2017. doi: 10.23915/dissill.00006. URL /ttp:://istilll.ubb11111
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
Alex Graves, Aldel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing, pp. 6645-6649. IEEE, 2013.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural compulation, 9(8):
1735-1780, 1997.
Andrej Karpathy, George Toderici, Sanketh Shetty, Thomas Leung, Rahul Sukthankar, and Li Fei-Fei. Large-scale video classification with convolutional neural networks. In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 1725-1732, 2014.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam to sgd. arXiv preprint 1rXiv:1712.07628, 2017.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 141 2014.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolu- tional neural networks. Advances neural information processing systems, pp. 1097-1105, 2012.
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, Patrick Haffner, et al. Gradient-based learning applied to document recognition. Proceedings of the IEFE, 86(11):2278-2333 1998.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. arXiv preprint arXiv: 1902.09843 2019.

---

Under review as a conference paper at ICLR 2021
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 5 518(7540):529, 2015.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference on machine learning (ICML-10), pp. 807-814, 2010.
Yurii E Nesterov. A method for solving the convex programming problem with convergence rate (l/k22). In Dokl. akad. nauk Sssr, volume 269, pp. 543-547, 1983.
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the 40th amnual meeting on association for computational linguistics, pp. 311 311-318. Association for Computational Linguistics, 2002.
Razvan Pascanu and Yoshua Bengio. Revisiting natural gradient for deep networks. arXiv preprint arXiv:1301.3584 2013.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In International conference on machine learning, pp. 1310-1318, 2013.
Boris T Polyak. Some methods of speeding up the convergence iteration methods. USSR
Computational Mathematics and Mathematical Physics, 4(5):1-17, 1964.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and llya Sutskever. Language models are unsupervised multitask learners. OpenAl Blog, 1(8), 2019.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv: / (w..:/044...9. 09237, 2019.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. nature, 323(6688) 1986.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115(3):211-252 2015.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chiel Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4510 45200, 2018.
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. arXiv preprint arXiv: (1I::091.00265. 2019.
Noam Shazeer and Mitchell Stemn Adafactor: Adaptive learning rates with sublinear memory cost.
arXiv preprint arXiv:1804.04222 2018.
David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484, 2016.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1rXiv:1409.1555 2014.
Houshang Sohrab. Basic real analysis, volume 231. Springer, 2003.
Matthew Staib. Sashank Reddi, Satyen Kale, Sanjiv Kumar, and Suvrit Sra. Escaping saddle points with adaptive gradient methods. arXiv preprint 19X 2019.
10

---

Under review as a conference paper at ICLR 2021
Iya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pp. 1139- 1139-1147, 2013.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31, 2012.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Ashish Vaswani, Samy Bengio, Eugene Brevdo, Francois Chollet, Aidan N Gomez, Stephan Gouws, Llion Jones, Lukasz Kaiser, Nal Kalchbrenner, Niki Parmar, al. Tensor2tensor for neural machine translation. arXiv preprint 1803.00100 2018.
Oriol Vinyals, Igor Babuschkin, Wojeiech M Czamecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung. David Choi, Richard Powell, Timo Ewalds, Petko Georgiev, al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350-33) -544003-4,---- 2019.
D Randall Wilson and Tony R Martinez. The general inefficiency of batch training for gradient descent learning. Neural networks, 16(10):1429-14511 2003.
Manzil Zaheer, Sashank Reddi, Devendra Sachan, Satyen Kale, and Sanjiy Kumar. Adaptive methods for nonconvex optimization. In Advances in neural information processing systems, pp. 9793-9803, 2018.
Matthew D Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv: 1212:52111,,011, 2012.


Reviews:
[{"review_id": "x4yIHNXCfgI", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The paper proposes a new adaptive method for stochastic optimization with convergence guarantees. Experimental results on two tasks viz., image classification and language translation are provided to show the benefit of the proposed algorithm.\n\nStrength:\n\n+ The paper proposes an adaptive stochastic optimization scheme called Expectigrad for training deep neural networks. Expectigrad is shown to converge (to a stationary point) at the same rate as other recently introduced adaptive methods such as Adam, and Yogi. To motivate their algorithm, the paper studies the Reddi problem introduced in Reddi et al., and show that there exists an averaging scheme to prevent divergence in that \"class\" of problems. The paper as such motivates the algorithm in the general case first and then applies the arithmetic mean normalization to the Reddi problem, but I find the other way also reasonable, and intuitive.\n+ Apart from the averaging scheme, they also propose a novel momentum term that automatically achieves scale invariance, that is, (if I understand correctly) the step size is invariant to coordinate transformations of the loss function. They provide a detailed theoretical and empirical justification for the momentum term. \n\nWeakness:\n\n- While the novelty of the algorithm proposed in clear, the paper is hard to read in certain parts, and I'm not sure if they are correct. For example, in Page 2, the paper mentions that Zaheer  et al, Reddi et al fail to address the \"fundamental\" issue, and I'm not sure if the paper specifies the issue explicitly anywhere. To this particular point, the paper misses an important reference arXiv:1910.07454 where they show that exponential learning rates may be possible indeed. Perhaps some discussion on this in the paper would make it clear to the reader.  Second, above equation (3), the authors mention that it is important to satisfy the \"superposition\" principle without any reference or explanation. Third, in section 4.1 (above Theorem 1), I'm not sure what \"topological\" changes are? In the function with respect to the parameters or data? Indeed, this is an important distinction that needs to be clarified. \n\n- The experiments showing the benefits of Expectigrad is far from convincing. There is a discrepancy in the results being reported. For example, in CIFAR10 experiments, training loss (and training error) are reported whereas for the language translation, BLEU scores on the test set are reported, and in imagenet experiments, again training (and validation) measures are reported. The experiments were averaged over 10 runs in CIFAR10 experiments whereas 3 runs in Imagenet experiments whereas averaging is not discussed for other simulations, MNIST experiments.  Do the training curves provided have confidence? I mean the results are averaged, so providing confidence interval is easy and provides more information about the algorithm.\n\nAfter response: Thanks for the clarifications. The proposed method is a modification of existing averaging schemes to schedule learning rate, but more experimental evaluations are required to determine the benefits of algorithm.", "extra_scores": {}, "extra_text": {}}, {"review_id": "VR13ttdlPGE", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes Expectigrad, which replaces the exponential moving average in Adam and RMSProp with averaging over all historical gradients. It shows theoretically and empirically that it outperforms the state-of-the-art stochastic optimization schemes. I have the following questions for the authors:\n\n\n1. Could you please elaborate more on why average over all historical data can be better than EMA? It's not fully convincing to me. Imagine the case when I first have very small gradients (but non-zero so n_t also adds up) for a long time, and suddenly I've got a gradient that is much larger. In this case, the gradient step would be arbitrarily large and brings a lot of instability. With this example, I can easily construct some scenarios that lead to divergence. \n\n\n\nWhy does this not conflict with Theorem 2? It seems that the  Lipschitz gradient assumption helps. But the Adam paper does have a convergence guarantee without the Lipschitz gradient assumption. So there does exist some scenario where Adam converges while Expertigrad diverges.\n\n\n2. At the end of the introduction, the authors claimed that 'Expectigrad provably converges on all instances of the Reddi Problem that causes Adam to diverge, and minimizes the function significantly faster than related methods using the same hyperparameters.' Does that mean you are comparing different algorithms with the same hyperparameters instead of doing grid-search for each algorithm separately?\n\n\n\n3. In the algorithm description and equation (1), it does not make sense to have a square of a vector: what does it mean? Is that element-wise square or two norm of the vector? Is s_t a scalar or vector? It is also weird to have the scalar n_t the same boldface as the other vectors.\n\n\nI read the author feedback and decide to keep my score. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "OrJGybNrTc5", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes Expectigrad, which is a new optimizer for nonconvex optimization. The main idea is to consider arithmetic mean of squared gradients instead of exponential moving average and to use a normalization factor that takes into account the number of nonzeros observed during the run of the algorithm, for each component. The algorithm is analyzed for solving smooth nonconvex optimization and its practical performance is investigated.\n\nIn terms of the strengths of the paper, I found the idea of using normalization $n_t$ depending on the sparsity interesting. However, the idea of using $s_t$, which is given in eq. (1) seems to be not novel. In particular, this step is already used in Adagrad based methods. For example, AdamNC method in Reddi et al., 2019 already shows that with such an update for second moment estimate, one can obtain convergence. This algorithm is also analyzed by Chen et al., 2018 in the nonconvex setting, which seems to be missed by the authors.\n\nIn terms of the analysis, the authors make the simplifying assumptions of $\\beta=0$ in page 5 and ignoring sparsity in page 16, which basically converts the algorithm to Adagrad. Can the authors clarify this connection and let me know if I am missing something? Therefore, I am not sure if the analysis brings new results that are not known in the literature. Such simplifications take away the novel parts of the algorithm and makes it impossible for the authors to show the effect of their idea in theory. Therefore the potential benefit of the method becomes purely experimental. For example, it is known in the literature that the extension of analyses for including nonzero (especially constant) $\\beta$ is not always easy and one needs to be careful [1].\n\nMoreover, the author's usage of the term \"regret\" is not correct. The authors use the expected gradient norm as the optimality measure, which is the standard one for nonconvex optimization. Regret is used for online optimization, which is more general than stochastic optimization which is considered in this paper. \n\nNext, the authors analyze the algorithm in Thm 2 with increasing mini-batch sizes. However, Zaheer et al., 2018 shows that with increasing (or depending on the number of iterations $T$) mini-batch sizes, Adam (which is non-convergent in general) also works. Therefore,  I think this setting is not suitable since increasing mini-batch sizes shadow most of the theoretical challenges. It is better to analyze the standard setting without increasing mini-batch sizes.\n\nIn practice, the comparisons with Adagrad and AdamNC are omitted. Moreover, it seems that the improvement of Expectigrad compared to SOTA is not significant.\n\nTherefore, in terms of algorithmic ideas and the novelties in theoretical analysis, this paper does not meet the bar for ICLR. In particular, the simplifying assumptions that the authors make for the algorithm ($\\beta=0$ and no sparsity) essentially takes away the interesting parts of the proposed algorithm, and making the theoretical analysis not consistent with the algorithm used in practice. Second, the algorithm needs to use increasing mini-batch sizes (the rate in Thm. 2 has $1/b$ as an additive term), which is another oversimplified assumption for the analysis, many adaptive algorithms are proven to converge without this assumption. Empirical merit of the method is also marginal and some important comparisons are missing. As a result, I am voting for rejection.\n\nChen et al., 2018: Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. ICLR, 2019.\n\n[1] A New Regret Analysis for Adam-type Algorithms, Alacaoglu, Malitsky, Mertikopoulos, Cevher, ICML 2020.\n\n\n======== after discussion phase =======\n\nThe main drawbacks of the paper remain after the discussion. Mainly, the analysis is too simplistic which basically ignores the new aspects of the algorithm and its comparison with well-known methods is unclear. Therefore, I keep my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "I07Ms4UK0e3", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper proposes the Expectigrad algorithm that normalizes the exponential moving average (EMA) of first moments on the fly. This avoids normalizing historical gradients by future gradients. The normalization factor is an unweighted average, instead of an EMA, of the historical second moments. For the special case where the EMA constant of the first moment is zero, the paper shows that Expectigrad converges to the optimum on the online convex problems proposed by Reddi et al. (2018) for which the vanilla ADAM fails to converge. For general stochastic smooth convex problems with bounded stochastic gradients, the paper shows that the convergence rate of mini-batch Expectigrad is $O(1 / \\sqrt{T} + 1 / b)$ where $b$ is the mini-batch size.\n\nPros:\n(1) The idea of normalizing on the fly is interesting because it is more sensitive when the gradient dynamic is non-stationary.\n\n(2) The algorithm performs well on the examples considered in the paper.\n\nConcerns:\n(1) Theorem 1 assumes $\\beta = 0$ \"for simplicity\". I think this is too weak to justify the algorithm. When $\\beta = 0$, the algorithm is almost identical to AdaGrad, except that AdaGrad does not take the sparsity into account and sets $n_{t} = t$. On the Reddi problem, the gradient is not sparse, and thus Expectigrad with $\\beta = 0$ is equivalent to AdaGrad, if I am not mistaken. Reddi et al. (2018) has already shown that AdaGrad does not diverge on the counterexamples. In order to justify the algorithm, it is necessary to prove a similar result for the case $\\beta > 0$, since it is set to be $0.9$ in the experiments. Reddi et al. (2018) have results of this kind (which only requires $\\beta < \\sqrt{\\beta_2}$ where $\\beta_2$ is the EMA constant of the second moment).\n\n(2) The paper claims (in the bottom of page 6) that Expectigrad has strictly better complexity than Yogi. I do not see why this is the case. The convergence rate of Yogi is $O(1 / T + 1 / b)$ (their Corollary 4) while that of Expectigrad if $O(1 / \\sqrt{T} + 1 / b)$. The latter is worse. To take one step further, in order to have $E ||\\nabla f(x)||\\le \\epsilon$, we need to set the convergence rate as $\\epsilon^2$ since the bound is proved for $E ||\\nabla f(x)||^2$. For Yogi, the mini-batch size $b$ needs to be $O(1 / \\epsilon^2)$ and the number of iterations $T$ needs to be $O(1 / \\epsilon^2)$ as well. So the overall complexity is $O(1 / \\epsilon^4)$ which matches the complexity of SGD. However, for Expectigrad, the mini-batch size $b$ needs to be $O(1 / \\epsilon^4)$ and the number of iterations $T$ needs to be $O(1 / \\epsilon^2)$. The overall complexity is $O(1 / \\epsilon^6)$, which is much higher than SGD. I do not understand why Expectigrad is better than Yogi or even SGD.\n\n(3) The footnote in page 2 states that \"This limitation is not specific to our work but affects convergence results for all first-order methods, including SGD\". This is incorrect. Under assumption 2 of the bounded stochastic gradient, SGD converges for non-smooth functions.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new adaptive optimization algorithm which is claimed to have better convergence properties and lower susceptibility to gradient variance. Reviewers found the idea of normalizing on the fly to be interesting, but raised some important concerns. Although similar to AdaGrad, Expectigrad has a very important differentiation due to division by $n_t$. Assuming $\beta=0$ in my opinion is also ok and many papers assume this for analysis. Even after accounting for these two facts, during discussions the reviewers considered the work to be incremental and a more thorough evaluation is needed to determine the benefits of algorithm. Specifically, please compare to important and relevant baselines (like AdamNC and Yogi), because sometimes it felt like baselines were picked and dropped randomly. The empirical improvement provided by Expectigrad compared to SOTA is not clear (both on synthetic problems from Reddi et al and real problems). Thus, unfortunately, I cannot recommend an acceptance of the paper in the current form. However, I would strongly encourage authors to resubmit after improving according to reviewer suggestions. 

Some other minor points that came up during discussion are: 
1. choice of hyperparameters was not clear to reviewers, e.g. different optimizer may behave very differently for same set of hyperparameters, so it would not be fair to compare them as is.
2. gradients would never be exactly zero in deep networks, so is current definition of $n_t$ good enough?
Decision: Reject