Title: PREDICTIVE LOCAL SMOOTHNESS FOR STOCHASTIC GRADIENT METHODS

Abstract: Stochastic gradient methods are dominant in nonconvex optimization especially for deep models but have low asymptotical convergence due to the fixed smoothness.
To address this problem, we propose a simple yet effective method for improving stochastic gradient methods named predictive local smoothness (PLS). First, we create a convergence condition to build a learning rate which varies adaptively with local smoothness. Second, the local smoothness can be predicted by the latest gradients. Third, we use the adaptive learning rate to update the stochastic gradients for exploring linear convergence rates. By applying the PLS method, we implement new variants of three popular algorithms: PLS-stochastic gradient descent (PLS-SGD), PLS-accelerated SGD (PLS-AccSGD), and PLS-AMSGrad. Moreover, we provide much simpler proofs to ensure their linear convergence. Empirical results show that the variants have better performance gains than the popular algorithms, such as, faster convergence and alleviating explosion and vanish of gradients.

1. INTRODUCTION:

In this paper, we consider the following nonconvex optimization:

EQUATION

where x is the model parameter, and neither f nor the individual f i (i ∈ [n]) are convex, such as, deep models. Stochastic gradient descent (SGD) is one of the most popular algorithms for minimizing the loss function in equation 1. It iteratively updates the parameter by using the product of a learning rate and the negative gradient of the loss, which is computed on a minibatch drawn randomly from training set. Unfortunately, small learning rate makes SGD painfully slow to converge, and high learning rate causes SGD to diverge. Therefore, choosing a proper learning rate (or step size) becomes a challenge.

A popular adaptive method adjusts automatically the learning rate by using some forms of the past gradients to scale coordinates of the gradient. For example, AdaGrad Duchi et al. (2011) is the first adaptive algorithm to update the sparse gradients by dividing positive square root of averaging the squared past gradients, and its several variants (e.g., Adadelta Zeiler (2012), RMSProp Tieleman & Hinton (2012), Adam Kingma & Ba (2015) , Nadam Dozat (2016) , and AMSGrad Reddi & Kumar (2018) ) have been widely and successfully applied into train deep models. Specifically, they use the exponential moving averages of squared past gradients to manage the rapidly decayed learning rate.

Most of these algorithms are to establish their convergence guarantees based on a maximum of the Lipschitz constant L, which governs smoothness of the loss function in whole parameter space, often called L-smoothness Bottou et al. (2016) ; Reddi et al. (2016) .

However, the maximum of the L-smoothness results in a small learning rate as it is inversely proportional to L1 Bottou et al. (2016) . Since the L-smoothness changes with the parameter and the given data, it leads to a local smoothness of the loss function near the optimum for selecting the learning rate. Specifically, the local smoothness is often computed by the the Hessian matrix ∇ 2 f (x), such as data dependent local smoothness (e.g., local SVRG Vainsencher et al. (2015) ) and parameter dependent local smoothness (e.g., Newton method Nocedal & Wright. (2006) ). Unfortunately, the Hessian matrix results in a high computational cost and a high memory requirement. Recently, Stochastic Quasi-Newton (SQN) Byrd et al. (2016) and Adaptive Quasi-Newton (adaQN) Keskar & Berahas (2016a) are to partly reduce the expensive cost by using the Hessian-vector product Nocedal & Wright. (2006) . However, these algorithms are still difficult to train a large number of the parameters of deep models due to the loop computation of the Hessian-vector product.

To address the above problem, we exploit a simple yet effective method to predict the parameter dependent local smoothness for the adaptive learning rate. To ensure the convergence of the stochastic algorithms, an ideal local smoothness L(x t ) of the loss function is based on an ideal neighborhood N rx t (x * ) of an equilibrium x * with a radius x t -x * by using the current parameter x t . However, it is difficult to apply the N rx t (x * ) into the stochastic algorithms due to the unknown equilibrium x * . Since the past parameter x t-1 has been known, we consider a local smoothness L(x t ) on a neighborhood

N rx t-1 (x t ) of x t with a radius x t -x t-1 . Because N rx t (x * ) and N rx t-1 (x t ) have a common point x t or region, L(x t ) is naturally used instead of L(x t ).

Based on the definition of the L-smoothness (or Lipschitz continuous gradients) Bottou et al. (2016) , L(x t ) on this neighborhood is easily predicted by using the past gradient ∇f (x t-1 ) and the current gradient ∇f

(x t ), that is, L(x t ) = ∇f (xt)-∇f (xt-1) 2 xt-xt-1 2

. Obviously, it only needs to storage the past parameter x t-1 and gradient ∇f (x t-1 ), and perform twice subtractions and norm computations. This paper, therefore, provides a local smoothness strategy to study the adaptive learning rate. In this strategy there are two important problems that how to easily build a direct functional relationship between the learning rate and the local smoothness, and how to calculate the local smoothness. To address these problems, the stochastic gradient algorithms are transformed into a linear dynamical system Lessard et al. (2016) ; Hu et al. (2017) by using the local smoothness to linearize the gradient function. The functional relationship is obtained by constructing the convergence condition for the linear dynamical system. Based on the above discussion, the local smoothness is simply predicted by using the current gradient and the latest gradient. Overall, our main contributions are summarized as

• We propose a predictive local smoothness (PLS) method to adjust automatically learning rate for stochastic gradient algorithms. Our PLS method will lead these algorithms to drive a loss function to fast converge to a local minimum.

• We apply PLS into SGD, SQN Byrd et al. (2016) , AMSGrad Reddi & Kumar (2018) and AccSGD Kidambi et al. (2018) . Correspondingly, we establish four PLS-SGD, PSL-SQN, PLS-AMSGrad and PLS-AccSGD algorithms, and provide corresponding theoretical conditions to ensure their linear convergence.

• We also provide an important empirical result that PLS can alleviate the exploding and vanishing gradients in the classical algorithms (e.g., SGD, AMSGrad Reddi & Kumar (2018) and AccSGD Kidambi et al. (2018) ) for training deep model with least squares regression.

Note that due to the limited space PLS-AccSGD is provided in subsection 6.1 in Supplementary Material. We do not provide PSL-SQN since it is similar to PLS-SGD. But, we empirically verify that PSL-SQN is faster than SQN in the subsection 4.1.

2. PRELIMINARIES:

In this section, we introduce some notations, local smoothness assumption, and three popular stochastic gradient algorithms: SGD, SQN Byrd et al. (2016) , AMSGrad Reddi & Kumar (2018) , and AccSGD Kidambi et al. (2018) .

Notation. ∇f (x) denotes exact gradient of f at x, while ∇f it (x) denotes a stochastic gradient of f , where i t is sampled uniformly at random from [1, • • • , n] and n is the number of samples. Since i t is sampled in an independent and identically distributed (IID) manner from {1, • • • , n}, the expectation of smoothness

L it (x t ) is denoted as L(x t ) = E [L it (x t )] = 1 n n i=1 L i (x t ).

A 1 or 2 -norm of a vector x is denoted as x , and its square is x 2 . A positive-definite matrix A is denoted as A 0. The Kronecker product of matrices A and B is denoted as A ⊗ B. We denote a d × d identity matrix by I d . A neighborhood of a point x 1 ∈ R d with radius r x2 is denoted as

N rx 2 (x 1 ) = {y ∈ R d | x 1 -y < r x2 = x 1 -x 2 }. Assumption 1. We say f is local smoothness on a set C ⊂ R d if there is a constant L such that ∇f (x) -∇f (y) ≤ L x -y , for ∀ x, y ∈ C.

(2) Assumption 1 is an essential foundation for convergence guarantees of most stochastic gradient methods as the gradient of f is controlled by L with respect to the parameter vector.

SGD. Stochastic Gradient Descent (SGD) simply computes the gradient of the parameters by uniformly randomly choosing a single or a few training examples. Its update is given by

EQUATION

where η t is the learning rate. η t is usually set to a decay form η 0 / √ t in practice. This setting leads to slower convergence. Moreover, the gradient of the loss of a deep model with rectified linear units (ReLU) Nair & Hinton (2010) often explodes when large initialization η 0 .

SQN. Stochastic Quasi-Newton (SQN) Byrd et al. (2016) employs iterations of the form

EQUATION

where

H t+1 = (I -ρ k s k y T k )H t (I -ρ k y k s T k ) + ρ k s k s T k with s k = x t -x t-1 , y k = ∇f it (x t ) - ∇f it-1 (x t-1 ) and ρ k = y T k s k .

In practice, the quasi-Newton matrix H t+1 is not formed explicitly, and is computed by the Hessian-vector product Nocedal & Wright. (2006) .

AMSGrad. AMSGrad Reddi & Kumar (2018) is an exponential moving average variant of the popular Adam algorithm Kingma & Ba (2015) in the scale gradient method. AMSGrad uses the factors β 1t = β 1 /t and β 2 to exponentially move the momentums of the gradient and the squared gradient, respectively. β 1t = β 1 = 0.9 and β 2 = 0.999 are typically recommended in practice. The key update is described as follows:

     m t+1 = β 1t m t + (1 -β 1t )∇f it (x t ), v t+1 = β 2 v t + (1 -β 2 ) (∇f it (x t )) 2 , v t+1 = max{v t+1 , v t }, x t+1 = x t -η t mt+1 √ vt+1 .

(5) AccSGD. Accelerated SGD (AccSGD) proposed in Jain et al. (2017) is much better than SGD, HB Polyak (1964) and NAG Nesterov (1983) in the momentum method. An intuitive version of AccSGD is presented in Kidambi et al. (2018) . Particularly, AccSGD takes three parameters: learning rate η t , long learning rate parameter κ ≥ 1, statistical advantage parameter ξ ≤ √ κ, and α = 1 -0.7 2 ξ/κ. This update can alternatively be stated by:

EQUATION

3. PREDICTIVE LOCAL SMOOTHNESS:

The popular adaptive learning rate methods are based on using gradient updates scaled by square roots of exponential moving averages of squared past gradients Reddi & Kumar (2018) . These methods indirectly adjust the learning rate as they can be essentially viewed as gradient normalization. In this section, we study the local smoothness to directly and adaptively adjust the learning rate, propose a predictive local smoothness (PLS) method, and apply this method into SGD, AMSGrad Reddi & Kumar (2018) , and AccSGD Kidambi et al. (2018) . Before showing our PLS method, we first give two local smoothness sequences definition.

Definition 1. Let x * be an equilibrium of the local minimum f (x * ) and {x t } t≥0 be a updating parameter procedure, where x 0 is an initial point. A corresponding neighborhood sequence of x * is denoted by

EQUATION

This definition reveals that L(x t ) governs the ideal local smoothness between the equilibrium x * and x t to strictly ensure the convergence of the updating parameter procedure. However, L(x t ) cannot be computed due to the unknown x * . Clearly, L(x t ) is easily calculated by using x t and x t-1 .

Procedure PLS • Build the learning rate η = η(L(x t )) by linearizing ∇f (x t ). PLS is an adaptive learning rate method based on the local smoothness. The local smoothness varies based on the updating parameters {x t } t≥0 in stochastic gradient algorithms. According to the definition 1, the local smoothness sequence {L(x t )} t≥0 are ideally used to adjust the learning rate in the neighborhood sequence {N rx t (x * )} t≥0 . However, it is difficult to compute {L(x t )} t≥0 because of the unknown x * . Since there is a common point sequence on {x t } t≥1 in both {N rx t-1 (x t )} t≥1 and {N rx t (x * )} t≥0 , {L(x t )} t≥1 can be predicted by {L(x t )} t≥1 , which is easily computed by using the current gradient and the latest gradient. In this paper, our key idea is to use the predictive local smoothness sequence {L(x t )} t≥1 instead of the unknown {L(x t )} t≥0 to adjust automatically the learning rate η t . PLS is described as the following three steps.

• Predict the local smoothness L(x t ) = ∇f (xt)-∇f (xt-1) xt-xt-1 + 1 . • Apply η(L(x t )) ∝ 1 L(xt)+ 2 to

Building adaptive learning rate with local smoothness. We firstly create a functional relationship between η t and L(x t ) by using the convergence conditions of stochastic gradient algorithms. Following the local smoothness in equation 7, since ∇f

EQUATION

where L(x t ) is computed by equation 10 in the neighborhood

N rx t-1 (x t ), and L(x t ) = ∇ 2 f (x t )

if f is twice continuously differentiable. Stochastic gradient algorithms can use the linearization in equation 9 to transform it into a simple time-varying linear system. The convergence of the algorithms is achieved by studying the stability of this linear system Lessard et al. (2016) ; Hu et al. (2017) . Therefore, the stability condition is naturally used to construct the functional relationship between η t and L(x t ), η t = η(L(x t )). This shows that the learning rate is adaptively tuned by L(x t ).

Predicting the local smoothness. We secondly predict the local Lipschitz constant L(x t ) by using the current gradient ∇f (x t ) and the latest gradient ∇f (x t-1 ). By using the local smoothness in equation 7, L(x t ) on N rx t-1 (x t ) is predicted by

EQUATION

)

where 1 is a parameter to prevent x t -x t-1 going to zero. This predictive Lipschitz constant L(x t ) is utilized to adjust automatically the learning rate η t for computing the parameter x t+1 . In the next subsections, we prove that η t is inversely proportional to L(x t ),

η t ∝ (1/(L(x t ) + 2 ))

, where 2 is another parameter to avoid the learning rate to be over large in the later updating process.

Applying the adaptive learning rate into any stochastic gradient algorithms. We thirdly use the adaptive learning rate η t = η(L(x t )) to update the parameter x t+1 in the stochastic gradient algorithm. Overall, Fig. 1 summarizes the proposed adaptive local smoothness method. This method can be applied into the adaptive method based on exponential moving averages (e.g., AdaGrad 2015), which require that the loss function is twice differentiable, PLS only requires the differentiable loss function. In addition, the unknown global smoothness is estimated along with the optimization Malherbe & Vayatis (2017) , while we provide an effective method to predict unknown local smoothness using equation 10.

3.2. PLS-SGD:

Algorithm 1 PLS-SGD. 1: input: η 0 , 1 , 2 . 2: initialize: x 0 . 3: for t = 1, • • • , T -1 do 4:

Randomly pick i t from {1, • • • , n};

5:

g t = ∇f it (x t ); 6: L it (x t ) = gt-gt-1 xt-xt-1 + 1 ; 7: η t = η0 (Li t (xt)+ 2) ; 8:

x t+1 = x t -η t ∇f it (x t ); 9: end for In this subsection, we introduce a PLS-SGD algorithm. By using the linearization in equation 9 and computing the expectation, the updating rule of SGD is converted into the linear system:

xt+1 -x * = ((1 -ηtLi t (xt)) ⊗ I d ) (xt -x * ), (11)

where i t is sampled in an IID manner from Ω = {1, • • • , n}. Then, the convergence condition of S-GD is obtained by employing the stability condition of the linear system in equation 11, which shows that x t converges to x at a given linear rate ρ. Now we present a linear convergence condition for the SGD as follows.

Theorem 12 . Consider the linear system in equation 11. Assume that i t is sampled in an IID manner from a uniform distribution, the assumption 1 holds and there exists an equilibrium

x * ∈ R d such that ∇f (x * ) = 0. Let µ = 1 n n i=1 L i (x t ), and ν = 1 n n i=1 L 2 i (x t ). For a fixed linear convergence rate 0 < ρ < 1, if µ 2 > (1 -ρ 2 )ν holds, then we have µ- √ µ 2 -ν(1-ρ 2 ) ν < η t < µ+ √ µ 2 -ν(1-ρ 2 ) ν

, and the linear system is exponentially stable, that is,

x t -x * 2 ≤ ρ t x 0 -x * 2 .

Theorem 1 provides a simple condition for the linear convergence of SGD, which benefits from our PLS method. The condition reveals that the functional relationship between η t , µ and ν. In the updating process, since i t is sampled uniformly at random from Ω, it only uses µ = L it (x t ) and ν = L 2 it (x t ). Hence, we have (1 -ρ)/L it (x t ) < η t < (1 + ρ)/L it (x t ) and set η t = η 0 /L it (x t ), where η 0 is an initialized learning rate and 1 -ρ ≤ η 0 ≤ 1 + ρ, and L it (x t ) can be predicted by using the equation 10. Similar to 1 , 2 is another parameter to stop L it (x t ) going to zero, and avoid the learning rate to be over large in the latter updating process. In our PLS-SGD algorithm, therefore, the learning rate η t is set to η 0 /(L it (x t ) + 2 ). The adaptive learning rate results in that PLS-SGD has a faster (linear) convergence rate than the traditional SGD. PLS-SGD is summarized in Algorithm 1.

3.3. PLS-AMSGRAD:

Similar to PLS-SGD, we integrate the proposed PLS method into the classical adaptive method based on exponential moving averages, AMSGrad Reddi & Kumar (2018) , and propose a PLS-AMSGrad algorithm. The Lipschitz linearization in equation 9 is used to linearize the updating rules in equation 5 of AMSGrad as:

EQUATION

v t+1 = max{v t+1 , v t }, v t+1 = (β 2 ⊗ I d ) v t + (1 -β 2 )L 2 it (x t ) ⊗ I d (x t -x * ) 2 .

In fact, m t is the momentum method to manage the velocity of the gradient. Using this linearization, we provide a much simpler convergence analysis of AMSGrad by studying the linear system in equation 12. The linear convergence condition of AMSGrad is described as Theorem 2. Consider the linear system in equation 12. Assume that i t is sampled in an IID manner from a uniform distribution, the assumption 1 holds and there exists an equilibrium x * ∈ R d such that ∇f (x * ) = 0. For a fixed linear convergence rate ρ = max t { √ β 1t }, if there exists a 2 × 2 positive definite matrix P 0 such that

EQUATION

or the following condition holds, for any

EQUATION

)

then the linear system is exponentially stable, that is,

m t+1 x t+1 -x * 2 ≤ cond(P )ρ t m 0 x 0 -x * 2 ,

where cond(P ) is the condition number of P and Cond(P ) = σ 1 (P )/σ p (P ), where σ 1 (P ) and σ p (P ) denote the largest and smallest singular values of the matrix P .

Algorithm 2 PLS-AMSGrad.

1: input: η 0 > 0, {β 1t > 0} T -1 t=0 , β 2 , 1 , 2 . 2: initialize: x 0 = 0, u 0 = v 0 = v 0 = 0. 3: for t = 1, • • • , T -1 do 4: Randomly pick i t from {1, • • • , n}; 5: g t = ∇f it (x t ); 6: L it (x t ) = gt-gt-1 xt-xt-1 + 1 ; 7: η t = η0 (Li t (xt)+ 2) ; 8: m t+1 = β 1t m t + (1 -β 1t )g t ; 9: v t+1 = β 2 v t + (1 -β 2 )g 2 t ;

10:

v t+1 = max{v t+1 , v t };

11: 2017)) to study the stability of the linear system equation 12.

x t+1 = x t -

It is easily solved by LMI toolbox Boyd et al. (1994) .

Although the condition in equation 13 is not very clear to the relationship between η t and L it (x t ), the condition in equation 13 directly reveals its functional relationship, that is, η t = η t v t+1 /L it (x t ), where 1-

√ β1t 1+ √ β1t < η t < 1+ √ β1t 1- √ β1t .

Based on the equation 5, v t+1 tends to zero as it is a linear system, 0 < β 2 < 1, and the gradient goes to zero. For simplification, η t = η 0 /L it (x t ), where η 0 is an initialized learning rate and 1-

√ β1 1+ √ β1 < η 0 < 1+ √ β1 1- √ β1 , since β 1t = β 1 . Similar to PLS-SGD, L it (x t ) is also sampled uniformly at random from [1, • • • , n], that is, L it (x t

) is computed by equation 10, and the learning rate η t is set to η0

(Li t (xt)+ 2) or η0 √ t(Li t (xt)+ 2)

for avoiding the over-large learning rate in the latter updating process. Thus, PLS-AMSGrad is summarized in Algorithm 2.

Remark 2. Based on the Lemma, the 2 × 2 LMI in equation 13 is equivalent to the condition in equation 14. The former is obtained by constructing the Lyapunov function in the control theory, while the latter is built by calculating the spectral radius of the weight matrix in the linear system in equation 12, which is defined as the magnitude of the largest eigenvalue of the weight matrix.

4. EXPERIMENTS:

In this section, we present empirical results to confirm the effectiveness of the PLS method on linear predictors (convex) and neural networks (nonconvex). We compare PLS-SGD, PLS-SQN, PLS-AMSGrad and PLS-AccSGD with SGD, SQN Byrd et al. ( 2016), adaQN Keskar & Berahas (2016a) , AMSGrad Reddi & Kumar (2018) and AccSGD Kidambi et al. (2018) .

4.1. PSL FOR CONVEX OPTIMIZATION:

In this subsection, we compare PLS-SGD and PLS-SQN with SGD, SQN and adaQN by using convex linear predictor problems (e.g., logistic regression and least squares regression). The code of SGD, SQN and adaQN is downloaded in the github3 Keskar & Berahas (2016b) . Based on this code, we implement PLS-SGD and PLS-SQN. We do experiments on mushroom dataset4 , which contains 8124 data points with 112 dimensions. We use mini-batches of size 256 and tune the learning rate for the best SGD, SQN and adaQN in all experiments. We report the training loss with respect to iterations in Figure 2 , and have the following observations. Figure 2 shows the effectiveness of PLS. Specifically, PLS-SGD has faster convergence and lower loss than SGD, and PLS-SQN is also faster convergent than SQN. Moreover, PLS-SGD and PLS-SQN are much better than adaQN.

4.2. PSL FOR NONCONVEX OPTIMIZATION:

In this subsection, we compare PLS-SGD, PLS-AMSGrad and PLS-AccSGD with SGD, AMSGrad and AccSGD by studying nonconvex multiclass classification and image reconstruction using neural network with least squares regression (LSR) loss and 2 -regularization. The weight parameters of the neural network are initialized by using the normalized strategy choosing uniformly from

[-6/(n in + n out ), 6/(n in + n out )],

where n in and n out are the numbers of input and output layers of the neural network, respectively. We use mini-batches of size 100 in all experiments.

Datasets. MNIST5 contains 60,000 training samples and 10,000 test samples with 784 dimensional image vector and 10 classes, and CIFAR106 includes 50,000 training samples and 10,000 test samples with 1024 dimensional image vector and 10 classes, and 512 dimensional features are extracted by deep residual networks He et al. (2016) for verifying the effectiveness of our methods. Classification. We train the neural networks with two fully-connected hidden layers of 500 ReLU units and 10 output linear units to investigate the performance of all algorithms on MNIST and CIFA10 datasets. The 2 -regularization is 1e-4 (MNIST) and 1e-2 (CIFAR10). A grid search is used to determine the learning rate that provides the best performance for SGD, AMSGrad and AccSGD. We set the adaptive learning rate η t =η 0 /(L it (x t ) + 2 ) for PLS-SGD, PLS-AMSGrad and PLS-AccSGD, where η 0 is chosen as 0.001 or 0.002. To enable fair comparison, we set typical parameters β 1 =0.9 and β 2 =0.999 for AMSGrad and PLS-AMSGrad, and set κ=1000 and ξ =10 for AccSGD and PLS-AccSGD Reddi & Kumar (2018) ; Kidambi et al. (2018) . For convenience, both parameters 1 and 2 are same, = 1 = 2 , and chosen as 0.01 for PLS-SGD and PLS-AMSGrad, and 0.001 for PLS-AccSGD.

We report the training loss and test loss with respect to iterations on MNIST in the left two columns of Figure 3 . We can see that PLS-SGD, PLS-AMSGrad and PLS-AccSGD preform much better than SGD, AMSGrad and AccSGD. The important reason is that our PLS method can directly adjust the learning rate from a small initialization value to a suitable value. In practice, a large fixed learning rate results in the explosion of the loss of neural network with ReLU using SGD, AMSGrad and AccSGD since the loss will go to infinity when the learning rate is larger than 0.011 in our experiments. We observe that the learning rate fast increases in the initial stage and slowly varies in the late stage in Figure 4 . Moreover, there are similar observations on CIFAR10. Due to the limited space, the losses and learning rate are plotted in Figure 5 in Supplementary Material.

Reconstruction. We train a deep fully connected neural network to reconstruct the images in comparison with all algorithms on MNIST dataset. Its structure is represented as 784-1000-500-200-500-1000-784 with the first and last 784 nodes representing the input and output respectively. In this experiment, we provides the best performance for SGD, AMSGrad and AccSGD by searching from a grid learning rates. The initial learning rate η 0 is set to 5e-7, 1e-2 and 1e-7 for PLS-SGD, PLS-AMSGrad and PLS-AccSGD, respectively. In addition, we also set to η t = η 0 /( √ t(L it (x t ) + 2 )) for PLS-AMSGrad, β 1 =0.9, β 2 =0.999, κ=1000 and ξ=10. Moreover, = 1 = 2 , and chosen as 0.01 for PLS-SGD and PLS-AccSGD, and 0.1 for PLS-AMSGrad.

The training loss and test loss with respect to iterations are reported in the right two columns of Figure 3 . We can still see that PLS-SGD, PLS-AMSGrad and PLS-AccSGD have significant better performance than SGD, AMSGrad and AccSGD since our PLS method adaptively adjusts the learning rate to prevent the explosion of the LSR loss with large learning rate. The adaptive learning rate is shown in Figure 6 in Supplementary Material. We also observe that the learning rate is initialized a small value, fast increases in the earlier stage and slowly varies in the latter stage.

5. CONCLUSIONS:

This paper introduced an adaptive local smoothness method for stochastic gradient descent algorithms. This method adjusted automatically learning rate by using the latest gradients to predict the local smoothness. We proposed PLS-SGD, PLS-AMSGrad and PLS-AccSGD algorithms by applying our adaptive local smoothness method into the popular SGD, AMSGrad and AccSGD algorithms. We proved that our proposed algorithms enjoyed the linear convergence rate by studying the stability of their transformed linear systems. Moreover, our proof was significantly simpler than the convergence analyses of SGD, AMSGrad and AccSGD. Experimental results verified that the proposed algorithms provided better performance gain than SGD, AMSGrad and AccSGD. 6 SUPPLEMENTARY MATERIAL

6.1. PLS-ACCSGD:

In this subsection, we present a PLS-AccSGD algorithm. Similar to PLS-AMSGrad, our PLS method is integrated into the classical momentum method, AccSGD Jain et al. (2017) ; Kidambi et al. (2018) .

Using the Lipschitz linearization in the equation 9, the updating rules in the equation 6 of AccSGD is simply linearized as:

EQUATION

where

B t = α (1 -α)(1 -aη t L it (x t )) bα (1 -b)(1 -η t L it (x t )) + b(1 -α)(1 -aη t L it (x t )) , α = 1 -0.7 2 ξ κ , a = κ 0.7 , b = 1-α 0.7+(1-α)

, ξ and κ are defined in the equation 6. This linearization leads us to provide a much simpler proof for linear convergence analysis of AccSGD by studying the stability of the linear system in the equation 15. We have following Theorem 3 for its convergence condition.

Theorem 3. Consider the linear system in the equation 15. Assume that i t is sampled in an IID manner from a uniform distribution, the assumption 1 holds and there exists an equilibrium x * ∈ R d such that ∇f (x * ) = 0. For a fixed linear convergence rate 0 < ρ < max 1 -0.7 2 ξ κ , max t κ(1-ηtLi t (xt)) κ+0.7ξ

, if there exists a 2 × 2 positive definite matrix P 0 such that

EQUATION

or the following condition holds, for any

EQUATION

then the linear system is exponentially stable, that is,

mt+1 -x * xt+1 -x * 2 ≤ cond(P )ρ t m0 -x * x0 -x * 2

, where cond(P ) is the condition number of P .

Algorithm 3 PLS-AccSGD.

1: input: η 0 , κ, ξ ≤ √ κ, 1 , 2 . 2: initialize: x 0 , u 0 = 0, α = 1 -0.7 2 ξ κ . 3: for t = 1, • • • , T -1 do 4:

Randomly pick i t from {1, • • • , n}; 5:

g t = ∇f it (x t ); 6: L it (x t ) = gt-gt-1 xt-xt-1 + 1 ; 7: η t = η 0 /(L it (x t ) + 2 ); 8: m t+1 = αm t + (1 -α) x t -κηt 0.7 g t ; 9: x t+1 = 0.7 0.7+(1-α) (x t -η t g t ) 10:

+ 1-α 0.7+(1-α) m t+1 ; 11: end for Theorem 3 shows that the linear convergence conditions in the equation 16 and the equation 17 are simpler than the convergence analysis of AccSGD Kidambi et al. (2018) . Similar to PLS-AMSGrad, the 2 × 2 LMI condition equation 16 is built by using the control theory and is easily solved by LMI toolbox Boyd et al. (1994) . The condition in the equation 17 directly opens the learning rate η t is a functional relationship with the local smoothness L it (x t ), η t = η0

Li t (xt) , where η 0 is an initialized learning rate, 1 -ρ κ+0.7ξ κ < η 0 < 1. This revels PLS η 0 can be set to a negative value. The reason is that the eigenvalues of the weight matrix in the system in the equation 15 are 1 -0.7 2 ξ κ and κ(1-ηtLi t (xt)) κ+0.7ξ

. The stability of the system in the equation 15 needs to satisfy the condition in the equation 17. Similar to PLS-SGD, L it (x t ) is also sampled uniformly at random from [1, • • • , n], that is, L it (x t ) is computed by the equation 10. To prevent the over-large learning rate, the learning rate η t is set to η 0 /(L it (x t ) + 2 ) in our PLS-AccSGD, which is outlined in Algorithm 3. Following Remark 2, the 2 × 2 LMI in the equation 16 is equivalent to the condition in the equation 17.

6.2. PROOFS:

Proof of Theorem 1: First, we prove that SGD in equation 3 is converted into the stochastic linear system in equation 11. By putting the Lipschitz linearization in equation 9 into the equation 3, we have

EQUATION

By adding -x * into the both sides of the equation 18 and combining like terms, it holds x t+1 -x * = ((1 -η t L it (x t )) ⊗ I d ) (x t -x * ). We thus have the equation 11.

Second, we construct the Lyapunov function V (x t ) = (x t -x * ) T (p ⊗ I d ) (x t -x * ), where p > 0, to prove the stability of the system in the equation 11. Defining

EQUATION

Then for any

x t = x * , E[∆V (x t )] < 0 if E[(1 -η t L it (x t )) 2 ] -ρ 2 < 0, which implies E[L 2 it (x t )]η 2 t -2E[L it (x t )]η t + 1 -ρ 2 < 0 (20) Since i t is sampled in an IID manner from {1, • • • , n}, we let µ = E [L it (x t )] = 1 n n i=1 L i (x t ), and ν = E L 2 it (x t ) = 1 n n i=1 L 2 i (x t )

. So, the equation 20 is satisfied if we have the condition in Theorem 1 as

EQUATION

This implies

EQUATION

By using the nonnegativity of the equation 19, we have

EQUATION

Inducting from l = 1 to t, we see that for all t

EQUATION

which implies x t -x * 2 ≤ ρ t x 0 -x * 2 , where p is a positive number. The proof is complete. Proof of Theorem 2: First, we prove that AMSGrad is converted into the stochastic linear system in the equation 12. By putting the Lipschitz linearization in the equation 9 into the equation 5, we have 

EQUATION

EQUATION

EQUATION

where v t+1 = max{v t+1 , v t }. , where cond(P ) is the condition number of P and Cond(P ) = σ 1 (P )/σ p (P ), where σ 1 (P ) and σ p (P ) denote the largest and smallest singular values of the matrix P .

Third, we prove the another condition in the equation 14. If it holds A T it P A it -ρ 2 P ≺ 0 for any i t ∈ Ω = {1, • • • , n}, then we have the equation 13. Moreover, A T it P A it -ρ 2 P ≺ 0 is equivalence to a simple condition that the eigenvalues of A it is less than ρ. Hence, we consider the eigenvalues of A it calculated by

EQUATION

EQUATION

EQUATION

EQUATION

where Γ = 1 + β 1t - 

EQUATION

-2

EQUATION

EQUATION

)

The proof is complete.

Proof of Theorem 3: First, we prove that AccSGD is converted into the stochastic linear system in the equation 15. By putting the Lipschitz linearization in the equation 9 into the equation 6, we have

EQUATION

x t+1 = 0.7 0.7 + (1 -α) (38b)

:

A large L results in a low learning rate to slowly move the loss function from a point f (x0) to local minimum loss f (x * ) with an equilibrium parameter x * , and vice versa.

All the proofs for the Theorems and the linear systems are provided in Supplementary Material.

https://github.com/keskarnitish/minSQN

https://archive.ics.uci.edu/ml/datasets/mushroom

http://yann.lecun.com/exdb/mnist/

https://www.cs.toronto.edu/~kriz/cifar.html

Figures and Tables:

update x t+1 by any stochastic gradient algorithms.

Figure 1: Predictive Local Smoothness

Figure 2: Logistic regression (convex) and least squares regression (convex) on mushroom using SGD, SQN, adaQN, PLS-SGD and PLS-SQN.

Figure 4: Adaptive learning rates of three layers of neural networks for classification task on MNIST dataset using PLS-SGD, PLS-AMSGrad and PLS-AccSGD.

By adding -x * into the both sides of x t+1 = x t -η t mt+1 √ vt+1 in the equation 5 and substituting the equation 25a and the equation 25b into the equation 5, it holds

4β 1t .Similar to the Proof of Proposition 1Lessard et al. (2016), if Γ < 0, then the magnitudes of the roots satisfy|λ t | < √ β 1t < ρ = max t { √ β 1t }. Then Γ < 0 implies that

(x t -η t (L it (x t ) ⊗ I d ) (x t -x * )) + 1 -α 0.7 + (1 -α) ⊗ I d m t+1 . (37b) Let a = κ 0.7 and b = 1-α 0.7+(1-α) , we have m t+1 = (α ⊗ I d ) m t + (1 -α) (x t -aη t (L it (x t ) ⊗ I d ) (x t -x * )) , (38a) x t+1 = (1 -b) (x t -η t (L it (x t ) ⊗ I d ) (x t -x * )) + (b ⊗ I d ) m t+1 .

and PSL uses the predictive local smoothness by equation 10. Compared to SQN, PSL has two advantages. First, PSL requires low computational time and low memory since it only needs to storage the past parameter and gradient, and perform twice subtractions and norm computations. Second, SQN can still be improved by using our PLS, and we empirically verify that PLS-SQN is better than SQN in subsection 4.1.

Table content: <table><tr><td>Remark 2. Compared to the related local smoothness methods Kpotufe &amp; Garg (2013); Johnson &amp;</td></tr><tr><td>Zhang (2013); Vainsencher et al. (</td></tr><tr><td>Duchi</td></tr><tr><td>et al. (2011), Adadelta Zeiler (2012), RMSProp Tieleman &amp; Hinton (2012), Adam Kingma &amp; Ba</td></tr><tr><td>(2015), Nadam Dozat (2016) and AMSGrad Reddi &amp; Kumar (2018)), the momentum methods (e.g.,</td></tr><tr><td>HB Polyak (1964), NAG Nesterov (1983) and AccSGD Jain et al. (2017); Kidambi et al. (2018)) and</td></tr></table>

T. Tieleman and G. Hinton. Rmsprop: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012. D. Vainsencher, H. Liu, and T. Zhang. Local smoothness in variance reduced optimization. In NIPS, pp. 2179-2187, 2015. Matthew D. Zeiler. Adadelta: An adaptive learning rate method. CoRR, abs/1212.5701, 2012.

Table content: <table/>

So, we have the equation 12 by combining the equation 25a with the equation 26. Second, we construct the Lyapunov function V (ζ t ) = ζ T t (P ⊗ I d ) ζ t , where ζ t =m t x t -x * and P 0 is a 2 × 2 positive matrix, to prove the stability of the system in the equation 12. DefiningE[∆V (ζ t )] = E[V (ζ t+1 ) -ρ 2 V (ζ t )] = E[ζ T t+1 (A t ⊗ I d ) ζ t+1 -ρ 2 ζ T t (A t ⊗ I d ) ζ t ] = ζ TThen if the condition in the equation 13 is satisfied, then E[∆V (x t )] < 0 for any x t = x * . By using the nonnegativity of the equation 19, we haveζ T l+1 (P ⊗ I d ) ζ l+1 ≤ ρ 2 ζ T l (P ⊗ I d ) ζ l .(28)Inducting from l = 1 to t, we see that for all tζ T t (P ⊗ I d ) ζ t ≤ ρ 2t ζ T 0 (P ⊗ I d ) ζ 0 ,

Table content: <table><tr><td/><td/><td/><td/><td/><td>(29)</td></tr><tr><td>which implies</td><td>m t+1 x t+1 -x  *</td><td>2</td><td>≤ cond(P )ρ t</td><td>m 0 x 0 -x  *</td><td>2</td></tr></table>

Peer review (iclr2019):
 # Unrealistic assumptions and trivial theory This papers proposes a method to adjust the learning rate of stochastic gradient methods. The problem is of great importance but the theoretical results and presentation contain many issues that make the paper unfit for publication. The main issue that I see is that the assumption made are unrealistic and make the theory trivial. First, for gradient descent, the authors assume that the gradient is of the form L(x_t) (x_t - x*). Under this assumption, gradient descent converges on a single step with step size 1 / L(x_t). In the stochastic setting, they assume that *each* stochastic gradient is of the form L_i(x_t) (x_t - x*), Eq. (11). Again, SGD in this scenario converges in a single iteration with step size 1 / L_i(x_t). No wonder in this scenario the authors are able to obtain linear convergence of SGD to arbitrary precision (which is known to be impossible even for quadratics). # Other Issues * Motivation of Eq. (9) is not discussed in sufficient detail. It is unclear to me how to obtain (9) from (7) as the authors mention. Regarding notation, L(x_t) is a scalar, hence (9) could be written more simply as .nabla f(x_t) = L(x_t) (x_t - x*). Why the need for the Kronecker product? * The authors should clearly state what are the assumptions in the theorem statement. For theorem 1 these are not clearly stated, and phrases like "Theorem 1 provides a simple condition for the linear convergence of SGD" give the wrong impression that the Theorem is widely applicable. # Minor * Belo Eq. (10): "where .epsilon_1 is a parameter to prevent ||x_t - x_{t-1}|| going to zero: . I guess what the authors meant is to prevent *the denominator* going to zero, you do want ||x_t - x_{t-1}|| to go to zero as you approach a stationary point