Zixuan WANG Shanjian TANG

Abstract The authors prove the gradient convergence of the deep learning-based numerical method for high dimensional parabolic partial differential equations and backward stochastic differential equations,which is based on time discretization of stochastic differential equations(SDEs for short)and the stochastic approximation method for nonconvex stochastic programming problem.They take the stochastic gradient decent method,quadratic loss function,and sigmoid activation function in the setting of the neural network.Combining classical techniques of randomized stochastic gradients,Euler scheme for SDEs,and convergence of neural networks,they obtain the O(K−14)rate of gradient convergence with K being the total number of iterative steps.

Keywords PDEs,BSDEs,Deep learning,Nonconvex stochastic programming,Convergence result

1 Introduction

Deep learning has recently sparked academic interest due to its great success in many application fields like image identification,voice recognition,natural language processing,and instant machine translation.The success of deep learning also leads to the deep learning-based algorithm in ordinary differential equations(ODEs for short),partial differential equations(PDEs for short)and stochastic control problems.Malek and Beidokhti[18]reported a novel hybrid method based on optimization techniques and neural networks for the solution of high ODEs.Sirignano et al.[24]proposed a deep Galerkin method,since it is similar in spirit to Galerkin methods,with the solution approximated by a neural network instead of a linear combination of basis functions.Beck et al.[1]delivered a numerical approximation of the Kolmogorov PDE on an entire region without suffering from the curse of dimensionality by means of deep learning.Rudd[21]presented a method for solving PDEs using neural networks,which uses a constrained-backpropagation approach for preserving prior knowledge during incremental training for solving nonlinear elliptic and parabolic PDEs adaptively in non-stationary environments.Han and E[13]developed a deep learning approach that directly solves high-dimensional stochastic control problems based on Monte-Carlo sampling,and the objective function for the control problem plays the role of the loss function for the deep neural network.E,Han and Jentzen[8]presented a deep learning-based numerical method for solving parabolic PDEs and backward stochastic differential equations(BSDEs for short)in high dimension and demonstrated its success,and we shall prove its gradient convergence result here.

The reason why deep networks work well in the above fields has been remaining to be a mystery,as it generally underlies a highly nonconvex optimization problem.Recently,there is a growing interest in the mathematical properties of these algorithms.E[10]used continuous dynamical systems to model nonlinear functions for machine learning in high-dimensional case.Furthermore,the continuous dynamical system approach to deep learning was explored by Li et al.[16],who proposed a framework for training algorithms.The convergence on the deep networks can be traced back to the study of nonconvex stochastic programming by Ghadimi and Lan[11],who focused on the theoretical development of stochastic approximation type methods.The methods can solve nonconvex stochastic programming problems which can be used to establish a theoretical framework on neural networks.Ithapu et al.[15]analyzed mini-batch stochastic gradients on multi-layer deep networks,and proved a gradient convergence on neural networks.The convergence of a new back-propagation algorithm with adaptive momentum(instead of stochastic gradient decent)was also studied(see[23,28]).There are also many other ways in studying this problem.Carreira and Wang[4]proposed the method of auxiliary coordinates,which replaces original deeply nested problem with a constrained problem involving a different function in an augmented space without nesting,then the constrained problem can be solved with penalty-based methods using alternating optimization over the parameters and the auxiliary coordinates.E et al.[9]gave“a posteriori”error estimates for two-layer neural networks.The convergence of block coordinate descent type algorithms to a critical point of objective functions under natural conditions of neural network was considered(see[26,27]).Zou et al.[29]studied the binary classification problem and showed that with a proper random weight initialization,the stochastic gradient descent method can find the global minima of the training loss for an over-parameterized deep ReLU(Rectified Linear Unit)network,under mild assumption on the training data.

The study of numerical methods for forward backward stochastic differential equations(FBSDEs for short)can be dated back to Douglas et al.[7]and Ma et al.[17],who proposed the four steps scheme to get the relation between the FBSDEs and their corresponding parabolic PDEs.Their work is based on the nonlinear Feynman-kac formulation(see[20,25]).Bouchard and Touzi[3]as well as Delarue and Menozzi[6]studied a time-space discretization scheme for FBSDEs and provided an efficient probabilistic representation of this type of equations.Bender and Zhang[2]proved the convergence through a time discretization and a Markovian iteration.Cvitanic and Zhang[5]transformed the FBSDE to a control problem and proposed the steepest descent method to solve the latter one.The Fourier method to solve quite general FBSDEs with second-order accuracy was also developed(see[14,22]).

There are numerous studies(see[7,18,27,30-32])on the convergence of neural networks,but few of them deal with the convergence of neural networks compound with stochastic system especially BSDEs.To the best of our knowledge,[12]is the only paper dealing with the convergence of deep BSDE method,but the work is quite different from us.They proved that as long as the objective function is optimized to be close to zero under fine time discretization,the approximate solution is close to the true solution.We focus on the convergence through the deep learning update steps.In other words,they proved that the deep BSDE method has abilities to get the true solution,and we obtain that the deep BSDERSG algorithm(we propose in Section 4)can get gradient convergence in the actual update method.On the other side,the mainstream research direction of neural networks’ convergence remains on the gradient convergence,only several papers for example Zou et al.[29]study the global convergence of neural networks.But their result depends on large number of neurons,which is far from using in practice.The main contribution of this work is as follows: We give the gradient convergence of the model raised by E,Han and Jentzen[8]of deep learning-based numerical methods for BSDEs,and we take the stochastic gradient decent method,quadratic loss function,and sigmoid activation function in our neural network settings.For sake of the nonconvexity of neural network,we get the gradient convergence,which can give some theoretical directions for this method,such as the choice of learning rate and how many iterative steps we need.

The rest of the paper is organized as the following five sections.

In Section 2 we give a brief introduction to the deep learning-based numerical method.In Section 3 we introduce the stochastic approximation type methods to solve the nonconvex stochastic programming problems with randomized stochastic gradient(RSG for short)method.In Section 4,we give the proof of the gradient convergence on the neural network first,and then prove the main result(Theorem 4.2)of this paper.In Section 5 we give the numerical experiment to explain our gradient convergence.Section 6 is the Appendix.

2 Deep Learning-Based Algorithm

This section focuses on giving the details of deep learning-based algorithm for a fairly general class of nonlinear parabolic PDEs,which was introduced by E et al.[8].To get a better understanding of the proof,we state the deep learning-based algorithm in its general case.

The main steps of the algorithm are as follows: Through the nonlinear Feynman-Kac formula,we can formulate the PDEs associated to the FBSDEs.The FBSDE is viewed as a stochastic control problem with the gradient of the solution being the policy function(control).The policy function can then be approximated by a deep neural network.

We consider the setup of a system of parabolic PDEs with terminal conditions since this facilitates making connections with BSDEs.Terminal value problems can obviously be transformed into initial value problems.

2.1 The formulation of the problem

2.2 Formulation of the algorithm

Figure 1 The sketch of deep BSDE algorithm(see[11,p.358]).

3 The Nonconvex Stochastic Programming

As we know,the deep networks generally relate to a highly nonconvex optimization problem.Before handling the deep BSDE algorithm,we first consider the stochastic approximation type methods for solving an important class of nonconvex stochastic programming problems,which was introduced by Ghadimi and Lan[11].More specifically,they studied the classical unconstrained nonlinear programming problem,which is given in the form of

The proof of Theorem 3.1 is given in the Appendix.

4 Gradient Convergence on Deep Learning-Based Algorithm

Our main idea follows the nonconvex stochastic approximation methods which are introduced in Section 3.In the next subsection,we give the setting and proof only for a simple neural network.

4.1 Convergence on neural network

Algorithm 1: Two Layers Neural Network Randomized Stochastic Gradients Input: dx,dy,B,N,γk,PR(·),X,W1.R ～PR(·), I=1dk×dv,for k=1,··· ,R −1, do(xi,yi)～X,i=1,··· ,B,ηi:=(xi,yi),Wk+1 ←Wk −I ∗γk B Bimages/BZ_47_921_1236_965_1277.png ∇W L(ηi;Wk),i=1 end for.Output: WR ∈Rdy×dx.

4.2 Convergence on deep learning-based algorithm

In this subsection,we prove the convergence of deep learning-based algorithm,under the formulation of the algorithm introduced in Subsection 2.2.We first propose our BSDE Randomized Stochastic Gradients algorithm.

Algorithm 2: BSDE Randomized Stochastic Gradients Input: T ∈(0,∞),d,ρ,K ∈N,ξ ∈Rq,Θ0,0=t0

Then we have the following convergence result of this algorithm.The main idea of the proof is as follows: We consider the whole problem as a nonconvex problem,and if we can prove our problem satisfies Assumptions A and condition(3.2),then using Theorem 3.1,we can finish the proof.Since the algorithm is combining stochastic differential equations with neural network,the results we get in Subsection 4.1 and the Euler scheme of SDE will help us.

We first give our assumptions.

then we can generate{yt}from{yk}by

With the Lipschitz continuity off,we have

With this two lemmas,we can finally give the proof of Theorem 4.2.

We have get the gradient convergence result.First,since our problem is nonconvex,we can only get the gradient convergence results even if in simple nonconvex stochastic programming problem.Second,in the numerical experiment,we can observe that when we change hidden layers from two to three,the experiment result(see in Section 5)may not convergence.

5 Numerical Experiment

We now give a numerical example to explain why we can only get the gradient convergence for deep BSDE algorithm.

The following results(see in Figure 2)show the difference between the two and three hidden layers.The results show that the approximation error and the gradient approximation error are convergence when the number of hidden layers is two.But when the number of hidden layers changes to three,the approximation error fails to converge while the gradient approximation error still does.

Figure 2 Numerical results for Allen-Cahn PDE(5.1).

6 Appendix

We first give the proof of Theorem 3.1(see[14,Theorem 2.1]).

which together with(3.7)implies(3.6).

In the proof of Theorem 4.1,we adapt the proof of[15],from the case of no hidden layer to our case of two hidden layers.

whereηb,kdenotes the sample used for theb-th noisy gradient computation at thek-th iteration.Adding up the above inequalities overNiterations

AcknowledgementThe authors would like to thank the anonymous reviewers for their careful work and many useful comments.