Stochastic Optimization with Non-stationary Noise: The Power of Moment Estimation
Authors: Jingzhao Zhang
Hongzhou Lin
Subhro Das
Suvrit Sra
Ali Jadbabaie
Venue:  (2021)
Keywords: Stochastic optimization

Abstract: We investigate stochastic optimization under weaker assumptions on the distribution of noise  than those used in usual analysis. Our assumptions are motivated by empirical observations in training neural networks. In particular, standard results on optimal convergence rates for stochastic optimization assume either there exists a uniform bound on the moments of the gradient noise, or that the noise decays as the algorithm progresses. These assumptions do not match the empirical behavior of optimization algorithms used in neural network training where the noise level in stochastic gradients could even increase with time. We address this nonstationary behavior of noise by analyzing convergence rates of stochastic gradient methods subject to changing second moment (or variance) of the stochastic oracle. When the noise variation is known, we show that it is always beneficial to adapt the step-size and exploit the noise variability. When the noise statistics are unknown, we obtain similar improvements by developing an online estimator of the noise level, thereby recovering close variants of RMSProp~\citep{tieleman2012lecture}. Consequently, our results reveal why adaptive step size methods can outperform SGD, while still enjoying theoretical guarantees.

Under review as a conference paper at ICLR 2021
STOCHASTIC OPTIMIZATION WITH NON-STATIONARY NOISE: THE POWER OF MOMENT ESTIMATION
Anonymous authors Paper under double-bling review
ABSTRACT
We investigate stochastic optimization under weaker assumptions on the distribu- tion of noise than those used in usual analysis. Our assumptions motivated by empirical observations in training neural networks. In particular, standard results on optimal convergence rates for stochastic optimization assume either there exists a uniform bound on the moments of the gradient noise, or that the noise decays as the algorithm progresses. These assumptions do not match the empirical behavior of optimization algorithms used in neural network training where the noise level in stochastic gradients could even increase with time. We address this nonstationary behavior of noise by analyzing convergence rates of stochastic gradient methods subject to changing second moment (or variance) the stochastic oracle. When the noise variation is known, show that it is always beneficial to adapt the step-size and exploit the noise variability. When the noise statistics are unknown, we obtain similar improvements by developing level, thereby recovering close variants of RMSProp (Tieleman and Hinton, 2012). Consequently, our results reveal why adaptive step size methods can outperform SGD, while still enjoying theoretical guarantees.
online estimator of the noise
INTRODUCTION
Stochastic gradient descent (SGD) one of the most popular optimization methods in machine learning because of its computational efficiency compared to traditional full gradient methods. Great progress has been made understanding the performance of SGD under different smoothness and convexity conditions (Agarwal et al., 2009; Arjevani et al., 2019; Drori and Shamir, 2019; Ghadimi and Lan, 2012: 2013; Nemirovsky and Yudin, 1983; Rakhlin et al., 2012). These results show that with fixed step size. SGD can achieve the minimax optimal convergence rate for both convex and nonconvex optimization problems, provided the gradient noise is uniformly bounded.
Yet, despite the theoretical minimax optimality of SGD, adaptive gradient methods (Duchi et al., 201 I; Kingma and Ba, 2014; Tieleman and Hinton, 2012) have become the methods of choice for training deep neural networks, and have received surge of attention recently (Agarwal al., 2018; Chen et al., 2019; Huang et al., 2019; Levy, 2017: Levy et al., 2018; Li and Orabona, 2019; Liu et al., 2019; 2020; Ma and Yarats, 2019; Staib al., 2019; Ward et al., 2019; Zhang al., 2019; 2020; Zhou et al., 2018; 2019; Zou and Shen, 2018; Zou et al., 2019). Instead of using fixed stepsizes, these methods construct their stepsizes adaptively using the current and past gradients. Despite advances in the literature on adaptivity, theoretical understanding of the benefits of adaptation is very limited.
We provide different perspective on understanding the benefits of adaptivity by considering context of non-stationary gradient noise, i.e.. the noise intensity varies with iterations. Surprisingly. this setting is rarely studied, even for SGD. To our knowledge, this paper is the first work formally study stochastic gradient methods in this varying noise scenario. Our main goal is to show that:
the
Adaptive step-sizes can guarantee faster rates than SGD when the noise is non-stationary We focus on this goal based on several empirical observations (Section 2), which lead us to model the noise of stochastic gradient oracles via the following iteration dependent quantities:
m E[]gg(=))
or ot B[ll((x)) v {zxx))]
(1)
where g(xx) is the stochastic gradient and (* the true gradient at iteration k. Notation (1) provides more fine-grained description of noise behavior than uniform bounds on the variance by

---

Under review as a conference paper at ICLR 2021
40
0.09
2.5E-7
0.075
2.0E-7
25
0.06
Second moment
1.5E-7
0.045
Varlance
1.0E-7
10
5
0.015
5.0E-6
0.0E-0
21
41
81
101
121
141
161
181
24
93
116
139
162
185
38
75
112
149
186
223
260
297
334
371
(a) ResNet18 on Cifar10
(b) AWD-LSTM on PTB
(c) Transformer on En-De translation
Figure I: We empirically evaluate the second moment (in blue) and variance (in orange) of stochastic gradients during the training of neural networks. We observe that the magnitude of these quantities changes significantly as iteration count increases, ranging from 10 times (ResNet) to 10 times (Transformer). This phenomenon motivates us to consider a setting with non-stationary noise.
permitting iteration dependent noise intensities. It is intuitive that one should prefer smaller stepsizes when the noise is large and vice versa. Thus, under non -ot-stationaritt, an ideal algorithm should adapt its stepsize according the parameters my ok, suggesting potential benefit of adaptive stepsizes.
Contributions. The primary contribution of our paper is to show that stochastic optimization method with adaptive stepsize can achieve faster rate of convergence (by factor that is polynomial- in-7) than fixed-step SGD. We first analyze an idealized setting where the noise intensities are known, using it to illustrate how to select noise dependent stepsizes that are provably more effective (Theorem 1). Next, we study the case with unknown noise, where we show under an appropriate smoothness assumption the noise variation that variant of RMSProp (Tieleman and Hinton, 2012) can achieve the idcalized convergence rate (Theorem 3). Remarkably, this variant does not require the noise levels. Finally, generalize results nonconvex settings (Theorems 12 and 14).
MOTIVATING OBSERVATION: NONSTATIONARY NOISE IN DEEP LEARNING
Neural network training involves optimizing an empirical risk minimization problem of the form min, f(x) : Σi= fxx),, where each fi represents the loss function with respect to the i-th data or minibatch. Stochastic methods optimize this objective randomly sampling an incremental gradient ff each iteration and using it as an unbiased estimate of the full gradient. The noise intensity of this stochastic gradient is measured by its second moments or variances, defined as,
1. Second moment: m²
Em= V (x)))
2. Variance: (² Σm V (z) - vf(=)] where V fxx) is the full gradient,
To illustrate how these quantities evolve over iterations, empirically evaluate them three popular tasks neural network training: ResNet18 training on Cifar10 dataset for image classification! LSTM training on PTB dataset for language modelling?; transformer training WMT16 en-de for language translation The results are shown in Figure 1, where both the second moments and variances evaluated using the default training procedure of the original code.
On one hand, the variation of the second moment/variance has a very different shape in each of the considered tasks. the CIFAR experiment, the noise intensity is quite steady after the first iteration, indicating a fast convergence of the training model. In LSTM training, the noise level increases and converges threshold. While, in training Transformers, the noise level increases very fast the early epochs, then reaches a maximum, and turns down gradually.
On the other hand, the preferred optimization algorithms in these tasks are also different. For CIFAR10, SGD with momentum is the most popular choice. While for language models, adaptive methods such as Adam or RMSProp are the rule of thumb. This discrepancy is usually taken as granted, based on empirical validation; and little theoretical understanding of it exists in the literature.
"Code source for CIFARIO http://gghhbb.oomuuuuggiuutttttt
"Code source for L.TM https:/giiiih..ommmaaccccc//cddd
Code source for Transformer http://gihhub.com/jddre00011
2

---

Under review as a conference paper at ICLR 2021
Based the observations made in Figure 1, a natural candidate emerges to explain this discrepancy in the choice of algorithms: the performance of stochastic algorithms varies according the characteristics of gradient noise encountered during training. Despite this behavior, noise level modeling has drawn surprisingly limited attention in prior art. Reference (Moulines and Bach, 201 studies convergence of SGD assuming each component function is convex and smooth; extensions to the variation of the full covariance matrix are in (Gadat and Panloup, 2017). A more fine-grained stochastic oracle assumes that the variances grow with the gradient norm as o² cll fx))l or grow with the suboptimality + - ae" 1|2 (Bottou et al., 2018; Jofré and Thompson, 2019; Rosasco et al., 2019).
Unfortunately, these existing oracles fail to express the variation of noise observed in Figure Indeed, the norm of the full gradient. represented as the difference between the orange and the blue line, is significantly smaller compared to the noise level. This suggests that noise variation is not due to the gradient norm, but due to some implicit properties of the objective function. This observation motivates us introduce the following non-stationary noise oracle:
Definition 1 (non-stationary noise oracle). The stochasticity of the problem is governed by sequence of second moments {mx KEN or variances {or KEN, such that, at the ken iteration, the gradient oracle returns unbiased gradient g(xx)) such that [[g(xx)] (.r(), and either
(a) with second moment [[([g((x))])) = m or (b) with variance [[llg(=))- - f (zx) o.
The non-stationary noise oracle is a relaxation the standard uniform noise oracle in which case m& or d% constant. By introducing the time dependency, we aim understand how the variation of noise influences the convergence rate of optimization algorithms. An example that falls into this category is when the noise is additive the gradient, namely g(xx)) ff(()) +N of).
We emphasize that our goal is to demystify the correlation between the noise intensity and the performance of optimization algorithm, instead of explaining why certain shape of noise occurs. In general, the variation in noise is a consequence of the combination on data distribution, training model and optimization method, which complex and highly non trivial. We simplify it by assuming that the noise intensity is decoupled from its location, meaning that, the parameters my σ only depend on the iteration number but do not depend on the specific location where the gradient is evaluated. This is empirically justified as the pattern of the noise is mostly determined by the task instead of the optimization algorithms, see Appendix A. The simplification helps to focus on the shape of noise, taking first step towards the goal: characterize the convergence rate of adaptive algorithms under non-stationary noise.
3 THE BENEFIT OF ADAPTIVITY UNDER NONSTATIONARY NOISE
In this section, we investigate the influence of nonstationary noise in an idealized setting where the noise parameters mg are known. For brevity, will first focus on the convex setting and present our results based on the second moment parameters my. We defer the discussion on nonconvex problems and variants on variance parameters de to Section 5. One reason that we prioritize the second moment than the variance is to draw a connection with the well-known adaptive method RMSProp (Tieleman and Hinton, 2012) and Adam (Kingma and Ba, 2014). One common feature shared by both algorithms is that they scale the step sizes inversely to an exponential moving average of estimated second moments. Below, we start from the idealized case assuming the second moments are known and show why inverse scaling could speed up convergence.
Let be convex and differentiable. We consider the problem min, f(x), where the gradient given by the nonstationary noise oracle defined in Definition I. We assume that the optimum is attained at x² and we denote f the minimum of the objective. We are interested in studying the convergence rate of stochastic algorithm with update rule
Tk+1 = F2 - 7)g(xx)
where are stepsizes that are oblivious of the iterates { JkeN. Theorem 1. Under the second moment oracle given in Definition I (a), the weighted average Fy (E m k== 1k) obtained by the update rule (2) satisfies the suboptimality bound
B[S(TT) 5 | - x² 112 +
k== m
(3)
Σ 1= 17
3

---

Under review as a conference paper at ICLR 2021
Although the theorem follows from standard analysis, it leads to valuable results explained below.
Corollary 2. Denote M max my and R ||:1 x²Il.
We have the following convergence rate:
1. SGD with constant stepsize: mı 17
I then
V 2= mi
([f(TT) - 5 28 Ei m
2RM vT
Ei mi M2
(constant baseline)
2. SGD with idealized stepsize: if Tj
then
VTmms
B[f(TT) - f 28
2RM VT
M
(idealized baseline)
T
To facilitate comparison, we have normalized the convergence rates with respect to the conventional rate 2RM/ /T (Nemirovski et al., 2009). In the standard setting, the values of m. are unavailable, but the uniform bound M is known, in such case taking m, M recovers the standard result.
When the values of my are given, both constant baseline and idealized baseline benefits from it, improving upon the conventional rate SRM/VI The improvement factor in constant baseline has depends on the average of the second moments vΣ m while as the improvement factor in idealized baseline depends on the average of the harmonic sum т 1/mms In particular, from Jensen's ' inequality [[ < X| 2]. we have
implying that the idealized baseline is always better than the constant baseline. This result is rather expected, as the stepsizes are adapted to the noise intensity.
As consequence, the accumulations of the parameters my in different forms governed the conver- gence rate. To further illustrate such difference, we consider an illustrative synthetic noise model, mimicking the shape of noise we observed in the training of Transformer (see Figure I(c)).
Example 1. Consider the following piece-wise linear noise model with 7 = 5(1 - T T
1.0
if E [1, T
7
7k
2T
+1
if E
T 27
1 3T
if
5: 5
2T 31
0.6
7(
+1
if
if E
(15 .].
0.2
Ta
0.0
0.2
0.4
0.6
0.8
1.0
Iteration #
1e6
In this example, the maximum noise intensity M is 1, and the minimum intensity 1/Ta, inducing a large ratio of order T Following the bounds developed in Corollary 2, the performance of the constant buseline maintains the standard 0(1/VT convergence rate, while as the idealized baseline converges / Hence nontrivial acceleration of order T is obtained by using the idealized stepsize, and this acceleration can be arbitrarily large as a increases.
This example is encouraging, showing that the speedup due to adaptive stepsizes can be polynomial in the number of iterations, especially when the ratio between the maximum and the minimum noise intensity is large. However, explicit knowledge on ma is required to implement these idealized stepsizes, which is unrealistic. The next sections of the paper demonstrates that estimating the moment bound an online fashion can achieve a convergence rate comparable to the idcalized setting.
ADAPTIVE METHODS: ONLINE ESTIMATION OF MOMENTS
From now on, we assume that the moment bounds my are not given. To address the non non-staiionarity we estimate the noise intensity based on an exponential moving average, technique commonly used adaptive methods. More precisely, the moment estimator my is constructed recursively as
m
Bm
B)1l
(ExpMvAvg)
4

---

Under review as a conference paper at ICLR 2021
Algorithm I Adaptive SGD (211 T, f,
Initialize r [1
2: for k = 1, 2...... ... ' do
3: Evaluate stochastic gradient Ot at rk-
4: #k++1 =
") with 1)s tm 3)
5: r = $
6: end for
7: return 2T ( / /E %b).
where ge is the k-th stochastic gradient and 3 the decay paramter. Then we choose the stepsizes inversely proportional to mig+1, leading to Algorithm 1.
Algorithm could be viewed as a "norm" version of RMSProp (Tieleman and Hinton, 2012): the exponential moving average is performed coordinate-wise wise in RMSProp, whereas we use the full norm of 9k to update the moment estimator 7 Such simplification via a full norm variant has also been analyzed in the uniformly bounded noise setting (Levy, 2017; Levy et al., 2018; Li and Orabona, 2019; Ward et al., 2019)-wa leave investigation of the more advanced coordinate-wise version as topic of future research.
Another important component of the stepsize is the correction constant m, the term appearing in the denominator. This constant provides a safety threshold when thg underestimates my, which com- monly used in the practical implementation of adaptive methods, and even beyond, in reinforcement learning as so-called exploration bonus (Azar al., 2017; Jin al., 201 8a; Strehl and Littman, 2008).
To show the convergence of the algorithm, we need to impose a regularity assumption on the sequence of noise intensities. Otherwise, previous estimate may not provide any information of the next one.
Assumption 1. We assume that an upper bound M my is given, i.e. max; m& S M such that
(a) The fourth moment of gı bounded by M namely, [[[[]g 112 m S M Vk.
(b) The total variation on my is bounded, namely Σか m - - m S D2 with D2 ((M²).
The bounded fourth moment ensures concentration of || 11 which necessary guarantee the quality of the online estimator. In particular, this assumption is satisfied when ||gs follows my sub-Gaussian distribution. Though stronger than bounded variance, this assumption does not lead to better convergence rates for SGD, as many existing results (including lower bounds) require sub-Gaussian or bounded noise, see Agarwal et al. (2009); Ghadimi and Lan (2013).
The bounded total variation assumption should be viewed as regularity condition the sequence of noise. is motivated and common in the dynamic online learning literature (Besbes et al., 2014; Jadbabaie et al., 2015; Mokhtari et al., 2016). A key aspect of it is to avoid infinite oscillation, such as the pathological setting where 722k = 1 and m2x+1 = M, which case the total variation scales with the number of iterations T. The specific constant in D S depends the shape of the noise. When mı is increasing in the first half and decreasing in the second half, as in the Transformer experiments and Example 1, the total variation is bounded by D < 2M2, More generally, if the noise can be decomposed into K piece-wise monotone fragments, then the bound D < KM² holds.
With the above assumptions, we are now ready to present our convergence result.
Theorem 3. Under Assumptions 1, with probability least 1/2, the iterates generated by Algoritlum I using parameters 3 27 3 m 4vD22 M In(T) R
satisfy
VT
((TT) - 2RM
ma+m
Remark 4. Our result directly implies 1 - high probability style convergence rate, by restarting (108(1/8) times. An additional log(1/5) dependency will be introduced the complexity, as in standard high probability results Fang et al. (2018); Jin et al. (2018b); Nemirovski et al. (2009).
The key to prove the theorem is to effectively bound the estimation error Im m2 relying on concentration, and bounded variation in Assumption 1. In particular, the choice of the decay
5

---

Under review as a conference paper at ICLR 2021
Constant
Adaptive
Idealized
T
142
a
a
T
T
11
O
T
1420
Table 1: Comparison of the convergence rate under the noise example 1.
parameter is critical, determining how fast the contribution of past gradients decays. Because of the non-stationarity in noise, the online estimator ri is biased. The proposed choice of (3 carefully balances the bias error and the variance error, leading to sublinear regret, see Appendix C.
Due to the correction constant m, the obtained convergence rate inversely depends on Ex=1 mm+m" 1. This additional term makes the comparison less straightforward and now discuss different scenarios for obtaining better understanding.
instead of the idealized dependency Σk=1 m.
4.1 DISCUSSION OF THE CONVERGENCE RATE
To illustrate the difference between convergence rates, we first consider the synthetic noise model introduced in Example I. The detailed comparison is presented in Table 1, where we observe two regimes regarding the exponent a::
When S J, the rate of the adaptive algorithm matches (idealized baseline) up to logarith- mic dependency, and is 7 better than the (constant baseline).
When 3 I the adaptive convergence rate no longer matches the (idealized baseline). Never- theless, is always T faster than the (constant baseline).
In both cases, the adaptive method achieves non-trivial improvement, polynomial in T, compared the (constant baseline). Even though the improvement T might seem in-significant, it is the first result showing plausible non-trivial advantage of adaptive methods over SGD under nonstationary- noise. Further, note that the adaptive convergence rate does not always match the (idealized baseline) when is large. Such discrepancy comes from the correction term m, which makes the stepsize more conservative than it should be, especially when my is small.
The above comparison relies the specific choice on the noise model given in Example 1. Now we formalize some simple conditions allowing comparison in more general settings.
Corollary 5. If the ratio M/(ming, m&) < Th, then udaptive method converges in the same order as the (idealized baseline), up to logarithmic dependency.
This result is remarkable since the adaptive method does not require any knowledge of m, values, and yet it achieves the idealized rate. In other words, the exponential moving average estimator successfully adapts to the variation in noise, allowing faster convergence than constant stepsizes.
Corollary 6. Let mavg = m? T be the average second moment. If M/ S Tb, then adaptive method is no slower than the (constant baseline), up to logarithmic dependency.
The condition in Corollary is strictly weaker than the condition in Corollary 5, which means even though an adaptive method may not match the idealized baseline, it could still be non non-trivially better than the constant baseline. This case happens e.g., when a > g in Table 1, where the adaptive method is OTT)) faster than the constant baseline. Indeed, ( is the maximum improvement one can expect according to our current analysis.
Corollary 7. Recall that M is an upper bound on mj, i.e., max my S M. Therefore
1. The convergence rate of the constant baseline is no slower than ((2RM/TT)
2. The convergence rate of the adaptive method is no faster than O(2RM/T4+3)
The order of maximum improvement (T is determined by the specific choice of m in Theorem which is chosen to be (MMT-5 $). Indeed, the correction term is helpful when the estimator mn underestimates the true value m4, avoiding the singularity at zero. Hence, the choice of is related

---

Under review as a conference paper at ICLR 2021
to the average deviation between my and my- Under stronger concentration assumption, can strengthen the maximum improvement ( as shown in Appendix E.
The noise model in Example provides a favorable scenario where the maximum improvement is attained. However, in some scenarios, the convergence rate of an adaptive method can be slower than the constant baseline.
Adversarial scenario. If m, 1/T" for all i [1,7] except at T/2 it takes the value mT/22 = with > 1/9, then the convergence rate of both constant and idealized baselines are O(T +), while the adaptive method only converges in O(T-'=a ). The subtle change iteration T/2 amplifies the exponential moving average estimator and requires a non-negligible period to get back to the constant level. It is clear that the estimator becomes less meaningful under such a subtle change.
Overall, it is hard to provide a complete characterization of the variation in noise. In Corollary 5 and 6, we show that when the ratio between the maximum and the minimum/average second moment not growing too fast, adaptive methods do improve upon SGD.
5 EXTENSIONS OF THM 3
In this section, we discuss several extensions to Thm 3. The results are nontrivial but the analysis is almost the same. Hence we defer the exact statements and proof's appendices.
Addressing the variance oracle. So far, we have focused on the noise oracle based on the second moment my and made the connection with existing adaptive methods. However, there is some unnaturalness underlying the non-stationary oracle mg. Indeed, it is hard to argue that my is iterate independent since m. = oi [[V](=*)]] Even though the influence of (xx))]l might be minor when the variance of is high (e.g. in Figure 1). is still changing my- In contrast, the variance 0% is an intrinsic quantity coming from the noise model, which could be iterate independent. Hence the variance oracle is theoretically more sound. We now present the necessary modifications in order to adapt to the variance oracle.
First, in order estimate the variance, we need to query two stochastic gradients Is and g the same iterate, then we construct the estimator following the recursion
0b+1 3ož (1 3) 1e1l
Second, the smoothness condition on f is required, i..., L-Lipschitzness on the gradient of f. In this case, it is necessary to ensure that the step-size being not larger than 1/2L. This translates an additional constraint on the correcting constant m. More precisely, the stepsize is given by 2cL.
πH dutm with
Note that the L-smoothness condition is not required in the second moment oracle. This is why the second moment oracle is more suitable to nonsmooth setting (see Section 6. of Bubeck (2014)). A complete algorithm for the variance oracle is provided in Algorithm 2. The convergence results essentially the same by replacing my with dg. see Appendix H.
Extension nonconvex setting. We also provide an extension of our analysis to non-convex smooth setting. In which case, we characterize the convergence with respect to the gradient norm [[vf(*))] i.e., convergence a stationary point. The conclusions are very similar the one the convex setting and the results (Theorems 12 and 14) are deferred to Appendix F.
Variants on stepsizes. To go beyond the second moment of noise, one could apply an estimator of the form + Bm + (1 9)]|g>||" when the p-th moment of the gradient is bounded. This
allows stepsize of the shape 7 1/ + m²) as in ADAM, Adamax Kingma and Ba (2014).
6 EXPERIMENTS
In this section, we describe two sets of experiments that verify the faster convergence of Algorithm 1 against vanilla SGD. The first experiment is on linear regression with synthetic noise described in Example and the second set of experiments is on neural network training.
6.1 SYNTHETIC EXPERIMENTS
In the synthetic experiment, generate random linear regression dataset using the sklearn' library. We design the stochastic oracle as full gradient with injected Gaussian noise, whose coordinate-wist
scikktt hoaailllmmmnnoyyalmmmeeeeeeeeeee http://mmnnneeeaaaamaaatttttteae reanukeeegrrssinnhttm

---

Under review as a conference paper at ICLR 2021
1.0
bsseline idua bascline
125-
Sabeptinalty
Subestmakk
10-1.
0.75
0.6
10:22 1.
2500 5000 Iteration #
7500
10000
10
2000
4000
6000 8000
10000
Zanderd peeetre
Aggnncee
Agonbm
lieration
The injected noise intensity over iterations. Middle: loss trajectory over 10 runs for four different algorithms: standard baseline, idealized baseline, Alg and Alg 2. The curve (idealized vs standard) confirms that adopting step sizes inverse to the noise level lead faster convergence and less variations. Right: Average and standard deviation of function suboptimality. The values are normalized by the average MSE of the standard baseline.
Figure 2: Left:
5.5
Agarthm
Algor 1
-Bodliiee
Rasebie
13
355
Figure 3: The left two plots show the accuracy of training ResNet18 on Cifarl0 dataset. The right two plots present the negative log-likelihood loss for LSTM Language modelling from Merity et al. (2018). The baselines are provided by the repos cited on page 2. Algorithm 1 is described in Alg 1.
standard deviation a is shown in the left figure of Fig 2. We then run the four algorithms discussed in this work: standard baseline, idealized baseline, Alg and Alg 2. We finetune the step sizes for each algorithm by frid-searching among 10a, where ls is an integer. We repeat the experiment for 10 runs and show the average training trajectory well the function suboptimality in Fig 2. We observe that the performance is ranked as follows: idealized baseline, Alg 2, Alg and standard baseline.
6.2 NEURAL NETWORK TRAINING
We demonstrate how the proposed algorithm performs in real-world neural network training. We first tested our algorithm on Cifar10 classification task. We then implement our algorithm into the AWD-LSTM codebase described in Merity et al. (2018). We see from Figure 3 that our proposed algorithm can achieve slightly better performance than baselines. Despite our main contribution being providing theoretical analysis for the fast convergence of adaptive methods with moment estimation, these results show that our analysis can also lead to efficient and practical algorithm design.
Besides convergence, we also measured noise level during neural network training with different optimizers and found that the noise pattern is mostly determined by the learning task instead of by the optimization algorithm. Details can be found in Appendix A.
7 CONCLUSIONS
This paper discusses convergence rates of stochastic gradient methods in empirically motivated setting where the noise level is changing over iterations. We show that under mild assumptions, one can achieve faster convergence than the fixed step SGD by a factor that is polynomial in number of iterations, by applying online noise estimation and using adaptive step sizes. Our analysis, therefore provides one explanation for the recent success of adaptive methods in neural network training.
There is much more to be done along the line of non-stationary stochastic optimization. Under our current analysis, there is a gap between the adaptive method and the idealized method when the noise variation is large (see second row in Table 1). A natural question to ask is whether one could reduce this gap, or alternatively, is there any threshold preventing the adaptive method from getting arbitrarily close to the idealized bascline? Moreover, could one attain further acceleration by combining momentum or coordinate-wise update techniques? Answering these questions would provide more insight and lead to better understanding of widely used adaptive methods.
Perhaps a more fundamental question is regarding the iterate dependency: the setting where the moments my or the variance d are functions of the current update T'k, not just of the iteration index k. Significant effort needs to be spent to address this additional correlation under appropriate regularity conditions. We believe our work lays the foundation to address this challenging research problem.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
A. Agarwal, M. J. Wainwright, P. L. Bartlett, and P. K. Ravikumar, Ctormatioonthhoreee lower bounds on the oracle complexity of convex optimization. In Proceedings of Advances Neural Information Processing Systems (NIPS), 2009.
N. Agarwal, B. Bullins, X. Chen, E. Hazan, K. Singh, C. Zhang, and Y. Zhang. The case for full-matrix adaptive regularization. arXiv preprint arXiv:/806.0294 2018.
Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint 1rXiv:1912.02366 2019.
M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conferences on Machine Learning (ICML), 2017.
O. Besbes, Y. Gur, and A. Zeevi. Stochastic multi-armed--aa bandit problem with non-stationary rewards. In Advances in neural information processing systems, pages 199-207, 2014.
L. Bottou, F. Curtis, and Nocedal. Optimization methods for large-scale machine learning. Siam Review, (0(2):223-311 ,01,,1111111111 2018.
S. Bubeck. Convex optimization: Algorithms and complexity. arXiv preprint arXiv: 1405.499994998 2014.
X. Chen, S. Liu, Sun, and Hong. non-convex optimization. In International Conference on Learning Representations (ICLR), 2019.
On the convergence of class ADAM-type algorithms for
Y. Drori and O. Shamir. The complexity of finding stationary points with stochastic gradient descent. arXiv preprint arXiv:1910.01845. 2019.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120ul):2121-2153) 2011.
C. Fang. J. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator. In Proceedings of Advances Neural Information Processing Systems (NIPS), 2018
S. Gadat and F. Panloup. Optimal non-asymptotic bound of the Ruppert-Polyy Polyykk averaging without strong convexity. arXiv preprint arXiv: 2017.
S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22 14922, 2012.
S. Ghadimi and Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341-23) -23688, 2013.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
H. Huang, C. Wang, and B. Dong. Nostalgic Adam: weighting more of the past gradients when designing the adaptive learning rate. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, 2019.
A. Jadbabaie, A. Rakhlin, Shahrampour, and K. Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398-406, 2015.
C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is q-learning provably efficient? In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2018a.
C. Jin, P. Netrapalli, and M. I. Jordan. Accelerated gradient descent escapes saddle points faster than gradient descent. In Conference On Learning Theory, pages 1042-1085, 8b.
A. Jofré and Thompson. On variance reduction for stochastic smooth convex optimization with multiplicative noise. Mathematical Programming, 174(1-2):233-222. 2019.

---

Under review as a conference paper at ICLR 2021
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXivv 2014.
K. Levy. Online to offline conversions, universality and adaptive minibatch sizes. In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2017.
K. Y. Levy, A. Yurtsever, and V. Cevher. Online adaptive methods, universality and acceleration. In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2018.
X. Li and F. Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes, In The 22nd International Conference on Artificial Intelligence and Statisties, 2019.
L. Liu, H. Jiang, P. He, W. Chen, X. Liu, Gao, and Han. On the variance of the adaptive learning rate and beyond, arXiv preprint 1908.v::000.33000
2019.
M. Liu, Y. Mrouch, J. Ross, W. Zhang, X. Cui, P. Das, and T. Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. International Conference on Learning Representations (ICLR), 2020.
J. Ma and D. Yarats. On the adequacy of untuned warmup for adaptive optimization. arXiv preprint arXiv: 1910,044994 2019.
S. Merity, N. S. Keskar, and R. Socher. Regularizing and optimizing LSTM language models. In International Conference on Learning Representations (ICLR), 2018.
A. Mokhtari, S. Shahrampour, A. Jadbabaie, and Ribeiro. Online optimization in dynamic environments: Improved regret rates for strongly convex problems. In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 7195-7201. IEEE, 2016.
E. Moulines and F. R. Bach. Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2011.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-160), 2009.
A. S. Nemirovsky and D. B. Yudin. Problem complexity and method efficiency in optimization. Wiley, 1983.
A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In International Conferences on Machine Learning (ICMI.), 2012.
L. Rosasco, Villa, and B. C. Vū. Convergence of stochastic proximal gradient algorithm. Applied Mathematics & Optimization, pages 1-27, 2019.
M. Staib, S. J. Reddi, S. Kale, S. Kumar, and S. Sra. Escaping saddle points with adaptive gradient methods. In International Conferences on Machine Learning (ICML), 2019.
A. L.. Strehl and M. L.. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8): 130911313333 2008
T. Tieleman and G. 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.
R. Ward, X. Wu, and L. Bottou. Adagrad stepsizes: Sharp convergence over nonconvex landscapes. In International Conferences on Machine Learning (ICML), 2019.
Zhang, S. Karimireddy, Veit, S. Kim, S. Reddi, Kumar, and S. Sra. Why adam beats sgd 2019.
for attention models. arXiv preprint
J. Zhang, T. He. S. Sra, and A. Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020.
D. Zhou, Y. Tang, Z. Yang, Y. Cao, and Q Gu. On the convergence adaptive gradient methods for nonconvex optimization. arXiv preprint a 006.05 2018
10

---

Under review as a conference paper at ICLR 2021
Z. Zhou, Q. Zhang, G. Lu, H. Wang, W. Zhang, and Y. Yu. Adashift: Decorrelation and convergence of adaptive learning rate methods. In International Conference on Learning Representations (ICLR), 2019.
Zou and L. Shen. On the convergence of weighted adagrad with momentum for training deep neural networks. arXiv preprint arXiv: 03408, 2018.
F. Zou, L. Shen, Z. Jie, W. Zhang, and W. Liu. A sufficient condition for convergences of adam and mmsprop. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 11 11127-11133 135, 2019.

---

Under review as a conference paper at ICLR 2021
40
0.16
0.14
30
0.12
Second moment
0.08
Second moment
Variance
0.04
VVaiiance
86
103
120
137
154
177
188
21
41
61
12
141
161
181
(a) 8 trained with Adam on Cifar10
(b) AWD-LSTM trained with Adam on PTB
Figure 4: We retrain the models with Adam optimizer and evaluate the second moment (in blue) and variance (in orange) of stochastic gradients for the Cifar10 experiments and PTB experiments Figure 1.
A ADDITIONAL EXPERIMENT DETAILS AND RESULTS
In this section, we provide more details on our experiment setup. The code for reproducing noise estimation and neural network training on AWS-LSTM model is uploaded the supplementary. The code for Cifar10 classification can be uploaded upon request.
A.1 DETAILS ON PTB TRAINING
Our implementation is based on the author's github repository 5, The original codebase trains the network using clipped gradient descent followed by average SGD (ASGD) algorithm to prevent overfitting. As generalization eтror is beyond our discussion, we focus on the first phase (which takes about 200 epochs) by removing the ASGD training part. Aside of the number of epochs, all other parameters are the same as the default training procedure. For our algorithm, we update the clipping value to be 0.25, and set the hyperparameters of Algorithm 1 Ue 5. = 0.95, 0.01.
A.2 DETAILS ON CIFAR10 TRAINING
Our implementation is based on pytorch implementation the original ResNet paper(He et al., 2016). We train the ResNet18 model on Cifar10 dataset for 200 epochs. The baseline uses SGD with learning rate initialized as 0.1. The learning rate is decayed by 10 at epochs 100, 150. We eventually achieves approximately 95% validation accuracy. For our algorithm, we set T) 3 = 0.99, m = 0.01 and use the same learning rate schedule as the baseline.
A.3 NOISE BEHAVIOR FOR DIFFERENT ALGORRITHMS
In this subsection, we include one interesting observation on the noise pattern of neural network training. From Figure 1, we see that the noise pattern looks very different for different task. One may naturally wonder whether the difference results from the particular training task or from the optimization algorithms. Noticing that each of these three tasks are trained with a different algorithm (Cifar10 with momentum SGD; PTB with clipped SGD; En-De translation with ADAM), we retrained the Cifar10 task and the PTB language modelling with Adam. and rerun the En-De translation experiment with momentum SGD. We found that the En-De translation task diverges when trained with SGD when learning rate is 0.001. Hence we only report the results from the other two experiments in Figure 4.
From Figure 4, these experiments suggest that the noise pattern is mostly determined by the learning task instead of by the optimization algorithms.
that the pattern looks very similar to the original plots in Figure 1. Hence
*Code source for LSTM https///ghht..ommaaasssn////ssss 'Code source for CIFARIO https//ggthaccookuuuungi/nnnnnhh
12

---

Under review as a conference paper at ICLR 2021
B PROOF OF THEOREM
Proof. The iterate suboptimality have the following relationship:
|| x² 2| = I 7/99k z=11 11 = |1 - x x²1 - 277 (9k: 24 - x²) + 1
Rearrange and take expectation with respect to Ih we have
(mxx)( - 1*) - ( f==x),
x²)
2 =² - Bllare
x² x12 + n/
Sum over and take expectation we get
T
T
E
[*'] S |,| x=1 1 +
1 m
2
==1
k=1
Then from convexity, we have
B[f(TT) 5 11 12 k= mm
Σl=
1
where Iт = -Ei= nat mt). Corollary 2 follows from specifying the particular choices of the stepsizes.
C KEY LEMMA
Lemma 8. Under Assumptions 1, taking 3 = 1 2/33,//3,, the total estimation error of the mi based on (ExpMvAvg) bounded by:
T
E
m
< 2 + 22 (/
Proof. On high level, we decouple the error in a bias term and a variance term. We use the total variation assumption to bound the bias term, and use the exponential moving average reduce variance. Then we pick /3 to balance the two terms.
From triangle inequality, we have
T
T
T
Σ E [ mill
S
I
E
Emilll
m
m
(4)
Variance
Bias
We first bound the bias term. By definition mik we have
E[m
m
[m + (1 - 3)m - m
(E 1 m +mm m2k)
Hence by recursion.
E Emmil
m = gk
[E(m²] - mf - 2 - m²) + ... + (m - m
=0
Therefore, the bias term could be bounded by
T
T k-1
E m
m
x
8k-1-1 mm m
k=
1=1
T-1
T-1-k
Σ Bd
m
m
1=0
T-1
1
mg
2
-
m
k=1
D2
(From Assumption (1))
1 1-3
13

---

Under review as a conference paper at ICLR 2021
The first inequality follows by traingle inequality. The third inequality the geometric over B. To bound the variance term, we remark that
2 A = (1 3) (1- + (1 3)39 (1 -333 23 +3h
Hence from independence the gradients, we have
[ [m S
Var[mng]
Varl (1 -3)9 Var( - 3)599 +... Var((1 -)3k-227 Varl3k-1
(1- +11++110 -1- 3) + +... +1 (1)--)333( + 12(k-1)
where 2 is an upperbound on the variance. The first inequality follows by Jensen's inequality. The second equality uses independence of 9s given 0i-1- The last inequality follows by assumption 1.
We distinguish two cases, when & is small, we simply bound the coefficient by 1, i.e.
(1 B1- -1-
+ (1 - (2 + -2(k-1) < 1
When large such that 1: 2 1 + y, with 7 2(1-8) In( 1 we have B2(k-11 1) S 1 - B, thus
(1 - 3)2+ + (1- ... + (1 - 3)2 32( + 32(k-1)
-332
1 32 + 11
(1 -)2
+ (1 - 3)
1 g2
5 / 3)
The second inequality follows by h: 2 1 + 7, with -[11 In( (n(1-)). Therefore, when k 2 4
E [ B[nnū]] < 2
Therefore, substitute in the above equation into the
E [ [[
E - +
Σ E [ [
1=1
1=1
k=
< ( + -T- 2211
Summing up the variance term and the bias term yields,
D2
[ - -mīl S 1- B
+ + + (T (T-))) ~B))
(5)
k=0
= Taking 3= 1- T 2/3
2/3 / yields.
T
E [ mill s 2(D2 + M22T2/3 (T(2/3))
(6)
14

---

Under review as a conference paper at ICLR 2021
D PROOF OF THEOREM 3
On a high level, the difference between the adaptive stepsize and the idealized stepsize mainly depends on the estimation error |nn m which has sublinear regret according Lemma C. Then we carefully integrate this regret bound to control the derivation from the idealized algorithm, reaching the conclusion.
Proof. By the update rule of IK+1, we have,
| - x²1 I 7a9h x²12 = || - x²112 1|2 277 (gte: - x²) 1ell9=1??
Noting that the stepsize 77 is independent of gk. taking expectation with respect to gk conditional on the past iterates lead to
27x(f(xN) - f*) s 27 (V fxxx), 24 - x²)
[2 (gk: Ft x²" lak: ... ,21]
-B[||+++1 x" ||/| 1. , mi + || - x²1 + n.
Recall that || x²) I1, taking expectation and sum over iterations k, we get
ERE nh) f*) R + m.
Hence by Markov's inequality, with probability at least 3/4,
2 (f)TT) f*) - 4 1 m)) ft) s 4 + (7)
Now we can upper bound the right hand side, indeed
m
(mg m)
1=
m mm
m
S 2
E
(FiRk + mm
(mi + m2
T
1
2
mx + +T m
m
k=1
(M* 22 In (T2/33)
<
+ T
< 3T
(8)
2
The last inequality follows by the choice m. Hence, from Eq. (7), we have with probability at least 3/4,
2 2 (() f*) 4(12 + 3c?
(9)
Next, by denoting (z)+ = max(x 0), we lower bound the left hand side,
1 7k
Σ
mi +
mi +
mi m
mh
(fig mx)+
2 Σ ma +
(m+ + m))(mn + m)
(mi - mx)+
2 my + m
VmL- + m m/3/2
(mi - -m+)²
Σ
+
my +
m
m& m
Σ
2m1 Σ
(mg mz
(10)
mh + m
15

---

Under review as a conference paper at ICLR 2021
Finally, by Markov's inequality, with probability 3/4
Σ (mn - fin) < 4EJ Σ (mi -ma)+] I 4E Σ (mi - M2)77233 In(2213)
Following the choice of m = 4VD2 + M In (T) $, we have
1
T
1 my
(m
10)e-m)32 mz)4
2m
4(M m)
+
k=1
k=
Consequently, together with (9) and (10), we know that with probability at least
1122,
7
4(R² + 3c
2R
32T
f(īr)
f f
(11)
Σn +m)
VT
k (m)+mm
where the last inequality follows by setting
R /T
Remark 9. For more general choices of stepsize Th [m 4mp3a7p. the upper bound in (q. holds exactly as in the above proof, and the lower bound in Eq. (10) follows from
Σ Th Σ (mg + mpyup
Σ (mL m2)1/o
1
1
(mh + mP)l/p (mL + mP)
(mh + mm)) (mp + mp)
Σ (mb + m0)1/p
(mig + mP) (np)//p(m² + mP)
(mh mx)+
2 Σ (mg + mp)1/p
(Minkowski inequality)
(mg + m 1/P + mp) (mi - mx) )
2 Σ (ml + mpy1/D
Σ
m mm/2mmm + mp)
2 Σ (mh + +PP)2/0
2m3 Σ
(me m
E PROOF WITH CONCENTRATE NOISE
In this section, we add additional constraints on noise concentrations. Assumption 2. The expected absolute value is not very different from the square root of the second moment, i.e.
(B[]gg(>|II
/[[lg(())|13)
The constant "2" in the assumption above is arbitrary and can increased to any fixed constant. The above assumption is satisfied if g(x) follows Gaussian distribution. It is also satisfied if for some fixed constant 7, ((()(()) 2 r) S (B[]] for all 2 >B[[][<)]]]]
We assume that the total variation on the first moment is bounded.
Assumption 3. We denote A = E[[lgl]], and assume that upper bound M such that
(a) The second moment of 9u is bounded by M2, namely, E[llgu| M Vk.
(b) The total variation on the first moment Ag is bounded by
Σg |e A 5 D
(12)
16

---

Under review as a conference paper at ICLR 2021
Constant
Adaptive
Idealized
a
S 6
T
T 122
1420
a
T
T
O
T
1420
Table 2: Comparison of the convergence rate under the noise example 1.
Under this stronger assumption, we can perform our online estimator on the first moment E( instead of the second moment, replacing line 6 of Algorithm by
fu++ 3m + (1 3)1ls>
(13)
The theorem below shows the convergence rate of the new algorithm.
Theorem 10. Under assumptions 2, 3,whth 16( D + M)7 c
R /T
Algorithm I
with update rule (13) achieves convergence rate
2R
12T
((TT)
(14)
VT
Σ (ma+mm)
With better concentration of the online estimator, could allow less conservative correction constant m, in the order of MT- é. It is this parameter that controls the maximum attainable improvement compared to the constant baseline. Indeed, we again consider the noise example
given in Table In this case, the adaptive method can obtain an improvement of order T compared to the constant baseline, while as previously only T achievable.
The proof of the result follows similar routine the proof of Theorem 3. We start by presenting an equivalent lemma Lemma
Lemma 11. Under assumption 3, we can achieve the following bound total estimation error.
T
mi - Aull < 2(D + M)T2/3 (nT2/3)
Proof. The proof is the same as the proof of Lemma 8, by replacing the second m by the first moment D [E[lg+|l]
Proof of Theorem 10. By Assumption 2, we can use first moment of gb to bound the second moment. Hence, Eq. (7) implies that with probability at least 3/4,
2 (F l*) s 4(R² + BAA 1
(15)
Now upper bound the right hand side, indeed
Em = 2
(viRk + m3
k=1
X - m
T
E
+
E
(m+ m)
(m+
m)
1=
(A+ mp (Ax + m+x
E
+
(mi + m)
2MM
T
[1As mx +T
m²
4(M D)MT233 (T
<2²
+T)
2T
m
17

---

Under review as a conference paper at ICLR 2021
Hence by Markov inequality, with probability at least 3/4,
2 2 (f(())))))))))))))))))))) f*) - (
s 4( + 222T)
Next, we lower bound the left hand side,
Σ The Σ my + m
1
Σ d + m
1
my + X + m
(mi Xxa++
Σ
d + m
(mi + mm + m²)
(m+ - Xxe++
d + m
m
By Markov's incquality and Lemma 11, with probability 3/4, we have
Σ (m - Ax) < 4E|
m Axll = 8(D + M)T In(2//))
Following the choice of m 16(D + M)T à/2 In IT()),
we have
T
1
- xx)+1
2(M + mm)
A + m
Consequently, we know that with probability at least 1 - 1
1/2,
f(xT) - - 4(R2 + 2)
2R
12T
2 VT
(16)
Σx 2()+tm)
Σx k: tm)
by setting and the fact that A S mk.
R vT
F VARIANCE ORACLE AND EXTENSION TO NONCONVEX SETTING
In this section, we show that can adapt our algorithm to the variance oracle in Definition (b), where
E Ellgg
ff(x))
of
To avoid redundancy, we present the result in the nonconvex smooth setting. We make the following smoothness assumptions.
Assumption 4. The function is L L-soohth, i.e. for any x. [V vf(wi s L| yll-
Remark that the L-smoothness condition is not required in the second moment oracle. This is why the second moment assumption is usually imposed in the non-differentiable setting (see Section 6.1 of Bubeck (2014)). We first provide the convergences of SGD serving the baselines.
Theorem 12 (Nonconvex baselines). Under the variance oracle in Desinition I (b) and Assumption 4, the convergence of SGD using update I441 2 mkGk with Tl S 2L satisfies
[x11) - - T
k= ROA
(17)
Σk= 7K
where I is an random variable with PII = x
This convergence result very similar to the one shown in the convex setting in Theorem 1. Instead of bounding the function suboptimality, the upper bound is only available on the norm of the gradient, implying convergence to a stationary point. We remark that an additional requirement on the stepsize is required, namely 7/& < 1//LL. This is not surprising since taking a large stepsize will not be helpful due to the L-smoothness condition. Hence, we can not take stepsize inversely depending σe when the noise is small. This restriction makes the comparison convergence rate less straightforward To facilitate the discussion on convergence rate, we make an additional assumption on the lower bound of the variance dR.
18

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Variance Adaptive SGD (Ii, c,
Initialize lio lim==ill where 91 91 are two independent stochastic gradients at 21.
2: for k = ....... do
3: Query two independent stochastic gradient yk, th at zk.-
4: Update + = 7/& (g): + 1///22 with f) tm
and 2 2cL.
5: Update o = 3
33 lo g(
6: end for
7: return 2σ where / is the random variable such that P(1 = x Th-
Assumption 5. For any E [1, oR -
We emphasize that the above condition is not necessary to derive convergence analysis, but only for the clarity in terms of comparison on different convergence rate. This assumption help us focus on the case when noise (instead of the shape of the deterministic function) dominates the convergence rate and determines the step size. otherword, our step size choice under this setting satisfies 7/ S 1/2T., leading to the following convergence rate:
Corollary 13. Let f(z)) f*. We have the following two convergence rate bounds for SGD:
1. SGD with constant stepsize: ih
2A
then
12
o7
{[]((())) V2LA
of
/
2LA
El
Σ
(constant baseline)
2. SGD with idealized stepsize: if
1
24 LT
then
V
V2LAA KL
2LA
(idealized baseline)
The resulting convergence rate are similar as the convex setting. We now modify the adaptive algorithm to make use of the variance oracle and the smoothness assumption. The through algorithm is presented in Algorithm 2. Particularly, we keep exponential moving average of the variance instead of the moments, using two stochastic gradients 9a and ge at the same iterate,
2 = 362 + - 11 gell
2
In particular, E[lggx [ is an unbiased estimator of o To provide the convergence analysis of the algorithm, we make the following assumptions on the variation of the variance.
Assumption 6. We assume upper bound on of = Eillg V 1 i.e. max; d3 S M. We also assume that the total variation in aı bounded. i.e. Σe o 0 D 4M2.
With the above assumptions, algorithm 2 achieve the following convergence rate. Theorem 14. Under the assumptions 4, and large enough such that S T2/3, algorithm with / 24 m 4vD2 + - 1/9 1/2 + 2cL, achieves with probability 1/2.
2LA
32T
[V/(Er) <
T
Σ (ac+m)
The above theorem is almost the same as Theorem 3, and hence all the remarks for Theorem also applies the nonconvex case.
G PROOF OF THEOREM 12
Proof. By L-smoothness, we have
Ln ||
f(x+11) S {((xx) m (gk, v)(xx)) +
19

---

Under review as a conference paper at ICLR 2021
Rearrange and take expectation with respect to Ik, we get
Lunk
Lone
- f(x)) f(ok+1) + |[
Blllg (xxx))
17k
2
From the condition Mn S 21.
we have,
mk
[
((x++1)
L 2
2 g/
2
Sum over and take expectation,
T
E
mel
[ < ((xn) - [(x') +
2 Σ
A=1
Denote I as the random variable such that PP[ i) x 7/-- We know
T Th m f(zo) f(x") +
T
k=
This yields the desired convergence rate in (17).
H PROOF OF THEOREM 14
The proof is almost identical the proof of Theorem 3. We start by presenting equivalent theorem of Lemma below.
Lemma 15. Under assumption 6, we can achieve the following bound on total estimation error using the estimator (ExpMvAvg):
T
16
o 2 + /2)TT/331
Proof. This follows by exactly the same proof Theorem 8 and the fact that B[[lg g'|l²] 2 gg V.]]].
Proof of Theorem 14. The first part of the proof follows the schema in the proof of Theorem 12, when TJs S 1/2L, we know that
L 2
< A
Emmoo
The rest of the proof is exactly the same as the proof of Theorem 3. We can upper bound the right hand side, indeed
T
E
El
E
k
K
(Øx
+ m)
R=1
1=1
of 0%
07
2
B
+ Σ E
(ōx m)
(ox m
k=1
T
<
| 021 +T
m
k=1
22M2 + 22/3 (T(33
<
+ +T
< 2c2TT
m
20

---

Under review as a conference paper at ICLR 2021
M m=
T4/3 S In(T)
The last inequality follows by the choice of parameters that inequality, with probability at least 3/4,
Hence by Markov
mx) V & 4E TH)
$4(A+ 2L
Next, we lower bound the left hand side as in (10),
1 Σ Th E
Σ ok + m
Σ Zōx - ox
(18)
σk +
2m3
Finally, by Markov's inequality, with probability 3/4,
(ox [ ox) - 4E Σ (ox - -+) - 41F Σ
(ōx- -0x) = ( + (
In(12/3).
Following the choice of m D2D2 M2T In (T) 2cL, have
T
Σ -6)
- 4(M + +
2m
0k + m
Together with (18) implies that with probability 3/4,
Σ Th
1
5h +
k=1
Consequently, we know that with probability at least
=
1/2
M 4(A +
2LA
32T
|V 5
(19)
T
Σ [ax+m)
by setting c= v 2A
LT
21


Reviews:
[{"review_id": "tJ_96LNCHHo", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The objective of the paper is to provide a theoretical justification for the value of using adaptive learning steps. The paper presents two results. The first is essentially of theoretical interest, and assumes that the noise level indicators defined in Eq. (1) [but which are difficult to understand at this level of the paper] are known. The second is more practical: it shows that a variant of the RMSprop algorithm achieves the same results as the \"theoretical\" algorithm.\n\nI perfectly understand the definition of the second moment $m^2(x)$ and $\\sigma^2(x)$. These quantities depend on the current value of the parameter. This is a feature of the function we are trying to optimize, and this is perfectly clear. The Definition 1 of the non-stationary noise oracle is more far-fetched: \"The stochasticity of the problem is  governed by a a sequence of second moment $\\{m_k\\}$ and variance $\\sigma_k^2$\". The definition is not even very well written and explained. This is an unconditional exceptation: it means in particular that the expectation is taken wrt to the distribution of the initial value  of the parameter (I guess therefore that the expectation is also taken on the initial condition, which can be concentrated on a point).  Even if we take a  this is very difficult to check, except in the situation in which the \"noisy gradient\" used in the procedure is the true gradient affected by some additive noise, independent from the current value of the parameter. The authors feel this embrassment in the sentence that their \"goal is to demystify the correlation between the noise intensity and the performance of the algorithm\" and two lines later \"the noise intensity\" (what does it mean \"intensity\" ?) is \"decoupled\" from the location, in strict contradiction of their earlier definiton of second moment and variance which are, of course, location dependent. We can of course argue that in most analysis the variance (or even the conditional variance) of the gradient is bounded, so that this may appear as a relaxation of the previous assumptions... Theorem 1 is not surprising, same three-lines proof where the bound on the gradient noise variance is simply replaced by a time-dependent variance. They illustrate the result with a very artificial example (Example 1), which substantiate an earier claim (that the adaptive stepsize can achieve a faster rate of convergence by a factor which is polynomial in T). In section 4, the authors start to consider the more interesting \"adaptive\" scenario. The algorithm is a simplified version of RMSprop in which a \"global\" scale is applied to the gradient instead of an \"component-dependent\" factor applied  on each individual component of the gradient.  The authors formulate Assumption 1, which a bit strange because the assumption is algorithm dependent (the unconditional variance of the algorithm after $k$-step depends on the algorithm itself, so we have to guess that Assumption 1 is formulated for the adaptive SGD algorithm... but then the quantities depend upon the constant $m$  and $c$ which are later optimized in the theorem. Everything is written as if the noise variance depends only on the iteration index, independently of the algorithm itself... Given this remark, it is very difficult to understand what theorem 3 is about... This really gives the impression of a snake biting its tail, because the definition of $m_k$ depends on the law of the  iterate and therefore on the SA algorithm, which we then allow ourselves to optimize the parameters of the algorithm but without affecting the law of iteration (because the m_k are always the same). Strange... Of course, the only scenario where this makes sense is when $g_k= \\nabla f(x_k) + \\sigma^_k Z_k$, i.e. when the gradient noise depends only on the iteration index but not on the current  value of the iterate. \n I find the paper interesting, but the conclusions must be rewritten very clearly so as not to mislead the reader. You are in fact studying the stochastic approximation with an error that would have a variance profile, perhaps unknown, and depending on the iteration index but not on the law of iterations. As a result, the conclusions have much less force.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "jatMVG1wDX", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 studies gradient-based stochastic optimization algorithms which incorporate (estimates of) the noise statistics in the adaptive stepsize design. Starting from the standard analysis of SGD with adaptive steps (Thm 1) the authors show in Cor 1 how, using a second-moment-dependent learning rate, one can “accelerate” (see comment later) the convergence of SGD. Next, the authors show (Thm 3) that one can recover a similar result by estimating the second moment using an exponential moving average.\n\nThe paper is well written, and I think Thm3 is novel, correct and interesting. However, I think the authors should address the following points to improve their work and make the paper publishable:\n\n1) The authors should discuss the performance of their method on neural nets more scientifically: the architecture and the hyperparameters selection of Figure 3 are not discussed. Also, just one architecture/dataset is presented. @authors, also how did you select the parameter beta in the experiments? Can you show us more results maybe on deeper models?\n\n2) We all know very well that the standard analysis of non-convex gradient descent (which the authors adapt here) does not lead to tight upper bounds. Hence, it would instead be interesting to also study the behavior of the methods proposed by the authors on convex problems and to provide some tight rates backed up on well-controlled experiments on ill-conditioned linear and logistic regression. This would better illustrate the idea. In short, since this phenomenon is also present in convex problems, I think the authors should provide a discussion on this too.\n\n3) The paper focuses a bit too much on example 1, showing very fast rates. It would be great to also compute the speed-up predicted by the algorithm based on the actual variance of a real-world optimization problem. How big is this theoretical speed-up given a real-world variance?\n\nIf the authors provide a good answer and are able to provide a convincing real-world example for point (3) then I will raise my score to a weak accept.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "bEBhBghH5Iy", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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\n\nThe authors provide a new analysis of SGD and versions of RMSprop, taking into account possible non-stationarity of the gradient noise. In particular, the authors propose. \n(i) the convergence analysis of SGD with stepsizes dependent on the second moment of stochastic gradients and a \"norm\" version of RMSprop (Moment Adaptive SGD) in the convex non-smooth case and\n(ii) the convergence analysis of SGD with stepsizes dependent on the variances of stochastic gradients and a variance adaptive SGD in the non-convex smooth case with rates of gradient norm decrease.\nThe rates are given in terms of high probability convergence.\n\n## Strengths\n\n1) The paper addresses an important and fundamental question for understanding why methods based on moment estimation (like RMSprop or Adam) work better in certain regimes.\n2) The experimental study of gradient noise non-stationarity shows interesting behavior of the gradient noise that can be useful for future research in this area.\n\n## Weaknesses\n\n1. The theory presented in the paper needs significant further development and refinement: some results are misleading, assumptions are too strong and not motivated well, several crucial statements are left without proof, and some of the presented proofs have inaccuracies/unexplained parts. Below, I provide a list of my major concerns about the paper.\n1.1. **Assumptions.** While authors state in the first sentence of the abstract that they analyze stochastic optimization under \"weaker assumptions on the distribution of noise than those used in usual analysis,\" this is not true. In fact, the main algorithms -- Algorithm 1 and Algorithm 2 -- are analyzed under Assumptions 1 and 6. These assumptions are strictly stronger (otherwise, according to Nemirovski and Yudin lower bounds for stochastic non-smooth optimization, it is impossible to get a better rate than SGD has) than the uniformly bounded second moment of the stochastic gradient and uniformly bounded variance of the stochastic gradient assumptions. Moreover, in the non-smooth convex case, which is considered as the main case of the paper, authors assume that $m_k = \\mathbb{E}[||g_k||^2]$, where $g_k$ is an conditionally unbiased estimator of $\\nabla f(x_k)$, is bounded and *does not depend on $x_k$*. Moreover, the authors do not explicitly state this as an assumption and do not emphasize this fact in the statements of Theorems 1 and 3. It is an important assumption and should be stated explicitly in the statements of these theorems. Next, $m_k$ depends on $x_k$ even when the noise is negligible, i.e., the stochastic gradients are almost gradients.\n  1.2. **Misleading results.** Unfortunately, some results require further explanations. For example, why can we choose $\\eta_k$ dependent on $\\sum_{t=1}^Tm_t$ in Corollary 2? It is misleading since $m_t$ for $t > k$ depends on $\\eta_k$ in general. Next, it is unclear how can we know $m_k$ or even $\\sum_{k=1}^T m_k$ to use these stepsizes? It seems, that in general it is not possible.\n 1.3. **Results without the proofs.** Some results that play a central role in the paper are left without rigorous proofs and even sketches of the proofs. In particular, the rates from Table 1 are not derived for the noise model considered in Example 1, and the most important results of the paper --- Corollaries 5, 6, and 7 --- are provided without the proofs as well. These results were meant to explain the main advantage of Algorithm 1 in comparison with vanilla SGD, but the proofs for them seem to be not that straightforward and should be added to the paper.\n 1.4. **Inaccuracies and unexplained parts in the proofs.** I have checked all proofs in detail. While, in general, they are sound and mathematically correct, some places in the proofs of the main convergence results for Algorithm 1 and 2 are left without explanation and seem to be inaccurate (see my list with comments below).\n2. Clarity of the paper should be improved. Some claims require further clarification; see my comments below.\n3. The paper contains a significant amount of typos and grammatical errors. Here are some of them:\n - page 4, \"The improvement factor ...\": has depends $\\to$ depends\n - page 13, \"The iterate suboptimality ...\": have $\\to$ has\n - numerous missing periods after formulas (e.g., (10) and before inequality (11))\n - page 19, \"This assumption help us ...\": help $\\to$ helps\n - page 19, \"In otherword ...\": otherword $\\to$ other words\n - page 19, \"The through algorithm ...\": the sentence is unclear and should be rewritten using academic English\n - page 19, \"With the above assumption ...\": algorithm $\\to$ Algorithm; achieve $\\to$ achieves\n - page 19, \"The above theorem is almost ...\": applies $\\to$ apply\n\n## Questions and Comments\n1. It would be interesting to see the comparison with recent relevant papers, e.g., \n - Ogaltsov, Aleksandr, et al. \"Adaptive gradient descent for convex and non-convex stochastic optimization.\" arXiv preprint arXiv:1911.08380 (2019).\n - Défossez, Alexandre, et al. \"On the Convergence of Adam and Adagrad.\" arXiv preprint arXiv:2003.02395 (2020).\n2. page 2, \"For CIFAR 10 ...\", \"While for language ...\": These claims should be supported by relevant references.\n3. page 3, Definition 1: Should be $\\mathbb{E}[g(x_k)\\mid x_k] = \\nabla f(x_k)$ instead of $\\mathbb{E}[g(x_k)] = \\nabla f(x_k)$. Do you use full expectations in (a) and (b)?\n4. page 3, \"This is empirically justified ...\": To justify this claim, authors should add at least plots comparing $m_k$ and $\\sigma_k$ for different optimizers.\n5. page 3, Theorem 1: One should explicitly state in the theorem that $f$ is convex.\n6. page 4, Assumption 1: Why is $ M$ used to estimate concentration and for bounding $m_k$? It can be the case that concentration is good (e.g., can be achieved via large bathes computed in parallel) while $\\max m_k$ is large. Is it possible to get tighter results after the refinement of this assumption? Next, when does this assumption hold for Algorithm 1? It should be stated explicitly in the text with concrete examples of the problems. Why $D^2 = \\Omega(M^2)$? The problem should be simpler when $D$ is small, even if $M$ is big. Do you mean $D^2 = O(M^2)$?\n7. page 5, Remark 4: it seems you mean standard amplification (the term from complexity theory), not restarts having a different meaning in optimization. One can do that, but this will require additional $O(log|\\delta|)$ computations of the functional value of $f$ to choose the best point. For example, it is not possible for the general expectation minimization problem, which restricts the applicability of the results proposed in the paper.\n8. page 6, Corollary 5: The proof of this corollary is vital for the paper. Next, the explanation of why this assumption on $M$ and $m_k$ is reasonable should be added.\n9. page 6, Corollary 6: The condition $M/m_{avg} \\leq T^{1/9}$ should be further explained and motivated. Next, the proof is also vital for the paper.\n10. page 7, \"The convergence results are ...\": This is not true since, in the variance oracle case, authors analyze only non-convex smooth problems and the convergence to the stationary points. It would be interesting to see the analysis for the smooth convex case and see what else we can get with smoothness in the convex case. The authors should explicitly write in the main part of the paper what results they have in the appendix. In the current form, this description is misleading.\n11. Experiments: How $m_k$ and $\\sigma_k$ were estimated? By definition, these parameters are the full expectation. Do authors apply Monte-Carlo approximation for these parameters in the experiments? Next, there are two idealized and constant baselines in the text (in Sections 3 and F). What baselines did the authors use in the experiments? Have the authors tried all options? If yes, what were the results?\n12. page 14, formula for $\\hat m_k^2$: Norms are missing for $g_{k-1}, g_{k-2}, \\ldots, g_0$.\n13. page 14, after the formula for $\\hat m_k^2$: independence $\\to$ conditional independence.\n14. **page 16, inequality above (11):** It is not clear how this inequality was obtained from the above one and the definition of $m$. This part should be clarified.\n15. page 16, Remark 9: Why (8) holds in this case? The proof is required.\n16. page 16, Remark 9: What does this remark imply? It should be either explicitly stated or removed.\n17. **page 18, inequality above (16):** This part should be explained.\n18. page 18, application of Markov's inequality: Right-hand side is incorrect.\n19. page 19, Assumption 6: Why $D^2 = 4M^2$ is needed? $D$ can be significantly smaller in some cases.\n20. **page 21, the second inequality after (18):** It is not clear how this inequality was obtained from the above one and the definition of $m$. This part should be clarified.\n\n## Final remarks\n\nTo conclude, the paper focuses on a very important problem but suffers from a number of serious issues described above. Therefore, for me, it is clear that in the current shape, the paper should be rejected. Though there is a chance that the authors will address all my comments, I believe that the paper requires significant improvements and, as a consequence, a new round of reviews.\n\n## AFTER REBUTTAL\nFirst of all, I would like to thank the authors for their detailed response: I realize that the authors spent a lot of effort to address most of my comments and questions. I have read other reviews and the responses by authors. However, I still have questions about the paper, preserving me from increasing the score.\n\n1. **Assumption 1.** Even in the updated form presented in the rebuttal, Assumption 1 is not mathematically rigorous. How can $\\mathbb{E}[||g(x,k)||^2]$ be independent of $x$? Can you provide any non-trivial example? Actually, it is highly relevant to my third concern (**Misleading results**) from the weaknesses part: when we use stepsizes dependent on $m_k$ from the future, we implicitly assume that we can use any stepsizes without changing the sequence {$m_k$} (otherwise $m_k$ should depend on $x_k$). Then, if we consider SGD with arbitrary small stepsize, we will get the method that generates arbitrary close points. In these settings, for the majority of problems, the sequence {$m_k$} should be stationary (since we can take arbitrary small stepsize). But it is not stationary, at least in the experiments presented in the paper. **It is a crucial contradiction that significantly decreases the value of the results given in the paper.** In other words, this assumption **never** holds. I understand that the authors simplified the assumption to handle the non-stationarity of the noise. However, the settings considered in the paper are too simplified: they do not cover any problem.\n2. **\"We could present the paper in terms of $\\sigma_k$...\"** The paper would significantly benefit from this. Moreover, without resolving the issue mentioned above, it is better to remove the whole part based on the independence of {$m_k$} on $x$.\n3. **\"Moreover, allowing the step size choice to depend on noise level is a standard approach in almost all SGD analysis.\"** I agree with the authors. Still, the key difference is that typically it is assumed that **the upper bound** for the noise level is known. It significantly differs from the case when {$m_k$} is known.\n4. **\"We have compared SGD and Adam in Figure 4 of the appendix (see Appendix A).\"** Unfortunately, I have to disagree: the authors presented the behavior of $m_k$ and $\\sigma_k$ for SGD and Adam in separate figures -- Figures 1 and 4. There are 10 pages between them, so there is no transparent comparison. It would be much better to see one figure for both algorithms --- this is what I meant by comparison in my review.\n5. I still find the proof of Remark 9 to be incomplete: in the proof of the analog of (8) for the case of Remark 9 the authors assumed that $\\hat m_{k+1}^2 = \\beta \\hat m_k^2 + (1-\\beta)||g_k||^2$ (in the proof of the last but one inequality), while in this remark it should be $\\hat m_{k+1}^p = \\beta \\hat m_k^p + (1-\\beta)||g_k||^p$. Next, what are the assumptions on $p$? Can it be any positive number? If yes, then what is the best choice of $p$? This part requires further discussion and development.\n6. **About my 19-th question from the list.** I meant that $D^2$ and $M^2$ could be unrelated in general. It would be interesting to see the discussion on how it influences the convergence rate. The current analysis says that the smaller $D$ is, the better the algorithm converges. It should be discussed how it relates to the empirical findings.\n7. The proofs of Corollaries 5, 6, and 7 were given nor in the rebuttal, neither in the paper. Actually, the authors have not updated the paper at all, although many corrections should be applied (at least grammatical errors and misprints noticed above).\n\nTo conclude, the most important questions and comments from my review have not been properly addressed by the authors. Therefore, I want to keep my initial score unchanged.", "extra_scores": {}, "extra_text": {}}, {"review_id": "XF0-hHagePh", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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 studies the problem of stochastic optimization where the gradient noise process is non-stationary. Based on a general convergence results based on a general sequence for the second moments of the stochastic gradient norms and a general stepsize sequence, the authors propose to use an online estimation procedure for the gradient norm second moments, in order to mimic the behavior of the ``idealized'' stepsize sequence. Finite-time convergence rates are established for the algorithms with adaptive stepsize, leading to an acceleration effect in certain regimes for the non-stationarity.\n\nBoth the adaptive stochastic gradient algorithms and handling non-stationary noise are indeed interesting problems. However, the two problems are of different natures and this paper attempts to address one of them from the standing point of another, which is not particularly convincing. Indeed, for any stochastic optimization problem for supervised learning (including training neural nets that the authors mentioned), the stochastic gradient oracles are i.i.d. copies of stochastic gradient function $\\nabla f (\\theta; \\xi_i)$, where $\\theta$ is the model parameter and $\\xi_i$ are i.i.d. data points. The sequence of functions $(\\nabla f (\\cdot; \\xi_i))_{i = 1}^{+\\infty}$ are not only stationary but also i.i.d., and the only reason for observing difference levels of noise variances is the point at which the stochastic gradient is evaluated. In the introductory parts, authors realized the existing works that assume bounds on the noise variance based on the norm of current iterates. Though the noise variance does not always scale like this in neural network training, it is due to more complicated landscape and noise structure, but not due to the time steps.\n\nTherefore, it is quite artificial to modle the noise process as a non-stationary sequence that varies with time. Indeed, if you use a difference algorithm, it is reasonable to expect that the sequence of points at which the stochastic gradients oracle are evaluated can change a lot, leading to a totally different noise variance sequence. There are applications, such as real-time stochastic control with a non-stationary environment, where the noises are intrinsically changing with time. But it is not the case with classical supervised learning.\n\nOn a related note, under the stochastic gradient moment sequence in Example 1 in the paper, it appears that the best thing to do might be to only use the first 1/5 and last 1/5 proportion of the data stream, while doing nothing with the middle 3/5 of the data when the noise is large. Up to a constant factor of 5, this naive algorithm gives the convergence rate the same as in the model where the noise is always of order $T^{-\\alpha}$, which is better than the results under ``idealized'' stepsize sequence predicted by the paper. In training neural networks, however, this will become a stupid algorithm, which does nothing but wasting 3/5 of the data. When it comes back to updating the parameter using the last 1/5 of the data, the noise will be still large because the iterates enters a region of large stochastic gradients. If this naive algorithm can be challenged by this reasoning, how can we argue that the algorithms designed in the paper does not suffer from this?\n\nBesides, the quantity $m_k^2$ is defined as the second moment for the stochastic gradient at the $k$-th iterate. It is larger than the squared norm of the population-level gradient, by Cauchy-Schwartz inequality. Imposing an upper bound on this quantity that depends on $T$ is implicitly assuming some convergence property of the algorithm. And this bound is $T{-\\alpha}$ at the initial point, which means that the algorithm starts at a near-stationary point. This makes the theory even more artificial. Even in an actual real-time non-stationary environment, it is ok to assume a sequence of noise variances, but it is not convincing to assume a bound on the gradient itself.\n\nThe adaptive stochastic gradient algorithm presented in this paper is interesting, and may make an interesting step towards more understanding into adaptive SGD methods based on online moment estimates. I would encourage the authors to dig deeper in this direction under a suitable set of assumptions, and show some real acceleration effect.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the problem of stochastic optimization where the gradient noise process is non-stationary. While this is an important problem in the community, the reviewers find that the assumptions are poorly justified. While the authors provided extensive feedback, the reviewers did not change their initial assessment. This paper can therefore not be accepted in its current form. I think the reviewers provided some very critical and useful feedback and I therefore strongly encourage the authors to take advantage of this feedback to resubmit their paper to another venue.

Decision: Reject