Title: DISSECTING ADAM: THE SIGN, MAGNITUDE AND VARIANCE OF STOCHASTIC GRADIENTS Anonymous

Abstract: The ADAM optimizer is exceedingly popular in the deep learning community. Often it works very well, sometimes it doesn't. Why? We interpret ADAM as a combination of two aspects: for each weight, the update direction is determined by the sign of the stochastic gradient, whereas the update magnitude is solely determined by an estimate of its relative variance. We disentangle these two aspects and analyze them in isolation, shedding light on ADAM's inner workings. Transferring the "variance adaptation" to momentum-SGD gives rise to a novel method, completing the practitioner's toolbox for problems where ADAM fails.

1. INTRODUCTION:

Many prominent machine learning models pose empirical risk minimization problems of the form

EQUATION

where θ ∈ R d is a vector of parameters, {x 1 , . . . , x M } a training set, and (θ; x) is a loss quantifying the performance of parameter vector θ on example x. Computing the exact gradient in each step of an iterative optimization algorithm becomes inefficient for large M . Instead, we construct a minibatch B ⊂ {1, . . . , M } of |B| M data points sampled uniformly and independently from the training set and compute an approximate stochastic gradient

EQUATION

which is an unbiased estimate, E[g(θ)] = ∇L(θ). We will denote by σ(θ) 2 i := var[g(θ) i ] its element-wise variances. 1 The basic stochastic optimizer is stochastic gradient descent (SGD, Robbins & Monro, 1951) and its momentum variants (Polyak, 1964; Nesterov, 1983) . A number of methods, widely-used in the deep learning community, choose per-element update magnitudes based on the history of stochastic gradient observations. Among these are ADAGRAD (Duchi et al., 2011) , RMSPROP (Tieleman & Hinton, 2012) , ADADELTA (Zeiler, 2012) and ADAM (Kingma & Ba, 2015) .

1.1. A CLOSER LOOK AT ADAM:

We start out from a reinterpretation of the widely-used ADAM optimizer. Some of the considerations naturally extend to ADAM's close relatives RMSPROP and ADADELTA, but we restrict our attention to ADAM to keep the presentation concise. ADAM maintains moving averages of the observed stochas-1 With k ∼ U({1, . . . , M }), the gradient ∇ k (θ) := ∇ (θ, x k ) is a random variable with mean (1, 1.5). In the right panel, we employ a variance adaptation (to be derived in §3.2) that scales the i-th coordinate by (1 + η2 i ) -1 . In this example, the θ 2 -coordinate has much higher relative variance (η 2 2 = 2.25) than the θ 1 -coordinate (η 2 1 = 0.25) and is thus shortened. This reduces the variance of the update direction at the expense of biasing it away from the true gradient in expectation. tic gradients and their element-wise square 2 ,

EQUATION

EQUATION

Here, m t and v t are "bias-corrected" versions of the exponential moving averages to obtain convex combinations of past observed (squared) gradients. ADAM then updates

θ t+1 = θ t -α m t √ v t + ε (5)

with a small constant ε > 0 guaranteeing numerical stability of this division. Ignoring ε and assuming |m t,i | > 0 for the moment, we can rewrite the update direction as3 

EQUATION

Since m t and v t approximate the first and second moment of the stochastic gradient g t , respectively, v tm 2 t can be seen as an estimate of element-wise stochastic gradient variances. The division by the non-central second moment effectively removes the magnitude of m t ; it only appears in the ratio

(v t -m 2 t )/m 2 t .

Hence, ADAM can be interpreted as a combination of the two following aspects:

• The update direction (±) for the i-th weight is given by the sign of m t,i .

• The update magnitude for the i-th weight is uniquely determined by the global step size α and an estimate of the relative variance,

EQUATION

Specifically, the update in the i-th coordinate is scaled by 1 + η2 t,i -1/2 , shortening steps in high-relative-variance coordinates. Fig. 1 shows a sketch of this variance adaptation. "Stochastic Variance-Adapted Gradient"

1.2 OVERVIEW Both aspects of ADAM-taking the sign and variance adaptation-are briefly mentioned in Kingma & Ba (2015) , who note that "[t]he effective stepsize [...] is also invariant to the scale of the gradients" and refer to m t / √ v t as a "signal-to-noise ratio". The purpose of this paper is to disentangle these two intertwined aspects in order to discuss and analyze them in isolation.

This perspective naturally suggests two alternative methods by incorporating one of the aspects but not the other (see Table 1 ). Taking the sign of the stochastic gradient (or momentum term) without any further modification gives rise to "Stochastic Sign Descent" (SSD). On the other hand, "Stochastic Variance-Adapted Gradient" (SVAG) applies element-wise variance adaptation factors directly on the stochastic gradient (or momentum term) instead of on its sign. We proceed as follows: In Section 2, we investigate the sign aspect. In the simplified setting of stochastic quadratic problems, we derive conditions under which the element-wise sign of a stochastic gradient can be a better update direction than the stochastic gradient itself. Section 3 discusses the variance adaptation. We present a principled derivation of "optimal" element-wise variance adaptation factors for a stochastic gradient as well as its sign. Subsequently, we incorporate momentum and briefly discuss the practical estimation of stochastic gradient variance. Section 4 presents some experimental results.

1.3. RELATED WORK:

The idea of using the sign of the gradient as the principal source of the optimizer update has already received some attention in the literature. The RPROP algorithm (Riedmiller & Braun, 1993) ignores the magnitude of the gradient and dynamically adapts the per-element magnitude of the update based on observed sign changes. With the goal of reducing communication cost in distributed training of neural networks, Seide et al. (2014) empirically investigate the use of the sign of stochastic gradients.

Regarding the variance adaptation, Schaul et al. (2013) derive element-wise step sizes for stochastic gradient descent that have (among other factors) a dependency on the stochastic gradient variance.

1.4. THE SIGN OF A STOCHASTIC GRADIENT:

We briefly establish a fact that will be used throughout the paper. The sign of a stochastic gradient s(θ) = sign(g(θ)) estimates the sign of the true gradient. Its distribution (and thus the quality of this estimate) is fully characterized by the success probabilities ρ i := P [s(θ) i = sign(∇L(θ) i )]. These depend on the distribution of the stochastic gradient. If we assume g(θ) to be Gaussian-which is strongly supported by a Central Limit Theorem argument on Eq. (2)-we have

EQUATION

) see §B.2 in the supplements. Furthermore, it is E[s(θ) i ] = (2ρ i -1) sign(∇L(θ) i ).

2. WHY THE SIGN?:

Can it make sense to ignore the gradient magnitude? We provide some intuition under which circumstances the element-wise sign of a stochastic gradient is a better update direction than the stochastic gradient itself. This question is difficult to tackle in general, which is why we restrict the problem class to the simple, yet insightful, case of stochastic quadratic problems, where we can investigate the effects of curvature properties and its interaction with stochastic noise.

Model Problem (Stochastic Quadratic Problem (QP)). Consider the loss function (θ, x) = 0.5 (θx) T Q(θx) with a symmetric positive definite matrix Q ∈ R d and "data" coming from the distribution x ∼ N (x * , ν 2 I). It is

EQUATION

with ∇L(θ) = Q(θx * ). Stochastic gradients are given by g(θ) = Q(θx) ∼ N (x * , ν 2 I).

2.1. THEORETICAL COMPARISON:

We want to compare update directions on stochastic QPs in terms of their expected decrease in function value from a single update step. If we update from θ to θ + αz, we have

EQUATION

For this comparison of update directions, we allow for the optimal step size that minimizes Eq. ( 10), which is easily found to be α * = -∇L(θ) T E[z]/E[z T Qz] and yields an expected improvement of

EQUATION

We find the following expressions/bounds for the improvement of SGD and SSD:

EQUATION

where the λ i ∈ R + are the eigenvalues of Q with orthonormal eigenvectors v i ∈ R d . Derivations can be found in §B.1 of the supplements. Comparing these expressions, we make two observations.

Firstly, I(s) has a dependency on i,j |q ij |. This quantity relates to the eigenvalues, as well as the orientation of the eigenbasis of Q. By writing Q in its eigendecomposition one finds that

i,j |q ij | ≤ i λ i v i 2 1 .

If the eigenvectors are perfectly axis-aligned (diagonal Q), their 1-norms are v i 1 = v i 2 = 1. It is intuitive that this is the best case for the intrinsically axis-aligned sign update. In general, the 1-norm is only bounded by

v i 1 ≤ √ d v i 2 = √ d,

suggesting that the sign update will have difficulties with arbitrarily oriented eigenbases. We can alternatively express this matter in terms of "diagonal dominance". Assuming Q has a percentage c ∈ [0, 1] of its "mass" on the diagonal, i.e., i |q ii | ≥ c i,j |q ij |, we can write

EQUATION

)

Becker & LeCun (1988) empirically investigated the diagonal dominance of Hessians in optimization problems arising from neural networks and found relatively high percentages of mass on the diagonals of c = 0.1 up to c = 0.6 for the problems they investigated.

Secondly, I(g) contains the constant offset ν 2 d i=1 λ 3 i in the denominator, which can become hugely obstructive for ill-conditioned and noisy problems. In I(s), on the other hand, there is no such interaction between the magnitude of the noise and the eigenspectrum; the noise only manifests in the element-wise success probabilities ρ i , its effect in the denominator is bounded. A recent paper (Chaudhari et al., 2016) investigated the eigenspectrum in deep learning problems and found it to be very ill-conditioned with the majority of eigenvalues close to zero and a few very large ones.

In summary, we can expect the sign update to be beneficial for noisy, ill-conditioned problems with "diagonally dominant" Hessians. There is some (weak) empirical evidence that these conditions might be fulfilled in deep learning problems. 

2.2. EXPERIMENTAL EVALUATION:

We verify the above findings on artificially generated stochastic QPs, where all relevant quantities are known analytically and controllable. We control the eigenspectrum by specifying a diagonal matrix Λ of eigenvalues: (1) a mildly-conditioned problem with eigenvalues drawn uniformly from [0.1, 1.1] and (2) an ill-conditioned problem with a structured eigenspectrum similar to the one reported for neural networks by Chaudhari et al. (2016) by uniformly drawing 90% of the eigenvalues from [0, 1] and 10% from [30, 60] . Q is then generated by (1) Q = Λ to produce an axis-aligned problem and (2) Q = RΛR T with a rotation matrix R drawn uniformly at random (see Diaconis & Shahshahani, 1987) . This makes four different matrices, which we consider at noise levels ν ∈ {0, 0.1, 4.0}. We compare SGD and SSD, both with the optimal step size as derived from Eq. ( 10), which can be computed exactly in this setting.

Figure 2 shows the results, which confirm the theoretical findings. On the well-conditioned, noisefree problem, gradient descent vastly outperforms the sign-based method. Surprisingly, adding even a little noise almost evens out the difference in performance. The orientation of the eigenbasis had little effect on the performance of SSD in the well-conditioned case. On the ill-conditioned problem, the methods work roughly equally well when the eigenbasis is randomly rotated. As predicted, SSD benefits drastically from an axis-aligned eigenbasis (last row), where it clearly outperforms SGD.

3. VARIANCE-BASED ELEMENT-WISE STEP SIZE ADAPTATION:

Besides the sign direction, the other defining property of ADAM are variance-based element-wise step sizes. Considering the variance adaptation in isolation from the sign aspect naturally suggests to employ it directly on the stochastic gradient, without taking the sign. In both cases, a motivation arises from the following consideration:

Assume we want to update in a direction p ∈ R d (or sign(p)), but only have access to an unbiased estimate p ∈ R d with E[p] = p. We allow for element-wise factors γ ∈ R d , i.e., we update γ p or γ sign(p). One way to make "optimal" use of these factors is to choose them such as to minimize the expected distance to the desired update direction. Using the squared Euclidean norm as a distance measure, we find the following result.

Lemma 1. Let p ∈ R d be a random variable with E[p] = p and var[p i ] = σ 2 i . Then min γ∈R d E[ γ p -p 2 2 ] is solved by γ i = p 2 i p 2 i + σ 2 i = 1 1 + σ 2 i /p 2 i (14)

and min

EQUATION

where

ρ i = P[sign(p i ) = sign(p i )].

In the sign case, γ i is proportional to the success probability with γ i = 1 if we are certain about the sign (ρ i = 1) and γ i = 0 if we have no information about the sign at all (ρ i = .5).

3.1. VARIANCE ADAPTATION FOR THE SIGN OF A STOCHASTIC GRADIENT:

Applying Eq. ( 15) to p = g, the optimal variance adaptation factors for the sign of a stochastic gradient are found to be γ i = 2ρ i -1, where

ρ i = P[sign(g i ) = sign(∇L i )].

Recall from Eq. ( 8) that, under the Gaussian assumption, the success probabilities of the sign of a stochastic gradient are

2ρ i -1 = erf[( √ 2η i ) -1 ]. ADAM uses the variance adaptation factors (1 + η 2 i ) -1/2 , which turns out to be a close approximation of erf[( √ 2η i ) -1 ],

as shown in Figure 5 in the supplements. Hence, ADAM can be regarded as an approximate realization of this optimal variance adaptation scheme. We experimented with both variants and found them to have identical effects. The small difference between them can be regarded as insignificant when η itself is subject to approximation error. We thus stick to (1 + η 2 i ) -1/2 for accordance with ADAM and to avoid the (more costly) error function.

3.2. STOCHASTIC VARIANCE-ADAPTED GRADIENT (SVAG):

Applying Eq. ( 14) to p = g, the optimal variance adaptation factors for SGD are found to be

EQUATION

)

This term is known from Schaul et al. (2013) , where it appears together with diagonal curvature estimates in element-wise step sizes for SGD. We refer to this method (without curvature estimates) as "Stochastic Variance-Adapted Gradient" (SVAG). A momentum variant will be derived below.

Intriguingly, variance adaptation of this form guarantees convergence without manually decreasing the global step size. We recover the O(1/t) rate of SGD for smooth, strongly convex functions. We emphasize that this result considers an "idealized" version of SVAG with exact η 2 i . It is a motivation for this form of variance adaptation, not a statement about the performance with estimated variances.

Theorem 1. Let f be µ-strongly convex and L-smooth. Assume we update θ t+1 = θ tα(γ t g t ), where g t is a stochastic gradient with E[g

EQUATION

)

where f * is the minimum value of f . (Proof in §B.4)

3.3. ESTIMATING GRADIENT VARIANCE:

In practice, the relative variance is of course not known and must be estimated. As noted in the introduction, ADAM obtains an estimate of the stochastic gradient variance from moving averages,

σ 2 t,i ≈ ŝt,i = v t,i -m 2 t,i .

The underlying assumption is that the function does not change drastically over the "effective time horizon" of the moving average, such that the recent gradients can approximately be considered to be iid draws from the stochastic gradient distribution. An estimate of the relative variance can then be obtained by (v tm 2 t )/(m 2 t ), as in ADAM. Unlike ADAM we do not use different moving average constants for m t and v t . The constant for the moving average should define a time horizon over which the gradients can approximately be considered to come from the same distribution. From this perspective, it is hardly justifiable to use different horizons for the gradient and its square. Furthermore, we found individual moving average constants for m t and v t to have only minor effect on the performance of our methods.

An alternative variance estimate can be computed locally "within" a single mini-batch. A more detailed discussion of both estimators can be found in §C of the supplements. We have experimented with both estimators and found them to work equally well for our purpose of variance adaptation. We thus stick to moving average-based estimates for the main paper. Appendix D provides details and experimental results for the mini-batch variant.

3.4. INCORPORATING MOMENTUM:

When we add momentum-i.e., we want to update in the direction r t or sign(r t ) with a momentum term r t = µr t-1 + g t = t s=0 µ s g t-s -the variance adaptation factors should be determined by the relative variance of r t , according to Lemma 1. It is

EQUATION

Replacing E[g t-s ] ≈ m t-s and var[g t-s ] ≈ v t-sm 2 t-s we could compute these quantities. However, this would require two additional moving averages and can thus be discarded as impractical. Fortunately, we can motivate an approximation that does not require any additional memory requirements (see §C):

EQUATION

)

Note that the correction factor κ(µ, t) does not appear in ADAM, which updates in the direction sign(m t ) = sign(r t ) but performs variance adaptation based on (v tm 2 t )/m 2 t . The supplements contain experiments with a variant of ADAM that includes this correction factor.

4. EXPERIMENTS:

We compare momentum-SGD (M-SGD) and ADAM to two new methods: First, we consider M-SSD: stochastic sign descent using a momentum term. The second method is M-SVAG, i.e., SGD with momentum and variance adaptation of the form (1 + η 2 ) -1 , where the relative variance of the momentum term is estimated from moving averages according to Eq. ( 19). These four methods are the four possible recombinations of the sign aspect and the variance adaptation aspect of ADAM, as laid out in Table 1 . Algorithms 1 and 2 provide pseudo-code for M-SSD and M-SVAG. For all experiments, we use µ = 0.9 for M-SGD, M-SSD and M-SVAG and default parameters (β 1 = 0.9, β 2 = 0.999, ε = 10 -8 ) for ADAM. Note that M-SVAG does not use an ε-parameter, see Alg. 2.

Algorithm 1 M-SSD (Stochastic Sign Descent with Momentum) Require: initial value θ 0 , step size α, momentum parameter µ ∈ [0, 1], number of steps T 1: Initialize m = 0, v = 0 2: for t = 1, . . . , T do 3:

Compute stochastic gradient g = g(θ)

4:

Update moving average m ← µm + g 5:

Update θ ← θα sign(m) 6: end for Under review as a conference paper at ICLR 2018 Algorithm 2 M-SVAG (Stochastic Variance-Adapted Gradient with Momentum) Require: initial value θ 0 , step size α, momentum parameter µ ∈ [0, 1], number of steps T 1: Initialize m = 0, ṽ = 0 2: for t = 1, . . . , T do 3:

Compute stochastic gradient g = g(θ)

4:

Update moving averages m ← µ m + (1µ)g, ṽ ← µṽ + (1µ)g 2

5::

Bias

-correct m = (1 -µ t ) -1 m, v = (1 -µ t ) -1 ṽ 6: Compute relative variance estimate η 2 = κ(µ, t) v-m 2 m 2

Eq. ( 19) 7:

Compute variance adaptation factors γ = (1 + η 2 ) -1 8:

Update θ ← θα(γ m) 9: end for We do not use an ε-parameter as in ADAM. In the (rare) case that m i = 0 for coordinate i, the division by zero in line 6 is caught and the update magnitude will be set to zero in line 8.

4.1. EXPERIMENTAL SET-UP:

We tested all methods on three problems: a simple fully-connected neural network on the MNIST data set (LeCun et al., 1998) , as well as convolutional neural networks (CNNs) on the CIFAR-10 and CIFAR-100 data sets (Krizhevsky, 2009) . On CIFAR-10, we used a simple CNN with three convolutional layers, interspersed with max-pooling, and three fully-connected layers. On CIFAR-100 we used the AllCNN architecture of Springenberg et al. ( 2014) with a total of nine convolutional layers. A complete description of all network architectures has been moved to §A. While MNIST and CIFAR-10 are trained with a constant global step size (α), we used a fixed decreasing schedule for CIFAR-100, dividing by 10 after 40k and 50k steps (adopted from Springenberg et al., 2014) . We used a batch size of 128 on MNIST and 256 on the two CIFAR data sets.

Step sizes (initial step sizes in the case of CIFAR-100) were tuned for each method individually by first finding the maximal stable step size by trial and error, then searching downwards over two orders of magnitude (details in §A). We selected the one that yielded maximal overall test accuracy within the fixed number of training steps. Experiments with the best step size have been replicated ten times with different random seeds and all performance indicators are reported as mean plus/minus one standard deviation.

4.2. RESULTS:

Results are shown in Figure 3 . On MNIST, ADAM clearly outperforms M-SGD. Interestingly, there is only a very small difference in performance between the two sign-based methods, M-SSD and ADAM. Apparently, the advantage of ADAM over M-SGD on this problem is primarily due to the sign aspect. Going from M-SGD to M-SVAG, gives a considerable boost in performance, but M-SVAG is still outperformed by the two sign-based methods.

On CIFAR-10, the sign-based methods again have superior performance. Neither M-SSD nor M-SGD can benefit significantly from adding variance adaptation.

Finally, the situation is reversed on CIFAR-100, where M-SGD outperforms ADAM. It attains lower minimal loss values (both training and test) and converges faster. This is also reflected in the test accuracies, where M-SGD beats ADAM by almost 10 percentage points. Furthermore, ADAM is much less stable with significantly larger variance in performance. On this problem, variance adaptation has a small but significant positive effect for the sign-based methods as well as for M-SGD. When going from M-SGD to M-SVAG we gain some speed in the initial phase. The difference is later evened out by the manual learning rate decrease (which was necessary, for all methods, to train this architecture to satisfying performance).

5. DISCUSSION AND CONCLUSION:

We have argued that ADAM combines two aspects: taking signs and variance adaptation. Our separate analysis of both aspects provides some insight into the inner workings of this method. Taking the sign can be beneficial, but does not need to be. Our theoretical analysis suggests that it depends on the interplay of stochasticity, the conditioning of the problem, and its "axis-alignment".

Our experiments confirm that sign-based methods work well on some, but not all problems.

Variance adaptation can be applied to any stochastic update direction. In our experiments it was beneficial in all cases, but its effect can sometimes be minuscule. M-SVAG, a variance-adapted variant of momentum-SGD, is a useful addition to the practitioner's toolbox for problems where sign-based methods like ADAM fail. Its memory and computation cost are identical to ADAM and it has two hyper-parameters, the momentum constant µ and the global step size α. Our TensorFlow (Abadi et al., 2015) implementation of this method will be made available upon publication.

SUPPLEMENTARY MATERIAL A DESCRIPTION OF EXPERIMENTS:

A.1 NETWORK ARCHITECTURES MNIST We train a simple fully-connected neural network with three hidden layers of 1000, 500 and 100 units with ReLU activation. The output layer has 10 units with softmax activation. We use the cross-entropy loss function and apply L 2 -regularization on all weights, but not the biases. We use a batch size of 128. The global learning rate α stays constant.

CIFAR-10:

The CIFAR-10 data set consists of 32×32px RGB images with one of ten categorical labels. We train a convolutional neural network (CNN) with three convolutional layers (64 filters of size 5×5, 96 filters size 3×3, and 128 filters of size 3×3) interspersed with max-pooling over 3×3 areas with stride 2. Two fully-connected layers with 512 and 256 units follow. We use ReLU activation function for all layers. The output layer has 10 units for the 10 classes of CIFAR-10 with softmax activation. We use the cross-entropy loss function and apply L 2 -regularization on all weights, but not the biases. During training we perform some standard data augmentation operations (random cropping of sub-images, left-right mirroring, color distortion) on the input images. We use a batch size of 256. The global learning rate α stays constant.

CIFAR-100:

We use the AllCNN architecture of Springenberg et al. (2014) . It consists of seven convolutional layers, some of them with stride, and no pooling layers. The fully-connected layers are replaced with two layers of 1×1 convolutions with global spatial averaging in the end. ReLU activation function is used in all layers. Details can be found in the original paper. We use the cross-entropy loss function and apply L 2 -regularization on all weights, but not the biases. We used the same data augmentation operations as for CIFAR-10 and a batch size of 256. The global learning rate α is decreased by a factor of 10 after 40k and 50k steps.

A.2 LEARNING RATE TUNING:

Learning rates for each optimizer have been tuned by first finding the maximal stable learning rate by trial and error and then searching downwards over two orders of magnitude with learning rates 6 • 10 m , 3 • 10 m , and 1 • 10 m for order of magnitude m. We evaluated loss and accuracy on the full test set at a constant interval and selected the best-performing learning rate for each method in terms of maximally reached test accuracy. Using the best learning rate, we replicated the experiment ten times with different random seeds.

B MATHEMATICAL DETAILS B.1 DETAILS OF THE ANALYSIS ON STOCHASTIC QPS:

We derive the expressions for I(s) and I(g) in Eq. ( 12). We drop the fixed θ from the notation for readability. For SGD, we have

E[g] = ∇L and E[g T Qg] = ∇L T Q∇L + tr(Qcov[g]),

which is a general fact for quadratic forms of random variables. For the stochastic QP the gradient covariance is cov

[g] = ν 2 QQ, thus tr(Qcov[g]) = ν 2 tr(QQQ) = ν 2 i λ 3 i .

Plugging everything into Eq. ( 11) yields

EQUATION

For stochastic sign descent, we have E[s i ] = (2ρ i -1) sign(∇L i ) and thus

∇L T E[s] = d i=1 ∇L i E[s i ] = i (2ρ i -1)|∇L i |.

Regarding the denominator, it is Plugging everything into Eq. ( 11) yields

EQUATION

EQUATION

B.2 SUCCESS PROBABILITIES OF THE SIGN OF A STOCHASTIC GRADIENT:

We have stated in the main text that the sign of a stochastic gradient, s(θ) = sign(g(θ)), has success probabilities

EQUATION

under the assumption that g ∼ N (∇L, Σ). The following Lemma formally proves this statement and Figure 4 provides a pictorial illustration.

Lemma 2. If X ∼ N (µ, σ 2 ) then

EQUATION

)

Proof. The cumulative density function

(cdf) of X ∼ N (µ, σ 2 ) is P[X ≤ x] = Φ((x -µ)/σ),

where Φ(z) = 0.5(1 + erf(z/ √ 2)) is the cdf of the standard normal distribution. If µ < 0, then

EQUATION

)

If µ > 0, then

EQUATION

where the last step used the anti-symmetry of the error function. Variance adaptation factor (1 + η 2 ) -1 is the optimal variance adaptation factor for SGD (Eq. 16) . The optimal factor for the sign of a stochastic gradient is erf(( √ 2η) -1 ) under the Gaussian assumption (Eq. 15). It is closely approximated by (1 + η 2 ) -1/2 , which is the factor implicitly employed by ADAM (Eq. 6).

(1 + η 2 ) -1 erf[( √ 2η) -1 ] (1 + η 2 ) -1/2

B.3 DETAILS:

EQUATION

Setting the derivative w.r.t. γ i to zero, we find the optimal choice

EQUATION

Using E[sign(p i )] = (2ρ i -1) sign(p i ) and sign(•) 2 = 1, we get

E[ γ sign(p) -sign(p) 2 2 ] = d i=1 γ 2 i E[sign(p i ) 2 ] -2γ i sign(p i )E[sign(p i )] + sign(p i ) 2 = γ 2 i -2γ i (2ρ i -1) + 1 (29)

and easily find the optimal choice

EQUATION

by setting the derivative to zero.

See Figure 5 for a plot of the variance adaptation factors considered in this paper.

B.4 CONVERGENCE OF IDEALIZED STOCHASTIC VARIANCE-ADAPTED GRADIENT:

We proof the convergence results for idealized variance-adapted stochastic gradient descent. We have to clarify an aspect that we have glossed over in the main text. A stochastic optimizer generates a discrete stochastic process {θ t } t∈N0 . We denote as

E t [•] = E[•|θ 0 , . . . , θ t ] the conditional expectation given a realization of that process up to time step t. Recall that E[E t [•]] = E[•].

Proof of Theorem 1. Using the Lipschitz continuity of ∇f , we can bound f

EQUATION

Under review as a conference paper at ICLR 2018 Plugging in the definition

EQUATION

and simplifying, we get

EQUATION

Using Jensen's inequality4 

EQUATION

)

Due to strong convexity, we have ∇f t 2 ≥ 2µ(f tf * ) and can further bound

EQUATION

)

Inserting this in (33) and subtracting f * , we get

EQUATION

and, consequently, by total expectation

EQUATION

which we rewrite, using the shorthand e

EQUATION

)

To conclude the proof, we will show that this implies e t ∈ O( 1 t ). Without loss of generality, we assume e t+1 > 0 and get

EQUATION

where the second step is due to the simple fact that (1-x) -1 ≥ (1+x) for any x ∈ [0, 1). Summing this inequality over t = 0, . . . , T -1 yields e -1 T ≥ e -1 0 + T c and, thus,

EQUATION

which shows that e t ∈ O( 1 t ).

g t , we anyways make the assumption that all gradients in the effective time horizon of the moving average have the same mean and variance. We thus further approximate by replacing m t-s with m t and get

EQUATION

EQUATION

)

The two scalar factors lead to the correction term κ(µ, t) in Eq. ( 19).

When estimating the gradient variance from the mini-batch (Eq. 44), we can obtain an unbiased estimate of var[r t ] in Eq. ( 18) via

EQUATION

)

where ŝt is given by Eq. ( 44).

D VARIATIONS OF VARIANCE-ADAPTED METHODS:

Based on the considerations in Section 3, we examined three more variance-adapted methods. The first is a variation of M-SVAG which estimates stochastic gradient variances locally within the minibatch, as explained in §C.2. Pseudo-code can be found in Alg. 5. Furthermore, we tested a variant of ADAM that applies the correction factor from Eq. ( 19) to the estimate of the relative variance of the momentum term. We refer to this method as ADAM*. Two variants of ADAM* with the two variance estimates can be found in Algorithms 4 and 5.

Algorithm 3 M-SVAG-mb (with mini-batch variance estimates) Require: initial value θ 0 , step size α, momentum parameter µ ∈ [0, 1], number of steps T 1: Initialize m = 0, s = 0 2: for t = 1, . . . , T do 3:

Compute stochastic gradient g(θ) and variance estimate ŝ(θ) Eq. ( 44) 4:

Update aggregators m ← µm + g(θ), s ← µ 2 s + ŝ(θ)

5:

Compute relative variance estimate η 2 = s/m 2 6:

Compute variance adaptation factors γ = (1 + η 2 ) -1 7:

Update θ ← θα(γ m) 8: end for Algorithm 4 ADAM* (with exp. moving average variance estimates) Require: initial value θ 0 , step size α, momentum/averaging constant µ ∈ [0, 1], number of steps T 1: Initialize m = 0, v = 0 2: for t = 1, . . . , T do 3:

Compute stochastic gradient g = g(θ)

4:

Update moving averages m ← µm + (1µ)g, v ← µv + (1µ)g 2

Bias-correct m = (1µ t ) -1 m, v = (1µ t ) -1 ṽ 6:

Compute relative variance estimate η 2 = κ(µ, t) v-m 2 m 2

Eq. ( 19) We evaluated the variants on the two CIFAR test problems. Figure 6 shows a comparison of the two ADAM* variants with the original ADAM. Figure 7 compares the mini-batch variant of M-SVAG to the one with exponential moving averages. 

:

Notation: Divisions, squares, etc. on vectors are to be understood element-wise. denotes element-wise multiplication. We occasionally drop θ, writing g instead of g(θ), etc. We use the shorthands ∇Lt, gt, σ 2 t , etc. for sequences θt and double-indices, e.g. gt,i = g(θt)i, to denote vector elements.

For convenience, we define sign(x) = 1 for x ≥ 0 and sign(x) = -1, x < 0, for our theoretical considerations, but use sign(0) = 0 in practice. Application to vectors is to be understood element-wise.

Jensen's inequality says that i ciφ(xi) ≥ φ( i cixi) for a convex function φ and convex coefficients ci ≥ 0, i ci = 1. Here, we apply it to the convex function φ(x) = 1/x, x > 0, and coefficients ∇f 2 t,i / ∇ft 2 .

This is ADAM (β1 = β2 = µ, ε = 0), expect for the correction factor κ(µ, t) for the relative variance.

Figures and Tables:

E[∇ k (θ)] = ∇L(θ) and variances var[∇ k (θ)i] = M -1 M k =1 (∇ k (θ)i -∇L(θ)i) 2 .If the elements of B are drawn iid with replacement, the variance of g(θ) scales inversely with |B|: σ(θ)2 i := var[g(θ)i] = |B| -1 var[∇ k (θ)i].This holds approximately for sampling without replacement if |B| M .

Figure1: Conceptual sketch of variance adaptation, ignoring the sign aspect of ADAM. The left panel shows the true gradient ∇L = (2, 1) and stochastic gradients scattered around it with (σ 1 , σ 2 ) = (1, 1.5). In the right panel, we employ a variance adaptation (to be derived in §3.2) that scales the i-th coordinate by (1 + η 2 i ) -1 . In this example, the θ 2 -coordinate has much higher relative variance (η 2 2 = 2.25) than the θ 1 -coordinate (η 2 1 = 0.25) and is thus shortened. This reduces the variance of the update direction at the expense of biasing it away from the true gradient in expectation.

Figure2: Performance of SGD and SSD on 100-dimensional stochastic quadratic problems. Rows correspond to different QPs: the eigenspectrum is shown and each is used with a randomly rotated and an axis-aligned eigenbasis. Columns correspond to different noise levels. Horizontal axis is number of steps; vertical axis is log function value and is shared per row for comparability.

Figure 3: Experimental results on the three test problems. Plots display training and test loss over the number of steps. Curves for the different optimization methods are color-coded. The shaded area spans plus/minus one standard deviation, obtained from ten replications. The table below contains test accuracies evaluated after the last iteration.

Figure4: Probability density functions (pdf) of three Gaussian distributions, all with µ = 1, but different variances σ 2 = 0.5 (left), σ 2 = 1.0 (middle), σ 2 = 4.0 (right). The shaded area under the curve corresponds to the probability that a sample from the distribution has the opposite sign than its mean. For the Gaussian distribution, this probability is uniquely determined by the fraction σ/|µ|, as shown in Lemma 2.

Figure 5: Variance adaptation factors as functions of the relative standard deviation η.(1 + η 2 ) -1 is the optimal variance adaptation factor for SGD(Eq. 16). The optimal factor for the sign of a stochastic gradient is erf(( √ 2η) -1 ) under the Gaussian assumption (Eq. 15). It is closely approximated by (1 + η 2 ) -1/2 , which is the factor implicitly employed by ADAM (Eq. 6).

Figure 6: Comparison of the original ADAM algorithm to the variants in Algs. 4 and 5. Set-up of the plots as in Fig. 3. All three algorithms exhibit very similar performance on both problems.

Figure 7: Comparison of the two variants of the M-SVAG algorithm. Set-up of the plots as in Fig. 3. Both variants exhibit very similar performance on both problems.

The methods under consideration in this paper.

Table content: <table><tr><td/><td>Sign + Magnitude</td><td>Sign</td></tr><tr><td>Not Variance-Adapted</td><td>SGD</td><td>SSD</td></tr><tr><td/><td/><td>"Stochastic Sign Descent"</td></tr><tr><td>Variance-Adapted</td><td>SVAG</td><td>ADAM</td></tr></table>

Peer review (iclr2018):
 Summary: The paper is trying to improve Adam based on variance adaption with momentum. Two algorithms are proposed, M-SSD (Stochastic Sign Descent with Momentum) and M-SVAG (Stochastic Variance-Adapted Gradient with Momentum) to solve finite sum minimization problem. The convergence analysis is provided for SVAG for strongly convex case. Numerical experiments are provided for some standard neural network structures with three common datasets MNIST, CIFAR10 and CIFAR100 compared the performance of M-SSD and M-SVAG to two existing algorithms: SGD momentum and Adam. Comments: Page 4, line 5: You should define .nu clearly. Theorem 1: In the strongly convex case, assumption E ||g_t ||^2 .leq G^2 (if G is a constant) is too strong. In this case, G could be equal to infinity. If G is not infinity, you already assume that your algorithm converges, that is the reason why this assumption is not so good for strongly convex. If G is infinity (this is really possible for strongly convex), your proof would get a trouble as eq. (40) is not valid anymore. Also, to compute .gamma_{t,i}, it requires to compute .nabla f_{t,i}, which is full gradient. By doing this, the computational cost should add the dependence of M, which is very large as you mentioned in the introduction. According to your rate O(1/t), the complexity is worse than that of gradient descent and SGD as well. As I understand, there is no theoretical results for M-SSG and M-SVAG, but only the result for SVAG with exact .eta_i^2 in the strongly convex case. Also, theoretical results are not strong enough. Hence, the experiments need to make more convincingly, at least for some different complicated architecture of deep neural network. As I see, in some dataset, Adam performs better than M-SSD, some another dataset, Adam performs better than M-SVAG. Same situation for M-SGD. My question is that: When should we use M-SSD or M-SVAG? For a given dataset, why should we not use Adam or M-SGD (or other existing algorithms such as Adagrad, RMSprop), but your algorithms? You should do more experiments to various dataset and architectures to be more convincing since theoretical results are not strong enough. Would you think to try to use VGG or ResNet to ImageNet? I like the idea of the paper but I would love if the author(s) could improve more theoretical results to convince people. Otherwise, the results in this paper could not be considered as good enough. At this moment, I think the paper is still not ready for the publication. Minor comments: Page 2, in eq. (6): You should mention that “1” is a vector. Page 4, line 4: Q in R^{d} => Q in R^{d x d} Page 6, Theorem 1: You should define the finite sum optimization problem with f since you have not used it before. Page 6, Theorem 1: You should use another notation for “.mu”-strongly convex parameter since you have another “.mu”-momentum parameter in section 3.4 Page 4, Page 7: Be careful with the case when c = 0 (page 4) and mu = 1 (page 7-8) with dividing by 0.