Title: LAPLACIAN SMOOTHING GRADIENT DESCENT

Abstract: We propose a class of very simple modifications of gradient descent and stochastic gradient descent. We show that when applied to a large variety of machine learning problems, ranging from softmax regression to deep neural nets, the proposed surrogates can dramatically reduce the variance and improve the generalization accuracy. The methods only involve multiplying the usual (stochastic) gradient by the inverse of a positive definitive matrix coming from the discrete Laplacian or its high order generalizations. The theory of Hamilton-Jacobi partial differential equations demonstrates that the implicit version of new algorithm is almost the same as doing gradient descent on a new function which (i) has the same global minima as the original function and (ii) is "more convex". We show that optimization algorithms with these surrogates converge uniformly in the discrete Sobolev H p σ sense and reduce the optimality gap for convex optimization problems. We implement our algorithm into both PyTorch and Tensorflow platforms which only involves changing of a few lines of code. The code will be available on Github.

1. INTRODUCTION:

Stochastic gradient descent (SGD) has been the workhorse for solving large-scale machine learning problems (Bottou et al., 2018) . It gives rise to a family of algorithms that make training of deep neural nets (DNN) practical, which is believed to somehow implicitly smooth the loss function of the DNN (Jastrzebski et al., 2018) . Many efforts have been carried out to improve training and generalization of DNN by directly searching for flat minima (Keskar et al., 2017; Chaudhari et al., 2017; 2016) . An alternative view of SGD's magic comes from the theory of uniform stability (Bousquet & Elisseeff, 2002; Duchi et al., 2011; Hardt et al., 2016; Bottou et al., 2016; Gonen & Shalev-Shwartz, 2017) .

The noise in SGD, on the one hand, helps gradient-based optimization algorithms circumvent spurious local minima and reach those that generalize well (Schmidhuber, 2014) . On the other hand, it slows down the convergence of regular gradient descent (GD). To recover the linear convergence rate for strongly convex functions, several interesting variance reduction algorithms have been proposed, e.g., SAGA (Defazio & Bach, 2014) and SVRG (Johoson & Zhang, 2013) . These algorithms have a certain amount of difficulty in training DNN. SAGA has a relatively high space complexity in storing the gradient for many samples. SVRG requires computation of the full batch gradient.

In this work, we propose a carefully designed positive definite matrix to smooth and to reduce variance of the (stochastic) gradient on-the-fly. The resulting surrogate tends to reduce noise in SGD and improve training of DNN. We call this procedure Laplacian smoothing. The gradient smoothing can be done by multiplying the gradient by the inverse of the following circulant convolution matrix (1)

EQUATION

for some positive constant σ ≥ 0. In fact, we can write A σ = I -σL, where I is the identity matrix, and L is the discrete one-dimensional Laplacian which acts on indices. We define the (periodic) forward finite difference matrix as .

D + =      -1 1 0 . . . 0 0 0 -1 1 . . .

Then, we have A σ = I -σD -D + , where D -= -D + is the backward finite difference. The resulting Laplacian smoothing stochastic gradient descent (LS-SGD) requires negligible extra computational cost and generalizes better than the standard SGD. When the Hessian has a poor condition number, gradient descent performs poorly. In this case, the derivative increases rapidly in one direction, while increasing slowly in others. Gradient smoothing can avoid jitter along steep directions and help make progress in shallow directions (Li & et al, 2018) . Moreover, we show that the operator A -1 σ plays role as a denoiser which enables better convergence in the presence of a very noisy stochastic gradient. The implicit version of our proposed approach is linked to an unusual Hamilton-Jacobi partial differential equation (HJ-PDE) whose solution makes the original loss function more convex while retaining its flat (and global) minima, and essentially works on this surrogate function with a much better landscape.

2. HAMILTON-JACOBI PDES AND CONVEXIFICATION:

Machine learning problems are generally formulated as finding the optimal parameters w of a parametric function y = h(x, w), such that for an input x, the output y is close to the ground-truth. The optimal w can be obtained by minimizing an empirical risk function, f (X, Y, w) . = f (w), given the training data {X, Y }. We start from the following unusual HJ-PDE with f (w) as initial condition

EQUATION

By the Hopf-Lax formula (Evans, 2010) , the unique viscosity solution to Eq. ( 2) is represented by

u(w, t) = inf v f (v) + 1 2t v -w, A σ (v -w) .

This viscosity solution u(w, t) makes f (w) "more convex", an intuitive definition and theoretical explanation of "more convex" can be found in (Chaudhari et al., 2017; 2016) , by bringing down the local maxima while retaining and widening local minima. An illustration of this is shown in Fig. 1 .

If we perform the smoothing GD with proper step size on the function u(w, t), it is easier to reach the global or at least a flat minima of the original nonconvex function f (w). Proposition 1. Suppose f (w) is differentiable, the LS-GD on u(w, t)

w k+1 = w k -tA -1 σ ∇ w u(w k , t

) is equivalent to the smoothing implicit GD on f (w)

EQUATION

All the proofs here and below are provided in the appendix.

2.1. LAPLACIAN SMOOTHING GRADIENT DESCENT:

Laplacian smoothing implicit gradient descent requires inner iterations as used in (Chaudhari et al., 2017) , which is computationally expensive. We consider the following explicit scheme

w k+1 = w k -γ k A -1 σ ∇f (w k ).

Intuitively, compared to the standard GD, this scheme smooths the gradient on-the-fly by an elliptic smoothing operator. We adopt fast Fourier transform (FFT) to compute A -1 σ ∇f (w k ), which is available in both PyTorch (Paszke et al., 2017) and TensorFlow (Abadi et al., 2016) . Given a vector g, a smoothed vector d can be obtained by computing d = A -1 σ g. This is equivalent to g = d -σv * d, where v = [-2, 1, 0, • • • , 0, 1] and * is the convolution operator. Therefore

d = ifft fft(g) 1 -σ • fft(v)

,

where we use component-wise division, fft and ifft are the FFT and inverse FFT, respectively. Hence, the gradient smoothing can be done in quasilinear time. This additional time complexity is almost the same as performing a one step update on the weights vector w. For many machine learning models, we may need to concatenate the parameters into a vector. This reshape might lead to some ambiguity, nevertheless, based on our tests, both row and column majored reshaping work for the LS-GD algorithm. Moreover, in deep learning cases, the weights in different layers might have different physical meanings. We then perform layer-wise gradient smoothing, instead. Remark 1. In image processing, the Sobolev gradient (Jung et al., 2009) involves a multidimensional Laplacian operator which operates on w, is different from the one-dimensional discrete Laplacian operator employed in our LS-GD scheme, which operates on indices.

We first show that LS-GD can help bypass sharp minima and reach the global minima. We consider the following function, in which we 'drill' narrow holes on a smooth convex function, f (x, y, z) = -4e -((x-π) 2 +(y-π) 2 +(z-π) 2 ) -4 i cos(x) cos(y)e -β((x-r sin( i 2 )-π) 2 +(y-r cos( i 2 )-π) 2 ) , (4)

where the summation is taken over the index set {i ∈ N| 0 ≤ i < 4π}, r and β are the parameters that determine the location and narrowness of the local minima and are set to 1 and 1 √ 500 , respectively. We do GD and LS-GD starting from a random point in the neighborhoods of the narrow minima, i.e., (x 0 , y 0 , z 0 ) ∈ { i U δ (r sin( i 2 ) + π, r cos( i 2 ) + π)| 0 ≤ i < 4π, i ∈ N}, where U δ (P ) is a neighborhood of the point P with radius δ. Our experiments (Fig. 2 ) show that, if δ ≤ 0.2, GD will converge to narrow local minima, while LS-GD convergences to wider global minima. 4)) with z = 2.34; panel (b) shows the paths of GD (red) and LS-GD (black). We take the step size to be 0.02 for both GD and LS-GD. σ = 1.0 is utilized for LS-GD.

2.2. GENERALIZED SMOOTHING GRADIENT DESCENT:

We can generalize A σ to the nth order discrete hyper-diffusion operator as follows

I + (-1) n σL n . = A n σ .

Each row of the discrete Laplacian operator L consists of an appropriate arrangement of weights in central finite difference approximation to the 2nd order derivative. Similarly, each row of L n is an arrangement of the weights of the central finite difference to approximate the 2nth order derivative.

Remark 2. The nth order smoothing operator I + (-1) n σL n can only be applied to the problem with dimension at least 2n + 1. Otherwise, we need to add dummy variables to the object function.

Again, we apply FFT to compute the smoothed gradient vector. For a given gradient vector g, the smoothed surrogate, (A n σ ) -1 g . = d, can be obtained by solving g = d + (-1) n σv n * d, where

v n = (c n n+1 , c n n+2 , • • • , c n 2n+1 , 0, • • • , 0, c n 1 , c n 2 , • • • , c n n-1 , c n n

) is a vector of the same dimension as the gradient to be smoothed. And the coefficient vector

c n = (c n 1 , c n 2 , • • • , c n 2n+1

) can be obtained recursively by the following formula

c 1 = (1, -2, 1), c n i =    1 i = 1, 2n + 1 -2c n-1 1 + c n-1 2 i = 2, 2n c n-1 i-1 -2c n-1 i + c n-1 i+1 otherwise.

Remark 3. The computational complexities for different order smoothing schemes are the same when the FFT is utilized for computing the surrogate gradient.

3. REDUCE OPTIMALITY GAP IN SGD:

We show advantages of the LS-(S)GD and generalized schemes for convex optimization. Consider finding the minima x * of the quadratic function f (x) defined in Eq. ( 5) by different schemes.

EQUATION

)

To simulate SGD, we add Gaussian noise to the gradient vector, i.e., at a given point x, we have

∇ f (x) := ∇f (x) + N (0, I),

where the scalar controls the noise level, N (0, I) is the vector with zero mean and unit variance in each coordinate. The corresponding numerical schemes can be formulated as

EQUATION

)

where σ is the smoothing parameter selected to be 10.0 to kill the intense noise. We take diminishing step sizes with initial values 0.1 for SGD/smoothed SGD; 0.9 and 1.8 for GD/smoothed GD, respectively. Without noise, the smoothing allows us to take larger step sizes, rounding to the first digit, 0.9 and 1.9 are the largest suitable step size for GD and smoothed version here. We compare constant learning rate and exponentially decaying learning rate, i.e., after every 1000 iteration, the learning rate is divided by 10. We apply different schemes that corresponding to n = 0, 1, 2 in Eq. ( 6) to the problem Eq. ( 5), with the initial point

x 0 = (1, 1, • • • , 1). Figure.

3 shows the iteration v.s. optimality gap when the constant learning rate is applied to different noise levels. In the noise free case, all three schemes converge linearly, but gradient smoothing has a smaller decay constant due to its increased condition number. When there is noise, our smoothed gradient helps to reduce the optimality gap and converges faster after a few iterations. The exponentially decaying learning rate helps our smoothed SGD to reach a point with a smaller optimality gap, and the higher order smoothing further reduce the optimality gap, as shown in Fig. 4 . One simple reason for this in the noisy case is because of the noise removal properties of the smoothing operators. The influence of the learning rate is still under investigation. We establish the convergence of our proposed smoothing gradient descent algorithms.

3.1. SOME PROPERTIES OF LAPLACIAN SMOOTHING GRADIENT DESCENT:

We say the objective function f has L-Lipschitz gradient, if for any w, u ∈ R m , we have ∇f (w)-∇f (u) ≤ L wu , and f is a-strongly convex, if ∇f (w) -∇f (u), wu ≥ a wu 2 . We define the vector norm induced by any matrix A as w A := w, Aw .

(a) = 0 (b) = 0.05 (c) = 0.1 (d) = 0.5 Figure 4 : Iterations v.s. optimality gap for GD and smoothed GD with order 1 and 2 for the problem in Eq.( 5). Exponentially decaying step size is utilized here.

Proposition 2. Suppose f is convex with the global minimizer w * , and f * = f (w * ). Consider the following iteration with constant learning rate η > 0

w k+1 = w k -η(A n σ ) -1 g k , where g k is the sampled gradient in the kth iteration at w k satisfying E[g k ] = ∇f (w k ). De- note G A n σ := lim K→∞ 1 K K-1 k=0 g k 2 (A n σ ) -1 and w K := K-1 k=0 w k /K the ergodic average of iterates. Then the optimality gap is lim K→∞ E[f (w K )] -f * ≤ ηG A n σ 2 .

Note that g (A n σ ) -1 generally decreases in n unless g is constant, which indicates that a bigger n implies smaller optimality gap. This is consistent with the experimental results above. Proposition 3. Suppose f is L-Lipschitz smooth and a-strongly convex with the global minimizer w * . Consider the generalized smoothing gradient descent algorithm

w k+1 = w k -η k (A n σ ) -1 g k

, where g k is the sampled gradient in the kth iteration at w k satisfying E g k = ∇f (w k ) and

E g k 2 (A n σ ) -1 ≤ C 0 + C 1 ∇f (w k ) 2 for all k ∈ N. If we take η k = C

k+1 for some C > 0, then we have In what follows, we present the noise reduction properties of the proposed smoothing operator A -1 σ . Proposition 5. For any vector g ∈ R m , d = A -1 σ g, let j max = arg max i d i and j min = arg min i d i . We have max i d i = d jmax ≤ g jmax ≤ max i g i and min i d i = d jmin ≥ g jmin ≥ min i g i . Proposition 6. The operator A -1 σ preserves the sum of components. For any g ∈ R m and d = A -1 σ g, we have j d j = j g j , or equivalently, 1 d = 1 g. Proposition 7. Given any vector g ∈ R m and d = A -1 σ g, then

E w k -w * 2 A n σ = E w k -w * 2 + σ D n + (w k -w * ) 2 = O 1 k + 1 , i.e., we have H n σ uniform convergence in σ of {w k } in expectation. The H n σ norm of w is defined by w n σ := w A n σ = w, A n σ w . Proposition 4. Consider the algorithm w k+1 = w k -η k (A n σ ) -1 ∇f (w k ). Suppose f is convex and L-Lipschitz smooth. If the step size satisfies 0 < η ≤ η ≤ η < 2 L . Then lim t→∞ ∇f (w k ) → 0. Moreover, if the Hessian ∇ 2 f of f is continuous with w * being the global minimizer of f , and η ∇ 2 f < 1, then w k -w * A n σ → 0 as k → ∞,

d + σ D + d 2 d ≤ g .

The above inequality is strict unless g = d is a constant vector. In particular, we have d ≤ g and

D + d ≤ 1 √ σ g .

Let g be the noise vector contained in the stochastic gradient, the above results imply that the extreme values in A -1 σ g are smaller than those in g (in magnitude), and it also has a much smaller 2 norm.

Proposition 8. For any g ∈ R m , define Var(g) := 1 m g 2 -1 g m 2 be the variance of components in g. Let d = A -1 σ g, then

Var(d) ≤ Var(g) -2σ D+d 2 m -σ 2 D+d 4 m d 2 .

The inequality is strict unless g = d is a constant vector.

Proposition 8 shows that the component-wise variance of A -1 σ g is considerably less than that of g, unless g is a constant vector. Our last result shows that A -1 σ g has diminishing 1 norm of finite difference of all orders. This is an excellent desnoising result. Proposition 9. Given vectors g and d = A -1 σ g, for any p ∈ N, it holds that D p + d 1 ≤ D p + g 1 . The inequality is strict unless D p + g is a constant vector. Remark 4. The above proofs generalize for n > 1, except for Propositions 5 and 9.

3.2. SOFTMAX REGRESSION:

Consider applying the proposed optimization schemes to Softmax regression. We run 200 epochs of SGD and different order smoothing algorithms to maximize the likelihood of Softmax regression with batch size 100. Based on the results from previous section, we apply the exponentially decay learning rate with initial value 0.1 and decay 10 times after every 50 epochs. We train the model with only 10 % randomly selected MNIST training data and test the trained model on the entire testing images. We further compare with SVRG under the same setting. 

4. APPLICATIONS TO DEEP NEURAL NETS 4.1 TRAIN NEURAL NETS WITH SMALL BATCH SIZE:

Many advanced artificial intelligence tasks make high demand on training neural nets with extremely small batch size. The milestone technique for this is group normalization (Wu & He, 2018) . In this section, we show that LS-SGD successfully trains DNN with extremely small batch size. We consider LeNet-5 devised by (LeCun et al., 1998) for MNIST classification. Our network architecture is as follows LeNet-5: input 28×28 → conv 20,5,2 → conv 50,5,2 → fc 512 → softmax.

The notation conv c,k,m denotes a 2D convolutional layer with c output channels, each of which is the sum of a channel-wise convolution operation on the input using a learnable kernel of size k ×k, it further adds ReLU nonlinearity and max pooling with stride size m. fc 512 is an affine transformation that transforms the input to a vector of dimension 512. Finally, the tensors are activated by a softmax function. The MNIST data is first passed to the layer input 28×28 , and further processed by this hierarchical structure. We run 100 epochs of both SGD and LS-SGD with initial learning rate 0.01 and divide by 5 after 50 epochs, and use a weight decay of 0.0001 and momentum of 0.9. Figure. 6(a) plots the generalization accuracy on the test set with the LeNet5 trained with different batch sizes. For each batch size, LS-SGD with σ = 1.0 keeps the testing accuracy more than 99.4%, SGD reduce the accuracy to 97% when batch size 4 is used. The classification become just a random guess, when the model is trained by SGD with batch size 2. Small batch size leads to large noise in the gradient, which may make the noisy gradient not along the decent direction, However, Lapacian smoothing rescues this by killing the noise. 

4.2. IMPROVE GENERALIZATION ACCURACY:

The skip connections in ResNet smooth the landscape of the loss function of the classical CNN (He et al., 2016; Li et al., 2017) . This means that ResNet has fewer sharp minima. On Cifar10 (Krizhevsky, 2009) , we compare the performance of LS-SGD and SGD on ResNet with the preactivated ResNet56 as an illustration. We take the same training strategy as that used in (He et al., 2016) , except that we run 200 epochs with the learning rate decaying by a factor of 5 after every 40 epochs. For ResNet, instead of applying LS-SGD for all epochs, we only use LS-SGD in the first 40 epochs, and the remaining training is carried out by SGD. The parameter σ is set to 1.0. Figure 6 (b) depicts one path of the training and generalization accuracy of the neural nets trained by SGD and LS-SGD, respectively. It is seen that, even though the training accuracy obtained by SGD is higher than that by LS-SGD, the generalization is however inferior to that of LS-SGD. We conjecture that this is due to the fact that SGD gets trapped into some sharp but deeper minimum, which fits better than a flat minimum but generalizes worse. We carry out 25 replicas of this experiments, the histograms of the corresponding accuracy are shown in Fig. 7 .

SGD:

LS-SGD with σ = 1.0 

4.3. TRAINING WASSERSTERIN GAN:

Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) are notoriously delicate and unstable to train (Arjovsky & Bottou, 2017) . In (M. Arjovsky & Bottou, 2017) , Wasserstein-GANs (WGANs) are introduced to combat the instability in the training GANs. In addition to being more robust in training parameters and network architecture, WGANs provide a reliable estimate of the Earth Mover (EM) metric which correlates well with the quality of the generated samples. Nonetheless, WGANs training becomes unstable with a large learning rate or when used with a momentum based optimizer (M. Arjovsky & Bottou, 2017) . In this section, we demonstrate that the gradient smoothing technique in this paper alleviates the instability in the training, and improves the quality of generated samples. Since WGANs with weight clipping are typically trained with RMSProp (Tieleman & Hinton, 2012) , we propose replacing the gradient g by a smoothed version g σ = A -1 σ g, and also update the running averages using g σ instead of g. We name this algorithm LS-RMSProp.

To accentuate the instability in training and demonstrate the effects of gradient smoothing, we deliberately use a large learning rate for training the generator. We compare the regular RMSProp with the LS-RMSProp. The learning rate for the critic is kept small and trained approximately to convergence so that the critic loss is still an effective approximation to the Wasserstein distance.To control the number of unknowns in the experiment and make a meaningful comparison using the critic loss, we use the classical RMSProp for the critic, and only apply LS-RMSProp to the generator.

RMSProp:

LS-RMSProp, σ = 3.0 We train the WGANs on the MNIST dataset using the DCGAN (Radford et al., 2015) for both the critic and generator. In 

4.4. DEEP REINFORCEMENT LEARNING:

Finally, we apply the LS-SGD to deep reinforcement learning. We provide a detailed discussion and present the numerical result in the appendix.

5. CONCLUDING REMARKS:

Motivated by the theory of Hamilton-Jacobi partial differential equations, we proposed Laplacian smoothing gradient descent and its high order generalizations. This simple modification dramatically reduces the optimality gap in stochastic gradient descent and helps to find better minima.

Extensive numerical examples ranging from toy cases to shallow and deep neural nets to generative adversarial networks and to deep reinforcement learning, all demonstrate the advantage of the proposed smoothed gradient. Several issues remain, in particular devising an on-the-fly adaptive method for choosing the smoothing parameter σ instead of using a fixed value. Therefore, ∇f (w k ) 2 (A n σ ) -1 → 0, and thus ∇f (w k ) → 0. For the second claim, we have

w k+1 -w * = w k -w * -η k (A n σ ) -1 (∇f (w k ) -∇f (w * )) = w k -w * -η k (A n σ ) -1 1 0 ∇ 2 f (w * + τ (w k+1 -w * )) • (w k -w * )dτ = w k -w * -η k (A n σ ) -1 1 0 ∇ 2 f (w * + τ (w k+1 -w * ))dτ • (w k -w * ) = (A n σ ) -1 2 I -η k (A n σ ) -1 2 1 0 ∇ 2 f (w * + τ (w k+1 -w * ))dτ (A n σ ) -1 2 ) (A n σ ) 1 2 (w k -w * )

Therefore,

w k+1 -w * A n σ ≤ I -η t (A n σ ) -1 2 1 0 ∇ 2 f (w * + τ (w k+1 -w * ))dτ (A n σ ) -1 2 w k -w * A n σ . So if η k ∇ 2 f ≤ 1 (A n σ ) -1 = 1, the result follows.

Proposition 5. For any vector g ∈ R m , d = A -1 σ g, let j max = arg max i d i and j min = arg min i d i . We have max

i d i = d jmax ≤ g jmax ≤ max i g i and min i d i = d jmin ≥ g jmin ≥ min i g i . Proof of Proposition 5. Since g = A σ d, it holds that g jmax = d jmax + σ(2d jmax -d jmax-1 -d jmax+1 ),

where periodicity of subindex are used if necessary. Since

2d jmax -d jmax-1 -d jmax+1 ≥ 0, We have max i d i = d jmax ≤ g jmax ≤ max i g i . A similar argument can show that min i d i = d jmin ≥ g jmin ≥ min i g i .

Proposition 6. The operator A -1 σ preserves the sum of components. For any g ∈ R m and d = A -1 σ g, we have j d j = j g j , or equivalently, 1 d = 1 g.

Proof of Proposition 6. Since g = A σ d,

i g i = 1 g = 1 (I + σD + D + )d = 1 d = i d i ,

where we used D + 1 = 0.

Proposition 7. Given any vector g ∈ R m and d = A -1 σ g, then

d + σ D + d 2 d ≤ g .

The above inequality is strict unless g = d is a constant vector. In particular, we have d ≤ g and D

+ d ≤ 1 √ σ g .

Proof of Proposition 7. By the definition of A σ ,

EQUATION

Therefore, pre-multiplying by d on both sides, we have

d 2 + σ D + d 2 = d g ≤ d g .

In particular, d ≤ g and σ D + d 2 ≤ d g ≤ g 2 , so D + d ≤ 1 √ σ g . All the inequalities are strict unless D + d = 0, and g = d is a constant vector.

Proposition 8. For any g ∈ R m , define Var(g

) := 1 m g 2 -1 g m 2 be the variance of components in g. Let d = A -1 σ g, then Var(d) ≤ Var(g) -2σ D + d 2 m -σ 2 D + d 4 m d 2 .

The inequality is strict unless g = d is a constant vector. The inequality is strict unless D + d = 0, and g = d is a constant vector.

Proposition 9. Given vectors g and d = A -1 σ g, for any p ∈ N, it holds that D p + d 1 ≤ D p + g 1 . The inequality is strict unless D p + g is a constant vector.

Proof of Proposition 9. Since (1 + 2σ)d i = g i + σd i+1 + σd i-1 , for any p ∈ N, we have The second order smoothing can further reduce variance of loss. The variance of loss in each iteration among 100 experiments is minimized when SVRG is use to train the Softmax model. However, the generalization performance of the model trained by SVRG is not as good as the ones trained by LS-SGD or higher order smoothed gradient descent.

Deep reinforcement learning (DRL) has been applied to playing games including Cartpole (Brockman et al., 2016) , Atari (Mnih et al., 2013) , Go (Silver & et al, 2016; Mnih & et al, 2015) . DNN plays a vital role in approximating the Q-function or policy function. We apply the Laplacian smoothed gradient to train the policy function to play the Cartpole game. We apply the standard procedure to train the policy function by using the policy gradient (Brockman et al., 2016) . We use the following network to approximate the policy function:

input 4 → fc 20 → relu → fc 2 → softmax.

:



Figures and Tables:

Figure 1: f (w) = w 2 1 + 1 2 sin(2π w ) is made more convex by solving Eq.(2). The plot shows the cross section of the 5D problem with σ = 1 and different t values.

Demo of GD and LS-GD. Panel (a) depicts the slice of the function (Eq.(

(a) = 0 (b) = 0.05 (c) = 0.1 (d) = 0.5 Figure 3: Iterations v.s. optimality gap for GD and smoothed GD with order 1 and 2 for the problem in Eq.(5). Constant step size was used.

and the convergence is linear and independent of σ.

Figure. 5 shows the histograms of generalization accuracy of Softmax regression model trained by SGD ((a)); SVRG ((b)); LS-SGD (order 1) ((c)); LS-SGD (oder 2) ((d)). It is seen that SVRG improves the generalization with higher average accuracy. But the first and second order smoothing schemes significantly improve averaged generalization accuracy by more than 1% and reduce the variance over 100 independent trials. The training loss of these 100 experiments by different optimization algorithms are shown in the appendix.

LS-GD: Order 1 (d) LS-GD Order 2 Figure 5: Testing accuracy of Softmax model trained on randomly selected 10% MNIST data.

Figure 6: (a). Testing accuracy of LeNet5 trained by SGD/LS-SGD on MNIST with various batch sizes. (b). The evolution of the pre-activated ResNet56's training and generalization accuracy by SGD and LS-SGD. (Start from the 20-th epoch.)

Figure 7: The histogram of the generalization accuracy of the pre-activated ResNet56 on Cifar10 trained with LS-SGD over 25 independent experiments.

Figure8: Critic loss with learning rate lrD = 0.0001, lrG = 0.005 for RMSProp (Left) and LS-RMSProp (Right), trained for 20K iterations. We apply a mean filter of window size 13 for better visualization. The loss from LS-RMSProp is visibly less noisy.

Figure 8 (left), we observe the loss for RMSProp trained with a large learning rate has multiple sharp spikes, indicating instability in the training process. The samples generated are also lower in quality, containing noisy spots as shown in Figure 9 (a). In contrast, the curve of training loss for LS-RMSProp is smoother and exhibits fewer spikes. The generated samples as shown in Fig. 9 (b) are also of better quality and visibly less noisy. The generated characters shown in Fig. 9 (b) are more realistic compared to the ones shown in Fig. 9 (a). The effects are less pronounced with a small learning rate, but still result in a modest improvement in sample quality as shown in Figure 9 (c) and (d).We also apply LS-RMSProp for training the critic, but do not see a clear improvement in the quality. This may be because the critic is already trained near optimality during each iteration, and does not benefit much from gradient smoothing. Samples from WGANs trained with RMSProp (a, c) and LS-RMSProp (b, d). The learning rate is set to lrD = 0.0001, lrG = 0.005 for both RMSProp and LS-RMSProp in (a) and (b). And lrD = 0.0001, lrG = 0.0001 are used for both RMSProp and LS-RMSProp in (c) and (d). The critic is trained for 5 iterations per step of the generator, and 200 iterations per every 500 steps of the generator.

Since 1 g = 1 d and d + σ D+d 2

2σ)(D p + d) i = (D p + g) i + σ(D p + d) i+1 + σ(D p + d) i-1 . So (1 + 2σ)|(D p + d) i | ≤ |(D p + g) i | + σ|(D p + d) i+1 | + σ|(D p + d) i-1 |.The inequality is strict if there are sign changes among the (D p + d) i-1 , (D p + d) i , (D p + d) i+1 . Summing over i and using periodicity, we have p + d) i |, and the result follows. The inequality is strict unless D p + g is a constant vector. 6.2 ITERATION V.S. LOSS FOR SOFTMAX REGRESSION In this part, we show the training loss evolution in training Softmax regression model, respectively, by SGD, SVRG, LSGD with first and second order smoothing. As illustrated in Fig. 10, all the optimization algorithms reduce loss of the model on the training set. At each iteration, among 100 independent experiments, SGD has the largest variance, SGD with first order smoothed gradient significantly reduces the variance of loss function.

Peer review (iclr2019):
 This paper proposed a variant of gradient descent that can be approximately understood as gradient descent on a smoothed version of the objective function. The motivation of this work is finding flat minima which could imply better generalization ability of a machine learning model. Compared with gradient, the proposed algorithm uses gradient multiplied by a special constant square matrix as update direction. The complexity of the matrix vector multiplication is brought down from O(d^2) to O(d*logd) by exploiting special structure of the matrix using FFT. It is proved that the new update vector has smaller variance and amplitude compared to gradient. Experiments on different applications showed that the proposed algorithm may have better generalization ability compared with SGD. This is a clearly written paper, but I have a few questions about theoretical gaps and simulation results in the paper. a). It seems the smoothing explanation at the beginning of section 2 is for implicit scheme (equation (3)). However, the explicit scheme used in practice (the first unnumbered equation in section 2.1) uses a heuristic relaxation which makes the smoothing explanation “approximate” for the explicit scheme. Since the implicit scheme is much more complicated than the explicit scheme, I don’t know if the argument for the implicit scheme will “approximately” hold for the explicit scheme used in practice. b). The concept flat minimum is only useful in nonconvex optimization, but the convergence of the algorithm is only proved in convex setting. Since the main motivation of the algorithm is finding flat minima, the lack of convergence proof for nonconvex setting concerns me. c). In the neural net experiment in section 4.1, both gradient descent and smooth gradient descent use the same stepsizes. It is known that the performance of gradient descent is sensitive to the choice of stepsizes, for a fair comparison, one should compare the performance of the two algorithms using optimized stepsizes. d). In the experiment in section 4.2, the proposed algorithm is only used for the first 40 epochs during training and SGD is used for the later phase of training. Why switching to SGD later? Overall, I feel the idea of this paper is interesting, but the theory and experiments in the paper are not very strong.