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):
 The paper considers SGD with a scaled norm; in the non-stochastic case (first equation in section 2.1), it is gradient descent in a fixed non-Euclidean norm, but it is the stochastic case that is most interesting. The paper connects this, somewhat, to a Hamilton-Jacobi equation, but then relaxes the implicit step to an explicit step. There is solid theory (Prop 2, 3 and 4) for convergence, which makes sense since this is the same as usual SGD but in a different Hilbert space. Since the inner product is stationary, it*s just a fixed Hilbert space, so any convergence proofs that work for arbitrary Hilbert space immediately give the result. The computational experiments are impressive, and demonstrate a lot of competence with modern neural nets. Some results are hard to interpret (Figs 9, 10) though. As for why use the Laplacian, Prop 8 (combined with Prop 6) gives some idea: that we lower the variance, without cheating (ie., we could trivially lower the variance by just multiplying by a small number, but because the operator preserves the sum of the components, it is not "cheating"). That is helpful, though it doesn*t give a complete picture yet. The explanation about the link to the "more convex" function I find completely inaccurate and misleading (see technical comments for why). The writing is mainly fine, though some sentences are written poorly and would benefit from a revision, e.g., 2nd paragraph, "But none of them is suitable to train deep neural nets (DNNs)." is quite awkward [also, in this sentence, please explain *why* they are not suitable!] The paper circumvents the page limit by using a smaller font (starting on page 3). This might seem like a minor issue, but it is violating the page limit, and not fair to other papers (unless I have misunderstood; the meta-reviewers can probably comment about this). I do not think it would be unfair to reject the paper on these grounds. It leaves a bad taste in my mouth after reading the paper. Technical comments: - page 1, this is called a "tri-diagonal" linear system, but it is not, it is circulant due to the upper-right and lower-left entries (the authors are well-aware of this, but the reader maybe confused; especially since if it were tri-diagonal, it would be inverted via the Thomas algorithm not the FFT). - Section 2: my first impression on reading this is that you*ve re-discovered the proximal point envelope and the Moreau envelope (and, looking at the proof of Prop. 1, the authors are aware of this connection). In this context, it*s not clear why A_sigma is helpful, as opposed to any positive definite matrix. - The actual statement of Proposition 1 is unclear. What does "the ... update ... permits .." mean? i.e., "permits" is a weird, vague choice of words. What are you actually proving? - Section 2.1 moves from the proximal point method (in a scaled norm) to the gradient descent method (in a scaled norm). Clearly, these two methods are different, and just as in ODE schemes, the implicit version is unconditionally stable while the explicit one isn*t. So motivating your method by "smoothing" or "adding convexity" is really misleading. You could define equation (2) and the u(w,t) equation by replacing A_sigma with the identity, and as long as tau > 0, this also "convexifies", but then if you go from implicit to explicit, you get regular GD, so you haven*t really done anything. So, I do not buy this connection that your method "convexifies" the function. - Using the FFT to invert seems slow (the theoretical flop-count is good, but it*s still super-linear, and requires global data movement, so not good for a distributed implementation). If you really did define A to be tri-diagonal, then you could invert naively in a linear time algorithm with local data movement. Why not use a tri-diagonal A? It might not satisfy prop 8 exactly, but it*d be close, and a lot faster in practice. From a "finite-difference" point-of-view, I don*t see an inherent argument about why you want circular boundary conditions. - Remark 1 seems out-of-place. Why is that included? - Section 3.2, and Fig. 5. It*s not clear that the improved generalization results are due to broader local minima, or if it*s because the methods converged faster on the training data (since they were limited to 200 epochs). Showing the training error, as a function of epoch, would help clarify. Similar comment for other experiments too. - Section 4 was impressive in the implementations. Nice work. - The acknowledgments used the boiler-plate latex template text. ** summary ** Quality: Good Clarity: OK Originality: mixed Significance: maybe high?