Adaptive Learning Rate via Covariance Matrix Based Preconditioning for Deep Neural Networks

1 Introduction

Adaptive learning rate algorithms are widely used for the efficient training of deep neural networks. RMSProp [Tieleman and Hinton, 2012] and its follow-on methods [Zeiler, 2012; Kingma and Ba, 2014] are being used in many deep neural networks such as Convolutional Neural Networks (CNNs) [LeCun et al., 1998] since they can be easily implemented with high memory efficiency.

The empirical success of RMSProp could be explained by using Hessian-based preconditioning [Dauphin et al., 2015]. Hessian is the matrix that represents the curvature of the loss function; Hessian-based preconditioning locally changes the curvature of the loss function. When training deep neural networks, pathological curvatures such as saddle points [Dauphin et al., 2014] and cliffs [Pascanu et al., 2013] can slow the progress of first order gradient descent, such as Stochastic Gradient Descent (SGD) [Robbins and Monro, 1951]. Hessian-based preconditioning improves the condition of the curvature, and thus enhances SGD speed. However, SGD with Hessian-based preconditioning incurs high computation cost because it generally computes the inverse matrix of Hessian. Since RMSProp approximates Hessianbased preconditioning by using first order gradients [Dauphin et al., 2015], it achieves efficient training. In addition, RMSProp is easy to implement. Therefore, in terms of practical use, RMSProp and its variants such as AdaDelta [Zeiler, 2012] and Adam [Kingma and Ba, 2014] are still seen as the most powerful approach to training deep neural networks.

However, the first order gradients used in RMSProp include noise caused by stochastic optimization techniques such as mini-batch setting. With batch setting, since the model inputs are fixed in each iteration, only parameter updates change the gradients. On the other hand, with minibatch setting, since the inputs are not fixed in each iteration, gradients can also be changed by randomly selecting the inputs in each iteration. This change in the mini-batch setting can be seen as noise. Since RMSProp uses the noisy first order gradients to approximate Hessian-based preconditioning, the approximation may be inaccurate. This indicates that the efficiency of RMSProp can be improved by effectively handling the noise in the first order gradients.

This paper proposes a novel adaptive learning rate algorithm called SDProp. The key idea is to use covariance matrix based preconditioning instead of Hessian-based preconditioning. The covariance matrix is derived by assuming a distribution for the noise in the observed gradients. Since the distribution effectively captures the noise, SDProp can effectively capture the changes in gradients caused by random input selection in each iteration. Interestingly, our theoretical analysis reveals that SDProp uses the information of directions over past gradients in adapting the learning rate while RMSProp and its variants use the magnitudes of the gradients. In experiments, we compare SDProp with RMSProp. SDProp needs 50 % fewer training iterations than RMSProp to reach the final training loss for CNN in Cifar-10, Cifar-100 and MNIST datasets. In addition, SDProp outperforms Adam, a state-ofthe-art algorithm based on RMSProp, in several datasets. Our approach is also more effective than RMSProp for training Recurrent Neural Network (RNN) [Elman, 1990] and very deep fully-connected neural networks.

2 Preliminary

We briefly review the background of this paper. First, we describe SGD, which is a basic algorithm in stochastic optimization such as mini-batch setting. Second, we review RMSProp. Finally, we explain the relationship between Hessianbased preconditioning and RMSProp.

2.1 Stochastic Gradient Descent

Many learning algorithms aim at minimizing loss function f(θ) with respect to parameter vector, θ[Fujiwara et al., 2016a; 2016b]. SGD is a popular algorithm in the mini-batch setting. To minimize f(θ), SGD iteratively updates θ with a mini-batch of samples as follows:

where α is the learning rate, θi,t is the i-th element of the parameter vector at time t, xt-1 is the sample or mini-batch at time t - 1, and ∇f (θi,t-1; xt-1) is the first order gradient with respect to the i-th parameter given by xt-1. SGD applies Equation (1) to each sample or mini-batch while Gradient Descent (GD) applies Equation (1) to all data in the batch setting. Although ∇f (θi,t-1; xt-1) includes noise due to the random selection of mini-batch xt-1, SGD uses it in the training phase. Since SGD only uses a part of the data for computing ∇f (θi,t-1; xt-1), each iteration has reduced computation cost while memory efficiency is high.

2.2 RMSProp

RMSProp is a popular algorithm based on SGD for training neural networks. AdaDelta and Adam are follow-up methods of RMSProp. RMSProp rapidly reduces loss function f(θ) by adapting the learning rate of SGD. The updating rule of RMSProp is as follows:

where vi,t is the moving average of uncentered variance over past first order gradients ∇f (θi,t-1; xt-1), β is the decay rate for computing vi,t, and ϵ is the small value for the stable computation. Intuitively, RMSProp divides the learning rate, α, by magnitude √vi,t of the past first order gradients ∇f (θi,t-1; xt-1). Therefore, if the i-th parameter has large ∇f (θi,t-1; xt-1) values in terms of the magnitude in the past, RMSProp yields a small learning rate because √vi,t in Equation (3) is large. Empirically, this idea efficiently reduces the loss function for deep neural networks. Follow-up methods such as AdaDelta and Adam are based on this idea. For the convex optimization, regret analysis can be used to explain the efficiency of the methods [Kingma and Ba, 2014]. For non-convex optimization such as deep neural networks, the empirical success of RMSProp could be explained by using Hessian-based preconditioning. We briefly review the relationship between Hessian-based preconditioning and RMSProp by following [Dauphin et al., 2015] in the next section.

2.3 Hessian-based Preconditioning

Some kind of pathological curvature of the loss function slows the progress of SGD [Dauphin et al., 2014]. Therefore, it is important to capture the curvature in order to efficiently train deep neural networks.

Hessian-based preconditioning locally changes the function by using Hessian H, which can capture the curvature of the function. Hessian is the square matrix of the second order gradients of function f(θ) represented by H=∇2 f(θ). The condition number of Hessian estimates the extent to which the curvature is pathological. Condition number is defined as σmax(H)/σmin(H) where σmax(H) and σmin(H) are the largest and smallest singular values of H, respectively. The function has less pathological curvature if the condition number has a small value. This is because the function equally curves if it has small condition number. Therefore, we can increase the efficiency of the training by reducing the Hessian condition number [Dauphin et al., 2015].

Hessian-based preconditioning locally transforms an original parameter into another parameter so that the Hessian has small condition number. Preconditioning matrix D gives transformations such as ˆ θ=D1/2 θ where ˆ θ is the transformed parameter. By using ˆ θ, function f is transformed into function ˆ f where f(θ)=f(D-1/2ˆ θ)= ˆ f(ˆ θ). If ˆ f(ˆ θ) has smaller condition number than f(θ), we can efficiently train a model by applying first order gradient descent to ˆ θ. The updating rule of ˆ θ is ˆ θt=ˆ θt-1-α∇ ˆ f(ˆ θ). Since ∇ˆ f(ˆ θ)=D-1/2∇f (θ), we have the following form for original parameter θ:

If ˆH is the Hessian of transformed function ˆ f(ˆ θ), ˆH is given as ˆH=(D-1/2 )THD-1/2 . When D1/2 =H1/2 , ˆH has a smaller condition number because ˆH is an identity matrix. In this case, Equation (4) corresponds the Newton method. However, H1/2 exists only when H is positive-semidefinite. Since deep neural networks have many saddle points where Hessian can be indefinite [Dauphin et al., 2014], the Newton method is unsuitable for training deep neural networks. On the other hand, the diagonal equilibration matrix of D= √diag (H2 ) works well even if H is indefinite [Dauphin et al., 2015]. This indicates that GD can efficiently escape from saddle points by preconditioning based on the diagonal equilibration matrix.

In RMSProp, the role of √vi,t in Equation (3) could be explained by using Hessian-based preconditioning [Dauphin et al., 2015]. A comparison of Equation (4) to Equation (3) indicates that √vi,t corresponds to the i-th element of the diagonal preconditioning matrix. In addition, empirical results suggest that √vi,t approximates the i-th element of the diagonal equilibration matrix which can be used to efficiently train deep neural networks [Dauphin et al., 2015]. Thus, RMSProp can be interpreted as Hessian-based preconditioning using an approximated diagonal equilibration matrix in the mini-bath setting. Therefore, since RMSProp is more efficient in escaping from saddle points than SGD, RMSProp and its follow-up methods achieve high efficiency.

3 ProposedMethod

We first introduce the novel preconditioning idea. Then, we derive SDProp based on this idea.

3.1 Idea

RMSProp approximates Hessian-based preconditioning by using the first order gradients ∇f (θi,t-1; xt-1) as described in the preliminary section. However, in stochastic optimization approaches such as mini-batch setting, the first order gradients ∇f (θi,t-1; xt-1) include noise because input xt-1 is randomly selected in each iteration. Since the first order gradients ∇f (θi,t-1; xt-1) in Equation (2) and the square roots of the uncentered variances √vi,t in Equation (3) contain noise, it is difficult to effectively approximate Hessian-based preconditioning. In order to effectively handle the noise, we replace Hessian-based preconditioning with covariance matrix based preconditioning.

In covariance matrix based preconditioning, we assume that the first order gradients ∇f (θi,t-1; xt-1) follow a Gaussian distribution. This is because the field of probabilistic modeling uses Gaussian distributions to model the noise of observations[Sra et al., 2012; Ida et al., 2013; Fukuda et al., 2014; Miyashita et al., 2013]. By following [Sra et al., 2012], we assume the following Gaussian distribution of first order gradient ˆ gt = ∇f (θt-1; xt-1) ∈ Rd :

where ¯ gt ∈ Rd is the true gradient without the noise while ˆ gt ∈ Rd includes the noise. N(¯ gt, Ct) is a Gaussian distribution with mean ¯ gt and covariance matrix Ct; Ct is the covariance matrix of ˆ gt whose size is d×d. The diagonal elements in Ct represent the magnitude of oscillation of the first order gradients ˆ gt that include the noise. Specifically, let Ct[i, j] be the i-th row and the j-th column element in Ct, Ct[i, j] represents the covariance of the i-th and the j-th first order gradient. Therefore, if the i-th first order gradient strongly correlates with the j-th first order gradient, Ct[i, j] has large absolute value. On the other hand, Ct[i, i] represents the variance of the i-th first order gradient. Therefore, Ct[i, i] has large value if the first order gradient strongly oscillates in the i-th dimension.

Intuitively, large oscillations in i-th dimension incur high variance of updating directions and inefficient progress in plain SGD. However, it is difficult to reduce the oscillation since it can be a result of the noise induced by the mini-batch setting. How can we reduce the oscillation by using Ct ? This is the motivation behind our approach; plain SGD efficiently progresses if we can control the oscillation by utilizing Ct. In this paper, we propose the preconditioning of Ct to control the oscillation. While Hessian-based preconditioning reduces the condition number of Hessian, our preconditioning reduces the condition number of Ct by transforming Ct into an identity matrix. We describe our approach in the next section.

3.2 Covariance Matrix Based Preconditioning

The previous section suggests that large values in the diagonal of Ct prevent the efficient progress of SGD. Therefore, if we could control the values in the diagonal of Ct, we improve the efficiency of SGD. Our covariance matrix based preconditioning transforms Ct into ρ2 I where I is an identity matrix whose size is d×d and ρ is a hyper-parameter that has a positive value. Since the element in the diagonal of Ct represents the variance of first order gradient, we can hold the variance to constant value ρ2 . If the variance is larger than ρ2 , its value is reduced to ρ2 . Therefore, SGD efficiently progresses if we transformCt into ρ2 I.

We first describe the approach used to transform Ct into I instead of ρ2 I. This is because once Ct is transformed into I, it is easy to transform I into ρ2 I as we describe later. Hessian-based preconditioning transforms first order gradients to yield ∇ˆ f(ˆ θ)=D-1/2∇f(θ) where D is a preconditioning matrix. The preconditioning matrix of D1/2 = H1/2 reduces the condition number of Hessian H as described in the preliminary section. Unlike the previous approach, we execute the preconditioning of Ct and so use the transformation gp=D-1 ˆ gt. In this transformation, gp is a transformed first order gradient and ˆ gt is a first order gradient as defined in Equation (5). Since the transformation is an affine transformation of ˆ gt generated from the Gaussian distribution in Equation (5), we have following distribution of gp:

In Equation (6), we use the following major rule to transform Equation (5) into (6): if X∼N(m,Σ) and Y =AX, then Y ∼N(Am, AΣAT ); N(m, Σ) is a Gaussian distribution that has mean m and covariance matrix Σ, A is a matrix for affine transformation and Y is a transformed variable. By setting D=C 1/2 t in Equation (6), we have the following property :

Theorem 1. If we transform first order gradient ˆ gt to yield gp=C -1/2 t ˆ gt, we have the following Gaussian distribution:

where I is an identity matrix whose size is d×d.

Proof. By using eigen decomposition, we can represent Ct as Ct = UΣU T where U is an orthogonal matrix of d × d and Σ is a diagonal matrix of (λ1, λ2, ..., λd). Since Ct is assumed to be a positive semi-definite matrix, all eigen values are equal to or higher than 0. Thus, C 1/2 t can be computed as C 1/2 t =UΣ1/2U T. By setting the covariance term of Equation (6) to D-1=(C 1/2 t )-1=UΣ-1/2U T, the Gaussian distribution of gp is represented as follows:

In the above formulations, since U is an orthogonal matrix, we use UU T = I and (UΣ-1/2U T)T =UΣ-1/2U T. As a result, we have the distribution of Equation (7).

The above theorem indicates that the transformation of gp = C -1/2 t ˆ g results in the Gaussian distribution of gp whose covariance matrix is identity matrix I. In other words, we can control the covariance matrix to be I by using gp instead of ˆ g.

Our preconditioning transforms the value of variance for first order gradients into 1 by using gp. However, gp may have an extremely large value if the variance is 1. Thus, we introduce hyper-parameter ρ to generalize our preconditioning. Specifically, by using the transformation of gp=ρC -1/2 t ˆ g instead of gp=C -1/2 t ˆ g, we have the following distribution:

The above equation denotes that ρ controls the value of the covariance matrix while the previous transformation only gives an identity matrix as shown in Equation (7). We show that ρ has the same role as learning rate α when we derive SDProp in the next section.

Since we compute the first order gradients at each time t in SGD, we have to incrementally compute the covariance matrix Ct although Theorem 1 is based on the property that Ct is a positive semi-definite matrix. In order to incrementally compute Ct as a positive semi-definite matrix, we use the online updating rule of [Sra et al., 2012] as follows:

where µt is the moving average of ˆ gt and γ is the hyperparameter of the decay rate for the moving average that has γ ∈ [0, 1). Ct and µt are initialized as µ1 = ˆ g1 and C1 = 0. The above updating rule gives the following property:

Theorem 2. If we compute covariance matrix Ct by using Equations (9) and (10), Ct is positive semi-definite.

Proof. In order to prove Theorem 2, we first prove that (ˆ gt - µt-1)(ˆ gt-µt-1)T in Equation (9) is a positive semi-definite matrix. By setting y = xT(ˆ gt-µt-1), we have:

By following the definition of positive semi-definite matrixes, if we have matrix A of d × d such that xTAx ≥ 0 holds for every non-zero column vector x of d real numbers, A is a positive semi-definite matrix. Since the above inequation shows that xT(ˆ gt-µt-1)(ˆ gt-µt-1)Tx ≥ 0 holds, it is clear that (ˆ gt-µt-1)(ˆ gt-µt-1)T is a positive semi-definite matrix even if µt-1 in Equation (10) has any real value.

Then, we prove that Ct in Equation (9) is a positive semidefinite matrix by mathematical induction.

Initial step: If t=1, the initialization yields C1=0. Since C2 is computed as C2 =γ(1 - γ)(ˆ g2 - µ1)(ˆ g2 - µ1)T by using Equation (9) and (10), C2 is a positive semi-definite matrix. This is because (ˆ gt - µt-1)(ˆ gt-µt-1)T is a positive semidefinite matrix as proved above.

Inductive step: We assume that Ct-1 is a positive semidefinite matrix. Since Ct is computed as Ct =γCt-1 +γ(1γ)(ˆ gt - µt-1)(ˆ gt - µt-1)T by using Equations (9) and (10), xTCtx is represented as follows:

In the above equation, xTCt-1x ≥ 0 and xT(ˆ gt-µt-1)(ˆ gtµt-1)Tx ≥ 0 because Ct-1 and (ˆ gt-µt-1)(ˆ gt-µt-1)T are positive semi-definite matrices. Therefore, Ct is a positive semi-definite matrix because xTCtx ≥ 0 holds in the above equation. This completes the inductive step.

Thus, if we compute Ct by using Equations (9) and (10), we can execute the preconditioning specified by Theorem 1.

Note that Hessian-based preconditioning cannot control the oscillation of first order gradients. This is because its transformation results in the distribution of N(H- 12 ¯ gt, H- 12 Ct(H- 1 2 )T) where the covariance matrix is uncontrollable. In addition, since Hessian H may not be a positive semi-definite matrix, it is difficult to compute H-1/2 . Therefore, our covariance matrix based preconditioning inherently differs from Hessian-based preconditioning. Our idea of preconditioning Ct is more suitable than Hessianbased preconditioning in handling the oscillation triggered by the noise of first order gradients.

3.3 Algorithm

Since deep neural networks have a large number of parameters, the idea described in the previous section incurs large memory consumption of O(d2 ) where d is the number of parameters. In addition, it costs O(d3 ) time to compute D=C 1/2 t by using eigenvalue decomposition [Halko et al., 2011]. To avoid these problems, we employ diagonal preconditioning matrix D=diag(Ct)1/2 . Since this approach only needs the diagonal terms, the memory and computation costs are O(d). Although this approach ignores the correlation of first order gradients, it is sufficient to control the oscillation in each dimension. This is because the diagonal of Ct represents the variance of the oscillation as described in the previous section. By picking the diagonal of Equation (8), the updating rule is:

We rewrite this updating rule (all steps) as follows:

where µi,t is the moving average of first order gradients for the i-th parameter at time t and γ is the hyper-parameter of the decay rate for the moving average that has γ ∈ [0, 1). c2i,t is the exponentially moving variance of first order gradients for the i-th parameter at time t. We use γ in Equation (13) as the decay rate of the exponentially moving variance. µi,t and c2i,t are initialized as µi,1=∇f (θi,0; x0) and c2i,1=0, respectively. For stable computation, ϵ is set at a small positive value. Equation (14) corresponds to Equation (11). We call the algorithm SDProp because Equation (14) includes Standard Deviation √c2i,t . Although ci,t includes the bias imposed by initialization, we can remove the bias in the same way as [Kingma and Ba, 2014].

Notice that ρ takes the same role as learning rate α in Equation (3) of RMSProp. Therefore, Equation (14) divides the learning rate by the square root of centered variance c2i,t while Equation (3) of RMSProp divides the learning rate by the square root of uncentered variance v2 i,t . In other words, RMSProp and its follow-up methods such as Adam adapt the learning rate by the magnitude of gradients while we adapt it by the variance of gradients. Although RMSProp and SDProp have similar updating rules, they have totally different goals as described in the previous sections. RMSProp executes Hessian-based preconditioning while SDProp executes covariance matrix based preconditioning.

4 Experiments

We performed experiments to compare SDProp to RMSProp and Adam, a state-of-the-art algorithm based on RMSProp. [Kingma and Ba, 2014] shows that Adam is a more efficient and effective approach than RMSProp or AdaDelta by integrating momentum into RMSProp. First, we show the efficiency and effectiveness of our approach by using CNN.

Second, since SDProp effectively handles the oscillation described in the previous section, we evaluate SDProp by using small mini-batches which suffer noise in the first order gradients. Third, we show the efficiency and effectiveness of SDProp for RNN. Fourth, we demonstrate the effectiveness of SDProp for 20 layered fully-connected neural network that is difficult to train due to many sadle points.

4.1 Efficiency and Effectiveness for CNN

We investigate the efficiency and effectiveness of SDProp. We used 4 datasets to assess the classification of images; Cifar-10, Cifar-100 [Krizhevsky and Hinton, 2009], SVHN [Sermanet et al., 2012] and MNIST. The experiments were conducted on a 7-layered CNN with ReLU activation function. The loss function was negative log likelihood. We compared SDProp to RMSProp and Adam. In SDProp, we tried various combinations of hyper-parameters by using γ ∈ {0.9, 0.99} and ρ∈{0.1, 0.01, 0.001}. In RMSProp, we tried combinations of hyper-parameters by using β ∈ {0.9, 0.99} and α∈{0.1, 0.01, 0.001}. As a result, SDProp achieves the lowest loss in the settings of γ = 0.99, ρ = 0.001. RMSProp has the lowest loss when β = 0.99 and α = 0.001. Adam achieves the lowest loss when β1 = 0.9, β1 = 0.999 and α = 0.001. The mini-batch size was 128. The number of epochs was 50. We use the training loss to evaluate the algorithms because they optimize the training criterion.

Figure 1 shows the training losses of each dataset. In Cifar10, Cifar-100 and SVHN, SDProp yielded lower losses than RMSProp and Adam in early epochs. In MNIST, although the training loss of SDProp and Adam nearly reached 0.0, SDProp reduces the loss faster than Adam. SDProp needs 50 % fewer training iterations than RMSProp to reach its final training loss in Cifar-10, Cifar-100 and MNIST. This suggests that our idea of covariance matrix based preconditioning is more efficient and effective than Hessian-based preconditioning in the mini-batch setting because RMSProp and Adam approximate Hessian-based preconditioning as described in the preliminary section. Since SDProp captures the noise, it effectively reduces the loss even if the gradients are noisy. In the next experiment, we investigate the performance of SDProp in terms of its effectiveness against noise by using noisy first order gradients.

4.2 Sensitivity of Mini-batch Size

The previous experimental results show that SDProp is more efficient and effective than existing methods because it well handles the noise in our idea and in practice. In other words, SDProp is expected to effectively train the model even if we use small mini-batch sizes that incur noisy first order gradients [Dekel et al., 2012]. Therefore, we investigated the sensitivity of SDProp and existing methods to mini-batch size. While the main purpose of this experiment is to reveal the one performance attribute of SDProp, the result suggests that SDProp can be used on devices with scant memory that must use small mini-batches.

We compared SDProp to RMSProp and Adam using minibatch sizes of 16, 32, 64 and 128. We used the Cifar-10 dataset for the 10-class image classification task. We used CNN as per the previous section. The hyper-parameters are also the same as the previous section; they are tuned by grid search. The number of epochs was 50.

Table 1 shows the final training accuracies. SDProp outperforms RMSProp and Adam in all mini-batch size values examined. Specifically, although small mini-batch size of 16 incurs very noisy first order gradients, SDProp obviously achieves effective training unlike RMSProp and Adam. In addition, Table 1 shows that the superiority of our approach over RMSProp and Adam increases as mini-batch size falls. For example, if the mini-batch size is 16, our approach has 8.75 percent higher accuracy than RMSProp and 2.24 percent more accurate if the mini-batch size is 128. This indicates that our covariance matrix based preconditioning effectively handles the noise of first order gradients.

4.3 Efficiency and Effectiveness for RNN

We evaluated the efficiency and effectiveness of SDProp for the Recurrent Neural Network (RNN). In this experiment, we predicted the next character by using previous characters via character-level RNN. We used the subset of shakespeare dataset and the source code of the linux kernel as the dataset [Karpathy et al., 2015]. The size of the internal state was 128. The pre-processing of the dataset followed that of [Karpathy et al., 2015]. The mini-batch size was 128. In SDProp, we tried grid search with ρ ∈ {0.1, 0.01, 0.001} and γ ∈ {0.9, 0.99}. As a result, SDProp used the settings of ρ = 0.01 and γ = 0.99. In RMSProp, we tried grid search with α ∈ {0.1, 0.01, 0.001} and β ∈ {0.9, 0.99}. Finally, we used the settings of α = 0.01 and β = 0.99 for RMSProp. The training criterion was cross entropy. We used gradient clipping and learning rate decay. Gradient clipping is a popular approach for scaling down the gradients by manually setting a threshold; it prevents gradients from exploding in RNN training [Pascanu et al., 2013]. We set the threshold to 5.0. We decayed the learning rate α every tenth epoch by the factor of 0.97 for RMSProp following [Karpathy et al., 2015]. In SDProp, ρ was also decayed the same as α of RMSProp.

Figure 2 shows the results of the shakespeare dataset and the source code of the linux kernel. SDProp reduces the training loss faster than RMSProp. Since SDProp effectively handles the noise induced by the mini-batch setting, it can efficiently train models other than CNN, such as RNN.

4.4 20 Layered Fully-connected Neural Network

In this section, we performed experiments to evaluate the effectiveness of SDProp for training deep fully-connected neural networks. [Dauphin et al., 2014] suggests that the number of saddle points exponentially increases with the dimensions of the parameters. Since deep fully-connected networks typically have parameters with higher dimension than other models such as CNN, this optimization problem has many saddle points. This problem is challenging because SGD slowly progresses around saddle points [Dauphin et al., 2014].

We used a very deep fully-connected network with 20 hidden layers, 50 hidden units and ReLU activation functions. We used the MNIST dataset for the 10-class image classification task. This setting is the same as [Neelakantan et al., 2015] used in evaluating the effectiveness of SGD with high dimensional parameters. Note that MNIST is sufficient for our evaluation because, unlike CNN, fully-connected networks do not saturate the accuracy in our experiment. Our purpose is to evaluate the effectiveness under the setting of very high dimensional parameter. Thus, it is sufficient to evaluate effectiveness if the accuracy is not saturated. The training criterion was negative log likelihood. The mini-batch size was 128. We initialized parameters from a Gaussian with mean 0 and standard deviation 0.01 following [Neelakantan et al., 2015]. We compared SDProp to RMSProp. In SDProp, we tried the combinations of hyper-parameters by using γ ∈ {0.9, 0.99} and ρ ∈ {0.1, 0.01, 0.001}. In RMSProp, we tried the combinations of hyper-parameters by using β ∈ {0.9, 0.99} and α ∈ {0.1, 0.01, 0.001}. The number of epochs was 50. Although these algorithms are trapped around saddle points, its frequency may depend the initialization of parameter. Therefore, we tried 10 runs for each of the above settings.

Table 2 lists the results for the best setting of α and ρ. It shows averages, best, worst of training accuracies for each setting. The result shows that SDProp achieves higher accuracy than RMSProp for the best setting. In addition, the difference between best and worst accuracy of SDProp is smaller than RMSProp. Since SDProp effectively handles the randomness of noise, it can reduce result uncertainty. The results show that SDProp effectively trains models that have very high dimensional parameters.

5 Conclusion

We proposed SDProp for the effective and efficient training of deep neural networks. Our approach utilizes the idea of using covariance matrix based preconditioning to effectively handle the noise present in the first order gradients. Our experiments showed that, for various datasets and models, SDProp is more efficient and effective than existing methods. In addition, SDProp achieved high accuracy even if the first order gradients were noisy.